Поиск на основе сравнения ключей

 

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

 

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

 

Этот вид поиска является единственно возможным для последовательных ЗУ, однако ввиду своей простоты и универсальности он часто применяется и для адресных ЗУ.

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

В случае удачного поиска возможное число сравнений лежит в пределах [1,N], где N – число записей в таблице. Для случая неудачного поиска всегда требуется N сравнений.

Пусть значения аргумента случайны, т.е. в текущем запросе с некоторой вероятностью Q аргумент не совпадает ни с одним ключом таблицы, а с вероятностью 1-Q совпадает хотя бы с одним ключом (Q – вероятность неудачного поиска). Кроме того, в случае удачного поиска существуют вероятности p_i того, что аргумент совпадает с ключом i- й записи таблицы (). Тогда среднее число сравнений в случае удачного поиска составляет

Для равновероятных запросов ,

Среднее число сравнений с учетом как удачного, так и неудачного поиска составляет

Для равновероятных запросов аргумента последняя формула принимает вид:

 

Пусть записи в файле или таблице упорядочены по возрастанию ключей, т.е. K₁<K₂<…<K_N. Во многих случаях упорядочивание файла легко производится с помощью разнообразных алгоритмов сортировки. Для удачного поиска предварительное упорядочивание файла никак не влияет на необходимое среднее число сравнений, однако в случае неудачного поиска это часто позволяет завершить поиск раньше, чем будет просмотрен весь файл. Действительно, лишь только ключ очередной записи превзойдет аргумент поиска, можно будет утверждать, что требуемая запись в таблице отсутствует. Таким образом, необходимое число сравнений в этом случае лежит в пределах [1,N].

Пусть известны вероятности q_i того, что в случае неудачного поиска аргумент принимает значения A< K₁ при i=1, K_i-1<A< K_i при i=2,3,…,N и A> K_N при i=N+1. Тогда среднее число сравнений при неудачном поиске составляет…

Для равновероятного случая

 

Среднее число сравнений при поиске в упорядоченном файле с учетом как удачного, так и неудачного поиска составляет

Для равновероятного случая эта формула принимает вид

 

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

 

Блочный поиск

 

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

Можно просматривать не каждую, а, например, сотые записи таблицы. Как только будет обнаружена запись с ключом, превышающим аргумент поиска, просматриваются (методом последовательного поиска) последние пропущенные 99 записей. Этот алгоритм называется поиском с пропусками или блочным поиском: записи группируются в блоки и сначала ищется нужный блок, а затем в нем ищется нужная запись.

Оптимальное число записей в блоке при равновероятных запросах равно квадратному корню из числа записей в файле. Среднее число записей, которые должны быть просмотрены при удачном поиске, в этом случае также равно . Примем это без доказательства.

 

Двоичный поиск

 

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

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

,

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

Рис. 2.4 поясняет алгоритм двоичного поиска на примере таблицы из 16 записей и значения аргумента . В этом методе особенно удивительно то, что уже после двух сравнений три четверти таблицы будут вне области поиска.

 

 

Рис.2.4.

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

 

Двоичный поиск удобно представить в виде двоичного дерева (см. рис.2.5). Вершинами дерева двоичного поиска являются ключи, сравниваемые с аргументом поиска. При этом корнем является ключ записи, сравниваемой на первом шаге. Поиск можно интерпретировать как прохождение дерева от корня до искомой записи. Если достигнута конечная вершина, а заданный ключ не найден, то искомая запись в файле отсутствует. Число вершин на единственном пути от корня к искомой записи равно числу сравнений, выполняемых алгоритмом двоичного поиска при попытке отыскания нужной записи.

 

Рис.2.5.

Представление двоичного поиска в виде бинарного дерева

 

 

Среднее число сравнений в случае равновероятных запросов равно

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

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

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

 

Поиск по бинарному дереву

 

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

позволяет достичь минимума среднего числа сравнений в условиях неравновероятных запросов;

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

Для реализации бинарного дерева в явном виде в каждой записи таблицы помимо поля ключа предусматривается два поля указателей U_R и U_L, в которых записываются адреса правого и левого преемников вершины дерева, соответствующей данной записи. Для свободных вершин, не имеющих преемников, в указателях помещается специальный символ «T» (тупик). Чтобы иметь возможность начать поиск, требуется адрес записи, соответствующей корню дерева: будем хранить его в специальной ячейке V. Пример явного задания бинарного дерева приведен на рис. 2.6.

Рис.2.6

Явное задание бинарного дерева поиска

 

На каждом i-м шаге алгоритма поиска по бинарному дереву производится чтение из таблицы некоторой записи с ключом K_i и указателями Uⁱ_R и Uⁱ_L. При этом первый шаг всегда начинается с корня дерева, адрес которого содержится в указателе V.

На каждом шаге ключ K_i сравнивается с аргументом поиска A и по результатам сравнения выполняются следующие действия:

а) A= K_i – запись найдена, поиск заканчивается удачно;

б) A> K_i, Uⁱ_R =T или A< K_i, Uⁱ_L =T – тупик, запись в таблице отсутствует, поиск заканчивается неудачно;

в) A> K_i, Uⁱ_R ≠T – поиск продолжается, считывается очередная запись (K_i+1, Uⁱ⁺¹_R, Uⁱ⁺¹_L) по указателю Uⁱ_R;

г) A< K_i, Uⁱ_L ≠T – поиск продолжается, считывается очередная запись (K_i+1, Uⁱ⁺¹_R, Uⁱ⁺¹_L) по указателю Uⁱ_L.

При продолжении поиска (случаи в и г) аналогичным образом выполняется (i+1)-й шаг для записи K_i+1, полученной на i-м шаге.

 

Конкретный вид бинарного дерева для заданного множества записей определяется порядком, в котором записи заносятся в таблицу. Например, оно может выродиться в цепочку (линейный список) или принять сбалансированный вид, когда свободные вершины находятся на примерно одинаковом расстоянии от корня (см. рис. 2.7).

 

Рис.2.7

Возможные варианты бинарного дерева

 

В первом случае на рис. 2.7 поиск по бинарному дереву соответствует последовательному поиску, во втором – двоичному. Следовательно, необходимое число сравнений определяется видом бинарного дерева. Например, при равновероятных запросах и удачном поиске среднее число сравнений меняется примерно от log₂N-1 (двоичный поиск) и до N/2 (последовательный поиск). Если записи добавляются в таблицу в случайном порядке с одинаковыми вероятностями (что часто встречается на практике), то получаются бинарные деревья, для которых среднее число сравнений приблизительно равно . Это несколько больше, чем для двоичного поиска, но существенно меньше (особенно при больших N), чем для последовательного поиска.

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

Недостатком поиска по бинарному дереву является дополнительный расход памяти в каждой записи на хранение указателей правого и левого преемников.

 

Чистый бинарный поиск

 

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

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

Для построения такого алгоритма предположим, что записи упорядочены по возрастанию значений p_i и разобьем каждое из множеств непроверенных записей посередине (если число записей в множестве нечетно, то для определенности будем относить серединную запись к подмножеству с меньшими значениями p_i). Пример такого разбиения приведен на рис. 2.8.

Рис.2.8. Пример чистого бинарного поиска

 

Для приведенного примера на первом шаге алгоритма выясняется, «равен ли аргумент поиска пяти или больше», т.е. производится первое сравнение. Пусть ответом на поставленный вопрос будет «нет», тогда следующим вопросом (второе сравнение) будет: «тройка или четверка?» и т.д.

Прямой подсчет среднего числа сравнений для рассмотренного примера дает: C₁₀’=4∙(1/55 + 2/55) + 3∙(3/55 + 4/55 + 5/55) + 4∙(6/55 + 7/55) + 3∙(8/55 + 9/55 + 10/55) = 3,291.

Рассмотренная задача соответствует удачному поиску. Однако, если сравнить этот алгоритм с алгоритмом двоичного поиска, то легко заметить, что его поведение в точности соответствует случаю неудачного двоичного поиска.

Сравнивая задачу чистого бинарного поиска с рассмотренной в разделе 1 задачей экономного кодирования, легко убедиться, что они идентичны. Дерево поиска соответствует при этом бинарному кодовому дереву. Следовательно, для улучшения алгоритма чистого бинарного поиска можно воспользоваться процедурами экономного кодирования (Шеннона-Фано или Хафмана). Так, применение этих процедур к рассматриваемому примеру обеспечивает среднее число сравнений, равное 3,145. При этом, ввиду оптимальности процедуры Хафмана, это число не может быть меньше.

 

Помехоустойчивый поиск

 

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

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

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

Другая идея решения этой задачи состоит в том, чтобы найти некоторое преобразование аргумента в код (маску), собирающий вместе все варианты данного ключа. За рубежом нашел широкое применение следующий метод кодирования фамилий:

а) оставить первую букву; все буквы A, E, H, I, O, U, W, Y, стоящие на других местах, - вычеркнуть;

б) оставшимся буквам (кроме первой) присвоить следующие значения:

(B, F, P, V) -> 1;

(C, G, J, K, Q, S, X, Z) -> 2;

(D, T) -> 3;

L -> 4;

(M, N) -> 5;

R -> 6;

в) если в исходном имени (перед шагом а) рядом стояли несколько букв с одинаковыми кодами, пренебречь всеми, кроме первой из этой группы;

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

Например:

Ключевое слово	Код маски
EULER	E460
GAUSS	G200
HILBERT	H416
KNUTH	K530

 

Разумеется, такая система собирает вместе не только родственные, но и достаточно различные имена. С другой стороны, некоторые родственные имена могут иметь различную кодировку. Но, вообще говоря, этот метод намного увеличивает вероятность обнаружить имя под одной из его масок.

 

B-деревья: общие сведения

 

На практике широко распространены модели данных в виде B-деревьев. Использование В-дерева обеспечивает высокое быстродействие поиска при удалении, добавлении и чтении записей без осуществления сортировки всего содержимого файла после каждого изменения. Отличительной особенностью деревьев данного вида является то, что в них допускается более двух ветвей, исходящих из одной вершины.

Каждая вершина В-дерева состоит из совокупности значений первичного ключа, указателей индекса и ассоциированных данных. Указатели индекса используются для перехода на следующий, более низкий уровень вершин в В-дереве. Ассоциированные данные фактически представляют собой совокупность указателей данных и служат для определения физического местоположения данных, ключевые значения которых хранятся в этой вершине индекса. Хотя записи данных можно было бы разместить непосредственно в вершинах индекса, для баз данных большой размерности такой способ оказался бы неэффективным. Обычно В-деревья используют только для организации индекса; записи данных располагаются в отдельной области.

Основные достоинства В-дерева:

1. Во всех случаях полезное использование памяти для хранения индексов составляет свыше 50%. Обеспечивается динамическое распределение и использование памяти. С ростом степени полезного использования памяти не происходит снижения качества обслуживания пользовательских запросов.

2. Произвольный доступ к записи реализуется посредством небольшого количества подопераций (обращений к физическим блокам) и по эффективности сопоставим с методами перемешивания.

3. В среднем достаточно эффективно реализуются операции включения и добавления записей. При этом сохраняется естественный порядок ключей с целью последовательной обработки, а также соответствующий баланс дерева для обеспечения быстрой произвольной выборки.

4. Упорядоченность по ключу обеспечивает возможность эффективной пакетной обработки.

Основной недостаток В-деревьев состоит в отсутствии для них средств выборки данных по вторичному ключу.

В-дерево степени k () обладает следующими свойствами:

1. Все пути от корневой вершины до вершин-листьев имеют одинаковую длину h, называемую также высотой В-дерева (т.е. h есть количество вершин от корня до листа включительно).

2. Для каждой вершины, за исключением корня и листьев, количество подчиненных ей вершин (вершин-преемников) должно быть не меньше k+1 и не больше 2k+1.

3. Для корневой вершины количество подчиненных ей вершин должно быть не меньше двух и не больше 2k+1.

4. В каждой вершине, за исключением корня, количество ключей должно быть не меньше k и не больше 2k. В корне допускается только один ключ. В общем случае любая неконечная (ветвящаяся) вершина с j ключами должна иметь j+1 подчиненных вершин.

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

Физическая организация ветвящейся вершины В-дерева подобна физически последовательной структуре, как показано на рис. 2.9.

p0

k1

α1

p1

k2

α2

p2

k3

α3

…

pn-1

kn

αn

pn

Рис.2.9

Структура ветвящейся вершины B-дерева с n ключами

 

При реализации каждый блок (или страница), как правило, содержит только одну вершину. Поэтому в блоке 2k-n ключевых позиций и соответствующих им указателей свободны. Ключевые значения обозначены через k_i, указатели индекса - p_i, а соответствующие указатели данных - α_i.

На рис. 2.10 приведены примеры В-деревьев степеней 1, 2 и 3. В явном виде показаны действительные ключевые значения, а указатели ветвей изображены стрелками, обозначающими направление путей доступа. Ассоциированные данные, соответствующие вершинам B-дерева, на рисунке не показаны. Все листья располагаются в В-дереве на одинаковом уровне, поскольку любое B-дерево полностью сбалансировано по высоте. Отметим также, что независимо от степени дерева его корень может иметь самое меньшее один ключ.

 

Рис.2.10

Возможные конфигурации В-дерева для файла с 12 ключами:

а) дерево степени 1 (h=3);

б) дерево степени 2 (h=2);

в) дерево степени 3 (h=2).

 

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

Алгоритм поиска для В-дерева аналогичен алгоритму поиска в бинарном дереве. Выполняется просмотр упорядоченных ключей в вершине с целью поиска хранимого ключа (индекса), равного или большего аргумента поиска. Если найден ключ, равный аргументу поиска, поиск считается завершившимся удачно и для определения местоположения записи используется значение указателя данных. Если в некоторой позиции найден ключ k_i, больший аргумента поиска, то осуществляется переход на вершину следующего уровня в соответствии со значением предыдущего указателя индекса p_i-1 и просмотр ключей в данной вершине. Если же все хранимые в вершине ключи меньше аргумента поиска, то осуществляется переход на следующий уровень в соответствии со значением самого правого указателя индекса p_n. Если аргумент поиска не найден в вершине-листе, то поиск заканчивается неудачно. Так, на рис. 2.10 поиск ключа 25 потребует: в случае а – трех обращений к блокам, в случае б – одного обращения к блоку и в случае в – двух обращений к блокам.