AOP_Tom3 (1021738), страница 136
Текст из файла (страница 136)
Если сравнить эффективность этой программы (при поиске на луче из табл. 1) и программы 6.2.2Т (с использованием оптимального бинарного дерева поиска (см. рис. 13)), можно сделать следующие выводы. 1, Луч занимает гораздо больше памяти; мы использовали 360 слов для представления 31 ключа, в то время как бинарное дерево поиска использует только 62 слова памяти (однако в упр. 4 будет показано, что можно ухитриться втиснуть луч из табл.
1 в 49 слов), 2. Успешный поиск требует 26 единиц времени в обеих программах. Неудачный поиск выполняется быстрее в случае луча и медленнее — в бинарном дереве поиска. Для наших конкретных данных неудачный поиск будет осуществляться гораздо чаще, чем успешный, а потому для них "лучевой поиск" предпочтительнее с точки зрения скорости работы. 3. В случае применения луча для указателя КЖ!С (сьь рис.
15) метод теряет свою привлекательность и силу природы используемых данных. Например, для различения слов СОИРОТАТ10И и СОИРОТАТТОИБ луч потребует 12 итераций. Поэтому было бы более разумно строить луч таким образом, чтобы сканирование слов происходило справа налево. Абстрактная концепция луча для представления семейства строк была предложена Акселем Тью (Ахе! ТЬпе) в статье о строках, которые не содержат смежных повторяющихся подстрок )Ясг1йег пг)81ппе аг РЫепэ)габэ-Бе!эАабес 1 СЛНэйап1а, Ма1Ьешас!эй-ИаСпггк!епэ)гаЬе)!К К!азэе (1912), Чо. 1; перепечатана в книге Тью Яе!есгес! Ма!Леша!!он! Рарегэ (Оэ!о: 1)ц!чегэ!сеМог!аКес, 1977), 413-477].
"Лучевая память" для компьютерного поиска была впервые рекомендована Рене дела Брианде (Вене сне!аВг!апс$а!э) [Ргос. И еэгегп .7ош! Сошрпгег Сопб 15 (1959), 295 — 298). Он указал, что можно сохранить память (за счет времени работы) при использовании связанного списка для каждого узла-вектора, поскольку большинство элементов вектора обычно пусто. На самом деле эта идея приводит к замещению луча из табл. 1 лесом, показанным на рис.
31. Поиск в таком лесу осуществляется Рис. 31. Луч из табл. 1, преобразованный в "лес". Ф' Ф' Ф Ф и Ф и Ф ч и и н м и и о ы й и Р О и путем нахождения корня, соответствующего первому символу, затем дочернего узла этого корня, соответствующего второму символу, и т. д. В своей статье де ла Брианде в действительности не прерывал ветвление дерева, как показано в табл. 1 или на рис.
31; вместо этого он продолжал представление каждого ключа, символ за символом, до достижения конца слова. Таким образом, де ла Брнанде использовал бы вместо дерева Н, показанного на рис. 31. Для такого представления требуется больше памяти, но при этом существенно упрощается работа с ключами переменной длины. При использовании двух полей ссылок на каждый символ легко осуществляются динамическая вставка и удаление. Если использовать обычный путь представления деревьев как бинарных деревьев, (1) становится бинарным деревом (2) (В представлении полного леса на рис. 31 следовало бы добавить указатель, ведущий вправо от Н к соседнему корню |.) Поиск в этом бинарном дереве выполняется посредством сравнения аргумента с символом в дереве и следования Н1.1ИК до поиска соответствия; после этого мы находим |Л.|ИК и точно так же работаем с очередным символом аргумента.
х х х х х и х а о а н и н и х х х м х ф х х н а х х х х х х о х х о ь н ОЪ н э х х н с х н х а х Поиск в таком бинарном дереве в большей или меньшей степени сводится к поиску путем сравнений, но ветвление осуществляется по признаку "'равно-не равно", а не "меньше-больше". Элементарная теория из раздела 6.2.1 гласит, что необходимо выполнить в среднем хотя бы!8 Х сравнений для того, чтобы различитыЧ ключей. Среднее количество сравнений, сделанных при поиске в дереве, которое подобно изображенному на рис. 31, должно быть не меньше количества сравнений, выполняемых при бинарном поиске с использованием описанных в разделе 6.2 технологий.
С другой стороны, луч из табл. 1 способен выполнять М-путевое ветвление за один раз; мы увидим, что среднее время поиска для больших Ж включает всего около 1ойх 7э' = 18Х/18М итераций при случайных входных данных. Мы также увидим, что "чистая" схема луча (подобная алгоритму Т) требует, в целом, примерно Х/1и М узлов для различения Л' случайных ключей; следовательно, общее количество необходимой памяти пропорционально М."1/1п М. Из этих рассуждений становится ясно, что идея луча хороша только для нескольких первых уровней дерева. Повысить производительность можно за счет комбинирования двух стратегий: луча для нескольких первых символов и переключения на другую стратегию -- для оставшихся. Например, Э.
Г. Сассенгат (мл.) (Е. Н. 8вээепбпСЬ, Лг.) [САСМ 6 (1963), 272-279] предложил использовать посимвольную схему до достижения части дерева, в которой возможны, скажем, не более шести ключей, а затем проходить последовательно по этому списку.
Далее мы увидим, что такая смешанная стратегия позволяет уменыпить количество уз.юв луча примерно в шесть раз без существенного изменения времени работы. Т. Н. Турба (Т. 1э'. ТпгЬа) ]САСМ 25 (1982), 522 — 526] указал, что иногда при поиске с ключами переменной длины удобно иметь по одному поисковому дереву или лучу для каждой длины ключа. Бинарный цифровой поиск. Допустим, что М = 2, и аргумент поиска сканируется по одному биту. Для этого случая разработаны два специальных интересных метода.
Первый метод, именуемый цифровым поиском но дереву (йуйа1 1гсе эеаггй), разработан Э. Г. Коффманом (Е. С. Сойшап) и Дж. Ивом (Д. Ече) ]САСМ 13 (1970), 427-432, 436]. Его суть заключается в хранении полных ключей в узлах так же, как в алгоритмах поиска по дереву из раздела 6.2.2, но с использованием битов аргумента вместо результатов сравнения для выбора левой нли правой ветви. На рис. 32 изображено бинарное дерево, построенное по этому методу путем вставки 31 наиболее употребительного английского слова в порядке уменьшения частот появления слов.
Чтобы получить данные для иллюстрации метода, слова были представлены в кодах символов Н1Х и конвертированы в двоичные числа с пятью битами на байт. Так, слово МН1СН представляется битовой последовательностью 11010 01000 01001 00011 01000. Для поиска слова ЫН1СН на рис. 32 сравним его со словом ТНЕ в корне дерева. Так как они не совпадают и первый бит слова НН1СН равен 1, мы двигаемся вправо и сравниваем его со словом ОР. Слова опять не совпадают, и следующий бит слова НН1СН равен 1, поэтому мы снова перемещаемся вправо и сравниваем наше слово ЫН1СН со словом Ы1ТН, и т. д.
Алфавитный порядок ключей в цифровом поиске по дереву больше не соответствует симметричному порядку узлов. Интересно обратить внимание на разницу между деревьями, представленными на рис. 32 и 12 (из раздела 6.2.2), так как последнее дерево было построено тем же способом, но с использованием сравнения ключей вместо битов. Если принять во внимание данные частоты появления слов, цифровой поиск по дереву на рис. 32 потребует в среднем 3.42 сравнений при успешном завершении поиска. Это несколько лучше, чем в случае дерева, показанного на рис. 12, для которого требуется 4.04 сравнения (хотя, конечно же, время самого сравнения различно для этих двух ситуаций). Рис.
32. Дерево цифрового поиска длв 31 наиболее употребительного английского слова, вставленного в порядке уменьшения частот. Алгоритм Р (Цифровой поиск со вставкой по дереву). Дана таблица записей, представляю1пих бинарное дерево, которое описано выше. Алгоритм предназначен для поиска некоторого аргумента К. Если К отсутствует в таблице, новый узел, содержащий К, вставляется в дерево в соответствующем месте. Алгоритм предполагает, что дерево не пусто и что его узлы имеют поля НЕТ, Е11НК и НЕ1МК, такие же, как в алгоритме 6.2.2Т. В действительности, как вы можете убедиться сами, алгоритмы практически идентичны.
Р1. [Инициализация.) Установить Р е- НООТ и К' +- К. Р2. ~Сравнение.] Если К = КЕТ(Р), поиск успешно завершается. В противном случае установить 6 равным лидирующему биту К' и сдвинуть К' влево на один бит (тем самым удалив этот бит и вставив 0 справа). Если Ь = О, перейти к шагу ПЗ; в противном случае перейти к шагу П4, ВЗ. [Перемещение влево.) Если ЬПИК(Р) ф Л, установить Р < — ЬЬТИК(Р) и перейти к шагу 1)2. В противном случае перейти к шагу ))5. Т)4. [Перемещение вправо.) Если М.1ИК(Р) ЭА Л, установить Р < — В1.1ИК(Р) и перейти к шагу П2. Т)5.
[Вставка в дерево.) Установить Ц з= АЧАПч КЕ? (Ц) +- К, Ы.1ИК(Ц) < — й1.1ИК(Ц) < — Л. Если Ь = О, присвоить ЫЬ1ИК(Р) +- Ц; в противном случае присвоить НЬТИК(Р) +- Ц 1 Хотя алгоритм поиска по дереву 6.2.2Т по сути своей бинарный, не сложно увидеть, что он может быть распространен на М-арный цифровой поиск для любого М > 2 (см. упр, 13). Дональд Р. Моррисон (1)опа!д В. Могпэоп) [дАСМ 15 (1968), 514 — 534) открыл весьма привлекательный способ построения Лцузловых деревьев поиска, основанных на бинарном представлении ключей без необходимости их хранения в узлах.
Этот метод, названный "Патриция" (Расс!с)а — Ргасбса1 А!КопгЬш То Вегпеге 1п(оппайоп Содей 1п А1рЬапшпепс), очень хорошо подходит для работы с большими ключами переменной длины, например с заголовками илн фразами, хранящимися в файле большого объема. Похожий алгоритм был одновременно опубликован в Германии (О. СггеЬепЬегКег, Е!е)сггоп!эсЛе ИесЛепап!а8еп 10 (1968), 223 — 226). Основная суть метода "Патриция" состоит в построении бинарного дерева без однопутевых ветвей посредством включения в каждый узел количества битов,которые можно пропустить, прежде чем приступить к следующему тесту.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
