Глава 6. Алгоритмы поиска

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

Как правило, записи файла имеют несколько ключей для поиска (например, ФИО, год рождения, стаж работы, и т. п.). Задача поиска может ставиться для набора значений нескольких ключевых полей — так обычно и происходит при работе с базами данных.

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

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

Принципиальными для алгоритмов поиска являются следующие факторы: упорядоченность/неупорядоченность данных; их структура (способ представления); наконец объём области поиска.

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

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

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

Если искомый ключ в таблице отсутствует или расположен в её конце необходимо сделать просмотров. Среднее число сравнений ключа равно.

Алгоритм прямого перебора:

╔

Ш1. признак— ключ найден/не найден.

Ш2. Цикл по :

если , то

запоминание ;

;

выход из цикла.

Ш3. Если обработка записи,

иначе сообщение об отсутствии таковой.

╚

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

Оптимизация циклической программы связана, прежде всего, с уменьшением количества действий в теле цикла, в данном случае — количества сравнений.

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

Последовательный поиск в упорядоченной таблице. Если

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

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

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

Алгоритм последовательного поиска состоит из следующих этапов:

╔

Ш1. Начальные присваивания: ;.

Ш2. Если , то перейти к шагуШ4.

Ш3. Увеличить ;

вернуться к шагу Ш2.

Ш4. Если , то ключ найден, в противном случае

ключ в таблице отсутствует.

╚

Переход к шагу Ш4 произойдёт, когда в первый раз встретится ключ, не меньший . Тогда либо он — искомый (), либо

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

Ускорение поиска возможно при наличии априорной информации о вероятностях различных значений ключа поиска:. Тогда сортировка ключей в порядке убывания вероятностей:

(),

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

На практике часто применяют эвристический принцип «80–20»: как правило, запросов на поиск относятся ксодержимого файла. Накопленная статистика позволит поместить этизаписей в начало файла и тем уменьшить среднее время поиска. Для получения указанной статистики можно на начальном этапе обращений к файлу связать с каждой записью счётчик числа запросов на её поиск.