Поиск в словаре и нагруженные деревья
Рассмотрим один важный частный случай задач поиска.
Пускай поиск ведется по строковому ключу не слишком большой длины. Практически имеются в виду ключи, являющиеся словами некоторого естественного или искусственного языка, поэтому рассматриваемая задача называется задачей поиска в словаре. Один из важных примеров применения такого поиска – распознавание команд, введенных пользователем с клавиатуры в диалоге с операционной системой или с прикладной программой.
Применим для хранения словаря совершенно иную структуру данных, чем использовались в предыдущих разделах. Весь словарь будет представлен деревом, вершины которого (кроме корневой) помечены буквами. Используется также специальный символ «конец слова», который мы будем обозначать знаком #.
Подобное представление принято называть нагруженным деревом1.
На рис. 5.1показано представление небольшого словаря из 9 слов: «бак», «бок», «бор», «борода», «борт», «к», «кора», «корова», «корт».
Рис. 5.1. Нагруженное дерево
Выполнение поиска по такому дереву понятно без особых пояснений. Отметим только, что вместо привычных сравнений «меньше/больше» здесь используются сравнения «равно/не равно» для очередной буквы ключа. Вставка и удаление слов также делаются без труда. Следует, однако, выбрать подходящую структуру данных для хранения небинарного дерева. Типовой способ преобразования дерева к бинарному виду предполагает, что для каждой вершины один из указателей направлен к «правому брату» вершины, а другой – к ее «старшему сыну». Результат преобразования показан на рис. 5.2.
Рис. 5.2. Бинарное представление нагруженного дерева
Довольно трудно провести корректное сравнение поиска по нагруженному дереву с традиционными алгоритмами бинарного поиска по массиву или по дереву. Если время бинарного поиска зависит от числа записей в таблице, то время поиска по нагруженному дереву определяется длиной ключа. С точки зрения расхода памяти нагруженные деревья весьма избыточны (на каждую хранимую букву приходится по два указателя), но, с другой стороны, одинаковые начальные части разных слов хранятся лишь один раз.
Удовлетворимся поэтому экспериментальными оценками, которые показывают, что нагруженные деревья все же заметно уступают традиционным структурам данных по памяти, но по скорости поиска превосходят ранее описанные методы и работают наравне с описанными ниже алгоритмами хеширования или даже быстрее.
Вопросы и упражнения
Дан массив дат A. Для упрощения принято, что номер года и номер дня лежат в пределах от 01 до 10. Выполнить поразрядную сортировку массива. Показать результаты каждого прохода. A = (06.12.03; 09.03.07; 01.01.01; 01.05.01; 10.10.10; 02.05.10; 06.01.03; 07.04.05; 07.11.05; 09.12.06; 09.12.02; 05.12.03).
Постройте нагруженное дерево для следующего словаря: «в», «век», «вена», «венок», «вентиль», «вентилятор», «у», «уха», «ухо», «юг». Преобразуйте дерево к бинарному виду.
Хеширование
Основные понятия хеширования
В предыдущих разделах были рассмотрены весьма эффективные алгоритмы сортировки и поиска, причем в подразд. 5.1 показано, что при определенных условиях время сортировки может быть сделано линейным. Казалось бы, пора успокоиться, трудно надеяться на возможность еще большего повышения эффективности. В отношении сортировки это, пожалуй, так и есть, однако оказывается, что использованы еще не все возможности ускорения поиска.
Вспомним, что до сих пор мы считали наилучшим возможным алгоритмом поиска процедуру бинарного поиска, выполняющуюся за время порядка O(log(n)). Можно ли добиться лучшего результата? Ответ на этот вопрос следующий. Если речь идет об алгоритме поиска, пригодном для произвольных ключей, т.е. не использующем никаких свойств ключей, кроме возможности их сравнения, то бинарный поиск оптимален. Однако возможны и другие подходы, позволяющиепри определенных условияхидля определенных типов ключейдобиться значительного ускорения поиска.
Основная идея заключается в том, чтобы вместо выполнения поиска как такового попытаться по известному значению ключа сразу вычислить индекс в массиве, по которому должна размещаться запись с данным ключом.
Рассмотрим эту мысль более подробно.
Пусть в некоторой прикладной задаче поиска используются ключи, принадлежащие множеству допустимых ключей X. В качестве такого множества в конкретной задаче может выступать, например, множество всех двухбайтовых (или четырехбайтовых) целых чисел или множество всех строк длиной не более 20 символов, или множество всех дат в пределахXXиXXIвеков, в зависимости от типа и диапазона данных, используемых в качества ключа.
Для хранения записей таблицы, среди которых будет производиться поиск, отведем массив из Nэлементов (будем использоватьNбольшое для размера таблицы в отличие отnмалого – числа фактически имеющихся записей). ПустьI– множество значений индексов этого массива. В зависимости от используемого языка и других соображений,Iможет представлять собой интервал [1 … N] или [0 … N–1], или другой интервал изNчисел.
Изначально массив записей пуст, он будет заполняться по мере добавления записей в таблицу.
Теперь самое главное: определим на множестве ключей Xнекоторую функциюh, принимающую значения из множестваI. Другими словами, придумаем такую функцию, которая по значению ключаxвычисляет позицию в массивеi = h(x), в которой должна находиться запись с ключомx(если такая запись вообще имеется в таблице).
Если такая функция построена, то задача поиска (со вставкой) сводится к вычислению i = h(x)и проверке, присутствует ли в позицииiзапись с ключомxили же данная позиция массива пуста и в нее можно вставить новую запись.
Как определить, что позиция пуста? В некоторых случаях можно инициализировать поля ключа всех записей каким-то «невозможным» значением, которое не может встретиться как реальный ключ. Более универсальное решение – добавить в каждую запись булевское поле «свободно/занято».
При описанном подходе получается, что время поиска вообще не зависит от числа записей, уже имеющихся в таблице. Это время сводится к времени вычисления функции h(x).
Подобный подход к организации поиска называется хешированием, функцияh–функцией хешированияилихеш-функцией, илифункцией расстановки, а массив, в котором размещаются записи, –хеш-таблицей.
Однако все не так просто, как может показаться на первый взгляд. Для эффективного использования хеширования следует решить несколько проблем.
Главная проблема заключается в следующем. Может ли случиться так, что при попытке занести новую запись в хеш-таблицу будет обнаружено, что данная позиция уже занята другой записью? Другими словами, может ли функция хеширования h(x)принимать одно и то же значение для разныхx?
Ответ на этот вопрос неутешительный: да, такая ситуация (ее называют коллизией хеширования) вполне возможна, и более того: в большинстве случаев нельзя построить такую хеш-функцию, которая полностью исключала бы коллизии. Причина этого очень проста. Как правило, множество допустимых ключейXзначительно больше, чем множество индексов хеш-таблицыI. А раз так, то хотя бы на некоторые значения индексаiдолжны отображаться несколько разных значений ключаx.
Действительно, если в качестве ключа используются, например, четырехбайтовые целые числа, то мощность множества Xравна 2324109. Трудно представить программу, в которой использовался бы массив подобного размера. Еще мрачнее обстоит дело со строковыми ключами. Если в качестве ключей используются фамилии людей, то для хранения ключей потребуется строковое поле длиной не менее 20 символов (и то, поднатужившись, можно найти фамилию длиннее). В большинстве используемых кодировок каждый символ занимает 1 байт, т.е. может принимать 28различных значений. Двадцатибайтовое поле, соответственно, может принимать 2160значений, что даже не хочется переводить в степень 10, настолько это много.
Конечно, из огромного множества допустимых ключей в действительности понадобится только небольшая часть: несколько сотен или тысяч чисел или фамилий, которые реально встретятся в обрабатываемых данных. Но это никак не облегчает проблему, ибо, как правило, заранее неизвестно, какие именно значения ключа понадобятся.
Из проблемы коллизий вытекают две конкретные задачи, которые должны быть решены для успешной реализации хеширования.
Первая задача – подбор удачной хеш-функции. Хотя ни одна самая хорошая хеш-функция не может совсем исключить коллизии, плохая хеш-функция может значительно увеличить их число.
Вторая задача – обработка ситуации, когда коллизия все-таки случилась. Эту задачу обычно называют разрешением коллизий.
Ни одна из двух поставленных задач не может быть однозначно решена раз и навсегда, для всех случаев жизни. Выбор наиболее удачного решения зависит от типа и длины ключа, от размера выделенной хеш-таблицы, от предполагаемого максимального количества записей и еще от ряда факторов. Таким образом, выбор конкретной реализации хеширования должен делаться по-новому для каждого разрабатываемого приложения. При этом можно и нужно руководствоваться общими рекомендациями, наиболее важные из которых приведены ниже.