Как реализовать autocomplete для набираемого слова в текстовом редакторе (при вводе первых букв показывать несколько возможных завершений слова).
Сортировка выдаваемых результатов должна быть с учетом частоты появления слова (в словаре для каждого слова задана частота использования)
Читал про trie-деревья, но как добавить в него учет частоты без получения всех возможных вариантов, а только первых k слов.
Нашел статью "An O(k log n) algorithm for prefix based ranked
autocomplete" - http://dhruvbird.com/autocomplete.pdf
но сложно для меня в переводе
они используют дерево отрезков
Подскажете какие структуры лучше использовать и как их использовать?

А сколько слов? 
Слова записываются в строку таблицы с полями -  первая буква, две первых буквы, три первых буквы, слово, частота. 1-2-3 буквы - ключевые поля. Если прилетело меньше 4 букв - выборка по ключу с сортировкой по частоте. Если больше - выборка по ключу из 3-х букв и дальше - LIKE по тестовому полю. Если слов не "очень много", то получается приемлемо по скорости. 

А словарь - на соседнем столе лежит... трёхтомный... или как?


Сортированный связный список.


Бинарный поиск.

Добавлено через 1 минуту и 39 секунд
Наверное, всё-таки просто индексированные?

Ну да, индексы.