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

Константный в среднем алгоритм поиска.

Пусть No = = N U {0} — множество целых неотрицательных чисел.

Пусть

— функция, определенная на множестве No-

Докажем следующее вспомогательное утверждение.

Лемма 12. Пусть Ь(1) — функция, определенная выше, пусть к, т 6Е N, пусть

Доказательство. Если доопределить функцию L(l) на положительную полуось числовой прямой, например, следующим образом:

то полученная функция будет непрерывной и вогнутой. И, вообще говоря, вогнутость этой функции объясняет результат леммы.

Более подробное доказательство будем вести от противного.

и среди чисел 1 (г = 1,т) существует 2 числа, разность которых не меньше двух.

Без ограничения общности можем считать, что 1[ — 1'2^ 2.

Пусть

Так как функция L(x) вогнутая, то по свойству вогнутых функций

Если в неравенстве (2.9) неравенство строгое, то получили проти-

т

воречие, так как ^ L (ZJ) — не максимально; если же нет, то обозна- »=1_

чим I" = 1 для i = 3, га и перейдем к рассмотрению суммы

Если среди чисел I” (г = 1 , га) нет пары чисел, разность которых превышает 1, то получим противоречие с неравенством (2.8), если же есть, то опять выполним операцию, описанную выше, и избавимся от такой пары, и так будем делать до тех пор, пока либо не получим строгое неравенство в неравенстве (2.9), либо не придем к разбиению

Zjn.. •, 1т такому, что ^Г, Li(ln^) = ri(fc,m), и все они отличаются

*=i

не более чем на 1, и тем самым получим противоречие с неравенством (2.8), что доказывает лемму 12.

Пусть на X задано вероятностное пространство (Л-, <7, Р).

Пусть д}п(х) — переключатель такой, что

где Ху..., Xm — разбиение множества X (т. е. X = Х U • • • U Хт и Х{ П Xj = 0, если г ф j) такое, что

где с — постоянная, не зависящая от га.

Так как

то отсюда сразу следует, что с ^ 1.

Пусть

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

Теорема 13. Пусть I = (X,V,pid) — задача поиска идентичных объектов, т. е. задача типа Sid, где V = k, Тбазовое множество, определяемое соотношениями (2.1)-(2.4), (2.10)—(2.13), т — натуральное число, сконстанта, определяемая соотношением (2.11), L(l)функция, определяемая соотношением (2.7). Тогда

В частности,

и T(I,T) ~ 1 при к -> оо. Кроме того, для ИГ U ? U(I,T), на котором достигается верхняя оценка, T(U) ^ 2 + ]log2 k[-

Доказательство. Построим ИГ U^, имеющий вид дерева, следующим образом.

Возьмем вершину ft) и объявим ее корнем графа UВыпустим из 0о т ребер, припишем им числа от 1 до т, объявим 0о точкой переключения и припишем ей переключатель дп{х).

Пусть Vi = Xi П V, li = | Vl|, i = 1 ,m.

Конец ребра с номером i обозначим ft.

Для всех таких г, что Vi Ф 0, выпустим из вершины ft первое дерево бинарного поиска, описанное в разделе 2.2.1, т. е. дерево ?>1(Vri).

Полученный ИГ с V = к листьями обозначим С/^. Это граф над базовым множеством Т.

Покажем, что разрешает задачу / = (X, V,pid).

Возьмем произвольную запись у ? V. Пусть у ? Vi (i ? {1, m}), т. е. лист а, которому приписана запись у, принадлежит дереву Dl(Vi). Так как ^(у) = г, запрос у пройдет по г-му ребру, исходящему из корня, в корень дерева Dl(Vi). Так как Dl(Vi) разрешает задачу поиска идентичных объектов для библиотеки Vi, то только запрос у пройдет в лист а.

Таким образом, мы показали, что <ра(х) = /=,у(х). Учитывая произвольность выбора у и теорему 1, получим, что ИГ U^ разрешает задачу I = (X,V,pid).

Подсчитаем объем графа U^.

Подсчитаем сложность ИГ UРассмотрим произвольный запрос х € X. Пусть хXi (i = 1, га).

где Li(l) — функция, определяемая соотношением (2.7).

По определению и учитывая лемму 12,

Возьмем m = к[. При этом Так как с ^ 1, то т ^ к. Если т = к, то к/тп = 1 и Если m > к, то к/тп = 0 и Следовательно,

Если взять т = ]к ? 7(&)[, где 7(к) -* оо при к —> с» и 7(fc) > 1 при любом к, то

С другой стороны, T(I,T) ^ 1, так как из корня должно исходить хотя бы одно ребро, поскольку к > 0.

И наконец, оценим В-сложность ИГ С/™, воспользовавшись соотношение (2.14),

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

Следствие 6. Если Т — базовое множество, определяемое соотношениями (2.1)“(2.4), (2.10) —(2.13), к — натуральное число, то

и при к —> оо

Приведем два примера задачи поиска идентичных объектов. Пример 1. Пусть 1 = (X,X,pid) — тип поиска идентичных объектов, где X — [0,1], причем задано вероятностное пространство (X, <7, Р) над X такое, что Р задается функцией плотностью вероятности р{х).

Пусть

Тогда переключатель ^(х) = тах(1,]а; • т[) удовлетворяет соотношению (2.10).

Если р(х) ^ с = const, то P(Xj) ^ с/m, и мы находимся в условиях теоремы 13.

Приведем неформальное описание алгоритма поиска, описанного в доказательстве теоремы 13, применительно к задаче I = (X, V, pid) типа Sidu где V = к.

Разобьем отрезок [0,1] на т равных частей в соответствии с соотношениями (2.15).

Каждой части сопоставим подмножество множества V, состоящее из точек, принадлежащих этой части.

Теперь для произвольной точки-запроса х поиск точки из V, идентичной запросу, будем вести следующим образом.

Определим ту часть отрезка, которой принадлежит запрос х. Ее номер равен шах(1,]х • т[).

Далее во множестве, сопоставленном найденной части, осуществим обычный бинарный поиск.

Согласно лемме 12 наибольшее среднее время поиска будет в том случае, когда точки из множества V равномерно распределены по всем m частям отрезка.

Если в качестве т взять m = fc, то случай, когда в каждую часть попадет по одной точке из V, будет иметь наибольшую сложность. А поскольку найти или не найти объект во множестве мощности 1 можно за 1 шаг, то в среднем за 2 шага (на первом мы определили номер нужной части) мы можем решить задачу поиска идентичных объектов.

Отметим, что в случае неудачного поиска алгоритм выводит к ближайшим соседям ненайденной точки.

Если внимательно присмотреться к описанному алгоритму, то можно заметить, что по своей структуре он напоминает хеширование по методу цепочек, в котором в качестве хеш-функции взято умножение, а цепочки-списки организованы в виде бинарного дерева.

Пример 2. Пусть Sid2 = {X,X,pid) — тип поиска идентичных объектов, где X = {1,..., N}.

Пусть (X, сг, Р) — вероятностное пространство над Л", где а — множество всех подмножеств, а вероятностная мера Р определяет равномерную вероятность на множестве запросов X, т. е. для любого хX имеем Р(ж) = 1/ЛГ.

Пусть задано т € N.

Пусть г = Nт[N/т].

Пусть Х,..., Хщ ~ такое разбиение множества, что и мы опять находимся в условиях теоремы 13 при с = 2.

Упражнения

2.2. Пусть I = (X,V,pc) — задача о близости, где X = {1,2,...,А}, V С Ху Рс — отношение поиска, задаваемое соотношением на X х V и определяемое соотношением (1.11). По аналогии с поиском идентичных объектов постройте ИГ, разрешающий задачу о близости I и имеющий константную сложность.

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