Один из вариантов, который, на мой взгляд, был бы особенно эффективным, состоял бы в предварительной обработке дерева в измененную структуру, специально оптимизированную для прогнозирования слов на основе нажатий клавиш.
Интуитивно понятно, что новая структура - это дерево, созданное из возможных цифр, которые можно нажимать в любой точке. Каждый узел Trie затем сохраняет приоритетную очередь слов, которые могут быть написаны с использованием этих цифр. Затем вы можете предсказать, какие слова использовать с помощью следующего алгоритма:
- Начните с корня дерева.
- Для каждой цифры следуйте указателю, соответствующему этой цифре.
- Если вы уйдете с трия, то нет никаких предложений.
- В противном случае посмотрите в очереди приоритетов слова, которые могут быть образованы именно из этих цифр, затем предложите элемент в этой очереди приоритетов с наибольшим количеством использований.
Этот алгоритм требует времени O (n + T max ), где n - длина строки цифр, а T max - время, необходимое для поиска наиболее популярного слова для данный префикс. Это может быть O (1) для чего-то вроде двоичной кучи, но может быть медленнее для более сложных куч.
Чтобы построить эту структуру данных, вы должны предварительно обработать исходный список слов / частот следующим образом. Для каждого слова определите последовательность цифр, соответствующих его буквам. Например, слово «муссон» будет 6667666, а слово «яблоко» будет 27753. Затем вставьте эту последовательность в набор цифр, создавая новые узлы по мере необходимости. Когда вы достигнете последнего узла, соответствующего этой строке цифр, вставьте слово в соответствующую очередь приоритетов для этого узла. Общее время для этой операции на самом деле довольно хорошее; учитывая список слов, содержащий всего n букв, это можно сделать за O (n T insert ), где T insert - время, необходимое для вставки слова в очередь приоритетов. Это связано с тем, что нам нужно посещать каждую букву не более трех раз - один раз, чтобы преобразовать ее в цифру, один раз, чтобы перейти к соответствующему краю в последовательности цифр, и один раз, чтобы вставить ее в очередь с приоритетами.
Этот подход также позволяет легко вставлять новые слова в предиктор. Всякий раз, когда пользователь уходит из дерева цифр или выбирает слово, которое не является словом номер один, вы можете просто вставить это слово в дерево цифр, создав соответствующую серию узлов в дереве, а затем вставить слово в правильный приоритет. очереди.
Если вы делаете свои очереди приоритетов из сбалансированного двоичного дерева поиска, в котором хранится указатель на его наименьший элемент, вы можете реализовать поиск самого быстрого слова для серии из n цифр за O (n) времени, а затем можете перечислить все остальные слова с этим префиксом в амортизированном O (1) раз за штуку. Таким способом вы также можете очень легко вставлять или удалять новые слова.
Поскольку слова хранятся в дереве, вы можете в O (1) обновить свое предположение о текущем слове, просто пройдя от текущего узла дерева до дочернего узла, заданного текущим номером. Когда пользователь нажимает клавишу пробела, вы просто сбрасываете обратно до корня дерева цифр. Наконец, когда пользователь нажимает на звездочку, вы можете использовать вышеуказанный трюк, чтобы просто посмотреть на следующее наиболее популярное слово для данного узла trie.
Надеюсь, это поможет!