Поиск предков: различия между версиями

Рассмотрим упорядоченную совокупность U и множество T <math> \subset</math> U, |T| = n. Целью является предварительная обработка T таким образом, чтобы можно было эффективно отвечать на следующий запрос: пусть задан элемент <math>x \in U</math>, требуется найти предка x, т. е. <math>max \{ y \in T | y < x \}</math>. Также можно рассмотреть динамическую задачу, когда элементы вставляются в T и удаляются из него. Обозначим за <math>t_q</math> время запроса, а за <math>t_u</math> – время обновления.

'''Коммуникативные игры''': предположим, что у Алисы есть запрос ''x'', а у Боба – множество T. Они пытаются найти предка ''x'' в результате <math>\tau</math> раундов коммуникации, где в каждом раунде Алиса посылает <math>m_A</math> бит, а Боб отвечает с помощью <math>m_B</math> бит.

Внешняя память: единицей доступа является страница, содержащая B слов по <math>\ell</math> бит каждое. B-деревья решают задачу со временем запроса и обновления <math>O(log_B \; n)</math>; этого также можно достичь, не обращая внимания на значение B ''(см. [[B-деревья без явного задания параметров кэша]])''. Модель клеточного зонда с <math>b = B \cdot \ell</math> сильнее данной модели.

'''<math>AC^0</math>-RAM''': это вариант пословной RAM-машины, в котором допустимыми операциями являются функции, имеющие постоянную глубину, неограниченные схемы объединения по входу. Это исключает умножение из стандартного набора операций.

Логарифмическая граница для сравнительного поиска в наихудшем случае не особенно информативна, когда эффективность особенно важна. На практике при работе с огромными массивами данных стандартным подходом является использование B-деревьев и их вариантов. Решения, основанные на изобретательном использовании оперативной памяти, подходят для случаев, когда набор данных не особенно велик, но быстрое время выполнения запроса имеет решающее значение – как, например, в программных решениях для поиска информации об IP-адресах [7].

Основываясь на длительной серии исследований, Петрашку и Торуп [15,16] в конечном итоге получили соответствующие верхние и нижние границы для статической задачи в моделях пословной RAM-машины, клеточного зонда, внешней памяти и коммуникативной игры.

Эта граница достигается детерминированным алгоритмом запроса. Для любого пространства S структура данных может быть построена за время O(S) с помощью рандомизированного алгоритма, начиная с множества T, заданного в отсортированном порядке. Обновления выполняются за ожидаемое время <math>t_q + O(S/n)</math>. Таким образом, помимо нахождения элемента за один запрос предка, обновления изменяют минимальную часть структуры данных.

Нижние границы справедливы для мощной модели клеточного зонда и выполняются для рандомизированных алгоритмов. Когда S > n1+", оптимальный компромисс для коммуникативных игр совпадает с (1). Заметим, что случай S = n1+o(1) практически устраняется при сведении к коммуникационной сложности, поскольку сообщения Алисы зависят только от lg S. Таким образом, нет асимптотической разницы между S = O(n) и, скажем, S = O(n2).

• B-деревья обеспечивают время запроса O(logB n) при линейном объеме памяти.

• Деревья слияния, предложенные Фредманом и Уиллардом [10], дают время запроса O(logb n). В основе этого результата лежит узел слияния – структура, которая может выполнять поиск среди b" значений за постоянное время. Это достигается путем признания того, что только несколько бит каждого значения являются важными, и упаковки соответствующей информации обо всех значениях в одно слово.

• Поиск ван Эмде Боаса [ ] способен решить задачу за время O(lg£) путем бинарного поиска длины самого длинного общего префикса между запросом и значением в T. Начиная поиск с просмотра таблицы на основе первых lg n бит и заканчивая, когда достаточно места для хранения всех ответов, можно сократить время запроса до O(lg((£ - lg n)/a)).

• Методика Бима и Фич [4] позволяет выполнять многоходовый поиск самого длинного общего префикса, поддерживая точный баланс между I и n. Это актуально, когда объем памяти составляет не менее n1+", и дает третью ветвь (1). Петрашку и Торуп [ ] показывают, как можно реализовать родственные идеи при меньшем объеме памяти, что дает последнюю ветвь (1).

Заметим, что внешняя память участвует в достижении оптимального компромисса только за счет члена O(logB n), приходящегося на B-деревья. Таким образом, оптимальным является либо использование стандартных B-деревьев, основанных на сравнении, либо использование наилучшей стратегии пословной RAM-машины, полностью обходящейся без внешней памяти.

Все нижние границы до выхода работы [15] были показаны на модели коммуникативной игры. Айтай [ ] первым представил суперконстантную нижнюю границу. Его результаты, с поправкой Милтерсена [12], показывают, что для полиномиального объема памяти существует n как функция от £, позволяющая получить время запроса £?(y/lg~£), и аналогично существует I как функция от n, позволяющая получить сложность запроса Q (3lgn).

Милтерсен и другие [ ] пересмотрели доказательство Айтая, распространив его на рандомизированные алгоритмы. Что более важно, они отразили суть доказательства в лемме о независимом исключении раунда, которая служит важным инструментом при доказательстве нижних границ в асимметричной коммуникации.

Бим и Фич [ ] улучшили нижние границы Айтая до и ^2(y'lg n/lglg n), соответственно. Сен и Венкатеш  [17] позже представили улучшенную лемму об исключении раунда, которая обосновывает эти нижние границы в том числе и для рандомизированных алгоритмов.

Наконец, используя лемму о сжатии сообщений из работы [6] (являющемся альтернативой исключению раунда), Петрашку и Торуп [15] предложили оптимальный компромисс для коммуникативных игр. Он также является оптимальной нижней границей в других моделях, в которых S > n1+", но не подходит для меньшего объема памяти.

Что более важно, в [ ] были разработаны первые инструменты для доказательства нижних границ, превышающих коммуникационную сложность, для случаев S = n1+o(1). Здесь впервые было проведено разделение между структурой данных полиномиального размера и структурой размера, близкого к линейному. Его принципиально невозможно получить при помощи нижней границы для прямых коммуникаций, поскольку редукция к коммуникативным играм зависит только от lg S.

Полный результат Петрашку и Торупа [ ] представляет собой компромисс (1). Первоначально он был показан только для детерминированных алгоритмов запросов, но со временем был распространен и на нижнюю границу рандомизированного алгоритма [16]. Среди удивительных последствий этого результата было то, что классический поиск ван Эмде Боаса является оптимальным для почти линейного объема памяти (и, следовательно, для динамических структур данных), тогда как при наличии квадратичного объема памяти он может уступать технике Бима и Фич.

С технической точки зрения идея [ ] заключается в одновременном анализе нескольких запросов. Затем рассматривается коммуникативная игра, включающая все запросы, и доказывается версия леммы об исключении раунда с прямой суммой. Возможно, доказательство в данном случае даже проще, чем у обычной леммы об исключении раунда. Это достигается за счет рассмотрения более сильной модели индуктивного анализа, в которой алгоритму разрешается отклонить большую часть запросов, прежде чем приступить к зондированию.

Поскольку блоки размером wO(1) могут обрабатываться деревьями слияния за константное время, из этого следует, что коэффициенты w объема памяти не имеют значения. Более экстремальное применение этой идеи дают экспоненциальные деревья [ ]. Здесь блоки имеют размер @(n1~y), где у – достаточно небольшая константа. Блоки обрабатываются рекурсивно таким же образом, что дает в итоге O(lglg n) уровней. Если начальное время запроса не меньше tq > lg" n, то время запроса на каждом уровне уменьшается в геометрической прогрессии, так что общее время растет только на постоянный коэффициент. Однако при соответствующем выборе у любое полиномиальное требование к памяти сводится к линейному. Кроме того, экспоненциальное дерево может быть обновлено за время O(tq), даже если исходная структура данных была статической.

Возможно, наиболее важным применением задачи поиска предков является просмотр информации об IP-адресах. Эту задачу решают маршрутизаторы для каждого пакета в Интернете, когда выбирают, в какую подсеть направить пакет. Таким образом, это, вероятно, самая часто выполняемая алгоритмическая задача в мире. Формально это запрос о поиске в интервале, который эквивалентен поиску предка в статическом случае [ ]. Поскольку при решении этой задачи эффективность исключитель важна, необходимо отметить, что самые быстро внедряемые программные решения [ ] используют стратегии целочисленного поиска (не основанные на сравнении), как и предсказывают теоретические результаты.

Кроме того, поиск предков широко используется в структурах данных при редукции задач к пространству рангов. Пусть имеется множество T. Часто требуется переразметить его в более простое f1...: ; ng («пространство рангов»), сохранив при этом отношения порядка. Если новые значения представляются динамически, возникает необходимость в запросе на поиск предка. Вот несколько наглядных примеров:

• При запросах в ортогональном диапазоне поддерживается набор точек в Ud и выполняются запросы на точки в некотором прямоугольнике [a1; b1] x - - - x [ad; bd]. Хотя границы обычно растут экспоненциально с увеличением размерности, зависимость от совокупности можно факторизовать. Во время запроса сначала выполняются 2d запросов предков, преобразующих совокупность в 1...nd.

Наконец, любопытно отметить, что нижние границы в задаче поиска предка оказываются применимы, путем редукции, ко всем описанным выше приложениям. Чтобы сделать такие редукции возможными, нижние границы на самом деле показаны для более слабой задачи поиска цвета предка. В этой задаче значения множества T окрашены в красный или синий цвет, и запрос должен найти только цвет предшественника.

Подход к реализации деревьев слияния с инструкциями AC0 известен [2], но для других стратегий запросов это не так. Каков наилучший компромисс между запросами, достижимый для RAM-машины AC0? В частности, может ли поиск ван Эмде Боаса быть реализован с помощью инструкций AC0?

Наконец, требуется ли запрос для обновления структуры предков? Иными словами, можно ли получить tu = o(tq), сохранив при этом эффективное время запроса?