Полная версия

Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ. ТЕОРИЯ ХРАНЕНИЯ И ПОИСКА ИНФОРМАЦИИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Базовое множество сверхлогарифмического поиска.

В данном пункте мы рассмотрим случай, когда базовое множество предикатов равно

где Аа множество, определяемое соотношением (4.3), а черта обозначает логическое отрицание, и положим = (4*4,0).

Понятно, что для Nf € <т для любого / 6 F*.

Справедлива следующая теорема [28, 156].

Теорема 48. Пусть функция плотности распределения вероятностей р(и, и), определяющая меру Р вероятностного пространства над множеством запросов Xint, такая, что p(u,v) ^ с = const. Пусть I = (Xint,V,Pint)произвольная ЗИП типа Sint. Тогда

Доказательство. Упорядочим записи в библиотеке V = = {yi, • • • ,Ук} так, что У1 ^ 2/2 ^ • • • Ук• _

Пусть S = {si,..., sm}, где Si = i/(m + 1), i = l,m. Здесь и далее m = [log2 fc].

Для каждого s* (г = l,m) найдем целое число li, которое является номером ближайшей к числу Sj записи из V, меньшей чем S;, причем если такой записи не существует, то примем 1{ = 0.

Построим для V граф U* так, как это было сделано в доказательстве теоремы 46. Объявим корень графа U1 обычной внутренней вершиной и обозначим через 0. Проведем в 0 ребро, начало его обозначим и объявим корнем полученного графа. Припишем этому ребру предикат /-д/(ш+1) из ^4- Выпустим из корня еще одно ребро, конец которого обозначим через 02» и припишем этому ребру предикат /_ti/(m+i)- Построим ориентированное сбалансированное бинарное дерево с m концевыми вершинами с корнем в вершине 02, все ребра которого ориентированы от ft к концевым вершинам. Из каждой внутренней вершины дерева исходит 2 ребра, одно из которых назовем левым (Л), а другое правым (П). Это так же, как и в доказательстве теоремы 46, порождает отношение порядка концевых вершин, и в соответствии с ним занумеруем концевые вершины этого дерева в порядке возрастания и обозначим их через 0[у...у0'т, т.е. вершине 0[ соответствует слово (Л,Л,. ..,Л), а вершине 0'т слово (П,П,. ..,П). Нагрузку ребер дерева предикатами из F3 определим следующим образом. Пусть 0 — произвольная внутренняя вершина дерева. Пусть /3'- — концевая вершина с максимальным номером в ветви, растущей из вершины, в которое ведет левое ребро, исходящее из 0. Тогда левому ребру, исходящему из 0, припишем предикат foiSj, а правому fo,Sj- Такую операцию проделаем для всех внутренних вершин дерева, и полностью определим нагрузку его ребер. Напомним, что в графе U1 листья обозначаются qj, ..., а* и им приписаны соответственно записи у,... ,ук- Построим еще к вершин, обозначим их а,..., и также объявим их листьями и припишем каждому листу а (г = 1, к) запись уу. Теперь для каждого i G {2, к} из листа построим ребро в лист и припишем ребру (а(, с*^) предикат fvi-uvt-i • Затем для каждого г € {1, т}, если Ц ф 0, то из вершины 0 выпустим ребро в лист а{ и припишем ему предикат fyii tVli, и если при этом li < к, то из вершины 0 выпустим еще одно ребро в лист оц{+1 и припишем ему предикат fyi +ьУ, +1.

Полученный граф обозначим через U2.

Покажем, что ПИГ U2 разрешает ЗИП I = (Xint, V,pint).

Рассмотрим произвольную запись у, 6 V. По построению ясно, что Lu2(yi) = {a*,aj}. В каждый из листьев а* и а[ ведут только ребра, которым приписан предикат /у., следовательно,

Пусть х = (и, v) — произвольный запрос, такой что и ^ у* ^ V, т. е. х G О (у i, рш). Покажем, что ?>ai(x) V ?>а;(х) = 1.

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

Тогда проводимость ребра (А» А) равна единице, а ребра (А> А) нулю. Поскольку любая цепь, ведущая в лист aj проходит через ребро (А), А), то рА;(*) = 0.

Обозначим через Gjj подграф графа U2 состоящий из цепей, исходящих из вершины р.

Так как проводимость ребра (А* А) на запросе х равна 1, то мы выходим в вершину А* По построению граф G'px совпадает с U1 и, следовательно, у>а<(х) = 1, так как U1 разрешает ЗИП I.

Теперь рассмотрим случай, когда х ? j4i/(m+i)-

Тогда проводимость ребра (А» Pi) равна нулю, а ребра (А» А) единице, т. е. мы попадем в вершину А» а проводимость всех цепей, проходящих через (А, А) равна 0. Из вершины А сначала растет дерево, и оно обладает тем свойством, что из каждой его внутренней вершины исходит 2 ребра, и им приписаны противоположные предикаты, т. е. всегда проводимость только одного из ребер равна 1. Отсюда следует, что для любого запроса всегда существует единственная цепь, соединяющая А с некоторой вершиной /3' , проводимость которой равна 1. Таким образом, после прохождения дерева мы попадем в некоторую вершину P'j, причем по построению этого дерева эта вершина, такая, что 8j является минимальным числом из 5, таким что $j ^ и.

Предположим сначала, что yi < Sj. Тогда г ^ Zj, и поскольку справедливо и ^ у* ^ yi. < Sj ^ v, то fyi.,yij (х) = 1, т.е. проводимость ребра (/?'•,а.) равна 1. Из вершины а. в вершину ведет цепочка ребер, которым приписаны функции /Уг>Уг, где г € {i, lj}, и поскольку и ^ Уг ^ Уг < У/, < V, ТО /Уг,Уг(х) = 1 ДЛЯ Любого Г € {t,Z,}, T. в. проводимость цепи из а. в а[ равна 1 на запросе х. Таким образом, мы показали, что существует цепь, ведущая из корня в лист проводимость которой равна 1 на запросе х, т. е. у>а/(х) = 1. Отметим, что если даже fyij+uyt +l (х) = 1, т. е. из вершины (р'- мы попадем еще

и в вершину or/j+i, то все равно у?в<(х) = 0, так как из листа оц.+1 в лист a нет цепи.

Осталось рассмотреть случай, когда у* ^ Sj. Тогда i ^ lj + 1 и поскольку справедливо и ^ Sj < y/i+i ^ у* ^ v, то /у^+ьУ| .,(х) = 1 и мы попадем в лист o^.+i. Из листа Qij+i в лист а* существует цепь, и ее проводимость по аналогии с предыдущим случаем равна 1 на запросе ж, т.е. у>а<(ж) = 1. Также аналогично предыдущему случаю V3o;(s) =0.

Таким образом, мы показали, что если ж 6 0(у,-, р*п*), то выполняется (pai(x) V W.(x) = 1- Более того мы показали, что при х 6 € 0{Vii Pint)

Учитывая (4.6), получаем, что более того, с учетом (4.7) будем иметь, что

В силу произвольности записи у* получаем, что U2 разрешает ЗИП I.

Оценим сложность графа U2.

Обозначим через N множество всех ребер графа U2. Пусть М — множество ребер графа U2, исходящих из листьев, и Л/г = NN. Если обозначить через Т(Л7) — сумму сложностей ребер из множества Л/*, то

Оценим сначала Т(М).

Множество состоит из 2 — 1) ребер, исходящих из листьев а* (г = 1, Л — 1) и oti (j = 2,fc), следовательно, учитывая (4.9), а затем (4.8), находим, что

Обозначим через G'^x (Сд2) подграф графа (G^2), состоящий из ребер, не принадлежащих М.

Граф Gpx представляет собой дерево, построенное в доказательстве теоремы 46. Поскольку в вершину /3 - 1 проходят только записи из множества то по аналогии с тем как это делалось в теореме 46, легко показать, что сумма сложностей ребер, исходящих из вершин одного яруса дерева Gpx, не превышает

Аналогично показывается, что сумма сложностей ребер, исходящих из вершин одного яруса дерева Gq7 , не превышает

Поскольку количество ярусов в деревьях G'L и <7^ не превышает соответственно ]log2 к[ и ]log2[log2 к][ + 1, то в силу (4.12) с учетом ребер, исходящих из корня, имеем

С учетом (4.10) и (4.11) получаем утверждение теоремы 48.

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

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

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

Если v — и < 1/([log2 А:] + 1), то ответ будем искать по методу, описанному в теореме 46. Если v - и ^ l/([log2fc] + 1), то мы за время Q(og2 l°g2 к) найдем в множестве S самую левую точку s*, попадающую в интервал х (такая точка обязательно существует), затем по ссылке идем в ближайшую слева к S{ запись библиотеки V и проверяем попадет ли она в х, если попадет, то справа налево просматриваем следующие записи и проверяем на попадание в х. Затем идем по ссылке /, + 1 и, начиная с записи, в которую ведет эта ссылка, просматриваем слева направо записи с проверкой на попадание в х.

Таким образом, в первом случае помимо перечисления ответа мы тратим время 0(log2 Ц, а во втором — 0(log2 log2 к). Поскольку в подавляющем большинстве интервал х будет достаточно большим, то мы получим оценку теоремы 48.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>