Другая возможность — создание двух попыток.
Первый (пусть будет T1) для имен, а второй (пусть T2) для фамилий.
При построении дерева из каждого терминатора слова в T1 (обычно обозначаемого знаком $) добавьте список указателей на соответствующие записи в T2 и наоборот.
т.е. если John Doe является основным блюдом:
T1:
J
|
O
|
H
|
N
|
$1
T2:
D
|
O
|
E
|
$2
$1 будет содержать список, содержащий указатель на $2, а $2 будет содержать список, содержащий $1.
каждый поиск по префиксу будет искать с обеих попыток, получая автоматическое завершение, а затем использовать указатели для получения полного имени (частичный поиск дал вам только имя/фамилию, вы получаете второе с помощью указателей).
Поиск полного имени выполняется путем поиска в обеих попытках (ищите имя в T1 и фамилию в T2 и получаете соответствующие $1 и $2 соответственно), затем вам нужно проверить, совпадают ли указатели (список l1 в $1 содержит $2, а список l2 в $2 содержит $1). Если да - имя в словаре.
Обратите внимание, что когда у вас есть указатель на узел $, можно просто вернуться к дереву, пока вы не доберетесь до корня, чтобы получить слово, которое представляет этот знак $. (требуется указатель на родителя от каждого узла)
Также обратите внимание: я объяснил о простых попытках, но на самом деле нет причин, почему бы не использовать вместо этого попытки patricia, используя тот же подход.
person
amit
schedule
06.06.2012
