По вашему запросу найдено: реализация нечеткого поиска

[AlexeyTokar]

добавьте предфильтр перед Левенштейном. Например н-граммный. Памяти будет есть чуть больше, но словарь можно будет существенно сократить для постобработки и деградация будет не экспоненциальной.
ну а на самом верху я бы вообще держал фильтр блюма, который позволил бы точные совпадения отдавать вообще с минимумом задействования ресурсов

занимался немного вопросом: youtu.be/G2zxxmF2iiA :)

[martovskiy]

В сфинксе есть удобная штука, на одном из этапов полезно её использовать.
CALL SUGGEST(word, index [,options])