Утяжеленное trie для функции autosuggest

Question

У меня есть trie (суффикс-дерево), которое я использую для функции автоматического предложения на своем веб-сайте.

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

Или я должен просто сортировать по весу в памяти?

Answer 1

На каждом узле вы можете добавить свойствоили weight и обновить его при создании трии, используя свои слова. Каждый символ будет иметь начальный вес 0, но если символ является символом терминала, то он будет иметь начальный вес 1. Когда вы продолжаете добавлять слова, вы можете настроить весы на символы терминала.

Так, например, вы могли бы:

t:0 
| 
o:1 
| 
w:3---e:0 
| \ \ 
n:2 a:0 l:4 
    \ 
     r:0 
     \ 
     d:2 

Для строк to (появляясь один раз), tow (появляясь трижды), towel (появляясь в четыре раза), town (появляясь дважды), и toward (также появляется дважды).

Тогда, если вы имели префикс tow, вы можете посмотреть на ненулевых взвешенных строк, таких как tow:3, towel:4, town:2 и toward:2.

После этого вы можете сортировать по весу.

Я не пробовал эту реализацию на практике; это всего лишь идея.