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

В данном пункте мы будем в качестве базового множества предикатов рассматривать множество F3 = F2 U {/о,а- а € [0,1]}, где F2 определяется соотношением (4.1), а черта обозначает логическое отрицание, и положим Тъ = (/*3,0).

Очевидно, что для Nf G с для любого / € F3.

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

Теорема 46. Пусть I = (X{nt, V,pint) — ЗИП типа Sint, где V = = {з/ъ ? • ? > У*}, причем 0 ^ У1 < ... < Ук < 1. Тогда

Доказательство. Возьмем произвольное ориентированное бинарное сбалансированное дерево с корнем и к концевыми вершинами высоты ]log2 fc[, у которого все ребра ориентированы от корня к концевым вершинам. Объявим концевые вершины листьями. Из каждой внутренней вершины дерева исходит 2 ребра, назовем одно из них левым (Л), а другое правым (П). Тогда каждому листу можно сопоставить слово из символов Л и П в соответствии с ребрами, встречающимися в цепи от корня к данному листу, причем первый символ слова соответствует ребру, исходящему из корня, а последний ребру, входящему в лист. Упорядочим листья в соответствии с лексикографическим порядком слов, соответствующих листьям, считая, что символ Л меньше символа П. Теперь г-ому листу (обозначим его а») сопоставим запись у» (г = 1,Аг). Определим теперь нагрузку ребер дерева предикатами из F3 следующим образом. Рассмотрим произвольную внутреннюю вершину 0. Обозначим через Vp множество записей соответствующих листьям ветви, растущей из вершины 0. Отметим, что Vp состоит из подряд идущих записей, т. е. если у* — запись с минимальным номером в Vp, а у; — с максимальным, то у/ € Vp для всех I 6 {г,.?}- Обозначим через /3' и 0" вершины, в которые ведут соответственно левое и правое ребра, исходящие из 0. Пусть yj — запись с максимальным номером в Vp>. Если 0' — не лист, то сопоставим левому ребру, исходящему из 0, предикат fotVj, а если лист, то — fyj,yj. Правому ребру сопоставим fo,yji если 0" — не лист, и /(?"),(?")> если 0" — лист. Такую операцию проделаем для всех внутренних вершин, тем самым определим нагрузку всех ребер. Теперь из листа а» выпустим ребро в лист сц+ и припишем этому ребру предикат /y<+1,yi+1 • Проделаем эту операцию для всех номеров i от 1 до к — 1. Полученный граф обозначим через U1.

Отметим одно достаточно очевидное свойство графа U1. Пусть 0 — вершина графа U не являющаяся листом. Пусть Vp = = •.,2/j}. (Здесь и далее Vp — то множество, которое

определялось ранее с помощью дерева.) Тогда

Покажем, что U1 разрешает ЗИП I. По теореме 1, для этого достаточно показать, что Для любого г € {1, Л:}.

Доказывать это будем индукцией по i.

Базис индукции, г = 1.

В лист c*i ведет единственное ребро из вершины, которую обозначим через 0'. Очевидно, Ql = (рр> &; fyi,yi. Через yj обозначим максимальную запись в библиотеке Vp>. Примем с = если j ф и с = 1, если j = к. Очевидно, с ^ у. Тогда

Т- G. (^q, = /у,,у, •

Индуктивный переход. Предположим, что для некоторого i ^ 1 функция фильтра листа Qi равна Qi = fyuyt.

Ргюсмотрим лист aj+i (г + 1 ^ к). В него ведут два ребра: из листа а* и некоторой вершины /3, не являющейся листом. Пусть yi и yj — минимальная и максимальная записи в библиотеке Vp соответственно. Пусть

Очевидно, что Ci ^ у* и С2 ^ 2Л+1- Тогда

или

Тем самым мы показали, что U1 разрешает I.

Покажем, что

Ярусом графа назовем множество вершин с одинаковой высотой (высота вершины — есть длина наименьшей цепи от корня к данной вершине), а значение высоты — номером яруса.

Пусть 0 и 02 — две вершины, не являющиеся листьями, из одного яруса. Очевидно, что V@l П Vp2 = 0, откуда NVfii П N^ = 0. Поэтому

где суммирование берется по всем вершинам одного яруса, не являющимися листьями. В графе U1 имеется ]log2 к[ ярусов, а из каждой вершины, не являющейся листом, исходит 2 ребра, следовательно, сумма сложностей ребер, исходящих из вершин, не являющихся листьями, не превышает 2]log2 к[. Из каждого листа а* (г = 1,к — 1) исходит одно ребро и его сложность равна Р(0(у», p»nt))- Следовательно,

Тем самым, теорема 46 доказана.

Алгоритм поиска, соответствующий графу U построенному в доказательстве теоремы 46, состоит в следующем. В упорядоченной по возрастанию библиотеке с помощью бинарного поиска за log2 к шагов находится самая левая запись, находящаяся не левее левого конца запроса. Затем слева направо, начиная с найденной записи, просматриваются записи и сравниваются с правым концом запроса, и если оказывается, что очередная запись не больше правого конца, то эта запись включается в ответ, а если больше, то поиск прекращается, т. е. — это традиционный алгоритм решения данной задачи поиска с помощью структуры данных, называемой прошитым двоичным деревом [86]. Там же [86, с. 93] утверждается, что описанный алгоритм оптимален как по времени поиска, так и по памяти, но имеется в ввиду время в худшем случае, а оптимальность понимается по порядку.

Теорема 47. Для любого к ? N существует такая функция плотности распределения вероятностей рк (и, v), определяющая меру вероятностного пространства над Х{пЬ, и такая библиотека V* мощности к, определяющая вместе с pk(u,v) ЗИП J* = = (Xint,Vk, Pint), что для любого измеримого базового множества Т — (F, 0), допустимого для I, справедливо неравенство

где сконстанта, в качестве которой можно взять, например,

Доказательство. Пусть нам дано число k G N. В качестве библиотеки Vk возьмем V* = {t/i,.. -, Ук}, где yi = i/(k + 1), г = = 1, к. В качестве плотности распределения рк, v) возьмем функцию Pi/(/t+i)(w, v), определяемую соотношением (4.4).

Нетрудно видеть, что Р(0(у{,рш)) = 1/(2к + 1) для любого i € е {1, Ас} и P{0(yi, рш) C0(yj,pint)) = 0 для любых i,j 6 {1 ,к), если

* Ф Э‘

Это означает, что мы находимся в условиях теоремы 7 и, значит, для любого измеримого базового множества Т = (F, 0), допустимого для Ik, справедливо неравенство

Учитывая, что

получаем утверждение теоремы.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >