AOP_Tom3 (1021738), страница 107
Текст из файла (страница 107)
Целью исследований был поиск метода преобразования аргумента в некий код, который позволил бы группировать различные варианты одной фамилии. Далее описан метод "Яоттпдех", первоначально разработанный Маргарет К. Оделл (Магйагет К. Ос1е!!) и Робертом С. Расселом (КоЪетз С. Впээе!!) (см. Г Я. Ратетйэ 1261167 (1916), 1435663 (1922)] и ншпедший широкое применение для кодирования фамилий. 1. Оставить первую букву именя и удалить все буквы а, е, Ь, Ь о, ц, тч, у в других позициях. 2.
Назначить оставшимся буквам (кроме первой) следующие числовые значения: Ь,т,р,ч — >1 ! — т4 с, я, ), !т, т1, з, х, г — > 2 тп, и — т 5 6, т — т 3 г т 6 3. Если в исходном слове до выполнения шага 1 две или более буквы с одним н тем же кодом стояли рядом, удалить их все, кроме первой. 4. Преобразовать полученный результат в формат "буква, цифра, цифра, цифра" (приписывая необходимое количество нулей справа, если в результате получилось меньше трех цифр, или отбрасывая лишние цифры, если их больше трех). Например, фамилии Ен1ег, Папээ, Н!!Ъегь, Кпн!Ь, Б!оус), Бц!гагйеи!ся и ЪЧасЬэ имеют коды Е460, С200, Н416, К530, Б300, Б222 и %200 соответственно.
Естественно, одинаковые коды могут иметь и совсем разные имена. Так, приведенные выше коды могут быть получены из следующих фамилий: Е1!егу, СЬоэЬ, Не!!Ьгопп, Кап!, Бп!Оу, Б!ээа)опэ и ЖапйЬ. С другой стороны, такие схожие имена, как Вокегэ и Кодйегэ, Яшс!юг и БК С!ап или ТсЬеЬуэ1~е!7 и СЬеЬуэЬег, имеют разные коды. Тем не менее коды Яонпбех существенно увеличивают вероятность нахождения имени по одному из вариантов написания.
(Чтобы получить более детальную информацию по этому вопросу, обратитесь к работам С. Р. Вопгпе, Р. Е. Ротс!, ХАСМ 8 (1961), 538 — 552; 1,еоп Рах!6эоп, САСМ 5 (1962), 169 — 171: Резбега! Роро!аг!ол Сепэиэеэ 1790— 1890 (%аэЬ|пйгоп, Р.Сл Ха!!опа! АгсЬ!чеэ, 1971), 90). При использовании схем типа Боппдех нет необходимости в предположении, что все ключи различны. Мы можем составить списки записей с одинаковыми кодами, рассматривая каждый список в качестве отдельно~о модуля. В больших базах данных наблюдается тенденция к более сложным выборкам.
Зачастую пользователи рассматривают различные поля записей как потенциальные ключи с возможностью поиска, если известна только часть информации, содержащейся в ключе. Например, имея большой файл с информацией об артистах, продюсер может захотеть найти незанятых актрис в возрасте от 25 до 30 лет, неплохо танцующих и говорящих с французским акцентом. Имея подобный файл с бейсбольной статистикой, спортивный обозреватель может захотеть узнать общее количество очков, заработанных командой СЬ!сабо ЖЬ!!е Яох в 1964 году в седьмых периодах ночных нгр при условии, что подающий был левшей...
Люди любят задавать сложные вопросы. Для того чтобы иметь возможность получить на них ответ, в книге имеется раздол 6.5, в котором содержится введение в методы поиска по вторичному ключу (многоатрибутный поиск). Прежде чем перейти к собственно изучению методов поиска, полезно взглянуть на историю данного вопроса. В докомпьютерную эру имелось множество книг с таблицами логарифмов, тригонометрическими и другими таблицами (те, кто помнят, что означает аббревиатура Б3-21 нли Б3-34, несомненно, помнят, что такое "таблицы Брадиса". — Прим.
перев.). Фактически многие математические вычисления были сведены к поиску. Затем эти таблицы трансформировались в перфокарты, которые использовались для решения научных задач с помощью распознающих, сортирующих и копирующих перфораторных машин. Однако с появлением компьютеров с хранимыми программами стало очевидным, что проще вычислить значение !ойх пли соэх заново, чем найти его в таблице. (Следует, однако, заметить, что на определенном этапе развития вычислительной техники для некоторых приложений, особо критичных ко времени расчетов (в основном для игр с графическим интерфейсом) оказсэлось крайне выгодным вернуться к предвычислению таблиц функций, а в процессе работы вместо вычиглений осуществлять поиск. К тому же в подобных случаях можно было испольэовать более быструю целочисленную арифметику.— )7рим.
перев.) Хотя задача сортировки привлекала большое внимание еще на заре компьютерной эры, алгоритмы поиска оставались в забвении достаточно долгое время. Малая внутренняя память и наличие только устройств последовательного доступа (наподобие лент) для хранении больших файлов делали поиск либо тривиальным, либо невозможным. Развитие и удешевление памяти с произвольным доступом уже в 50.х годах привело к пониманию того, что проблема поиска важна и интересна сама по себе. После многих лет жалоб на огриеиченность пространства программисты столкнулись с таким изобилием, которое попросту не могли переварить и эффективно использовать. Первые обзоры по проблеме поиска опубликованы А.
И. Думи (А. 1. Бщпеу), Сощрисегв й Аиеошайоп 5, 12 (11есешбег, 1956), 6-9; В. В. Петерсоном (1Ъ'. %. Ре1егвоп), 1ВМ д. ВеэеагсЬ де Веге1ортеп1 1 (1957), 130 — 146; Э. Д. Бугом (А. Б. Воо1Ь), 1п1ог1паеюп апд Соп1го! 1 (1958), 159 — 164; А. Ш. Дугласом (А. 8. Бои81ав), Сотр.
д. 2 (1959), 1 — 9. Более подробный обзор, посвященный проблемам сортировки, был сделан несколько позже Кеннетом К). Айверсоиом (Кеппегй Е. 1тегэоп), А Рго8гахпшш8 Ъвл8иа8е (Кеи Уогк: Ж1!еу, 1962), 133. 158, и Вернером Букхольцем (%егпег ВисЬЬо1в), 1ВМ 81игетэ д. 2 (1963), 86 — 111. В начале 60-х годов было разработано несколько новых процедур поиска, основанных на древовидных структурах (с ними мы встретимся немного позже).
Исследования алгоритмов поиска ведутся и в настоящее время. 6.1. ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК "Начать с нлчвлл и продолжать, пока не будет найден искомый ключ; затем остановиться.п Эта последовательная процедура представляет собой очевидный путь поиска и может служить отличной отправной точкой для рассмотрения множества алгоритмов поиска, поскольку они основаны на последовательной процедуре. Мы увидим, что за простотой последовательного поиска скрывается ряд очень интересных, несмотря на их простоту, идей. Вот более точная формулировка алгоритма. Алгоритм Б (Последоватпельнмй поиск (Беуиеп1ю1 эеогсЬ)). Дана таблица записей В,, 77в,..., Ви с ключами Км Кэ, Км соответственно. Алгоритм предназначен для поиска записи с заданным ключом К. Предполагается, что 1У > 1.
Б1. (Инициализация.] Установиты +- 1. 82. (Сравнение.] Еспи К = Ки алгоритм заканчивается успешно. ЯЗ. (Продвижение.] Увеличиты на 1. В4. ]Конец файла7] Если 1 < 1У, перейти к шагу 82. В противном случае алгоритм заканчивается неудачно. 1 Обратите внимание на то, что этот алгоритм может завершиться успешно (искомый ключ найден) и неудачно (искомый ключ отсутствует). Данное утверждение справедливо для большинства алгоритмов, рассматриваемых в этой главе.
'п1Х-программа пишется очень просто. Нвудвезае звзерввззе Уавевзае зззврввзве Рис. 1. Последовательный поиск. Программа Я (Последовательный поиск). Предположим, что К, хранится по адресу КЕУ+ 1, а оставшаяся часть записи (Л,) — по адресу 1МРО+ й Программа использует гА = К, гП в— э 1 — Х.
По адресу ЯОССЕЯЯ находится команда 1.ОА 1МРО+М,1, которая помещает необходимую информацию в гА. $ Анализ этой программы несложен. Очевидно, что время выполнения алгоритма Я зависит от двух факторов: С вЂ” количество сравнений ключей; Б = 1 при успешном окончании поиска, О -- при неудачном.
(1) Программа Я требует для работы 5С вЂ” 25+ 3 единиц времени. Если при поиске успешно найден К = К,, получим С = 1, Б = 1; таким образом, полное время составляет (51+ 1)и. С другой стороны, если поиск неудачен, мы получим С = Х, Б = О и общее время работы программы — (5Аз + 3) и. Если все ключи поступают на вход программы с одинаковой вероятностью, то среднее значение С в случае успешного поиска равно 1+ 2+ .. +% 1'т'+ 1 у При этом значение среднеквадратичного отклонения, естественно, достаточно велико и составляет около 0.289% (см. упр. 1). Данный алгоритм, несомненно, знаком всем программистам, но липзь некоторые из них знают, что этот способ — не самая лучшая реализация последовательного поиска! Небольшое изменение -- и алгоритм выполняется существенно быстрее (если записей не слишком мало). Алгоритм Ц (Бысзпрый последовательный поиск).
Перед вами тот же алгоритм, что и алгоритм Я, однако в нем имеется дополнительное предположение о наличии фиктивной записи Лкчч в конце файла. еЕ1. (Инициализация.] Установиты +- 1 и Км 1 < — К. О! ЯТАНТ 1.ОА Ой ЕИТ1 О,У 2Н СИРА Ов' ЛЕ Об 1МС1 Об 31МР 07 РА11.ОНЕ ЕЦО К 1-И КЕМ+И,1 ЯОССЕЯЯ 1 2В 1 1 С С С вЂ” Б С вЂ” Б 1 — Б Взь в вв ~ю се — 1, я2. а Выход, если К = К,. й ЗА вз ЗВМ, Выход при отсутствии в таблице.
142. (Сравнение.) Если К = Ко перейти к шагу ь)4. ь43. (Продвижение.) Увеличиты на 1 и перейти к шагу 142. ь44. (Конец файла7) Если 1 ~ Аг, алгоритм заканчивается успешно: в противном случае алгоритм заканчивается неудачно (4 = Аг+ 1). 1 Программа ье (Быстрый последовательный поиск). гА = К, г11 = г — Аг. е~. ипг Кь+г < — К.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
