Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 34
Текст из файла (страница 34)
М. ВЬеппап, САСМ 4 (19б1), 172 — 173, 175). Алгоритм Т ("Лучевой поиск" (2)те эеагсЬ)). Дана таблица записей в форме М- ариого луча. Алгоритм осуществляет поиск по заданному аргументу К. Узлы луча представляют собой векторы, индексы которых изменяются от О до М вЂ” 1; каждый компонент такого вектора представляет собой ключ или ссылку (возможио, пустую). Т1.
(Ииициализация.) Установить ссьиочиую переменную Р таким образом, чтобы оиа указывала иа корень луча. Т2. (Ветвление.) Установить А равиым следующему символу входного аргумента ключа К слева направо. (Если аргумент полностью просканироваи, установить е Наличие у страницы книги трех свободных сторон позволило однажды переводчику этого рлэделв оснэстить свой словэрь метками поиски до третьей буквы слова включнтельео. Прим, иерее. ьэ В орнгинвле используется термин аче (произяосится клк екглийское слово "сгу"), предложенный Э, Фредкиным (Е. Егебрбп) (САСМ а (!900), 490-000). Этот термин предстивляет собой часть слова "гегггетэ!т В русском переводе будет использоваться честь слова "получение" (информации). И хотя при этом теряется определенная игра слов, основвинвя ив схожести гчов иге и нее, приобретается некоторый смысл, зэложениый в слове лрч: быстрый четко определеикый по направлению движения поиск.
— Прим. персе. )г равным "пустому" символу или символу "конец слова". Символ должен быть представлен в виде числа в диапазоне О < к < М). Обозначим через Х й-й элемент в КИПЕ(Р). Если Х представляет собой ссылку, перейти к шагу ТЗ, если Х вЂ” ключ, перейти к шагу Т4. ТЗ. (Продвижение.) Если Х ф Л, установить Р е- Х и вернуться к шагу Т2; в противном случае алгоритм завершается неудачей. Т4, (Сравнение,) Если Х = К, алгоритм завершается успешно; в противном случае алгоритм завершается неудачей. $ Таблица 1 ЛУЧ ДЛЯ М НАИБОЛЕЕ УПОТРЕБИТЕЛЬНОГО АИГЛИЙСКОГО СЛОНА (ц (2) (з) (4) (б) (е) (т) (е) (и) ((и) (Гт) (12) а в с и Е Р 6 Н х 8 3 Х К М о Р 0 и Ф п Я т и Ч и х Т х Заметим, что при неудачном поиске будет найден элемент, более всего совпадающий с пскомым, что может оказаться полезным в некоторых приложениях.
Для сравнения скорости работы данного алгоритма со скоростями других алгоритмов из этой главы напишем коротенькую И1Х-программу, в которой предполагается, что символы представляют собой байты, а максимальная длина ключа— б байт. Программа Т ( "Лучевой поиск" ( 2Не веагсй ) ). В этой программе предполагается, что все ключи занимают одно слово машины И1Х; в случае, если в ключе содержится менее 5 символов, он дополняется пробелами справа. Поскольку мы используем коды символов И1Х, каждый байт аргумента поиска содержит число, меньшее 30. Ссылки представлены в виде отрицательных чисел в поле 0:2 узла слова. гП хз Р, гХ = непросканированная часть К.
~о 1 Р е- указатель на корень луча. С Т2, Ветвление. С Получение следующего символа, т. е. А. С О е- Р+Й. С Р = ь1МК(О). С Т3, Поо01МЯкеяне, Переход к Т2, если РфЛ, 1 пгх ху~,А Ее~ о! 1 1 Успешное завершение ирн гА = К.. Выход прн отсутствии в луче. 8 01 ЯТАИТ 00 ОУ 2Н 04 00 Об 07 00 00 10 11 РА110МЕ ЫХ К ЕМТ1 ИОСТ ЯЬАХ 1 ЯТА э+1(2:2) ЕМТ2 0,1 Ы1М 0,2(0:2) 01Р 28 ЬОА 0,2 СИРА К 0Е ЯОССЕЯЯ ЕЦО Время работы программы составляет 8С+ 8 единиц„где С вЂ” количество проверяемых символов. Поскольку С < 5, время поиска никогда не превышает 48 единиц времени. Если сравнить эффективность этой программы (при поиске на луче. нз табл.
1) и программы 6.2.2Т (с использованием оптимального бинарного дерева поиска (см, рис. 13)), можно сделать следующие выводы. 1, Луч занимает гораздо больше памяти; мы использовали 360 слов для представления 31 ключа, в то время как бинарное дерево поиска использует только 62 слова памяти (однако в упр.
4 будет показано, что можно ухитриться втиснуть луч из табл. 1 в 49 снов). 2. Успешный поиск требует 26 единиц времени в обеих программах. Неудачный поиск выполняется быстрее в случае луча и медленнее — в бинарном дереве поиска. Для наших конкретных данных неудачный поиск будет осуществляться гораздо чаще, чем успешный, а потому для них "лучевой поиск" предпочтительнее с точки зрения скорости работы. 3. В случае применения луча для указателя КЖ1С (см. рнс. 15) метод теряет свою привлекательность в силу природы используемых данных.
Например, для различения слов СОИРОТАТ10М и СОИРОТАТ10МЯ луч потребует 12 итераций. Поэтому было бы более разумно строить луч таким образом, чтобы сканирование слов происходило справа налево, Абстрактная концепция луча для представления семейства строк была пред; ложена Акселем Тью (Ахе1 ТЬие) в статье о строках, которые не содержат смежных повторяющихся подстрок [оАт)ггег и68!Рие аг" 'ек)епзйаЬэ-БеЫиЬег 1 СЬг1эбап1а,, МагЬешаг1зЬ-НагагтдепэйаЬей8 К1ааэе (1912), Ко.
1; перепечатана в книге Тью Бе1есГед МаГЬета11са1 Рарегэ 10э1о: Пп1еегэ)герое)а8ет, 1977), 413-477]. "Лучевая память" для компьютерного поиска была впервые рекомендована Рене делаБрианде (Непб бе1аВНап6Ыэ) 1Ргос. Рреэгегп,Уо1пс Соглригег Сопб 15 (1959), 295-298). Он указал, что можно сохранить память (за счет времени работы) при использовании связанного списка для каждого узла-вектора, поскольку большинство элементов вектора обычно пусто. На самом деле эта идея приводит к замещению луча нз табл, 1 лесом, показанным на рис. 31. Поиск в таком лесу осуществляется Рнс.
31, Луч нз табл. 1, преобразованный в "лес". ° ~ И ~ в с Ф ы '6 '6 с Я с с с с с сс с с путем нахождении корин, соответствующего первому символу„затем дочернего узла этого корня, соответствующего второму символу, и т. д. В своей статье де ла Брнанде в действительности ие прерывал ветвление дерева, как показано в табл. 1 или на рис, 31; вместо этого он продолжал представление каждого ключа, символ эа символом, до достижения конца слова.
Таким образом, де ла Брианде использовал бы вместо дерева Н, показанного на рис. 31. Для такого представления требуется больше памяти, но при этом существенно упрощаетсн работа с ключами переменной длины. При использовании двух полей ссылок на каждый символ легко осуществляются динамическая вставка и удаление.
Если использовать обычный путь представлении деревьев как бинарных деревьев, (1) становится бинарным деревом (В представлении полного леса на рис. 31 следовало бы добавить указатель, ведущий вправо от Н к соседнему корню Х.) Поиск в этом бинарном дереве выполняется посредством сравнении аргумента с символом в дереве и следования й1.1МК до поиска соответствии; после этого мы находим Ы.1ИК и точно так же работаем с очередным символом аргумента.
ы ~ и н н н н м о о о н н и н м м и и $ м м н а м и и й й й о ~ Ф н о м И и я н н Я Поиск в таком бинарном дереве в большей или меньшей степени сводится к поиску путем сравнений, но ветвление осуществляется по признаку "равно-неравно", а не "меньше-больше". Элементарная теория нз раздела 6.2.1 гласит, что необходимо выполнить в среднем хотя бы 1к Х сравнений для того, чтобы различить 1У ключей. Среднее количество сравнений, сделанных при поиске в дереве, которое подобно изображенному на рис.
31, должно быть не меньше количества сравнений, выполняемых ири бинарном поиске с использованием описанных в разделе 6.2 технологий. С другой стороны, луч из табл. 1 способен выполнять ЛХ-путевое ветвление за один раз; мы увидим, что среднее время поиска для больших Л включает всего около 1ойм)У = 16Л/16М итераций при случайных входных данных. Мы также увидим, что "чистая" схема луча (подобная алгоритму Т) требует, в целом, примерно Х/1пМ узлов дпя различения М случайных ключей: следовательно, общее количество необходимой памяти пропорционально АХИ/1п ЛХ. Из этих рассуждений становится ясно, что идея луча хороша только для несколькпх первых уровней дерева. Повысить производительность можно за счет комбинирования двух стратегий: луча для нескольких первых символов н переключения на другую стратегию — для оставшихся.
Например, Э. Г. Сассенгат (мл.) (Е. Н. БиззепйпСЬ, Зг.) (САСМ 6 (1963), 272-279) предложил использовать посимвольную схему до достижения части дерева, в которой возможны, скажем, не более шести ключей, а затем проходить последовательно по этому списку. Далее мы увидим, что такая смешанная стратегия позволяет уменьшить количество узлов луча примерно в шесть раз без существенного изменения времени работы. Т. Н. Турба (Т.
К. ТпгЬа) (САСМ 26 (1982), 522 †5) указал, что иногда при поиске с ключами переменной длины удобно иметь по одному поисковому дереву или лучу для каждой длины ключа. Бинарный цифровой поиск. Допустим, что М = 2, и аргумент поиска сканируется по одному биту. Для этого случая разработаны два специальных интересных метода. первый метод, именуемый цифровым поиском по дереву (йй11п( 1гее зеагсь), разработан Э. Г.
Коффманом (Е. С. Со((шап) и Дж. Ивом (Л. Ете) (САСМ 13 (1970), 427-432, 436]. Его суть заключается в хранении полных ключей в узлах так же, как в алгоритмах поиска по дереву из раздела 6.2.2, но с использованием битов аргумента вместо результатов сравнения для выбора левой илн правой ветви. На рис. 32 изображено бинарное дерево, построенное по этому методу путем вставки 31 наиболее употребительного английского слова в порядке уменьшения частот появления слов. Чтобы получить данные для иллюстрации метода, слова были представлены в кодах символов Н11 и конвертированы в двоичные числа с пятью битами на байт.
Так, слово ННХСН представляется битовой последовательностью 11010 01000 01001 00011 01000. Для поиска слова ЫН1СН на рис. 32 сравним его со словом ТНЕ в корне дерева, Так как они не совпадают и первый бит слова НН1СН равен 1, мы двигаемся вправо и сравниваем его со словом ОР. Слова опять не совпадают, и следующий бит слона ННТСН равен 1, позтому мы снова перемещаемся вправо и сравниваем наше слово ЧН1СН со словом Н1ТН, и т. д. Алфавитный порядок ключей в цифровом поиске по дереву больше не соответствует симметричному порндку узлов. Интересно обратить внимание на разин~у между деревьями, представленными на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
