Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 8
Текст из файла (страница 8)
Естественно, в этом случае очень важно подобрать эффективный алгоритм поиска. Методы поиска могут быть классифицированы несколькими способами. Мы можем разделить их на внутренний и внешний поиск так же, как в главе 5 мы разделили алгоритмы сортировки на внутренние и внешние. Возможно деление на статические и динамические методы поиска, где термин "статический' означает, что содержимое таблицы остается неизменным и главная задача — уменьшить время поиска беэ учета времени, необходимого для настройки таблицы.
Термин "динамический" означает, что таблица часто изменяется путем вставки (а возможно, и удаления) элементов. Третья возможная схема классификапяи методов поиска —. их разделение в.зависимости от того, на чем они основаны: на сравнении ключей или на некоторых числовых свойствах ключей (по аналогии с разделением на сортировку методом сравнения и сортировку методом распределения). И наконец, можно разделить методы сортировки на методы с использованием ключей действительных и преобразованных (трансформированных). Организация этой главы представляет собой комбинацию двух последних способов классификации. Раздел 6,1 посвящен методам последовательного поиска, т. е, методам поиска "в лоб".
В разделе 6.2 рассмотрены усовершенствования, основанные на сравнении ключей с использованием алфавитного или числового порядка для управления решениями. Раздел 6.3 посвящен числовому поиску, а в разделе 6.4 обсуждается важный класс методов с общим названием "хеширование", основанных на арифметическом преобразовании действительных ключей. В каждом из этих разделов рассматривается как внутренний, так и внешний поиск )как для статического, так и для динамического случаев). В каждом разделе вы найдете описание достоинств и недостатков рассматриваемых алгоритмов.
Поиск и сортировка зачастую тесно связаны между собой. Например, рассмотрим следующую задачу. Даны два числовых множества, А = (аы аз,..., а,„) н В = (Ьы Ьт,..., Ь„). Необходимо определять, янляется лн множество А подмножеством множества В:А С В.
Очевидными представляются такие варианты решения. 1. Сравнивать юокдое а, со всеми Ьз последовательно до нахождения совпадения. 2. Сначала рассортировать множества А и В, а затем сделать только один последовательный проход с проверкой по обоим файлам. 3. Внести все элементы Ь; в таблицу и выполнить поиск каждого значения а,, Каждое из этих решений имеет свои достоинства для различных значений ги и п. Решение 1 требует порядка с~гни единиц времени, где сг — некоторая константа.
Решение 2 требует порядка сз(пт 1к гп + и!я п) единиц времени, где сз — некоторая (ббльшая) константа, При выборе подходящего метода хеширования решение 3 займет около сзт + схп единиц времени для некоторых (еще ббльшнх) констант сэ и сз. Отсюда следует, что решение 1 подходит для очень небольших значений пт и и; прн увеличении множеств лучшим становится решение 2. Затем наилучшим станет решение 3 — до тех пор, пока и не превысит размер внутренней памяти. После этого наилучшим обычно вновь становится решение 2, пока и не вырастет до совсем уж громадных значений...
Итак, мы видим, что существуют ситуации, в которых сортировка служит хорошей заменой поиску, а поиск — отличной заменой сортировке. Более сложные задачи поиска зачастую сводятся к более простым (которые мы н рассматриваем). Предположим, например, что ключи представляют собой слова, которые могут быть записаны с небольшими ошибками. Наша задача— найти запись, невзирая на ошибки в ключах.
Если мы сделаем две копии файла, в одном из которых ключи расположены в обычном лексикографическом порядке„ а в другом — в обратном порядке, справа налево (как если бы их читали задом наперед), искаженный аргумент поиска будет, вероятно, совпадать до половины (нли более) своей длины с записью в одном из файлов, Методы поиска, описываемые в разделах 6.2 и 6,3, таким образом, могли бы быть приспособлены для поиска по искаженному ключу. Подобные задачи привлекли внимание в связи с вводом в действие систем резервирования билетов на самолеты и других подобных им систем, в которых велика вероятность возникновении ошибки из-за плохой слышимости или некаллиграфического почерка.
Целью исследований был поиск метода преобразования аргумента в некий код, который позволил бы группировать различные варианты одной фамилии. Далее описан метод "8оцпдех", первоначальна разработанный Маргарет К. Оделл (Магяаге1 К. Обей) и Робертом С. Расселом (Нобег1 С. НпээеП) [см. Г Я. Рагепгэ 1261167 (1918), 1435663 (1922)) и нашедший широкое применение для кодирования фамилий.
1. Оставить первую букву имени и удалить все буквы а, е, Ь, 1, о, и, ж, у в других позициях. 2. Назначить оставшимся буквам (кроме первой) следующие числовые значения: Ь, Е, р, г -э 1 1-э 4 с, к, 1, Й, с1, э, х, х -+ 2 ш, и -э 5 а,с-з г -+ 6 3. Если в исходном слове до выполнения шага 1 две или более буквы с одним и тем же кодом стояли рядом, у,калить их все, кроме первой, 4. Преобразовать полученный результат в формат "буква, инфра, цифра., цифра" (приписывая необходимое количество нулей справа, если в результате получилось меньше трех цифр, или отбрасывая лишние цифры, если нх больше трех).
Например, фамилии Еп!ег, Сапээ, Н!!Ьегг, Кпи!Ь, Ыоуб, 1лйвэ!еич!сх и %асЬэ имеют коды Е460, 6200, Н416, К530, Б300, Б222 и %200 соответственно. Естественно, одинаковые коды могут иметь и совсем разные имена. Твк, приведенные выше ходы могут быть получены из следующих фамилий; Е11егу, СЬоэЬ, Не1!Ьгопп, Кап!, !лппу, Ыээа!оцэ и %ацйЬ. С другой стороны, такие схожие имена, как Войегэ и Водйегэ, Б!пс!в1г н БП С1а!г нли ТсЬеЬуэЬе!7 и СЬеЬуэЬег, имеют разные коды.
Тем не менее коды Боцпс1ех существенно увеличивают вероятность нахождения имени по одному из вариантов написания. (Чтобы получить более детальную информацию по этому вопросу, обратитесь к работам С. Р. Воцгпе, П. Р. росса, эАСМ 8 (1961), 536-552: ! еоп Паидэоп, САСМ 5 (1962), 169-171: Рег)ега) Рори!аВоп Сепэиэеэ 1790- !890 (%аэЫпй!оп, В.Сл Хайопа! АгсЬглеэ, 1971), 90). Прн использовании схем типа Бошк1ех иет необходимости в предположении, что все ключи различны, Мы можем составить списки записей с одинаковыми кодами, рассматривая каждый список в качестве отдельного модуля. В болыпих базах данных наблюдается тенденция к более сложным выборкам.
Зачастую пользователи рассматрнвшот различные поля записей как потенциальные ключи с возможностью поиска, если известна только часть информации, содержащейся в ключе. Например, имея большой файл с информацией об артистах, продюсер может захотеть найти незанятых актрис в возрасте от 25 до 30 лет, неплохо танцуюших и говорящих с французским акцентом.
Имея подобный файл с бейсбольной статистикой, спортивный обозреватель может захотеть узнать общее количество очков. заработанных командой СЫсако %ЬВе Яох в 1964 году в седьмых периодах ночных нгр при условии, что подающий был левшой... Люди любят задавать сложные вопросы, Для того чтобы иметь возможность получить на них ответ, в книге имеется раздел 6.5, в котором содержится введение в методы поиска по вторичному ключу (многоатрибутный поиск). Прежде чем перейти к собственно изучению методов поиска, полезно взглянуть на историю данного вопроса.
В докомпьютерную эру имелось множество книг с таблицами логарифмов, тригонометрическими и другими таблицами (те, кто помнят, что означает аббревиатура БЗ-21 или Б3-34, несомненно, помнят, что такое "таблицы Брадиса"'. — Прим. перев.). Фактически многие математические вычисления были сведены к поиску. Затем эти таблицы трансформировались в перфокарты, которые использовались для решения научных задач с помощью распознающих, сортирующих и копируя>щих перфораторных машин.
Однако с появлением компьютеров с хранимыми программами стало очевидным, что п!юще вычислить значение !ойх или соэх заново, чем найти его в таблице. (Следует, однако, заметить, что на определенном этапе развития вычислительной техники,:пш некоторых приложений, особо критичных ко времени расчетов (в основном для игр с графическим интерфейсом) оказалось крайне выгодным вернуться к предвычнслению таблиц функций, а в процессе работы вместо вычислений осуществлять поиск.
К тому же в подобных случаях можно было использовать более быструю целочисленную арифметику.— Прим. перев.) Хотя задача сортировки привлекала болыпое внимание еще на заре компьютерной эры, алгоритмы поиска оставались в забвении достаточно долгое время. Малая внутреннян память и наличие только устройств последовательного доступа (наподобие лент) для хранения больших файлов делали поиск либо тривиальным, либо невозможным. Развитие и удешевление памяти с произвольным доступом уже в 50-х годах привело к пониманию того, что проблема поиска важна и интересна сама по себе. После многих лет жалоб на ограниченность пространства программисты столкнулись с таким изобилием, которое попросту не могли переварить и эффективно использовать.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
