FIND THE OBJECT THE INFORMATION SYSTEM BY SOLVING THE PROBLEM OF INTERVAL SEARCH

详细

The article is devoted to optimizing algorithms of interval search on different base set using information-graph models designed to reduce time-consuming when you restore a backup of information.

全文:

Введение. Обозначим временной отрезок резервных копий множеством точек на отрезке [0; 1]. Задача интервального поиска является распространенной геометрической задачей, согласно которой при подаче запроса на поиск отрезка [а,6]с[0, 1] необходимо перечислить элементы множества, входящие [a; b]. В статье рассматриваются алгоритмы, возникающие при различных базовых множествах. В одномерной задаче интервального поиска множество записей Ymi есть отрезок [0, 1], множество запросов Хы - множество всех отрезков [m>v]c[0, 1], или, другими словами, множество пар точек (u, v), таких, что 0<m<v<1, то есть хы = {* = (h,v):0<h<v<1}. Зададим на Хы вероятностное пространство (Х-Ш,сг,Р), где а - алгебра подмножеств множества Хы , состоящая из всех прямоугольников и прямоугольных равнобедренных треугольников со сторонами, параллельными осям координат, и на плоскости uOv [1]. P - вероятностная мера на а , определяемая плотностью распределения вероятностей p(u,v) для любого В ест, то есть Р(В) - |р(м,у) du dv. в Будем считать, что плотность вероятностей p(u,v) определена на всем квадрате [0, 1] х [0, 1], но p(u,v) = 0 при (w,v) 0 Хы. Отношение интервального поиска р-ш определим соотношением (m,v)ры you<y<v, где (M,v)eXint, У^УЫ. Обозначив Smt=(Xmt’Ymt’Pmt’CT’P) типом одномерного интервального поиска, исследуем задачи данного типа над различными базовыми множествами. Представление бинарного поиска с помощью графовой модели Базовое множество характеристических функций. Рассмотрим I = {X,V,p): |F|=£ над базовым множеством F1=^F1,0'j, Fi = {ХЪР.Ш : У є • Напомним, что \\,еслихрыу, %у,гЛх> = in [0, в противном случае. Отметим, что Nf имеет вид, представленный на рис. 1, а значит, Nf е а для любого предиката f є Fy. Кроме того, понятно, что F[ полно для 5Ы. Рассмотрим следующее утверждение. Если I = (X,V,p) и F = (F,0) такие, что VyeVXyJfeF, 0{y,p)\{ [J Nf)*0, f£F\{Zy,p) то T{I,F) = \V\. Доказательство данной теоремы приводится в [1]. v Рис. 1. Характеристическое множество вида 1 V Рис. 2. Характеристическое множество вида 2 Рис. 3. Характеристическое множество вида 3 «Инфокоммуникационные технологии» Том 11, № 1, 2013 Лялин В.Е., Мальцев С.А., Тарануха В.П., Шишов Д.Р. 13 Множество х = 0(у,р)\( U Nf) является f*F\{Zy,p) множеством всех запросов х, таких, что ZyP(x) - единственный предикат из F, принимающий на у значение «1». Покажем, что оно не пусто. Для этого необходимо найти хотя бы один запрос, который для произвольного y попадет в множество X. Рассмотрим запрос (у,у) . Для любого yeYint очевидно выполняется (y,y)^N , а для любо- %У>РЬА го y'eYM :у'*у выполняется (у,y)&Nr , то Ху'.ры есть запрос (у,у) принадлежит множеству X, а значит, X Ф 0. Таким образом, T(I,F) = \V\=k. Простое базовое множество. Обозначим Majb = ix = (м>V)є :и < Ъ, v > а} . Рассмотрим случай, когда базовое множество предикатов равно F2={fay.(a,b)cXM,Nu=Mab}, а базовое множество равно F2={F2,Qi^. Отметим, что Ny имеет вид, представленный на рис. 2, а значит, Nf є а для любого предиката / eF2 и для любой записи у є Ym выполняется V —f то есть К полно для SL. лУ,Ры J У,У’ 2 м \ Тогда для сложности ЗИП I = (Хы,У,ры) при ^ = |к|—>оо справедливы следующие нижняя и верхняя оценки: X Р{0(,у,ры)) < T{I,F2) < XР(0(у,Ры)) + 0{4к). ysV уєГ Доказательство данного утверждения приводится в [1]. Базовое множество логарифмического поиска. Рассмотрим базовое множество предикатов Ръ=Р2^ {7о,я: в є [0, 1]}, где 0, если и<а 1, если и> а Положим, что F3=(F3,0). Nj имеет вид, представленный на рис. 3, а значит, Nf є<г для любого /gF3. Пусть V - упорядоченная библиотека мощности k (V = ІУ^ — гУь} , причем 0<^ <...<ук <1). Тогда для сложности ЗИП 1 = {Хы,У,ры) при k ->оо справедлива следующая верхняя оценка: T(I,F3) < ^Р{0{Уі,ртХ)) + 2]log2 к[, І=1 где запись ]log2 к[ обозначает наименьшее целое число, которое больше или равно log2 к. При этом ИГ, для которого получена данная оценка, строится нижеописанным способом. Возьмем произвольное ориентированное сбалансированное бинарное дерево с корнем и k листьями высоты у которого все ребра ориентированы по направлению от корня к листьям. Обозначим правые и левые ребра бинарного дерева соответственно символами «П» и «Л». Сопоставим каждому листу слово, состоящее из символов «Л» и «П», согласно последовательности символов, приписанных ребрам, составляющим цепь из корня в рассматриваемый лист. Таким образом, исходящему из корня ребру будет соответствовать первый символ в записи, а входящему в лист - последний. Упорядочим листья согласно порядку слов, считая символ «Л» меньше символа «П». Обозначим z'-ый лист at и сопоставим ему запись yt (і = 1,к). Теперь определим нагрузку ребер дерева предикатами из F3. Для этого рассмотрим некоторую произвольную внутреннюю вершину Р . Обозначим множество записей, соответствующих листьям ветвей, растущих из вершины Р , через Vp . Обозначим запись с минимальным в Vp номером как уи а с максимальным как у.. Заметим, что в Vp записи идут друг за другом, то есть Уі^-Ур- Через Р' и Р" обозначим вершины с ребрами, исходящими из Р. Пусть у'. - запись с максимальным номером в Vp,. В случае, если /?' - не лист, сопоставим ребру, ведущему из Р в р\ предикат f0j , а если лист, то - f/.y.. Правому ребру сопоставим /0у , если Р” - не лист, и fy,y , если Р" - лист, где у* -запись с максимальным номером в Vp„. Проделав данную операцию для всех внутренних вершин, мы определим нагрузку ребер. Теперь из всех листов at (/ = 1,&-1) выпустим ребра в листья ам и припишем этим ребрам предикаты f . Полученный граф обозначим через С/1. На рис. 4 представлен пример графа U1 при k = 10. Алгоритм поиска, соответствующий графу U1 , состоит в следующем. С помощью бинарного поиска в отсортированной по возрастанию библиотеке за ]log2 к[ шагов определяется самая левая запись, расположенная правее левого конца запроса либо совпадающая с ним. Далее, от найденной записи двигаясь вправо, просматриваемые записи поочередно сравниваются с правым концом запроса. При этом если оказывается, что просмотренная запись не больше правого конца, то она включается в ответ, иначе поиск завершается, т.е. этот алгоритм решения представляет собой традиционный поиск с помощью структуры, «Инфокоммуникационные технологии» Том 11, № 1, 2013 14 Лялин В.Е., Мальцев С.А., Тарануха В.П., Шишов Д.Р. называемой прошитым двоичным деревом. Доказано [2], что описанный алгоритм оптимален по времени поиска в худшем случае и по памяти. Пусть, как и прежде, V - упорядоченная библиотека мощности k. Тогда для любого k существуют такие ЗИП I = (Хы,У,ры) и плотность распределения вероятностей pk{u,v), что для любого измеримого базового множества F3 справедлива следующая нижняя оценка сложности включающего поиска: д/Д)г £Р(РЬ„РыУ)+(3’°g‘*71)*. уєУк + 1 Рис. 4. Пример ИГ логарифмического поиска Оптимизация алгоритма бинарного поиска в информационно-графовой модели Базовое множество сверхлогарифмического поиска. Рассмотрим следующие два предиката: /-,« : a = {(u,v) єХы : 0< v-u < а} /_а: ={(и,у)е1й :(v-M>a)v(v-M<0)}, где 0 < а < 1. Характеристические множества Nf и Nj представлены на рис. 5 и рис. 6 соответственно. Пусть базовое множество предикатов равно: F4=F3^{f-,a> «є [0, 1]}и{/_а, а є [0, 1]}. Понятно, что Nf є а для любого f eF4. Положим F4=(F4,0). Пусть I = (Хы,У,ры) - ЗИП типа S{nt. Построим ПИГ U2 над базовым множеством F4 = (F4,0), разрешающий данную ЗИП. Упорядочим записи в библиотеке V = {ylt...,yk} по возрастанию (ух<...<ук). Обозначим т = [log2 А:], то есть максимальное целое число, не превосходящее log2к. Пусть S = {s1,...,sm}, где sf = , i = l,m. Для каждого s, (г = 1,т) найдем целое число /,■ - номер ближайшей к s,-записи из V, меньшей чем j а в случае отсутствия такой записи примем /. = 0 . Аналогичным образом, как и для базового множества логарифмического поиска, построим для V граф U1. Перестроим его в U2 по следующему алгоритму. Объявим корень U1 как обычную внутреннюю вершину и обозначим как Д. Проведем в Д ребро с началом Д0, которое объявим корнем нового графа. Для этого ребра определим предикат /_ _l ’m+1 из F4. Далее выпустим из корня еще одно ребро с предикатом и построим ориентированное сбалансированное" бинарное дерево с m вершинами и корнем Д, ребра которого направлены от Д2 к концевым вершинам. Как и в случае логарифми V и и Рис. 5. Характеристическое множество вида 4 Рис. 6. Характеристическое множество вида 5 «Инфокоммуникационные технологии» Том 11, № 1, 2013 Лялин В.Е., Мальцев С.А., Тарануха В.П., Шишов Д.Р. 15 ческого поиска, введем понятия левого и правого ребер, что также порождает отношение порядка концевых вершин. В связи с этим пронумеруем концевые вершины по возрастанию и обозначим их через Р[,-,Р'т. Таким образом, вершине Д' будет соответствовать слово (Л, Л, ..., Л), а вершине Р'т - (П, П, ., П). Нагрузка ребер предикатами определяется следующим образом. Возьмем произвольную внутреннюю вершину Д. Пусть р'. -концевая вершина с наибольшим номером в ветви, исходящей из вершины с входящим левым ребром из Д. Исходящему из р левому ребру сопоставим предикат /0 а правому - f0s . Полная нагрузка ребер определяется после применения данной операции всех внутренних вершин дерева. В графе U1 листья обозначены как ах,...,ак , и им приписаны записи у1,...,ук соответственно. Построим еще k листьев и припишем каждому а' запись yt. Теперь для каждого ie{2,k} из листа а\ проведем ребро в а\_х и припишем ребру предикат fyy . Далее если 1^0, то для каждого і є {1,/и} из PI выпустим ребро в а\ и припишем ему предикат fyj . При этом в случае lt <к из Д' построим еще одно ребро к листу dj и припишем ему предикат /Л(+1,Л(+1. После этого удалим все предикатные ребра, не являющиеся частью цепи из корня в каком-либо из листьев, вместе с их началами. Уі У2 Уъ У'у4,у4 УA fу$,у$ Уі Уі fУ\,У\ У2 fУг<Уг У^ Рис. 7. Пример ИГ сверхлогарифмического поиска Полученный граф обозначим через U2. На рис. 7 представлен пример ИГ U2 для библиотеки у = {Уі=^, к = Ъ5}. Дадим неформальное описание алгоритма сверхлогарифмического поиска. Пусть нам дан запрос х = (w,v) є Хы . Для начала вычислим длину интервала х. Если v-u< l/([log2£] + l) , то ответ будем искать по методу, описанному в алгоритме логарифмического поиска (левое ребро, исходящее из корня на рис. 7), в противном случае за время 0(log2 log2 к) найдем в множестве S самую левую точку , попадающую в интервал х, затем по ссылке lt перейдем к ближайшей слева к st записи библиотеки V и проверим, попадет ли она в х. Если попадет, то справа налево проверяем на попадание в х все следующие записи. Затем слева направо начиная с записи по ссылке +1 проверяем на попадание в х все оставшиеся записи. Таким образом, в первом случае помимо времени на перечисление ответа мы тратим время 0(log2 к), а во втором - O(log2 log2 к). Для данного ИГ была доказана верхняя оценка сложнос ти [3]. Пусть плотность распределения вероятностей p(u,v), определяющая вероятность P на алгебре сг, ограничена сверху некоторой константой с. Пусть I = (X^V ,ры) - произвольная ЗИП типа . Тогда справедлива следующая верхняя оценка сложности алгоритма включающего поиска над базовым множеством F4: T(I,Fa) < XР(0(у,ры)) + 2]log2 log2 \V\[ + 6 + 2с. y^V Мгновенное решение. Пусть G1 = {&-,m («»'V) = maX (l, ]М ■»?[)} , (fl, если u<a: \ g<,a(u,v)= ’ ’ а є [0, 1] k 12, если u>a; G3 =\g-Ju,v) I [2 в противном случае где Fx - базовое множество характеристических функций. «Инфокоммуникационные технологии» Том 11, № 1, 2013 16 Лялин В.Е., Мальцев С.А., Тарануха В.П., Шишов Д.Р. Справедливо следующее утверждение [4]. Пусть ЗИП I = {Хы,У,ры) - одномерная задача интервального поиска над базовым множеством Fs, причем |f|=&. Тогда если плотность распределения вероятностей p{u,v), определяющая вероятность P на алгебре сг, ограничена сверху некоторой константой с, то существует граф U0 объема Q(U)<4k-l + 6c[log2k], для которого Р{0{у,ры)) < T(I,FS) < XР{0{у,Ры1) + 5 . уєГ уеГ Построим ИГ U0, на котором достигается данная оценка сложности. Возьмем точку Д0 и сделаем ее корнем графа. Выпустим из корня 2 ребра - левое и правое. Обозначим через Д конец левого ребра, а через Д2 - конец правого. Пусть т-2с [log2 £]. Зададим для корня переключатель g_m(u,v) из <j3. Сопоставим левому и правому ребрам значения «1» и «2» соответственно. Из вершины Д выпустим дерево бинарного поиска D для библиотеки V, как описано далее. Возьмем бинарное сбалансированное дерево с к листьями высоты ]log2 к[ с ребрами, направленными от корня к листьям. Если к нечетно, то в этом дереве существует внутренняя вершина, из которой исходит одно ребро, ведущее в лист, а другое - во внутреннюю. Из ребра, ведущего из данной вершины в лист, выпустим одно ребро, его конец объявим листом, а текущую вершину - внутренней. В полученном дереве сопоставим листьям слева направо в порядке возрастания элементов из V. Объявим все внутренние вершины дерева D с ребрами, ведущими к другим внутренним вер шинам, вершинами переключения и припишем 1 левому исходящему из них ребру и 2 - правому, а самим вершинам припишем переключатель g^a(u,v), где a - максимальная запись, достижимая из вершины, в которую ведет левое ребро из данной вершины. Все входящие в листья ребра дерева D объявим предикатными и каждому такому ребру, ведущему в лист с записью a, припишем предикат Ха,Ріл є . Для дальнейшего удобства назовем множество переключательных ребер дерева D левой переключательной частью, а множество предикатных ребер - левой предикатной частью. Листья, которым соответствует запись yt, обозначим через at (г = 1,к). От каждого листа at (г = 1,£-1) выпустим ребро, ведущее в ам, и припишем ему предикат ХУм,р.м є . Множество этих ребер назовем правосторонней концевой цепью. Теперь из Д выпустим т-1 ребер и пронумеруем их числами от 1 до т-l, объявим Д точкой переключения с переключателем g.m(u,v) є Gy. Обозначим Д' - конец ребра, исходящего из Д и имеющего номер І. Введем множество номеров S -, такое, что si - номер записи из V такой, что ys_ - Уі %Уг,Ры У2 %Уъ,РыУ* %У4,Рі,і У* %У5’Рші У5 запись, ближайшая слева к точке (i = \,m-\), а если такой записи не существует, то st = 0. Возьмем к новых точек, объявим их листьями и обозначим а[ (і = 1,к). Каждому листу а\ (/ = 1,£) припишем запись Уі. Таким образом, каждая запись yt приписана двум листьям - at и а'. Из каждого листа а\ (г-2,к) выпустим ребро, ведущее в лист а\_у, и припишем ему предикат Ху,^,^ є . Это множество назовем левосторонней концевой цепью [1]. Теперь для каждой вершины Д', если st ^ 0 , то из Д выпустим ребро, ведущее в а[ и припи- Уі У 2 Уъ X Уз> Pint Рис. 8. Пример ИГ U° «Инфокоммуникационные технологии» Том 11, № 1, 2013 Лялин В.Е., Мальцев С.А., Тарануха В.П., Шишов Д.Р. 17 шем ему предикат Ху,.,р^ є-^і; если st <к, то из Д выпустим ребро, ведущее в а'(+1, и припишем ему предикат ХУі^,р.шєр\. Правой предикатной частью назовем множество ребер, исходящих из вершин Д {і = \,т-\). Граф, состоящий из корня Д,, левой переключательной части, левой предикатной части, правосторонней концевой цепи, левосторонней концевой цепи и правой предикатной части, и будет искомым ИГ U0. Заметим, что из полученного графа можно удалить все предикатные ребра, не являющиеся частью цепи из корня в один из листьев, вместе с вершинами, являющимися их началами, а также все переключательные вершины, из которых исходит одно ребро, вместе с данным ребром, заменив рассматриваемую переключательную вершину концом исходящего из него ребра. На рис. 8 представлен пример ИГ U0 для библиотеки V = {уі=2^г, А: = 1,5} и с = 0,5. Заметим, что в этом случае т = 2, а значит, переключатель g. m может принимать только значение «1». Таким образом, мы убираем из рассматриваемого графа этот переключатель вместе с исходящим из него ребром. Дадим неформальное описание алгоритма, приведенного выше. Пусть нам дано множество V = {у1,...,ук}, в котором мы должны произвести поиск. Упорядочим это множество по возрастанию. В случае если оценка сверху с функции плотности распределения вероятностей появления запросов уже определена, то m возьмем как т = 2c[log2 к\ , если же константа с неизвестна, то в качестве нее можно взять любое число, например, с = 2 . Затем для V построим множество номеров ‘S' = , описанное выше. Теперь поиск по произовльно взятому запросу производится следующим образом. Сначала определяется длина запроса x. Если х<^, то во множестве V с помощью бинарного поиска находится запись, ближайшая к точке и справа. Далее от найденной записи просматрива ются все записи из V слева направо и сравниваются с точкой v, пока очередная запись меньше v. Таким образом, производится ]log2*[ действий, не считая перечисления ответа. Если же v~u-th’ то, применяя функцию g.m, . j „ ’ получаем номер j точки щ, входящей в интервал [M>v]. Далее просматриваем и сравниваем с и все записи из V справа налево начиная с записи с номером Sj . Как только очередная запись окажется меньше и, с записи с номером Sj +1 просматриваются и сравниваются с правым концом запроса (точкой v) слева направо записи из V до тех пор, пока очередная запись не станет больше v. В данном случае, кроме перечисления ответа, мы производим 4 лишних действия (сравнение v — u с ^, вычисление переключателя g, m, движение по правосторонней и левосторонней концевой цепи). Заметим, что параметр m определяется так, что средняя сложность первого случая не больше 1 при известной оценки сверху плотности распределения вероятностей запросов и не превышает некоторой константы, если эта оценка неизвестна.