6.5. Префиксный цифровой поиск

6.5.1. Префиксное дерево

При цифровом поиске сравнение ключей связано не с проверкой числового соотношения , а с последовательным учётом символов, входящих в состав ключа поиска (как это делается при поиске перевода данного слова с помощью словаря). В качестве ключа может использоваться любая строка из символов данного алфавита (включая символ конца слова). Например, ключ может задаваться как последовательность цифр и/или букв. На практике обычно, символы алфавита кодируются числами.

Введём необходимые определения.

Алфавитом будем называть конечный набор различных символов (включая символ конца слова). Словом в этом алфавите называется любой набор его символов, заканчивающийся символом.

Решается задача поиска слов, которые, возможно, хранятся в базе данных («пробить по базе»).

База данных реализована в виде-арного дерева, то есть дерева, у которого каждый узел является корнем не более чем поддеревьев (иными словами, каждый узел является родителем не более чем для узлов).

Префиксом узла уровня называется последовательностьсимволов данного алфавита(среди которых могут быть и совпадающие). Префиксом корня является пустое слово (состоящее только из символа конца слова).

Узел уровня — это-мерный вектор

;

каждая его компонента соответствует определённому символуалфавита и может иметь в качестве значения:

- либо слово, начинающееся с префикса узла — в том случае, когда в базе имеется единственное слово, начинающееся с таким префиксом; именно оно является целью поиска;

- либо ссылку на узел уровня , если префикс не является законченным словом, но в базе есть слова с таким началом; в-м узле в этом случае следует смотреть компоненту, соответствующую символу префикса

- либо пустую ссылку , если слова с таким префиксом в базе нет.

Реализованная таким образом база данных называется префиксным деревом (или лучом, или нагруженным деревом).

Пример. База данных состоит из слов

{лес, лето, лото, лотос, лось, мал, мала, мол, мел, мех, меха, место, смета, сом, соха, тол, холл}

в алфавите {м, л, х, с, т, а, о, ь, е, }.

Символ конца слова подразумевается присутствующим в конце каждого слова (на рис. 42, изображающем соответствующее префиксное дерево, символзаменён жирным подчёркиванием клетки с полным словом). Префиксное дерево содержит пять уровней, включая корень.

Рис. 42.

6.5.2. Алгоритм префиксного поиска

Префиксный (или лучевой) поиск — это поиск по префиксам в базе, представленной префиксным деревом. Символы ключа обычно представляются числами в диапазоне от до, где символу конца слова соответствует нуль, так что поиск называетсяцифровым.

Алгоритм. Пусть — указатель на дерево (то есть адрес корня);— ссылка на узел;— вектор в текущем узле; ключ, где каждое— символ алфавита;— текущий номер символа в ключе.

╔

Ш1. Начальная установка.

—ссылка указывает вначале на корень луча;

.

Ш2. Переход к узлу следующего уровня:

;

; здесь — компонента узлового вектора,

закреплённая за символом ;

если является ссылкой, то

перейти к Ш3;

если является ключом, то

перейти к Ш4 (— это единственный претендент на

совпадение с ключом поиска).

Ш3. Продвижение по лучу:

если , то

;

вернуться к Ш2;

если , то

ключ в базе данных отсутствует.

Ш4. Сравнение ключа со словом в соответствующей компоненте

вектора :

если , то

ключ найден, указывает на искомую запись;

иначе

ключ отсутствует.

╚

NB: При неудачном поиске он завершается со значением ключа , наиболее близким к.

Префиксный поиск со вставкой. Алгоритм поиска легко дополняется до алгоритма поиска со вставкой отсутствующего ключа в базу: пустая ссылка в компоненте вектора на шаге Ш4 заменяется ключом поиска. Таким образом, подавая в корень очередные слова для поиска со вставкой, можно сформировать базу данных в виде префиксного дерева.

Бинарный цифровой поиск. Это частный случай лучевого поиска по -арному дереву при. Каждый символ исходного алфавита кодируется двоичным числом фиксированной длины. Теперь очередной символ ключа поиска — бит с возможными значениямиили. Эти значения определяют выбор ветки в двоичном дереве при переходе к очередному узлу.