Автозаполнение простого слова просто отображает список слов, которые соответствуют уже введенным символам. Но я хотел бы заказать слова в списке автозаполнения в зависимости от вероятности появления слов в зависимости от слов, которые были напечатаны до этого, опираясь на статистическую модель текстового корпуса. Какие алгоритмы и структуры данных мне нужны для этого? Можете ли вы дать мне ссылки на хорошие учебники?
Алгоритмы/теория за прогностическим автозаполнением?
Ответ 1
У Peter norvig была статья Как написать корректор правописания, в котором объясняется, как Google имел в виду...? которые используют байесовский вывод, чтобы сделать его эффективным. Он очень хорошо читается и должен быть адаптирован к функции автозаполнения.
Ответ 2
Вам не нужна вероятность для автозаполнения. Вместо этого создайте дерево префикса (aka trie) со словами в корпусе в виде ключей и их частотой в качестве значений. Когда вы сталкиваетесь с частичной строкой, пройдите три, насколько сможете, затем сгенерируйте все суффиксы с точки, которую вы достигли, и отсортируйте по частоте.
Когда пользователь вводит ранее невидимую строку, просто добавьте ее в trie с частотой one; когда пользователь вводит строку, которую вы видели (возможно, выбрав ее из списка кандидатов), увеличьте ее частоту.
[Обратите внимание, что вы не можете сделать простой приращение с вероятностной моделью; в худшем случае вам придется пересчитать все вероятности в модели.]
Если вы хотите углубиться в такие алгоритмы, я настоятельно рекомендую вам прочитать (первые главы) Обработка речи и языка Юрафский и Мартин. Он довольно подробно рассматривает дискретную вероятность обработки языка.