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

Случай базового множества характеристических функций.

Пусть Отметим, что Nf € сг для любого предиката / 6 F. Кроме того, понятно, что Т полно для типа 5jnt, так как для произвольной библиотеки V = {у 1,... , г/*} дерево, изображенное на рис. 1.5 и соответствующее переборному алгоритму, разрешает ЗИП I = (Xintl У,р,*я*).

Теорема 43. Для любой ЗИП I типа Sint T(I,Fj) = к.

Доказательство. Нетрудно убедиться, что для любого аYint точка (а, а) 6 NXa p_nt и для любого а' G Yint, такого, что а! ф а выполняется (а,а) ф NXa, т.е. мы находимся в условиях теоремы 5,

откуда следует, что Т(/,Т) = к.

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

Случай простого базового множества.

Обозначим

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

где Nfa ь = Ма>ь, а базовое множество равно Тч = (/*2,0).

Отметим, что Nf 6 <т для любого предиката f € F2, и для любой записи у G Yint Xy,pint = /у,у> т-е- ?2 полно для типа Sint. Справедлива следующая теорема.

Теорема 44. Если функция плотности распределения вероятностей p(u,v), определяющая меру Р вероятностного пространства над множеством запросов Xintf ограничена, то для произвольной ЗИП I = {XinUVt pint) типа Sint

где k = V, С (к) = 0(у/к) при к —> оо.

Доказательство. Нижняя оценка следует из теоремы 4. Докажем верхнюю оценку. Пусть р(щ v) < с = const. Пусть т =

= и ti = i/m (i = 0, т) — точки на отрезке [0,1].

Построим для ЗИП I следующее дерево, которое обозначим через Dm. Возьмем вершину и объявим ее корнем. Выпустим из корня га ребер и г-ому ребру = 1, га) припишем предикат Рассмотрим

теперь произвольную запись у ? V. Пусть у ? 6 [

t = l). Тогда из вершины, в которую ведет t-oe ребро, выпустим ребро с предикатом /УэУ, конец этого ребра объявим листом и припишем этому листу запись у. Эту операцию проделаем со всеми к записями из V. Очевидно, что полученное дерево разрешает ЗИП I.

Пусть (/3,а) — ребро, ведущее в лист, которому соответствует запись у. Его сложность равна

Следовательно, сумма сложностей ребер второго яруса (а их к штук) не больше чем

Учитывая, что сложность каждого ребра первого яруса равна 1, получаем

Остается заметить, что к • с/га + га = 0(у/к) при к оо. Тем самым теорема доказана.

Прежде чем перейти к формулировке следующей теоремы докажем некоторые вспомогательные утверждения.

п 771 j

Лемма 47. Пусть /а,а = V fj> г^е fj — А /а0,ь<,, тогда суще-

J=1 »=1

ствует такое j ? {1,п}, что fj = /а,а.

Доказательство. Обозначим min bij = 6,-, max at, = a*. Лег-

n

ко видеть, что Nfj = Ma.^ • Следовательно, N/a а = Ма,а = |J Maj,br

i=i

Очевидно, что bj ^ а и aj ^ а для любого j ? {1,п}, откуда следует, что bj ^ CLj. Легко видеть, что если 6 < а, то МЛ)ь не содержит точек вида (и, и). Но М0)0 содержит точку (а, а), следовательно, существует j ? {1,п} такое, что = а7- = а, т. е. fj = /а>а, что и требовалось доказать.

Лемма 48. Пусть I = {Xint, V, pint) произвольная ЗИП типа Sint, U — произвольный ПИГ над базовым множеством Т, разрешающий ЗИП I. Тогда существует ОИГ U', разрешающий ЗИП I, такой, что в любой его лист а ведет единственное ребро (0, а), причем грр ^ 2, tpa = 0 и T(U') ^ T(U).

Доказательство. Рассмотрим произвольную запись у € V. Так как U разрешает I и 0(у,рш) Ф 0, то Ьц(у) ф 0 и

Иными словами, если считать, что С = {Си... п) — множество цепей, ведущих из корня графа U в листья из Ьц(у), а проводимость

_ 171 j п mi

цепи Cj (j = 1,п) равна fj = Д /ао,ь„. то /v,y = V А /а,,,ь,г

Согласно лемме 47 существует j ? {1,п} такое, что /7 = /у>у, т. е. проводимость цепи Cj равна /У)У.

Пусть V = {г/1,.. • ,Ук}- Мы показали, что для каждой записи у{ (t = 1, к) можно подобрать цепь, ведущую из корня в лист с записью у, проводимость которой равна Xyuptnf Среди всех таких цепей (если их несколько) выберем минимальную по длине и обозначим ее С. Обозначим через Uo ПИГ, получающийся из U выбрасыванием всех ребер, не принадлежащих ни одной из цепей С (г = 1, к). По построению, Uo разрешает ЗИП I и его сложность не превышает сложности U.

Покажем, что каждая цепь С[ (г = 1,к) содержит ровно два полюса: корень и лист, в который она ведет (обозначим его через а*). Отметим, что (а*) = j/j.

Предположим, что это не так, т. е. существует некоторая цепь С, такая, что она проходит через некоторый лист 0 ф 04. Рассмотрим сначала случай, когда 0 ? Lu(yi). Так как проводимость цепи С- равна fyitVi, то и проводимость подцепи цепи С от корня до вершины 0 будет равна /yiiJ/., а это противоречит минимальности длины С[.

Пусть теперь 0 ? Lu(yi), где I ф i. Проводимость подцепи цепи С[ от корня до вершины 0 (обозначим ее /') покрывает проводимость цепи С (скажем, что предикат / покрывает предикат если Nf Э Ng) и, значит, /'(у*,у») = 1, но так как XybPint(&,2/*) = 0, то это противоречит тому, что граф U разрешает ЗИП I.

Таким образом, каждая из цепей С (г = 1 ,к) содержит ровно 2 полюса, а так как в Uq ребер, не принадлежащих цепям С[ (г =

= 1 ,к), нет, то это означает, что в Uq ровно к листьев, и каждый из них имеет полустепень исхода 0 и в каждый из них ведет единственное ребро. Обозначим ребро, ведущее в лист а», через (ft, а») (г = 1,к). Если грр. ^ 2, то мы просто переобозначим цепь С[ на С”. Если г1>р. = = 1, то рассмотрим цепь С[, которой принадлежит ребро (ft,<*i). Пусть 7i — ближайшая к ft вершина в цени С[, такая что гръ ^ 2. Очевидно, что такая вершина есть. Отметим также, что часть цепи С[ между вершинами 7* и а* не принадлежит никакой другой цепи. Заменим в цепи С цепь, ведущую из 7» в <**, ребром (7», а»), которому припишем предикат fyi}Vi. Полученную цепь обозначим через С"{. Очевидно, что проводимость цепи С' также будет равна fyitVi, а ее сложность не больше сложности цепи С. Такую операцию проделаем для каждого листа а» (г = 1, Д:). Полученный в результате граф, состоящий из цепей С", (г = 1 ,fc), обозначим через U'. Этот граф удовлетворяет требованиям леммы, и, значит, лемма доказана.

Введем следующее обозначение Му = U ^у,у? ГДС У ~~ некоторая библиотека. yev

Лемма 49. Если V — произвольная библиотека, то существует такое разбиение V па непсресскающиеся части V,..., V*

(т.е. U V; = V и Vi П Vj =0, если i ф , причем, возможно, ' *=1 '

V = 0, что сложность ЗИП I = (Xint, V, рш) типа Sint

Доказательство. Возьмем произвольный ПИГ U ? Согласно лемме 48, существует ОИГ Uq, такой что в каждый лист а € С(Цо) ведет единственное ребро (ft а), грр ^ 2 и Т([/) ^ T{Uq). Разобьем множество этих ребер графа Uq на группы так, что в одну группу объединяются ребра, начала которых совпадают. Если среди этих групп есть группа ребер, исходящих из корня, то назовем эту группу первой группой ребер, а если такой группы нет, то будем считать, что первая группа пустая. Остальные группы занумеруем, начиная с 2. Пусть t — число групп. Через обозначим множество записей, соответствующих концам ребер из г-ой группы (г = 1,<) (возможно, V =0). Поскольку сложность ребра, исходящего из корня равна 1, то сумма сложностей ребер из первой группы равна |Vi|.

Теперь рассмотрим случай, когда г € {2,?}. Обозначим через ft начало ребер из г-ой группы. Очевидно, N^0i Э Myi (i = 2,?). Отсюда следует, что каждое ребро из г-ой группы имеет сложность не меньшую, чем Р(Му.). Добавим к г-ой группе (г = 2,t) множество ребер, входящих в ft. Ясно, что сумма сложностей этих ребер также не меньше чем Р(Му.).

Так как все /?* (г = 2, t) различны и для любого листа полустепень его исхода равна 0, то разные группы ребер не пересекаются. Следовательно,

Произвольность выбора графа U доказывает утверждение леммы.

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

где k = V, ?(к) = Q(y/k) при к —? оо.

Доказательство. Нам надо доказать, что существует такая ЗИП

I = (Хш, V, рш), что

где (к) = 0{Vk) и <2) = 0{fk) при кУ оо.

Верхняя оценка следует из теоремы 44.

Докажем нижнюю оценку.

Пусть Аа — множество точек плоскости, определяемое следующим соотношением:

где 0 < а < 1/2. Площадь фигуры Аа равна

Рассмотрим следующую функцию плотности распределения вероятностей:

Возьмем а такое, чтобы а > 1/3.

Меру Р вероятностного пространства над Xint определим с помощью функции Ра(щ v).

Заметим, что для любого у G [а, 1 - а]

Рассмотрим библиотеку V = {уь...,у*}> где у* = а + (г - 1)?, t = (l-2a)/k, i = ljk.

Заметим, что для любого i € {1,к} а ^ у ^ 1 — аи t < а при к ^ 1. Пусть V,...,УГ — разбиение библиотеки V, удовлетворяющее условию леммы 49, т. е.

где I(XintlViPint).

Заметим что Р(Му4) будет минимально, если Vi состоит из подряд идущих записей из V, и тогда Му{ имеет вид, изображенный на рис. 4.1, и

Рис. 4.1. Тени подряд идущих записей где 0 < cj < • Такая константа существует, поскольку t < а и t

где 0 < с < 257) • Такая константа существует, поскольку t < а и t

убывает с ростом к. Из (4.5) также видно, что |Vi| = д(к) при к —У оо, поскольку в противном случае нижняя оценка превысит верхнюю, чего быть не может.

Теперь воспользуемся следующим известным фактом. Пусть mi,... ,mi — целые неотрицательные числа. Тогда минимум функции i I

52 т? при условии, что 52т* = п> достигается, когда первые

*=i i=i

п — [п/1]I слагаемых равны [n/l] -f- 1, а остальные слагаемые равны п/1, т.е.

откуда

Подставляя это в 4.5 и учитывая, что t = (1 — 2а)/к, находим, что где

Заметим, что при к —> оо, где ci и С2 — константы.

Остается заметить, что Сг(&) минимально по порядку при г ж А: и тогда ^ у/к. Последнее доказывает утверждение теоремы,

поскольку

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Популярные страницы