Минимальный запрос диапазона
В информатике запрос минимума диапазона ( 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 , j ] , а только для диапазонов, размер которых равен степени двойки. существует O(log n ) Для каждой начальной позиции i таких запросов , поэтому размер таблицы динамического программирования B равен O( n log n ) . Значение B [ i , j ] является индексом минимума диапазона A [ i … i +2 дж -1] . Заполнение таблицы занимает время O( n log n ) с индексами минимумов с использованием следующей рекурсии [ 1 ] [ 2 ]
- Если A [ B [ i , j -1]] ≤ A [ B [ i +2 Дж -1 , j -1]] , то B [ i , j ] = B [ i , j -1] ;
- иначе B [ i , j ] = B [ я +2 Дж -1 , j -1] .
После этого этапа предварительного вычисления на запрос RMQ A ( l , r ) теперь можно ответить за постоянное время, разделив его на два отдельных запроса: один — это предварительно вычисленный запрос с диапазоном от l до наибольшего запомненного значения, меньшего r. . Другой — это запрос интервала одинаковой длины, равна r правая граница которого . Эти интервалы могут перекрываться, но поскольку мы пытаемся вычислить минимум, а не, например, сумму чисел в массиве, это не имеет значения. Таким образом, общий результат может быть получен после предварительного вычисления линейного времени за постоянное время: на два запроса можно ответить за постоянное время, и единственное, что остается сделать, это выбрать меньший из двух результатов.
| к | |||||
|---|---|---|---|---|---|
| 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 | |
Решение с использованием логарифмического времени запроса после предварительного вычисления линейного времени и пространства.
[ редактировать ]Это решение выполняет предварительные вычисления за время O ( n ) . Его структуры данных используют пространство O ( n ) , а его структуры данных могут использоваться для ответа на запросы в логарифмическом времени. [ 2 ] Массив сначала концептуально разделяется на блоки размером s = журнал n / 4 . Затем минимум для каждого блока можно вычислить за время O ( n ) , а минимумы сохранить в новом массиве.
На запросы RMQ теперь можно отвечать за логарифмическое время, просматривая блоки, содержащие левую границу запроса, правую границу запроса и все блоки между ними:
- Два блока, содержащие границы, можно легко найти. На элементы за пределами границы даже не нужно смотреть. Это можно сделать за логарифмическое время.
- Для ответа на запрос необходимо сравнить минимумы всех блоков, которые полностью содержатся в диапазоне, и два упомянутых выше минимума.
- Поскольку массив был разделен на блоки размером log n / 4 , их не более 4 n / log n блоков, полностью содержащихся в запросе.
- Используя линеарифмическое решение, можно найти общий минимум среди этих блоков. Эта структура данных имеет размер O ( n / журнал n журнал ( n / logn = ) ) О ( п ) .
- Теперь нужно сравнить только три минимума.
Например, использование массива A = [0,5,2,5,4,3,1,6,3] и размера блока 3 (только для иллюстративных целей) дает минимальный массив A' = [0,3 ,1] .
Решение с использованием постоянного времени и линейного пространства.
[ редактировать ]Используя приведенное выше решение, на подзапросы внутри блоков, которые не полностью содержатся в запросе, все равно необходимо отвечать за постоянное время. Всего таких блоков не более двух: блок, содержащий l, и блок, содержащий r . Постоянное время достигается за счет хранения декартовых деревьев для всех блоков массива. Несколько наблюдений:
- Блоки с изоморфными декартовыми деревьями дают одинаковый результат для всех запросов в этом блоке.
- Число различных декартовых деревьев с s узлами равно C s , s -е каталанское число.
- Следовательно, количество различных декартовых деревьев для блоков находится в пределах 4 с
Для каждого такого дерева необходимо сохранить возможный результат для всех запросов. Это сводится к тому, что 2 или О (лог. 2 п ) записи. Это означает, что общий размер таблицы равен O ( n ) .
Для эффективного поиска результатов декартово дерево (строка), соответствующее определенному блоку, должно быть доступно за постоянное время. Решение состоит в том, чтобы сохранить результаты для всех деревьев в массиве и найти уникальную проекцию двоичных деревьев на целые числа для обращения к записям. Этого можно добиться, выполнив поиск в ширину по дереву и добавив листовые узлы так, чтобы каждый существующий узел в декартовом дереве имел ровно два дочерних узла. Затем целое число генерируется путем представления каждого внутреннего узла как 0-бита и каждого листа как 1-бита в битовом слове (путем повторного обхода дерева в порядке уровней). Это приводит к размеру log n / 4 для каждого дерева. Чтобы обеспечить произвольный доступ к любому дереву в постоянное время, необходимо также включить деревья, не содержащиеся в исходном массиве. Массив с индексами log n / 4 длина бит имеет размер 2 журнал n / 4 знак равно О ( п ) .
| Индекс | 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 используются как инструмент для решения многих задач по точному и приблизительному сопоставлению строк. Несколько применений можно найти у Фишера и Хойна (2007). [ 3 ] : 3
Вычисление наименьшего общего предка в дереве
[ редактировать ]RMQ можно использовать для решения проблемы наименьшего общего предка. [ 1 ] [ 2 ] и используются в качестве инструмента для решения многих задач по точному и приблизительному сопоставлению строк . Запрос LCA LCA S ( v , w ) корневого дерева S = ( V , E ) и двух узлов v , w ∈ V возвращает самый глубокий узел u (который может быть v или w ) на путях от корня к обоим w и в . Габоу, Бентли и Тарьян (1984) показали, что задачу LCA можно свести за линейное время к задаче RMQ. Отсюда следует, что, как и проблема RMQ, проблема LCA может быть решена в постоянном времени и линейном пространстве. [ 3 ]
Вычисление самого длинного общего префикса в строке
[ редактировать ]В контексте индексации текста RMQ можно использовать для поиска LCP (самого длинного общего префикса), где LCP T ( i , j ) вычисляет LCP суффиксов, которые начинаются с индексов i и j в T . Для этого мы сначала вычисляем массив суффиксов A и массив обратных суффиксов A. −1 . Затем мы вычисляем массив LCP H, давая LCP соседних суффиксов в A . Как только эти структуры данных вычислены и предварительная обработка RMQ завершена, длину общего LCP можно вычислить за постоянное время по формуле: LCP( i , j ) = RMQ H ( A -1 [ я ] + 1, А -1 [ j ]) , где для простоты предполагаем, что A -1 [ я ] + 1 <= А -1 [ j ] (в противном случае поменяйте местами). [ 4 ]
См. также
[ редактировать ]Ссылки
[ редактировать ]- Беркман, Омер; Вишкин, Узи (1993). «Рекурсивная параллельная структура данных звездного дерева» . SIAM Journal по вычислительной технике . 22 (2): 221–242. дои : 10.1137/0222017 . Архивировано из оригинала 23 сентября 2017 года.
- Йоханнес Фишер (декабрь 2009 г.). Оптимальная краткость для запросов с минимальным диапазоном (технический отчет). Университет Тюбингена, Центр биоинформатики. arXiv : 0812.2775 . Бибкод : 2008arXiv0812.2775F .
- [ 2 ]
- ^ Jump up to: а б с Бендер, Майкл А.; Фарах-Колтон, Мартин ; Пеммасани, Гиридхар; Скиена, Стивен ; Сумазин, Павел (2005). «Наименьшие общие предки в деревьях и ориентированных ациклических графах» (PDF) . Журнал алгоритмов . 57 (2): 75–94. дои : 10.1016/j.jalgor.2005.08.001 .
- ^ Jump up to: а б с д Бендер, Майкл; Фарах-Колтон, Мартин (2000). «Возвращение к проблеме LCA». ЛАТИНЬ 2000: Теоретическая информатика . ЛАТИНЬ 2000: Теоретическая информатика. ЛНКС. Том. 1776. Спрингер. стр. 88–94. дои : 10.1007/10719839_9 . ISBN 978-3-540-67306-4 .
- ^ Jump up to: а б Фишер, Йоханнес; Хойн, Волкер (2007). «Новое краткое представление информации RMQ и улучшения расширенного массива суффиксов». Комбинаторика, алгоритмы, вероятностные и экспериментальные методологии . Труды международного симпозиума по комбинаторике, алгоритмам, вероятностным и экспериментальным методологиям. ЛНКС. Том. 4614. Спрингер. стр. 459–470. дои : 10.1007/978-3-540-74450-4_41 . ISBN 978-3-540-74449-8 .
- ^ Фишер Дж. и В. Хойн (2006). «Теоретические и практические улучшения проблемы RMQ с применением к LCA и LCE». Комбинаторное сопоставление с образцом . Конспекты лекций по информатике. Том. 4009. стр. 36–48. CiteSeerX 10.1.1.64.5439 . дои : 10.1007/11780441_5 . ISBN 978-3-540-35455-0 .