Поиск

Введение

Задача поиска является фундаментальной в комбинаторных алгоритмах, так как она формулируется в такой общности, что включает в себя множество задач, представляющих практический интерес. При самой общей постановке "Исследовать множество $$T$$ с тем чтобы найти элемент, удовлетворяющий некоторому условию $$C$$ ", о задаче поиска едва ли можно сказать что-либо стоящее. Удивительно, однако, что достаточно незначительных ограничений на структуру множества $$T$$, чтобы задача стала интересной: возникает множество разнообразных стратегий поиска различной степени эффективности. Мы сделаем некоторые предположения о структуре множества $$T$$, позволяющие исследовать $$T$$ $${\rm O}(\log n)$$ или $${\rm O}(1)$$. Большинство алгоритмов поиска попадает в одну из трех категорий, характеризуемых временем поиска $${\rm O}(n)$$.

Поиск и другие операции над таблицами

Любой способ поиска оперирует с элементами, которые будем называть именами, взятыми из множества имен $$S$$ - оно называется пространством имен. Это пространство имен может быть конечным или бесконечным. Самыми распространенными пространствами имен являются множества целых чисел с их числовым порядком (нумерацией), и множества последовательностей символов над некоторым конечным алфавитом с их лексикографическим (то есть словарным) порядком. Каждый из алгоритмов поиска, обсуждаемых в этой лекции, основан на одном из трех следующих предположений о пространстве $$S$$.

Предположение 1. На $$S$$ определен линейный порядок, называемый естественным порядком и обозначаемый знаком <. Такой порядок имеет следующие свойства.

Предположение 2. Каждое имя в $$S$$ есть последовательность символов или цифр над конечным линейно упорядоченным алфавитом $$A = \{ a_1,a_2,\ldots,a_c \}$$. Естественным порядком на $$S$$ является лексикографический порядок, индуцированный линейным порядком на $$A$$. Мы полагаем, что исход ( $$<$$, $$=$$ или $$>$$ ) сравнения двух символов (не имен) получается за время, не зависящее от $$\left| S \right|$$ или $$n$$.

Предположение 3. Имеется функция $${h\colon S \to \{ 0,1,\ldots,m - 1}\}$$, которая равномерно отображает пространство имен $$S$$ в множество $$\{ 0,1,\ldots,m - 1\}$$, то есть все целые $$i,0 \leqslant i \leqslant m - 1$$, приблизительно с одинаковой частотой являются образами имен из $$S$$ при отображении $$h$$. Мы полагаем, что функция $$h$$ не зависела от $$\left| S \right|$$, это с теоретической точки зрения выглядит шатко, но с практической - довольно реально.

Как уже было отмечено, поиск производится не в самом пространстве $$S$$ имен, а в конечном подмножестве $$T = \{ x_1,x_2,\ldots,x_n \}$$ множества $$S$$, называемом таблицей. На большинстве таблиц, которые мы рассматриваем, определен линейный порядок, называемый табличным порядком: ему соответствует нижний индекс имени (то есть $$x_1$$ есть первое имя в таблице, $$x_2$$ - второе и тому подобное). Табличный порядок часто совпадает с естественным порядком, определенным на пространстве имен, однако такое совпадение не обязательно.

Мощность таблицы $$T$$ обычно намного меньше, чем мощность пространства имен $$S$$, даже если $$S$$ конечно.

Представление о таблице как об упорядоченном множестве имен существенно для многих целей. Но иногда бывает необходимо рассматривать таблицу как множество ячеек, каждая из которых может содержать одно имя. Например, если процесс включения нового имени рассматривать более подробно, то обнаружится, что сначала нужно расширить таблицу добавлением ячейки, для того чтобы заготовить место для новой записи: только потом туда заносится новое имя.

Мы будем предполагать, что имена появляются в таблице не больше одного раза (исключение составляет переходный период, в течение которого заносится новое имя; в таблице допускается два вхождения одного имени). В большинстве случаев вследствие такого предположения таблица с $$n$$ именами имеет ровно $$n$$ ячеек. Однако важный класс алгоритмов, основанных на вычислении адреса, опирается на предположение о том, что таблица содержит больше ячеек, чем имен. Эти алгоритмы должны четко принимать во внимание наличие пустых ячеек.

Существует ряд синонимов для объектов, именуемых здесь таблицей и именем. В обработке данных существуют файлы, элементами которых являются записи ; каждая запись есть последовательность полей, одно из которых (участвующее в поиске) называется ключом. Если сам файл проходится во время поиска, "файл" и "ключ" представляют собой то, что мы называем "таблицей" и "именем" соответственно. (Эта терминология несколько двусмысленна, поскольку понятие "ключ" можно отнести либо к самой ячейке, либо к содержимому ячейки.) Однако при поиске в большом файле часто не подразумевается просмотр самого файла; вместо этого поиск осуществляется на справочнике или указателе файла. При успешном поиске найденная в указателе отдельная запись указывает на соответствующую запись в файле. В таком типе организации файлов нашему понятию таблицы соответствует указатель или справочник.

Мы рассматриваем только четыре табличные операции: поиск, включение, исключение и распечатка. Подробное определение того, что должны делать эти операции над таблицей $$T = \{ x_1,x_2,\ldots,x_n \}$$, зависит от структуры данных, использованной для реализации таблицы.

поиск $$z$$: если $$z \in T$$, то отметить его указателем, то есть переменной $$i$$ присвоить такое значение, что $$z = x_i$$ ; в противном случае указать, что $$z \notin T$$ ;

включение $$z$$: если $$z \notin T$$, то поместить его на соответствующее место.

Включение в общем случае предполагает прежде всего поиск соответствующего места, поэтому иногда удобно разделить операцию на две фазы. Сначала используем процедуру поиска для отыскания места, куда должно быть помещено $$z$$, и затем помещаем z на это место.

включить $$z$$ на $$i$$ -е место: включить $$z$$ сразу после имени $$x_{i -1}$$. До включения $$T = \{ x_1,\ldots,x_{i - 1},\ldots,x_{i - 1} z,x_i,\ldots,x_n \}$$.

исключить $$z$$: если $$z \in T$$, то исключить его.

Как и включение, исключение иногда реализуется процедурой поиска для получения места $$z$$ и последующей процедурой:

исключить с $$i$$ -го места: исключить $$x_i$$ из $$T$$.До исключения $$T = \{ x_1,\ldots,x_{i - 1},x_i,x_{i + 1},\ldots,x_n \}$$ \\ После исключения $$T = \{ x_1,\ldots,x_{i - 1},x_{i + 1},\ldots,x_n \}$$

Таблица, в которой осуществляются включения или исключения, называется динамической ; в противном случае она носит название статической.

Последней операцией, которую мы будем рассматривать для каждой табличной структуры, является

распечатка: напечатать все имена из $$T$$ в их естественном порядке

Среди всех операций, которые можно производить над таблицами, четыре, рассматриваемые в этой лекции (поиск, включение, исключение и распечатка), и сортировка (лекции 14, 15) - наиболее важные.

Последовательный поиск

Под последовательным поиском мы подразумеваем исследование имен в том порядке, в котором они встречаются в таблице. При таком поиске в таблице в худшем случае получается просмотр всей таблицы; даже в среднем последовательный поиск имеет тенденцию к использованию числа операций, пропорционального $$n$$. Для больших таблиц его не следует относить к методам быстрого поиска, поскольку последовательный поиск асимптотически гораздо медленнее других алгоритмов, описанных в этой лекции. Несмотря на его низкие асимптотические возможности, имеется ряд причин, по которым этот метод следует обсудить вначале. Во-первых, хотя идея его проста, он позволяет нам ввести важные понятия и методы, применимые к поиску вообще. Во-вторых, последовательный поиск является единственным методом поиска, применимым к отдельным устройствам памяти и к тем таблицам, которые строятся на пространстве имен без линейного порядка. Наконец, последовательный поиск является быстрым для достаточно малых таблиц и для больших таблиц, организованных иерархическим способом: более быстрый метод используется для исследования окрестности верхушки иерархии, а последовательный поиск – для подтаблицы на нижнем уровне иерархии.

Для последовательного поиска по таблице $$T = \{ x_1,x_2,\ldots,x_n \}$$ мы предполагаем, что имеется указатель $$i$$, значение которого принадлежит отрезку $$1 \leqslant i \leqslant n$$ или, возможно, $$0 \leqslant i \leqslant n + 1$$. Над этим указателем разрешается производить только следующие операции; первоначальное присваивание ему значения 1 или $$n$$ (или, если удобнее, 0 или $$n + 1)$$, увеличение и /или уменьшение его на единицу и сравнение его с 0, 1, $$n$$ или $$n + 1$$. При таких соглашениях наиболее очевидный алгоритм поиска в таблице $$T$$ первого вхождения данного имени $$z$$ имеет вид алгоритма 13.1. Здесь, как и во всех других алгоритмах поиска, изложенных в настоящей лекции, мы полагаем, что алгоритм останавливается немедленно по отыскании $$z$$ или установлении, что $$z$$ в таблице нет.

Алгоритм 13.1. Последовательный поиск

$$for$$ $$i = 1$$ $$to$$ $$n$$ $$do$$ $$if$$ $$z = x_i$$ $$then$$ $$\{$$ найдено: $$i$$ указывает на $$z\}$$ $$\{$$ не найдено: $$z$$ не входит в $$T\}$$

Рассмотрим некоторые аспекты эффективности последовательного поиска, начиная со стандартных методов программирования. В программе, построенной в виде одного цикла, как алгоритм 13.1, любое значительное ускорение должно быть следствием улучшения кода в цикле. Для того чтобы увидеть, какие операции выполняются внутри цикла, необходимо переписать алгоритм 13.1 в форме, близкой к языку машины:

i<-1 
цикл: if z = xi then найдено
      if i = n then не найдено
	  i<-i + 1
          goto цикл

За каждую итерацию выполняется до четырех команд: два сравнения, одна операция увеличения и одна передача управления.

Для ускорения внутреннего цикла общим приемом является добавление в таблицу специальных строк, которые делают необязательной явную проверку того, достиг ли указатель границ таблицы. Это можно сделать в алгоритме 13.1. Если перед поиском мы добавим искомое имя $$z$$ в конце таблицы, то цикл всегда будет завершаться отысканием вхождения $$z$$ ; таким образом, нам не нужно в цикле каждый раз делать проверку $$i = n$$. В конце цикла проверка условия $$i > n$$, выполняемая лишь однажды, говорит о том, является ли найденное вхождение $$z$$ истинным или специальным элементом таблицы. Это демонстрируется в алгоритме 13.2.

i<-1
while z !=xi do i <-i+1
if i<=n then{найдено: i указывает на z}
       else{не найдено}

Алгоритм 13.2. Улучшенный последовательный поиск

Улучшение алгоритма 13.1 будет наиболее очевидным, если мы перепишем алгоритм 13.2 в тех же близких к языку машины обозначениях, которые использовались раньше:

i<-1
    цикл: if z = xi then goto возможно
	      i<-i+1
		  goto цикл
возможно: if i<=n then {найдено:i указывает на z}
              else{не найдено}

При каждой итерации выполняются лишь три действия вместо четырех, как это было в алгоритме 13.1. Таким образом, в большинстве вычислительных устройств цикл в алгоритме 13.2 будет выполняться гораздо быстрее, чем в алгоритме 13.1, и поскольку скорость цикла определяет скорость всей программы, такое же сравнение имеет место для двух программ.

Печально то, что фокус с добавлением $$z$$ в конец таблицы перед поиском удается, только если мы имеем прямой непосредственный доступ к концу таблицы. Это возможно, если таблица хранится в памяти с произвольным доступом, но невозможно в общем случае, когда используется связанное размещение или память с последовательным доступом.

Единственным недостатком алгоритма 13.2 является то, что при безуспешном поиске (поиске имен, которых нет в таблице) всегда просматривается вся таблица. Если такой поиск возникает часто, то имена надо хранить в естественном порядке; это позволяет завершать поиск, как только при просмотре попалось первое имя, большее или равное аргументу поиска. В этом случае в конец таблицы следует добавить фиктивное имя $$\infty$$ для того, чтобы гарантировать выполнение условия завершения ( $$\infty$$ - это новое имя, которое по предположению больше любого имени из пространства имен $$S$$ ). Таким образом получаем алгоритм 13.3.

i<-1
    while z > xi do i <- i+1
if z=xi then{найдено:i указывает на z}
          else{не найдено}

Алгоритм 13.3.Последовательный поиск по таблице, хранимой в естественном порядке

Логарифмический поиск в статических таблицах

Мы говорим о логарифмическом времени поиска, как только возникает возможность за время $$c$$, не зависящее от $$n$$, последовательно свести задачу поиска в таблице, содержащей $$n$$ имен, к задаче поиска в таблице, содержащей не более $$\alpha n$$ имен, где $$\alpha < 1$$ - константа. В этом случае время $$t(n)$$, требующееся для поиска в таблице с $$n$$ именами, удовлетворяет рекуррентному соотношению$$t(n) = c + t(\alpha n),$$ решение, которого имеет вид$$t(n) = c\log _{1/\alpha } n + b,$$ где $$b$$ определяется начальными условиями и коэффициент $$c$$ при логарифме есть время, требуемое для уменьшения размера таблицы от $$n$$ до $$\alpha n$$.

Самыми распространенными предположениями, которые дают возможность уменьшить размер таблицы от $$n$$ до $$\alpha {\text{ }}n$$ за время, не зависящее от $$n$$, являются предположения о том, что пространство имен $$S$$ линейно упорядочено и что сравнение двух имен $$x,y$$ из $$S$$ (для определения $$x < y,x = y,x > y)$$ есть элементарная операция, требующая постоянного количества времени, не зависящего от $$n$$. В результате время, необходимое для большинства логарифмических алгоритмов поиска,естественно измеряется числом сравнений (с тремя исходами) пар имен. Для некоторых алгоритмов, однако, более естественны сравнения с большим, но фиксированным числом исходов.

В этом разделе мы рассматриваем только статические таблицы, то есть таблицы, в которых включение и исключение либо не встречаются, либо так редки, что когда они появляются, строится новая таблица. Динамические структуры таблиц, допускающие логарифмическое время поиска, так же как и эффективные алгоритмы включения и исключения, обсуждаются в конце этой лекции. Для статических таблиц нужно обсудить лишь алгоритмы поиска и построения таблицы. Алгоритмы поиска достаточно просты, но некоторые из алгоритмов построения таблицы сложны. Такая ситуация возникает потому, что в случае статической таблицы разумно считать частоты обращения известными, и, может быть, стоит затратить существенные усилия на построение оптимальной таблицы – таблицы с минимальным средним временем поиска (относительно данных частот обращения). Алгоритмы построения таблиц и их анализ являются наиболее важными темами этого раздела.

Бинарный поиск

Когда ячейки таблицы последовательно распределены в памяти с произвольным доступом и имена хранятся в таблице в их естественном порядке, возможен бинарный поиск - один из наиболее широко используемых методов поиска. Идея этого метода состоит в том, чтобы искать имя $$z$$ в интервале, крайними точками которого являются два заданных указателя $$l$$ (для "низа") и $$h$$ (для "верха"). Новый указатель $$m$$ (для "средней точки") устанавливается где-то около середины интервала, и либо $$z$$ с именем в этой ячейке сводит интервал поиска к одному из интервалов $$[l,m - 1]$$ или $$[m + 1,h]$$. Если интервал становится пустым, поиск завершается безуспешно.

Для получения логарифмического времени поиска существенно устанавливать указатель $$m$$ за время, не зависящее от длины интервала; это требование делает непригодным бинарный поиск на большинстве вспомогательных запоминающих устройств. Требование, чтобы $$m$$ помещалось точно в середине интервала, несущественно, хотя выбор средней точки в качестве $$m$$ обычно дает самый эффективный алгоритм. В некоторых частных случаях полезно разбить интервал на подинтервалы длины $$\alpha (h - l + 1)$$ и $$(1 - \alpha )(h - l + 1)$$ для фиксированного значения $$\alpha$$, отличного от $$\frac{1} {2}$$. Когда таблица размещена не последовательно, а хранится в виде списка древовидной структуры, доля $$\alpha$$ должна, вероятно, меняться от интервала к интервалу.

Бинарный поиск по идее прост, но с деталями условия завершения поиска нужно обращаться осторожно. Частные случаи $$h - l = 1$$ и $$h - l = 0$$ требуют пристального внимания в любой программе бинарного поиска. В алгоритме 13.4 эти случаи обрабатываются тем же кодом, что и в общем случае, и поучительно посмотреть, как это делается, проследив за выполнением алгоритма для $$n = 2$$ и $$n = 1$$.

Корректность алгоритма 13.4 следует из утверждения, данного в комментарии в начале тела цикла. Он устанавливает, что если $$z$$ находится где-либо в таблице, то оно должно находиться в интервале $$[l,h]$$ ; иначе говоря, при нашем предположении, что имя появляется в таблице не больше одного раза, утверждается, что $$z$$ не встречается ни в интервале $$[1,l - 1]$$, ни в интервале $$[h + 1,n]$$. Это утверждение очевидно первый раз, когда мы входим в цикл при $$l = 1$$ и $$h = n$$, и непосредственно по индукции проверяется, что оно выполняется при каждом проходе через цикл. Когда мы выходим из цикла, то должно быть $$l > h$$, и поэтому утверждение принимает вид $$z \notin \{ x_1,\ldots,x_{l - 1} \}$$ и $$z \notin \{ x_{h + 1},\ldots,x_n \}$$, откуда следует, что $$z \notin \{ x_1,\ldots,x_n \}$$.

Оптимальные деревья бинарного поиска

Бинарный поиск в последовательно распределенной таблице ( алгоритм 13.4.) обеспечивает очень быстрое нахождение имен, которые являются средними точками на раннем этапе процесса деления пополам, именно имен, близких к вершине дерева $$T(1,n)$$. Таким образом, любое имя в таблице можно выбрать примерно за $$\lg n$$ сравнений.

На практике в большинстве таблиц встречаются имена, к которым обращаются гораздо чаще, чем к другим, и "привилегированные" места в таблице разумно постараться использовать для наиболее часто вызываемых имен, а не для имен, выбранных для этих мест в результате бинарного поиска. Это невозможно осуществить для последовательно распределенных таблиц, поскольку место имени определяется его положением относительно естественного порядка имен в таблице. Введем структуру данных, легко приспосабливаемую как к месту бинарного поиска, так и к возможности выделять точки, в которых таблица делится на две части.

Деревом бинарного поиска над именами $$x_1,x_2,\ldots,x_n$$ называется расширенное бинарное дерево, все внутренние узлы которого помечены различными именами из списка $$x_1,x_2,\ldots,x_n$$ таким образом, что симметричный порядок узлов совпадает с естественным порядком. Каждый из $$n + 1$$ внешних узлов соответствует промежутку в таблице. На рис. 13.1 показаны четыре различных дерева бинарного поиска на множестве имен $$\{ A,B,C,D\}$$. Деревья (а) и (b) - вырожденные, поскольку они по существу являются линейными списками, которые должны просматриваться последовательно.

Поиск имени $$z$$ в дереве бинарного поиска осуществляется путем сравнения $$z$$ с именем, стоящим в корне. Тогда

Пусть бинарное дерево имеет вид, в котором каждый узел представляет собой тройку (LEFT, NAME, RIGHT), где LEFT и RIGHTсодержат указатели левого и правого сыновей соответственно, и NAME содержит имя, хранящееся в узле. Указатели могут иметь значение $$\Lambda$$, означающее, что поддерево, на которое они указывают пусто. Если указатель корня дерева есть $$\Lambda$$, то само дерево пусто. Как и следовало ожидать, успешный поиск завершается во внутреннем узле дерева бинарного поиска и безуспешный поиск завершается во внешнем узле.

Эта процедура нахождения имени $$z$$ в таблице, организованная в виде дерева бинарного поиска $$T$$, показана в алгоритме 13.5. Отметим его сходство с алгоритмом 13.4 (бинарный поиск).

Логарифмический поиск в динамических таблицах

Здесь мы рассмотрим организацию в виде деревьев для таблиц, в которых часто встречаются включения и исключения. Что происходит с временем поиска в дереве, которое модифицировалось путем включения и исключения? Если включенные и исключенные имена выбраны случайно, то оказывается, что в среднем время поиска мало изменяется; но в худшем случае поведение плохое - деревья могут вырождаться в линейные списки, поиск в которых нужно осуществлять последовательно. Проблема вырождения дерева в линейный список, приводящая к времени поиска $${\rm O}(n)$$ вместо $${\rm O}(\log n)$$ в практических применениях выражена более резко, чем это указывается теоретическим анализом. Такой анализ обычно предполагает, что включения и исключения появляются случайным образом, но на практике часто это не так.

Случайные деревья бинарного поиска. Как ведут себя деревья бинарного поиска без ограничений в качестве динамических деревьев? Другими словами, предположим, что дерево бинарного поиска меняется при случайных включениях и исключениях.

Для включения $$z$$ мы используем незначительную модификацию алгоритма 13.5. Если $$z$$ не было найдено, мы получаем для $$z$$ новую ячейку и связываем ее с последним узлом, пройденным во время безуспешного поиска $$z$$. Соответствующее предложение нельзя однако просто добавить в конце алгоритма 13.5, поскольку при нормальном окончании цикла $$while$$ указатель $$p$$ не указывает больше на последний пройденный узел, а вместо этого имеет значение $$\Lambda$$. В связи с этим мы должны производить включение до того, как выполняется предположение $$p \leftarrow LEFT(p)$$ или $$p \leftarrow RIGHT(p)$$ ; мы можем осуществить это, сделав процедуру включения рекурсивной. Процедура $$INSERT(z,T)$$ выдает в качестве значения указатель на дерево, в которое добавлено $$z$$. Таким образом, $$T \leftarrow INSERT(z,T)$$ используется для включения $$z$$ в $$T$$.

Исключение гораздо сложнее включения, и мы изложим здесь только основную идею. Если подлежащее удалению имя $$z$$ имеет самое большее одного сына, то при исключении $$z$$ его сын (если он вообще есть) объявляется сыном отца $$z$$. Если $$z$$ имеет двух сыновей, его прямо удалить нельзя. Вместо этого мы находим в таблице либо имя $$y_1$$, которое непосредственно предшествует $$z$$, либо имя $$y_2$$, которое непосредственно следует за $$z$$ в естественном порядке. Оба имени принадлежат узлам, которые имеют не больше одного сына, и, таким образом, $$z$$ можно исключить заменой его либо именем $$y_1$$, либо $$y_2$$, и затем исключением узла, который содержал $$y_1$$ или $$y_2$$, соответственно.

Сбалансированные сильно ветвящиеся деревья

Деревья бинарного поиска естественным образом обобщаются до $$m$$ -арных деревьев поиска, в которых каждый узел имеет $$k \leqslant m$$ сыновей и содержит $$k - 1 \leqslant m - 1$$ имен. Имена в узле делят множество имен на $$k$$ подмножеств, каждое подмножество соответствует одному из $$k$$ поддеревьев узла. На рис. 13.2 показано полностью заполненное 5-арное дерево с двумя уровнями. Заметим, что мы не можем требовать, чтобы каждый узел $$m$$ -арного дерева имел ровно $$m$$ сыновей и включал равно $$m - 1$$ имен; если мы захотим включить $$Z$$ в дерево на рисунке 13.2, то должны будем создать узлы с меньше чем $$m$$ сыновьями и меньше чем $$m - 1$$ именами. Таким образом, определение $$m$$ -арного дерева утверждает только, что каждый узел имеет не более $$m$$ сыновей и содержит не более $$m - 1$$ имен. Ясно, что на $$m$$ -арных деревьях можно осуществлять поиск так же, как и на бинарных деревьях.

Как и в деревьях бинарного поиска, полезно различать внутренние узлы и листья. Внутренний узел содержит $$k \geqslant 1$$ имен, записанных в естественном порядке, и имеет $$k + 1$$ сыновей, каждый из которых может быть либо внутренним узлом, либо листом. Лист не содержит имен (разве что временно в процессе включения), и, как раньше, в листьях - завершаются безуспешные поиски. Обычно за очевидностью мы на рисунке их опускаем.

Сбалансированное сильно ветвящееся дерево порядка $$m$$ есть $$m$$ -арное дерево в котором: