Минимальный запрос диапазона - Range minimum query

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

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

Определение

Учитывая массив А[1 … п] из п объекты взяты из полностью заказанный установить, например целые числа, минимальный диапазон запроса RMQА(л,р) = arg min А[k] (с 1 ≤ л ≤ k ≤ р ≤ п) возвращает позицию минимального элемента в указанном подмассиве А[л … р].

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

Алгоритмы

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

В типичных условиях массив А является статическим, то есть элементы не вставляются и не удаляются во время серии запросов, а запросы, на которые нужно ответить в интерактивном режиме (то есть, весь набор запросов заранее неизвестен алгоритму). В этом случае подходящая предварительная обработка массива в структуру данных обеспечивает более быстрый ответ на запрос. Наивное решение - предварительно вычислить все возможные запросы, то есть минимум всех подмассивов А, и сохраните их в массиве B такой, что B[я, j] = мин (А[я…j]); тогда запрос минимального диапазона может быть решен за постоянное время путем поиска в массиве в B. Есть Θ (п²) возможные запросы по длине-п массив, и ответы на них могут быть вычислены в Θ (п²) время по динамическое программирование.[1]

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

Как и в приведенном выше решении, ответы на запросы в постоянное время будут достигнуты путем предварительного вычисления результатов. Однако в массиве будут храниться предварительно вычисленные минимальные запросы для всех элементов и только диапазонов, размер которых является степенью двойки. Есть Θ (журнал п) такие запросы для каждой стартовой позиции я, поэтому размер таблицы динамического программирования B является Θ (п бревно п). Каждый элемент B[я, j] содержит индекс минимума диапазона А[я…я+2j-1]. Таблица заполняется индексами минимумов с использованием рекуррентности[1]

Если А[B[я, j-1]] ≤ А[B[я+2j-1, j-1]], тогда B[я, j] = B[я, j-1];
еще, B[я, j] = B[я+2j-1, j-1].

Запрос RMQА(л,р) теперь можно ответить, разделив его на два отдельных запроса: один - это предварительно вычисленный запрос с диапазоном от л до самой высокой границы меньше, чем р. Другой - запрос интервала такой же длины, который имеет р как его правая граница. Эти интервалы могут перекрываться, но поскольку вычисляется минимум, а не, скажем, сумма, это не имеет значения. Общий результат может быть получен за постоянное время, потому что на эти два запроса можно ответить за постоянное время, и единственное, что осталось сделать, - это выбрать меньший из двух результатов.

Таблица результатов для А = [0,5,2,5,4,3,1,6,3]
 k
0123
л11111
22337
33337
44567
55677
66777
77777
88777
99777

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

Это решение отвечает на вопросы RMQ в О(бревно п) время. Его структуры данных используют О(п) пространство и его структуры данных также могут использоваться для ответов на запросы в постоянное время. Массив сначала концептуально делится на блоки размером s = бревно п/4. Тогда минимум для каждого блока можно вычислить в О(п) общее время и минимумы сохраняются в новом массиве.

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

  • Можно наивно искать два блока, содержащих границы. Элементы за пределами границы даже не нужно смотреть. Это можно сделать за логарифмическое время.
  • Для ответа на запрос необходимо сравнить минимумы всех блоков, которые полностью содержатся в диапазоне, и два минимума, упомянутых выше.
  • Поскольку массив был разделен на блоки размером бревно п/4, есть не более 4п/бревно п блоки, которые полностью содержатся в запросе.
  • Используя линейное решение, можно найти общий минимум среди этих блоков. Эта структура данных имеет размер О(п/бревно п бревно (п/бревно п)) = О(п).
  • Теперь нужно сравнить только три минимума.

Например, используя массив А = [0,5,2,5,4,3,1,6,3] и размер блока 3 (только для иллюстративных целей) дает минимальный массив А ' = [0,3,1].

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

Используя вышеприведенное решение, на подзапросы внутри блоков, которые не полностью содержатся в запросе, по-прежнему нужно отвечать в постоянное время. Таких блоков не более двух: блок, содержащий л и блок, содержащий р. Постоянное время достигается за счет сохранения Декартовы деревья для всех блоков в массиве. Несколько наблюдений:

  • Блоки с изоморфный Декартовы деревья дают одинаковый результат для всех запросов в этом блоке.
  • Количество различных декартовых деревьев s узлы Cs, то sй Каталонский номер
  • Следовательно, количество различных декартовых деревьев для блоков находится в диапазоне 4s

Для каждого такого дерева необходимо сохранить возможный результат для всех запросов. Это сводится к s2 или же О(бревно2 п) записи. Это означает, что общий размер стола равен О(п).

Для эффективного поиска результатов декартово дерево (строка), соответствующая конкретному блоку, должно иметь постоянную адресацию. Решение состоит в том, чтобы сохранить результаты для всех деревьев в массиве и найти уникальную проекцию из двоичных деревьев в целые числа для адресации записей. Этого можно добиться, выполнив поиск в ширину через дерево и добавление листовых узлов так, чтобы каждый существующий узел в декартовом дереве имел ровно двух дочерних элементов. Затем создается целое число, представляя каждый внутренний узел как 0-бит, а каждый лист как 1-бит в битовом слове (путем повторного обхода дерева в порядке уровней). Это приводит к размеру бревно п/4 для каждого дерева. Чтобы разрешить произвольный доступ в постоянное время к любому дереву, необходимо также включить деревья, не содержащиеся в исходном массиве. Массив с индексами бревно п/4 длина бит имеет размер 2бревно п/4 = О(п).

Пример декартовых деревьев для А = [0,5,2,5,4,3,1,6,3]. Обратите внимание, что первое и третье дерево имеют одинаковую структуру, поэтому в таблице слева есть ровно два предварительно вычисленных набора запросов.
Предварительно вычисленные результаты для трех декартовых блочных деревьев А = [0,5,2,5,4,3,1,6,3]
Индекс123
123123123
0—
23 (Битовое слово 0010111)123—23——3
39 (Битовое слово 0100111)111—23——3
127—

Приложения

RMQ используются как инструмент для многих задач по точному и приблизительному сопоставлению строк. Несколько приложений можно найти в Fischer and Heun (2007).[2]:3

Вычисление наименьшего общего предка в дереве

RMQ могут использоваться для решения проблемы с наименьшим общим предком[1][3] и используются как инструмент для многих задач в точном и приблизительном соответствие строк.Запрос LCA LCAS(v, ш) корневого дерева S = (V, E) и два узла v, ш ∈ V возвращает самый глубокий узел ты (что может быть v или же ш) на путях от корня к обоим ш и v.Gabow, Bentley и Tarjan (1984) показали, что проблема LCA может быть сведена за линейное время к проблеме RMQ. Отсюда следует, что, как и проблема RMQ, проблема LCA может быть решена в постоянном времени и линейном пространстве.[2]

Вычисление самого длинного общего префикса в строке

В контексте текстового индексирования RMQ могут использоваться для поиска LCP (самый длинный общий префикс), где LCPТ(я, j) вычисляет LCP суффиксов, начинающихся с индексов я и j в Т. Для этого мы сначала вычисляем массив суффиксов А, и массив обратных суффиксов А−1. Затем мы вычисляем массив LCP ЧАС давая LCP соседних суффиксов в А. После того, как эти структуры данных вычислены и предварительная обработка RMQ завершена, длина общей LCP может быть вычислена за постоянное время по формуле: LCP (я, j) = RMQЧАС(А-1[я] + 1, А-1[j]), где для простоты предполагается, что А-1[я] + 1 <= А-1[j] (иначе поменяйте местами).[4]

Смотрите также

Рекомендации

  • Беркман, Омер; Вишкин, Узи (1993). «Рекурсивная структура параллельных данных типа« звезда-дерево »». SIAM Журнал по вычислениям. 22 (2): 221–242. Дои:10.1137/0222017.
  • Йоханнес Фишер (декабрь 2009 г.). Оптимальная лаконичность для запросов о минимальном диапазоне (технический отчет). Universität Tübingen, Центр биоинформатики. arXiv:0812.2775. Bibcode:2008arXiv0812.2775F.
  1. ^ а б c Бендер, Майкл А .; Фарах-Колтон, Мартин; Пеммасани, Гиридхар; Скиена, Стивен; Сумазин, Павел (2005). «Наименьшие общие предки в деревьях и ориентированных ациклических графах» (PDF). Журнал алгоритмов. 57 (2): 75–94. Дои:10.1016 / j.jalgor.2005.08.001.
  2. ^ а б Фишер, Йоханнес; Хойн, Волкер (2007). Новое краткое представление RMQ-информации и улучшения в расширенном массиве суффиксов. Материалы Международного симпозиума по комбинаторике, алгоритмам, вероятностным и экспериментальным методологиям. LNCS. 4614. Springer. С. 459–470. Дои:10.1007/978-3-540-74450-4_41.
  3. ^ Бендер, Майкл; Фарах-Колтон, Мартин (2000). Возвращение к проблеме LCA. ЛАТИН 2000: Теоретическая информатика. LNCS. 1776. Springer. С. 88–94. Дои:10.1007/10719839_9.
  4. ^ Фишер, Дж. И В. Хойн (2006). Теоретические и практические улучшения по RMQ-проблеме с приложениями к LCA и LCE. Комбинаторное сопоставление с образцом. Конспект лекций по информатике. 4009. С. 36–48. CiteSeerX  10.1.1.64.5439. Дои:10.1007/11780441_5. ISBN  978-3-540-35455-0.

внешняя ссылка