новые функции для алгоритма автозаполнения

Question

Я встретил эту проблему в интервью. Легко реализовать базовую систему автозаполнения (https://www.futurice.com/blog/data-structures-for-fast-autocomplete/), чтобы получить список строк из строки префикса. Теперь мы хотим добавить некоторые новые функции.

ех, Ввод пользователя: lun pla Вывод: план обеда (автозаполнение нескольких слов)

Ввод пользователя: pla Вывод: план обеда

Ввод пользователя: unc Вывод: обед (автозаполнение формы слова)

Как реализовать функции?

Answer 1

Вы можете попробовать следующий (базовый) подход, а я позже дам предложения для расширений:

• загрузить словарь принятых слов
• построить BK-дерево из этих слов, используя расстояние Левенштейна-Дамерау в качестве базовой метрики
• разбить входную последовательность на символ пробела, чтобы получить слова
• для каждого слова проверьте, является ли оно принятым словом. Если он не находит ближайшего (в пределах допустимого расстояния) слова в BK-дереве

Теперь для улучшений:

• Как вы указали, иногда совпадение имеет больше смысла, когда два слова сгруппированы вместе
• Используйте для этого алгоритм Google word2Phrase. Вы можете найти версию C ++ здесь .
• Используйте более умный подход к поиску границ слов. Стохастический метод, такой как HMM (скрытая модель Маркова), может быть полезен (чтобы избежать разделения дат, времени, сокращений и т. Д.)
• Используйте более интеллектуальную метрику ошибок. Вы можете принять во внимание типичные ошибки в написании, ошибки раскладки клавиатуры (для людей, привыкших набирать qwerty и неожиданно сталкивающихся с azerty, есть очень специфические ошибки) и т. Д.
• Попробуйте определить слово тип части речи . (Прилагательное, существительное, глагол и т. Д.). Делая это, вы можете сделать гораздо лучшие дополнения.