Поиск префикса по основному дереву /patricia trie

Question

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

Моя реализация основана на этой статье, но код в ней не включает поиск префиксов, хотя автор говорит:

[...] Скажем, вы хотите перечислить все узлы, которые имеют ключи с общим префиксом "AB". Вы можете выполнить поиск в глубину, начиная с этого корня, останавливаясь всякий раз, когда вы сталкиваетесь с задними гранями.

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

болезнь
воображаемый
воображение
представить
имитация
немедленный
немедленно
огромный
в

Я получу точно такое же "лучшее соответствие" для префиксов "i" и "in", что мне будет сложно собрать все подходящие слова, просто пройдя по дереву из этого лучшего соответствия.

Кроме того, в Java есть реализация radix tree, в которой реализован поиск префиксов в RadixTreeImpl.java. Этот код явно проверяет все узлы (начиная с определенного узла) на соответствие префикса - он фактически сравнивает байты.

Может кто-нибудь указать мне подробное описание реализации поиска префикса на основаниях деревьев? Является ли алгоритм, используемый в реализации Java, единственным способом сделать это?

Answer 1

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

• Λ
• Λ →"я"

В узле "i" есть два дочерних элемента, один для "m" и один для "n". Следующая буква "н", так что вы принимаете это,

• Л →"я"→"п"

и так как единственное слово, начинающееся с "i", "n" в вашем наборе данных, это "in", дочерних элементов от "n" нет. Это совпадение.

Теперь предположим, что в наборе данных вместо "in" был "infindibulum". (На какой SF я ссылаюсь, оставляем в качестве упражнения.) Вы все равно доберетесь до узла "n" таким же образом, но если следующая буква, которую вы получите, это "q", вы знаете, что слово не появляется в вашем наборе данных вообще, потому что нет ветки "q". В этот момент вы говорите: "Хорошо, нет совпадений". (Может быть, вы начнете добавлять слово, а может и нет, в зависимости от приложения.)

Но если следующая буква "f", вы можете продолжать. Тем не менее, вы можете замкнуть это с небольшим ремеслом: как только вы достигнете узла, представляющего уникальный путь, вы можете повесить всю строку на этом узле. Когда вы попадаете на этот узел, вы знаете, что остальная часть строки должна быть "findibulum", поэтому вы использовали префикс, чтобы соответствовать всей строке и вернуть ее.

Как вы это используете? во многих интерпретаторах команд, отличных от UNIX, таких как старый DCL VAX, вы можете использовать любой уникальный префикс команды. Итак, эквивалент ls(1) был DIRECTORY, но никакая другая команда не начиналась с DIR, поэтому вы можете набрать DIR и это было так же хорошо, как делать целое слово. Если вы не можете вспомнить правильную команду, вы можете просто набрать 'D' и нажать (я думаю) ESC; CLI-интерфейс DCL вернет вам все команды, которые начинаются с D, который он мог бы искать чрезвычайно быстро.

Answer 2

Оказывается, расширения GNU для стандартной библиотеки C++ включают в себя реализацию Patricia trie. Он находится под расширением структур данных на основе политик. См. http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/trie_based_containers.html

Answer 3

Альтернативный алгоритм: Keep It Simple Stupid!

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

Этот алгоритм потребует только 5% кода Патрисии, и его будет легко поддерживать, понимать и обновлять. Почти наверняка этот простой поиск по списку также будет более эффективным.

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

Answer 4

Другой альтернативный алгоритм - троичное дерево поиска (более эффективное использование памяти) https://github.com/varunpant/TernaryTree/tree/master/TernaryTree