к равным "пустому" символу или символу "конец слова" Символ должен быть представлен в виде числа в диапазоне О < fc < М). Обозначим через X к-й элемент в NODE(P). Если X представляет собой ссылку, перейти к шагу ТЗ, если X - ключ, перейти к шагу Т4.

ТЗ. [Продвижение.] Если X ф к, установить Р Х и вернуться к шагу Т2; в противном случае алгоритм завершается неудачей.

Т4. [Сравнение.] Если X ~ К, алгоритм завершается успешно; в противном случае алгоритм завершается неудачей.

Таблица 1

ЛУЧ для 31 НАИБОЛЕЕ УПОТРЕБИТЕЛЬНОГО АНГЛИЙСКОГО СЛОВА

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

Для сравнения скорости работы данного алгоритма со скоростями других алгоритмов из этой главы напишем коротенькую MIX-программу, в которой предполагается, что символы представляют собой байты, а максимальная длина ключа - 5 байт.

Программа Т ( "Лучевой поиск" [Trie search )). В этой программе предполагается, что все ключи занимают одно слово машины MIX; в случае, если в ключе содержится

менее 5 символов, он дополняется пробелами справа. Поскольку мы используем коды символов MIX, каждый байт аргумента поиска содержит число, меньшее 30. Ссылки представлены в виде отрицательных чисел в поле 0:2 узла слова. гИ = Р, гХ = непросканированная часть К.

Время работы программы составляет 8С + 8 единиц, где С - количество проверяемых символов. Поскольку С < 5, время поиска никогда не превышает 48 единиц времени.

Если сравнить эффективность этой программы (при поиске на луче из табл. 1) и программы 6.2.2Т (с использованием оптимального бинарного дерева поиска (см. рис. 13)), можно сделать следующие выводы.

1. Луч занимает гораздо больше памяти; мы использовали 360 слов для представления 31 ключа, в то время как бинарное дерево поиска использует только 62 слова памяти (однако в упр. 4 будет показано, что можно ухитриться втиснуть луч из табл. 1 в 49 слов).

2. Успешный поиск требует 26 единиц времени в обеих программах. Неудачный поиск выполняется быстрее в случае луча и медленнее - в бинарном дереве поиска. Для наших конкретных данных неудачный поиск будет осуществляться гораздо чаще, чем успешный, а потому для них "лучевой поиск" предпочтительнее с точки зрения скорости работы.

3. В случае применения луча для указателя KWIC (см. рис. 15) метод теряет свою привлекательность в силу природы используемых данных. Например, для различения слов COMPUTATION и COMPUTATIONS луч потребует 12 итераций. Поэтому было бы более разумно строить луч таким образом, чтобы сканирование слов происходило справа налево.

Абстрактная концепция луча для представления семейства строк была предложена Акселем Тью (Axel Thue) в статье о строках, которые не содержат смежных повторяющихся подстрок [Skrifter udgivne af Videnskabs-Selskabet i Christiania, Mathematisk-Naturvidenskabehg Klasse (1912), No. 1; перепечатана в книге Тью Selected Mathematical Papers (Oslo: Universitetsforlaget, 1977), 413-477].

"Лучевая память" для компьютерного поиска была впервые рекомендована Рене делаВрианде (Rene de la Briandais) [Ргос. Western Joint Computer Conf. 15 (1959), 295-298]. Oh указал, что можно сохранить память (за счет времени работы) при использовании связанного списка для каждого узла-вектора, поскольку большинство элементов вектора обычно пусто. На самом деле эта идея приводит к замещению луча из табл. 1 лесом, показанным на рис. 31. Поиск в таком лесу осуществляется

Рис. 31. Луч из табл. 1, преобразованный в "лес".

а а

а <

путем нахождения корня, соответствующего первому символу, затем дочернего узла этого корня, соответствующего второму символу, и т. д.

В своей статье де ла Брианде в действительности не прерывал ветвление дерева, как показано в табл. 1 или на рис. 31; вместо этого он продолжал представление каждого ключа, символ за символом, до достижения конца слова. Таким образом, де ла Брианде использовал бы

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

Если использовать обычный путь представления деревьев как бинарных деревьев, (1) становится бинарным деревом

(В представлении полного леса на рис. 31 следовало бы добавить указатель, ведущий вправо от Н к соседнему корню I.) Поиск в этом бинарном дереве выполняется посредством сравнения аргумента с символом в дереве и следования RLINK до поиска соответствия; после этого мы находим LLINK и точно так же работаем с очередным символом аргумента.