Минимальный запрос диапазона - 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А(л,р) теперь можно ответить, разделив его на два отдельных запроса: один - это предварительно вычисленный запрос с диапазоном от л до самой высокой границы меньше, чем р. Другой - запрос интервала такой же длины, который имеет р как его правая граница. Эти интервалы могут перекрываться, но поскольку вычисляется минимум, а не, скажем, сумма, это не имеет значения. Общий результат может быть получен за постоянное время, потому что на эти два запроса можно ответить за постоянное время, и единственное, что осталось сделать, - это выбрать меньший из двух результатов.
| 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 в О(бревно п) время. Его структуры данных используют О(п) пространство и его структуры данных также могут использоваться для ответов на запросы в постоянное время. Массив сначала концептуально делится на блоки размером 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 = О(п).
| Индекс | 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 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.
- ^ а б c Бендер, Майкл А .; Фарах-Колтон, Мартин; Пеммасани, Гиридхар; Скиена, Стивен; Сумазин, Павел (2005). «Наименьшие общие предки в деревьях и ориентированных ациклических графах» (PDF). Журнал алгоритмов. 57 (2): 75–94. Дои:10.1016 / j.jalgor.2005.08.001.
- ^ а б Фишер, Йоханнес; Хойн, Волкер (2007). Новое краткое представление RMQ-информации и улучшения в расширенном массиве суффиксов. Материалы Международного симпозиума по комбинаторике, алгоритмам, вероятностным и экспериментальным методологиям. LNCS. 4614. Springer. С. 459–470. Дои:10.1007/978-3-540-74450-4_41.
- ^ Бендер, Майкл; Фарах-Колтон, Мартин (2000). Возвращение к проблеме LCA. ЛАТИН 2000: Теоретическая информатика. LNCS. 1776. Springer. С. 88–94. Дои:10.1007/10719839_9.
- ^ Фишер, Дж. И В. Хойн (2006). Теоретические и практические улучшения по RMQ-проблеме с приложениями к LCA и LCE. Комбинаторное сопоставление с образцом. Конспект лекций по информатике. 4009. С. 36–48. CiteSeerX 10.1.1.64.5439. Дои:10.1007/11780441_5. ISBN 978-3-540-35455-0.