Сверхлогарифмический поиск. 
Интеллектуальные системы

Пусть.

где Fi, Gi определяются соотношениями (2.28), (2.29).

Понятно, что для Nf G сг для любого / 6 .

Справедлива следующая теорема.

Теорема 16. Пусть функция плотности распределения вероятностей p (u, v), определяющая меру Р вероятностного пространства над множеством запросов Хш, такая, что p (u, v) < с = const; I = (Xi_nt, V, pint) ~ произвольная ЗИП типа Si_nt; Т2 — базовое множество, определяемое соотношением (2.32). Тогда

Доказательство. Упорядочим записи в библиотеке у = {уь • • • > 2/fc} так, что у, < у₂ <? ?? < Ук?

Пусть т — некоторый параметр, значение которого определим позже.

Введем множество номеров S = {"I,…, s_m_i} такое, что Si — номер записи из V такой, что y_Si — ближайшая слева запись к точке i/m (г = 1, т — 1), а если такой записи не существует, то Si = 0.

Возьмем точку, объявим ее корнем графа и обозначим /%• Выпустим из корня два ребра, одно из которых будем считать левым, а другое правым. Конец левого ребра обозначим Д, а конец второго — fo.

Припишем корню переключатель g-_%rn(u, v) из множества?? з. Левому ребру припишем 1, а правому 2.

Построим для V граф Uy так, как это было сделано в доказательстве теоремы 15 и совместим его корень с вершиной А;

Построим ориентированное сбалансированное бинарное дерево с т — 1 концевыми вершинами с корнем в вершине Д, все ребра которого ориентированы от ft к концевым вершинам. Обозначим это дерево через D_m_i. Из каждой внутренней вершины дерева Дп-i исходит 2 ребра, одному из них припишем 1, а другому — 2, т. е. все ребра дерева D_m_i будут переключательными. Тогда каждой концевой вершине дерева D_m_i можно сопоставить слово из символов 1 и 2 в соответствии с ребрами, встречающимися в цепи от корня к данному листу, причем первый символ слова соответствует ребру, исходящему из корня, а последний ребру, входящему в концевую вершину. Занумеруем концевые вершины в соответствии с лексикографическим порядком слов, соответствующих концевым вершинам, и обозначим их через 0[,… т. е. вершине 0[ соответствует слово 11… 1, а вершине 0^>т- слово 22… 2. Нагрузку внутренних вершин дерева D_m-i переключателями из G определим следующим образом. Пусть 0 — произвольная внутренняя вершина дерева D_m-Пусть /?'• — концевая вершина с максимальным номером в ветви, растущей из вершины, в которое ведет ребро с номером 1, исходящее из 0. Тогда вершине 0 припишем переключатель 9/_m• Такую операцию проделаем для всех внутренних вершин дерева, и полностью определим нагрузку вершин и ребер дерева Dm-1;

Напомним, что в графе Uy листья обозначаются c*i,…, а* и им приписаны соответственно записи у_х,…, у к. Возьмем к новых точек, объявим их листьями и обозначим а,…, а*. Каждому листу <*{ (г = 1, к) припишем запись уг (тем самым каждая запись у{ будет приписана двум листьям — а* и а). Из каждого листа а (г = 2, А:) выпустим ребро, ведущее в лист ot__x, и припишем ему предикат Xy.-i ,_Pint € F_x.

Это множество из (к — 1)-го ребра назовем левосторонней концевой цепью.

Теперь для каждой вершины 0[ проделаем следующие действия. Если Si 0, то из 0[ выпустим ребро, ведущее в лист a'_t, и припишем ему предикат X_y,_itp_int € F_x. Если Si < к, то из 0[ выпустим ребро, ведущее в лист a₅.+i, и припишем ему предикат *_Ув<+1tPint € F_x.

Это множество ребер, исходящих из вершин 0[ (i = 1, т — 1), назовем правой предикатной частью.

Полученный таким образом ИГ обозначим через U_m.

Покажем, что граф U_m решает одномерную задачу интервального поиска I = (Xinty V,pint).

Рассмотрим произвольную запись у* € V. По построению LumiVi) = В каждый из листьев а" и а' ведут только ребра, которым приписан предикат x_yiiPint, следовательно,.

Пусть х = (и. v) — произвольный запрос, такой что и < у" < v, то есть х € 0(у{.рш) — Покажем, что 4>сч (^х) ^v 4>с*(^х) = 1*.

Обозначим Л_а = {х = (и, и): 0 < v — и < а}.

Рассмотрим сначала случай, когда х € ^i/(_m+i);

Тогда проводимость ребра (Po.Pi) равна единице, а ребра (Ро. Р2) — нулю. Поскольку любая цепь, ведущая в лист а' проходит через ребро (Ро.р2). то <�р_а[(^х) = О;

Обозначим через G’p подграф графа ?/_т, состоящий из цепей, исходящих из вершины р.

Так как проводимость ребра (Ро.Рх) на запросе х равна 1, то мы выходим в вершину Pi. По построению граф Gp_x совпадает с Uv и, следовательно,.

ai(^x) = 1> так как Uv решает ЗИП I.

Теперь рассмотрим случай, когда х # j4i/(_m+i>.

В этом случае р_ _ш(х) — 2 и проводимость ребра (Po.Pi) будет равна 0, а ребра (Р0.Р2) равна 1, то есть мы попадем в вершину Р2, а проводимость всех цепей, проходящих через (Ро.Рх) равна 0. Из вершины Р2 растет дерево An-i, и оно обладает тем свойством, что из каждой его внутренней вершины исходит 2 переключательных ребра, и, следовательно, всегда проводимость ровно одного из ребер равна 1. Отсюда следует, что для любого запроса всегда существует единственная цепь, соединяющая Р2 с некоторой вершиной /?', проводимость которой равна 1. Таким образом, после прохождения дерева мы попадем в некоторую вершину /?', причем по построению этого дерева эта вершина, такая, что j является минимальным числом, таким что j/m > и.

Так как v — и > 1/т, то точка j/m принадлежит отрезку.

U, v].

Рассмотрим два случая.

1) 2Н < j/m.

Тогда и < у. < у_Sj < v, так как y_9j — ближайшая слева к j/m запись из библиотеки V. Отсюда следует, что проводимость ребра, ведущего из /?' в лист a'_Sj равна 1. Осталось заметить, что проводимость части левосторонней концевой цепи, ведущей из a'_3j в orj, также будет равна 1, так как 0 < yi < y_Sj < v.

Отметим также, что в этой ситуации ip_ai(x) = 0, так как в лучшем случае мы попадем в вершины правосторонней концевой цепи в точке o_4j+i, которая в этой цепи находится после ТОЧКИ c*j.

2) Vi > j/m.

Тогда и _Sj+1 < у, — < v. Отсюда следует, что проводимость ребра, ведущего из /3' в лист a^+i, равна 1, и проводимость части правосторонней концевой цепи, ведущей из a_Sj+i в c*j, также равна 1 на запросе х.

Аналогично предыдущему случаю ip_a> (х) = 0.

Тем самым мы показали, что для любой записи у*? V и любого запроса? Xi_nt такого, что xpi_ntyi в графе U_m существует проводящая на запросе х цепь, ведущая из корня в какой-либо (но ровно в один) из листьев а, и с/_{.

Что и доказывает, что граф С/_т решает задачу I.

Подсчитаем сложность графа U_m.

Рассмотрим сначала произвольный запрос х? Ai/_m.

В этом случае

Здесь первое слагаемое соответствует вычислению переключателя g-_tm в вершине /3₀. Второе слагаемое дают переключатели, входящие в единственную проводящую цепь, пролегающую через переключательную часть дерева D. Третье слагаемое соответствует вычислению одного или двух предикатов, соответствующих предикатным ребрам из предикатной части дерева D, растущим из вершины, в которую ведет проводящая цепь. Четвертое слагаемое соответствует вычислению предикатов, соответствующих ребрам, исходящим из листьев, записи которых входят в ответ (по одному на каждую запись).

Рассмотрим случай, когда х? XAi/_m.

Тогда

Здесь первое слагаемое соответствует вычислению переключателя <7_,_т. Второе слагаемое дают переключатели, входящие в единственную проводящую цепь, пролегающую через дерево D_m-1. Третье слагаемое соответствует вычислению одного или двух предикатов, приписанных ребрам, исходящим из той вершины /3', в которую ведет проводящая цепь дерева D_m-i- И, наконец, четвертое слагаемое, как и ранее, соответствует вычислению предикатов, соответствующих ребрам, исходящим из листьев, записи которых входят в ответ. Как мы показали ранее, для любой записи у, вошедшей в ответ, ровно у одного из листьев а, и а' функция фильтра будет равна 1, и, следовательно, каждой записи соответствует ровно одно ребро и соответственно ровно один вычисленный предикат.

Подсчитаем сложность графа U_m.

Поскольку граф U_m решает задачу /, то и следовательно, используемое выше равенство.

доказывается простой сменой порядка суммирования.

Установив значение параметра m =]2clog₂fc[, получим.

Теорема 16 доказана. ?

Алгоритм поиска, соответствующий графу U_m, представляет собой следующее.

Пусть нам дан некий запрос х — (и, v) е X_lnt. Поиск по этому запросу будем осуществлять следующим образом.

Сначала вычислим длину интервала х.

Если v — и < l/([log₂ к] + 1), то ответ будем искать по методу, описанному в теореме 15. Если v — и > l/([log₂A;] + 1), то мы за время og₂og₂k найдем номер j точки j/m, попадающей в интервал [и, и]. Затем, начиная с записи с номером Sj₎ просматриваем справа налево записи из V и сравниваем с левым концом запроса — точкой и. Как толька очередная запись окажется меньше и_у мы, начиная с записи с номером +1, просматриваем слева направо записи из V и сравниваем с правым концом запроса — точкой v до тех пор, пока очередная запись не станет больше v.

Таким образом, в первом случае помимо перечисления ответа мы тратим время порядка log₂ к, а во втором — log₂ log₂ к. Поскольку в подавляющем большинстве интервал х будет достаточно большим, то мы получим оценку теоремы 16.