Хотя цель поиска - нахождение информации, хранящейся в ассоциированной с К записи, алгоритмы в этой главе предназначены для поиска К. После нахождения К поиск связанной с ним информации становится тривиальной задачей, зависящей от способа хранения информации. Например, найдя К в TABLE -I- г, мы обнаружим связанные с ним данные в TABLE -I- г -I- 1, в DATA -- г или в еще каком-то месте, которое определяется способом хранения информации. Поэтому мы считаем задачу выполненной в тот момент, когда находим К (или убеждаемся в его отсутствии).

Поиск обычно является наиболее "времяемкой" частью многих программ, и замена плохого метода поиска хорошим может значительно увеличить скорость работы программы. К тому же часто представляется возможным так изменить данные или используемые структуры, что поиска удается избежать совсем. Одним из таких способов может быть связь данных (например, при использовании списка с двойными связями поиск предшествующего и последующего элементов данного становится совершенно излишним). В случае, когда мы можем выбирать ключи, имеется еще один способ избежать поиска: выбрать в качестве ключа натуральные числа {1,2,..., Л}; при этом запись с ключом К просто размещается в TABLE -I-К. Обе эти технологии были использованы, чтобы избежать поиска в алгоритме топологической сортировки , обсуждавшемся в разделе 2.2.3. Однако поиск необходим, если объекты для топологической сортировки представлены не числовыми, а символьными значениями. Естественно, в этом случае очень важно подобрать эффективный алгоритм поиска.

Методы поиска могут быть классифицированы несколькими способами. Мы можем разделить их на внутренний и внешний поиск так же, как в главе 5 мы разделяли алгоритмы сортировки на внутренние и внешние. Возможно деление на статические и динамические методы поиска, где термин "статический" означает, что содержимое таблицы остается неизменным и главная задача - уменьшить время поиска без учета времени, необходимого для настройки таблицы. Термин "динамический" означает, что таблица часто изменяется путем вставки (а возможно, и удаления) элементов. Третья возможная схема классификации методов поиска - их разделение в.зависимости от того, на чем они основаны: на сравнении ключей или на некоторых числовых свойствах ключей (по аналогии с разделением на сортировку методом сравнения и сортировку методом распределения). И наконец, можно разделить методы сортировки на методы с использованием ключей действительных и преобразованных (трансформированных).

Организация этой главы представляет собой комбинацию двух последних способов классификации. Раздел 6.1 посвящен методам последовательного поиска, т. е. методам поиска "в лоб" В разделе 6.2 рассмотрены усовершенствования, основанные на сравнении ключей с использованием алфавитного или числового порядка для управления решениями. Раздел 6.3 посвящен числовому поиску, а в разделе 6.4 обсуждается важный класс методов с общим названием "хеширование", основанных на арифметическом преобразовании действительных ключей. В каждом из этих разделов рассматривается как внутренний, так и внешний поиск (как для статического, так и для динамического случаев). В каждом разделе вы найдете описание достоинств и недостатков рассматриваемых алгоритмов.

Поиск и сортировка зачастую тесно связаны между собой. Например, рассмотрим следующую задачу. Даны два числовых множества, А = {01,02,... ,ат} и В = {bi,b2,.. -, Ьп}. Необходимо определить, является ли множество А подмножеством множества В:А С В. Очевидными представляются такие варианты решения.

1. Сравнивать каждое щ со всеми bj последовательно до нахождения совпадения.

2. Сначала рассортировать множества А и В, а затем сделать только один последовательный проход с проверкой по обоим файлам.

3. Внести все элементы bj в таблицу и выполнить поиск каждого значения Oj.

Каждое из этих решений имеет свои достоинства для различных значений тип. Решение 1 требует порядка cimn единиц времени, где ci - некоторая константа. Решение 2 требует порядка c2(mlgm -I- nlgn) единиц времени, где сг - некоторая (большая) константа. При выборе подходящего метода хеширования решение 3 займет около с-тп + сп единиц времени для некоторых (еще больших) констант сз и с4. Отсюда следует, что решение 1 подходит для очень небольших значений т и п; при увеличении множеств лучшим становится решение 2. Затем наилучшим станет решение 3 - до тех пор, пока п не превысит размер внутренней памяти. После этого наилучшим обычно вновь становится решение 2, пока п не вырастет до совсем уж громадных значений... Итак, мы видим, что существуют ситуации, в которых сортировка стужит хорошей заменой поиску, а поиск - отличной заменой сортировке.

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

Подобные задачи привлекли внимание в связи с вводом в действие систем резервирования билетов на самолеты и других подобных им систем, в которых велика вероятность возникновения ошибки из-за плохой слышимости или некаллиграфического почерка. Целью исследований был поиск метода преобразования аргумента в некий код, который позволил бы группировать различные варианты одной фамилии. Далее описан метод "Soundex", первоначально разработанный Маргарет К. Оделл (Margaret К. Odell) и Робертом С. Расселом (Robert С. Russell) [см. (7. S. Patents 1261167 (1918), 1435663 (1922)] и нашедший широкое применение для кодирования фамилий.

1. Оставить первую букву имени и удалить все буквы а, е, h, i, о, и, w, у в других позициях.

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

b, f, р, V 1 1-4

c, g, j, к, q, S, X, Z2 ш, n5

d, t 3 г 6

3. Если в исходном слове до выполнения шага 1 две или более буквы с одним и тем же кодом стояли рядом, удалить их все, кроме первой.

4. Преобразовать полученный результат в формат "буква, цифра, цифра, цифра" (приписывая необходимое количество нулей справа, если в результате получилось меньше трех цифр, или отбрасывая лишние цифры, если их больше трех).

Например, фамилии Euler, Gauss, Hilbert, Knuth, Lloyd, Lukasiewicz и Wachs имеют коды E460, G200, H416, K530, L300, L222 и W200 соответственно. Естественно, одинаковые коды могут иметь и совсем разные имена. Так, приведенные выше коды могут быть получены из следующих фамилий: ЕПегу, Ghosh, Heilbronn, Kant, Liddy, Lissajous и Waugh. С другой стороны, такие схожие имена, как Rogers и Rodgers, Sinclair и St. Clair или TchebyshefF и Chebyshev, имеют разные коды. Тем не менее коды Soundex существенно увеличивают вероятность нахождения имени по одному из вариантов написания. (Чтобы получить более детальную информацию по этому вопросу, обратитесь к работам С. Р. Bourne, D. F. Ford, JACM 8 (1961), 538-552; Leon Davidson, САСМ 5 (1962), 169-171; Federal Population Censuses 1790-1890 (Washington, D.C.: National Archives, 1971), 90).

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

В больших базах данных наблюдается тенденция к бо.лее сложным выборкам. Зачастую пользователи рассматривают различные поля записей как потенциальные ключи с возможностью поиска, если известна только часть информации, содержащейся в ключе. Например, имея большой файл с информацией об артистах, продюсер может захотеть найти незанятых актрис в возрасте от 25 до 30 лет, неплохо танцующих и говорящих с французским акцентом. Имея подобный файл с бейсбольной статистикой, спортивный обозреватель может захотеть узнать общее количество очков, заработанных командой Chicago White Sox в 1964 году в седьмых периодах ночных игр при условии, что подающий был левшой... Люди любят задавать сложные вопросы. Для того чтобы иметь возможность получить на них ответ, в книге имеется раздел 6.5, в котором содержится введение в методы поиска по вторичному ключу (многоатрибутный поиск).

Прежде чем перейти к собственно изучению методов поиска, полезно взглянуть на историю данного вопроса. В докомпьютерную эру имелось множество книг с таблицами логарифмов, тригонометрическими и другими таблицами (те, кто помнят, что означает аббревиатура БЗ-21 или БЗ-34, несомненно, помнят, что такое "таблицы Брадиса". - Прим. перев.). Фактически многие математические вычисления были сведены к поиску. Затем эти таблицы трансформировались в перфокарты, которые использовались для решения научных задач с помощью распознающих, сортирующих и копирующих перфораторных машин. Однако с появлением компьютеров с хранимыми программами стало очевидным, что проще вычислить значение log а; или cos а: заново, чем найти его в таблице. (Следует, однако, заметить, что на определенном этапе развития вычислительной техники для некоторых приложений, особо критичных ко времени расчетов (в основном для игр с графическим интерфейсом) оказалось крайне выгодным вернуться к предвычислению таблиц функций, а в процессе работы вместо вычислений осуществлять поиск. К тому же в подобных