Auto Suggest: Подстановка подстроки

Question

Я пытаюсь реализовать автоматическое предложение, используя тройное дерево поиска (TST), но TST полезен, когда мы ищем префиксные поиски, как мы можем реализовать Auto Suggest для подстрочных совпадений? Есть ли какая-либо другая структура данных, которая может быть использована?

Например, подстрочные совпадения: Когда я пытаюсь выполнить поиск UML с помощью автоматического предложения, даже строка «Руководство для начинающих для UML» должна совпадать.

Answer 1

Это из верхней части моей головы, а не какой-либо собственно и проверенная структура данных/алгоритм:

1. Выберите отображение всех юридических символов до N символов (для простоты: 26 символов для латинских букв и аналогичные нелатинские буквы, игнорирующие случай + 1 для не-букв = всего 27 символов).

2. Из вашего словаря создайте мелкое дерево с макс. Коэффициентом ветвления N (т.е. достаточно высоким). Листовые узлы будут содержать ссылки на все слова, содержащие комбинацию символов, ведущую от корня к этому листу (промежуточные узлы могут содержать ссылки на слова, которые короче, чем глубина листового узла, или вы можете просто игнорировать слова, которые являются короткими).

3. Глубина дерева будет переменной, вероятно, в диапазоне 1..4, так что каждый листовой узел будет содержать примерно такое же количество слов (одно и то же слово, конечно, перечисленное под многими листьями, например MATCH под листьями MAT, ATC , TCH, если глубина дерева оказалась 3).

4. Когда пользователь вводит буквы, следуйте за деревом до тех пор, пока вы не останетесь с относительно небольшим набором слов. Затем выполните линейную фильтрацию оставшихся слов после того, как вы находитесь на листе дерева, и пользователь вводит больше текста для соответствия. Необязательно отфильтровывать символ соответствует которые на самом деле являются символ не совпадает, хотя это было бы неплохо, чтобы соответствовать также äöO, когда пользователь вводит ao0 и т.д.

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

---

Конечно, есть фактические исследуемые алгоритмы поиска строки (какой пользователь вошел) в большом куске текста (все фразы/слова, которые вы хотите, чтобы соответствовать), как Aho–Corasick и Rabin–Karp, которые вероятно, стоит исследовать.