Минимальный запрос диапазона

Построение соответствующего декартова дерева для решения минимального запроса диапазона.

Запрос минимального диапазона уменьшен до самой низкой проблемы общего предка .

В информатике запрос на минимальный диапазон ( RMQ ) решает проблему поиска минимального значения в подмассиве массива сопоставимых объектов. Запросы с минимальным диапазоном имеют несколько вариантов использования в информатике, такие как проблема с наименьшим общим предком и проблема с самым длинным общим префиксом (LCP).

Определение

Для массива $A$ $[1\dots$ $n$ $]$ из $n$ объектов, взятых из полностью упорядоченного набора, такого как целые числа, минимальный запрос диапазона $RMQ$ $A$ $($ $l$ $,$ $r$ $) = arg min$ $A$ $[$ $k$ $]$ (при $1 \leq$ $l$ $\leq$ $k$ $\leq$ $r$ $\leq$ $n$ ) возвращает позицию минимального элемента в указанном подмассиве $A$ $[$ $l$ $\dots$ $r$ $]$ .

Например, когда $A = [0,5,2,5,4,3,1,6,3]$ , то ответ на запрос минимального диапазона для $подмассивов$ $A [3\dots 8] = [2,5 , 4,3,1,6]$ - это7 , так как $A [7] = 1$ .

Алгоритмы

Наивное решение

В типичной настройке массив $A$ является статическим, т. Е. Элементы не вставляются и не удаляются во время серии запросов, а запросы, на которые необходимо ответить в интерактивном режиме (т. Е. Весь набор запросов заранее неизвестен алгоритму ). В этом случае подходящая предварительная обработка массива в структуру данных обеспечивает более быстрый ответ на запрос. Наивное решение состоит в том, чтобы предварительно вычислить все возможные запросы, т.е. минимум всех подмассивов $A$ , и сохранить их в массиве $B так$ , чтобы $B [i, j] = min (A [i \dots j])$ ; тогда запрос диапазона min может быть решен за постоянное время поиском массива в $B$ . Существует $(n ²)$ возможных запросов для массива длиной $n$ , и ответы на них могут быть вычислены за $Θ (n ²)$ времени с помощью динамического программирования . ^[1]

Решение с использованием логарифмического времени и линейного пространства

Как и в приведенном выше решении, ответы на запросы в постоянное время будут достигнуты путем предварительного вычисления результатов. Однако в массиве будут храниться предварительно вычисленные минимальные запросы для всех элементов и только для диапазонов, размер которых является степенью двойки. Для каждой начальной позиции $i$ существует $Θ (log n)$ таких запросов , поэтому размер таблицы динамического программирования $B$ равен $($ $n$ $log$ $n$ $)$ . Каждый элемент $B$ $[$ $i$ $,$ $j$ $]$ содержит индекс минимума диапазона $A$ $[$ $i$ $\dots$ $i$ $+2$ $j$ $-1]$ . Таблица заполняется индексами минимумов с использованием рекуррентности ^[1]

Если

A [B [i, j -1]] \leq 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$ . Эти интервалы могут перекрываться, но, поскольку вычисляется минимум, а не, скажем, сумма, это не имеет значения. Общий результат может быть получен за логарифмическое время, потому что на эти два запроса можно ответить за логарифмическое время, и остается только выбрать меньший из двух результатов.

Таблица результатов для $A = [0,5,2,5,4,3,1,6,3]$
		$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 = log n / 4$ . Затем минимум для каждого блока может быть вычислен за время $O (n) в$ целом, и минимумы сохраняются в новом массиве.

Теперь на RMQ можно ответить в логарифмическом времени, посмотрев на блоки, содержащие левую границу запроса, правую границу запроса и все блоки между ними:

Два блока, содержащих границы, можно наивно искать. Элементы за пределами границы даже не нужно смотреть. Это можно сделать за логарифмическое время.
Минимумы всех блоков, которые полностью содержатся в диапазоне, и два минимума, упомянутых выше, необходимо сравнить, чтобы ответить на запрос.
Поскольку массив был разделен на блоки размером $log$ $n$ $/$ $4$ , в запросе полностью содержится не более $4$ $n$ $/$ $log$ $n$ блоков.
Используя линейное решение, можно найти общий минимум среди этих блоков. Эта структура данных имеет размер $O (n / log n log (n / log 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$ для каждого дерева. Чтобы разрешить произвольный доступ в постоянное время к любому дереву, деревья, не содержащиеся в исходном массиве, также должны быть включены. Массив с индексами длиной $log$ $n$ $/$ $4$ бит имеет размер $2$ $log$ $n$ $/$ $4$ $=$ $O$ $($ $n$ $)$ .

Пример декартовых деревьев для

A = [0,5,2,5,4,3,1,6,3]

. Обратите внимание, что первое и третье дерево имеют одинаковый макет, поэтому в таблице слева есть ровно два предварительно вычисленных набора запросов.

Предварительно вычисленные результаты для трех декартовых деревьев блоков $A = [0,5,2,5,4,3,1,6,3]$
Показатель	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 \in 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 .

^ ^a b c Бендер, Майкл А .; Фарач-Колтон, Мартин ; Пеммасани, Гиридхар; Скиена, Стивен ; Сумазин, Павел (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 .
^ Фишер, J. и В. Heun (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

[bender-jalg-1] Бендер, Майкл А .; Фарач-Колтон, Мартин ; Пеммасани, Гиридхар; Скиена, Стивен ; Сумазин, Павел (2005). «Наименьшие общие предки в деревьях и ориентированных ациклических графах» (PDF) . Журнал алгоритмов . 57 (2): 75–94. DOI : 10.1016 / j.jalgor.2005.08.001 .

[fischer07-2] а б Фишер, Йоханнес; Хойн, Волкер (2007). Новое краткое представление информации RMQ и улучшения в расширенном массиве суффиксов . Материалы Международного симпозиума по комбинаторике, алгоритмам, вероятностным и экспериментальным методологиям. LNCS. 4614 . Springer. С. 459–470. DOI : 10.1007 / 978-3-540-74450-4_41 .

[3] Бендер, Майкл; Фарах-Колтон, Мартин (2000). Возвращение к проблеме LCA . ЛАТИН 2000: Теоретическая информатика. LNCS. 1776 . Springer. С. 88–94. DOI : 10.1007 / 10719839_9 .

[10.1007/11780441_5-4] Фишер, J. и В. Heun (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=( справка )

[1]