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

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

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

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

О чем я думаю:

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