Поиск префикса в исходном дереве /patricia trie
-
18-09-2019 - |
Вопрос
В настоящее время я внедряю дерево оснований / patricia trie (называйте как хотите).Я хочу использовать его для поиска префиксов в словаре на аппаратном обеспечении с крайне низкой мощностью.Предполагается, что это должно работать более или менее как автоматическое завершение, i.e.отображение списка слов, которым соответствует введенный префикс.
Моя реализация основана об этой статье, но содержащийся в нем код не включает поиск по префиксу, хотя автор говорит:
[...] Допустим, вы хотите перечислить все узлы, у которых есть ключи с общим префиксом "AB".Вы можете выполнить поиск в глубину, начиная с этого корня, останавливаясь всякий раз, когда сталкиваетесь с задними краями.
Но я не понимаю, как это должно работать.Например, если я построю исходное дерево из этих слов:
болезнь
воображаемый
воображение
представьте себе
имитация
немедленный
немедленно
необъятный
в
Я получу точно такое же "наилучшее совпадение" для префиксов "i" и "in", так что мне кажется трудным собрать все совпадающие слова, просто пройдя по дереву из этого наилучшего совпадения.
Кроме того, существует реализация базового дерева в Java который имеет реализованный поиск по префиксу в RadixTreeImpl.java.Этот код явно проверяет все узлы (начиная с определенного узла) на соответствие префиксу - фактически он сравнивает байты.
Кто-нибудь может указать мне на подробное описание реализации поиска по префиксу в деревьях оснований?Является ли алгоритм, используемый в реализации Java, единственным способом сделать это?
Решение
Подумайте о том, что кодирует ваш 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
, который он мог бы искать чрезвычайно быстро.
Другие советы
Оказывается, расширения GNU для стандартной библиотеки C++ включают реализацию дерева Patricia.Он находится в расширении структур данных на основе политик.Видеть http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/trie_based_containers.html
Альтернативный алгоритм:Держать его просто глупо!
Просто составьте отсортированный список ключевых слов.Если у вас есть префикс, выполните двоичный поиск, чтобы найти, где этот префикс будет расположен в списке.Все ваши возможные завершения будут найдены, начиная с этого индекса, и к ним можно будет получить доступ на месте.
Этот алгоритм потребует всего 5% кода дерева Patricia, и его будет легко поддерживать, понимать и обновлять.Почти наверняка этот простой поиск по списку также будет более эффективным.
Единственным недостатком является то, что если у вас огромное количество длинных ключевых слов со схожими префиксами, trie может сэкономить некоторое пространство, поскольку ему не нужно сохранять полный префикс для каждой записи.На практике, если у вас меньше нескольких миллионов слов, это не экономия, поскольку будут доминировать издержки указателя в дереве.Эта экономия больше подходит для таких приложений, как поиск в базах данных строк ДНК с миллионами символов, а не текстовых ключевых слов.
Другим альтернативным алгоритмом является троичное дерево поиска (более эффективное использование памяти) https://github.com/varunpant/TernaryTree/tree/master/TernaryTree