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

Question

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

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

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

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

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

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

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

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

Answer 1

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

• Λ
• Λ→"я"

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

• Λ→"i"→"n"

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

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

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

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

Answer 2

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

Answer 3

Альтернативный алгоритм:Держать его просто глупо!

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

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

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

Answer 4

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