Как эффективно рассчитать левенштейновское расстояние для большого словаря?

У меня довольно большой словарь (200 тыс. Слов, длина 2-16 символов) и различные входные строки (5-200 слов, разделенных пробелами, длина 2-20 символов).
Используя PHP в режиме cli, мне нужно сравнить каждое входное слово со словами в словаре и вычислить минимальное расстояние Левенштейна с почти максимальной эффективностью — как я могу это сделать?

Что я уже пробовал:

1. Реализовал свой собственный базовый алгоритм сравнения (с экспоненциальной сложностью) — очень медленно.
2. Реализовал собственный продвинутый алгоритм сравнения (по длине слова) — быстрее, но все еще очень медленно.
3. Преобразовал словарь в структуру данных Trie и реализовал поиск в Trie — быстрее, чем п.2, но все же недостаточно.
4. Добавлена ​​дополнительная хеш-таблица для случаев, когда входное слово совпадает со словом dict (нулевое расстояние). Также входные слова с вычисленным расстоянием помещаются в хеш-таблицу, чтобы они не вычислялись дважды при повторении во входной строке. До сих пор не достаточно быстро.

О чем я думаю:

1. Предварительный расчет узлов Trie для словаря, поскольку последний никогда не изменяется.
2. Использование массивов вместо объектов для узлов Trie.
3. Реализуете другой алгоритм? Как н-граммы или левенштейновые автоматы? Не уверен, стоит ли это того.