Предсказание слов с использованием четырехугольников в питоне

Question

В настоящее время я использую Quadgrams в Python, чтобы предсказать следующее слово предложения. Для этого я использую вложенный словарь для хранения вероятностей. Вот ссылка на код

Но эта реализация принимает O(n) в худшем случае. Так есть ли другой способ реализовать это, используя другие структуры данных, которые принимают O(logn) или меньше для поиска?

Answer 1

Тройные деревья поиска являются эффективными структурами данных для реализации автозаполнения. Вы можете хранить вероятности в узлах (100%, если ветвления нет, и X%, если ветвления).

Поиск будет в O(log n).