| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Autocomplete по словарю с учетом частоты |
| Автор: WhoogMan 18.6.2015, 19:20 |
| Как реализовать autocomplete для набираемого слова в текстовом редакторе (при вводе первых букв показывать несколько возможных завершений слова). Сортировка выдаваемых результатов должна быть с учетом частоты появления слова (в словаре для каждого слова задана частота использования) Читал про trie-деревья, но как добавить в него учет частоты без получения всех возможных вариантов, а только первых k слов. Нашел статью "An O(k log n) algorithm for prefix based ranked autocomplete" - http://dhruvbird.com/autocomplete.pdf но сложно для меня в переводе они используют дерево отрезков Подскажете какие структуры лучше использовать и как их использовать? |
| Автор: ksnk 18.6.2015, 20:56 |
| А сколько слов? Слова записываются в строку таблицы с полями - первая буква, две первых буквы, три первых буквы, слово, частота. 1-2-3 буквы - ключевые поля. Если прилетело меньше 4 букв - выборка по ключу с сортировкой по частоте. Если больше - выборка по ключу из 3-х букв и дальше - LIKE по тестовому полю. Если слов не "очень много", то получается приемлемо по скорости. |
| Автор: Akina 19.6.2015, 08:48 | ||||||||
А словарь - на соседнем столе лежит... трёхтомный... или как?
Сортированный связный список.
Бинарный поиск. Добавлено через 1 минуту и 39 секунд
|
| Автор: ksnk 19.6.2015, 11:58 | ||
Ну да, индексы. |
