В информатике запрос на минимальный диапазон ( RMQ ) решает проблему поиска минимального значения в подмассиве массива сопоставимых объектов. Запросы с минимальным диапазоном имеют несколько вариантов использования в информатике, такие как проблема с наименьшим общим предком и проблема с самым длинным общим префиксом (LCP).
Определение
Для массива A [1… n ] из n объектов, взятых из полностью упорядоченного набора, такого как целые числа, минимальный запрос диапазона RMQ A ( l , r ) = arg min A [ k ] (при 1 ≤ l ≤ k ≤ r ≤ n ) возвращает позицию минимального элемента в указанном подмассиве A [ l … r ] .
Например, когда A = [0,5,2,5,4,3,1,6,3] , то ответ на запрос минимального диапазона для подмассивов A [3… 8] = [2,5 , 4,3,1,6] - это7 , так как A [7] = 1 .
Алгоритмы
Наивное решение
В типичной настройке массив A является статическим, т. Е. Элементы не вставляются и не удаляются во время серии запросов, а запросы, на которые необходимо ответить в интерактивном режиме (т. Е. Весь набор запросов заранее неизвестен алгоритму ). В этом случае подходящая предварительная обработка массива в структуру данных обеспечивает более быстрый ответ на запрос. Наивное решение состоит в том, чтобы предварительно вычислить все возможные запросы, т.е. минимум всех подмассивов A , и сохранить их в массиве B так , чтобы B [ i , j ] = min ( A [ i … j ]) ; то диапазон мин запрос может быть решен в постоянное время с помощью поиска в массиве B . Существует ( n ²) возможных запросов для массива длиной n , и ответы на них могут быть вычислены за Θ ( n ²) времени с помощью динамического программирования . [1]
Решение с использованием логарифмического времени и линейного пространства
Как и в приведенном выше решении, ответы на запросы в постоянное время будут достигнуты путем предварительного вычисления результатов. Однако в массиве будут храниться предварительно вычисленные минимальные запросы для всех элементов и только для диапазонов, размер которых является степенью двойки. Для каждой начальной позиции i существует Θ (log n ) таких запросов , поэтому размер таблицы динамического программирования B равен ( n log n ) . Каждый элемент B [ i , j ] содержит индекс минимума диапазона A [ i … i +2 j -1] . Таблица заполняется индексами минимумов с использованием рекуррентности [1]
- Если A [ B [ i , j -1]] ≤ A [ B [ i +2 j -1 , j -1]] , то B [ i , j ] = B [ i , j -1] ;
- иначе, B [ i , j ] = B [ i +2 j -1 , j -1] .
На запрос RMQ A ( l , r ) теперь можно ответить, разделив его на два отдельных запроса: один - это предварительно вычисленный запрос с диапазоном от l до самой высокой границы, меньшей, чем r . Другой - запрос интервала такой же длины, правая граница которого - r . Эти интервалы могут перекрываться, но, поскольку вычисляется минимум, а не, скажем, сумма, это не имеет значения. Общий результат может быть получен за логарифмическое время, потому что на эти два запроса можно ответить за логарифмическое время, и остается только выбрать меньший из двух результатов.
k | |||||
---|---|---|---|---|---|
0 | 1 | 2 | 3 | ||
л | 1 | 1 | 1 | 1 | 1 |
2 | 2 | 3 | 3 | 7 | |
3 | 3 | 3 | 3 | 7 | |
4 | 4 | 5 | 6 | 7 | |
5 | 5 | 6 | 7 | 7 | |
6 | 6 | 7 | 7 | 7 | |
7 | 7 | 7 | 7 | 7 | |
8 | 8 | 7 | 7 | 7 | |
9 | 9 | 7 | 7 | 7 |
Решение с использованием логарифмического времени и линейного пространства
Это решение отвечает на RMQ за время O (log n ) . Его структуры данных используют пространство O ( n ), и его структуры данных также могут использоваться для ответов на запросы в постоянное время. Массив сначала концептуально делится на блоки размером s =журнал n/4. Затем минимум для каждого блока может быть вычислен за время O ( n ) в целом, и минимумы сохраняются в новом массиве.
Теперь на RMQ можно ответить в логарифмическом времени, посмотрев на блоки, содержащие левую границу запроса, правую границу запроса и все блоки между ними:
- Два блока, содержащих границы, можно наивно искать. Элементы за пределами границы даже не нужно смотреть. Это можно сделать за логарифмическое время.
- Минимумы всех блоков, которые полностью содержатся в диапазоне, и два минимума, упомянутых выше, необходимо сравнить, чтобы ответить на запрос.
- Поскольку массив был разделен на блоки размером журнал n/4, есть не более 4 п/журнал n блоки, которые полностью содержатся в запросе.
- Используя линейное решение, можно найти общий минимум среди этих блоков. Эта структура данных имеет размер O ( п/журнал n бревно ( п/журнал n)) = O ( n ) .
- Теперь нужно сравнить только три минимума.
Например, используя массив A = [0,5,2,5,4,3,1,6,3] и размер блока3 (только для иллюстративных целей) дает минимальный массив A ' = [0,3,1] .
Решение с использованием постоянного времени и линейного пространства
Используя приведенное выше решение, на подзапросы внутри блоков, которые не полностью содержатся в запросе, по-прежнему необходимо отвечать в постоянное время. Таких блоков не больше двух: блок, содержащий l, и блок, содержащий r . Постоянное время достигается за счет хранения декартовых деревьев для всех блоков в массиве. Несколько наблюдений:
- Блоки с изоморфными декартовыми деревьями дают одинаковый результат для всех запросов в этом блоке.
- Количество различных декартовых деревьев узлов s равно C s , s -му каталонскому числу.
- Следовательно, количество различных декартовых деревьев для блоков находится в диапазоне 4 с.
Для каждого такого дерева необходимо сохранить возможный результат для всех запросов. Это сводится к s 2 или O (log 2 n ) записям. Это означает, что общий размер таблицы составляет O ( n ) .
Для эффективного поиска результатов декартово дерево (строка), соответствующее конкретному блоку, должно иметь постоянную адресацию. Решение состоит в том, чтобы сохранить результаты для всех деревьев в массиве и найти уникальную проекцию от двоичных деревьев к целым числам для адресации записей. Этого можно достичь, выполнив поиск в ширину по дереву и добавив листовые узлы, чтобы у каждого существующего узла в декартовом дереве было ровно два дочерних элемента. Затем создается целое число, представляя каждый внутренний узел как 0-бит, а каждый лист как 1-бит в битовом слове (путем повторного обхода дерева в порядке уровней). Это приводит к размеружурнал n/4для каждого дерева. Чтобы разрешить произвольный доступ в постоянное время к любому дереву, деревья, не содержащиеся в исходном массиве, также должны быть включены. Массив с индексамижурнал n/4длина бит имеет размер 2журнал n/4= O ( п ) .
Индекс | 1 | 2 | 3 | ||||||
---|---|---|---|---|---|---|---|---|---|
1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 | |
0 | - | ||||||||
23 (Битовое слово 0010111) | 1 | 2 | 3 | - | 2 | 3 | - | - | 3 |
39 (Битовое слово 0100111) | 1 | 1 | 1 | - | 2 | 3 | - | - | 3 |
127 | - |
Приложения
RMQ используются как инструмент для многих задач по точному и приблизительному сопоставлению строк. Несколько приложений можно найти в Fischer and Heun (2007). [2] : 3
Вычисление наименьшего общего предка в дереве
RMQ могут использоваться для решения самой младшей проблемы общего предка [1] [3] и используются в качестве инструмента для многих задач при точном и приблизительном сопоставлении строк . Запрос LCA LCA S ( v , w ) корневого дерева S = ( V , E ) и двух узлов v , w ∈ V возвращает самый глубокий узел u (который может быть v или w ) на путях от корня к обоим w и v . Габоу, Бентли и Тарджан (1984) показали, что проблема LCA может быть сведена за линейное время к задаче RMQ. Отсюда следует, что, как и проблема RMQ, проблема LCA может быть решена в постоянном времени и линейном пространстве. [2]
Вычисление самого длинного общего префикса в строке
В контексте текста индексации, RMQs может быть использован , чтобы найти LCP (длинный общий префикс), где ЖКП Т ( я , J ) вычисляет LCP из суффиксов , которые начинаются с индексами I и J в T . Для этого мы сначала вычисляем массив суффиксов A и массив обратных суффиксов A −1 . Затем вычисляется массив ЖКПА H , дающий LCP смежных суффиксов в A . После того, как эти структуры данных вычислены и предварительная обработка RMQ завершена, длина общего LCP может быть вычислена за постоянное время по формуле: LCP ( i , j ) = RMQ H ( A -1 [ i ] + 1, A - 1 [ j ]) , где для простоты мы предполагаем, что A -1 [ i ] + 1 <= A -1 [ j ] (иначе поменять местами). [4]
Смотрите также
Рекомендации
- Беркман, Омер; Вишкин, Узи (1993). «Рекурсивная структура параллельных данных типа« звезда-дерево »» . SIAM Journal on Computing . 22 (2): 221–242. DOI : 10.1137 / 0222017 .
- Йоханнес Фишер (декабрь 2009 г.). Оптимальная лаконичность для запросов о минимальном диапазоне (технический отчет). Universität Tübingen, Центр биоинформатики. arXiv : 0812.2775 . Bibcode : 2008arXiv0812.2775F .
- ^ а б в Бендер, Майкл А .; Фарач-Колтон, Мартин ; Пеммасани, Гиридхар; Скиена, Стивен ; Сумазин, Павел (2005). «Наименьшие общие предки в деревьях и ориентированных ациклических графах» (PDF) . Журнал алгоритмов . 57 (2): 75–94. DOI : 10.1016 / j.jalgor.2005.08.001 .
- ^ а б Фишер, Йоханнес; Хойн, Волкер (2007). Новое краткое представление информации RMQ и улучшения в расширенном массиве суффиксов . Материалы Международного симпозиума по комбинаторике, алгоритмам, вероятностным и экспериментальным методологиям. LNCS. 4614 . Springer. С. 459–470. DOI : 10.1007 / 978-3-540-74450-4_41 .
- ^ Бендер, Майкл; Фарах-Колтон, Мартин (2000). Возвращение к проблеме LCA . ЛАТИН 2000: Теоретическая информатика. LNCS. 1776 . Springer. С. 88–94. DOI : 10.1007 / 10719839_9 .
- ^ Фишер, Дж. И В. Хойн (2006). «Теоретические и практические улучшения по проблеме RMQ с приложениями к LCA и LCE». Комбинаторное сопоставление с образцом . Конспект лекций по информатике. 4009 . С. 36–48. CiteSeerX 10.1.1.64.5439 . DOI : 10.1007 / 11780441_5 . ISBN 978-3-540-35455-0. Отсутствует или пусто
|title=
( справка )
Внешние ссылки
- Статья о минимальном диапазоне запросов на TopCoder
- Статья о минимальном диапазоне запросов на PEGWiki / P3G
- Презентационные слайды Stanford CS166 RMQ