Здравствуйте, vdimas, Вы писали:

V>У меня есть решение, но мне банально интересно, к какой сложности относятся подобные задачи? ))

Сопоставить каждому слову свой вектор в N-мерном пространстве, найти в нем K ближайших за логарифм. И уже с ними линейно сравниться алгоритмом типа Левенштейна.
Найти в пространстве — можно взять готовую библиотеку типа faiss или любой аналог.
Как сопоставить слову вектор — вот тут я бы взял лёгкую нейросеть для текстовых эмбеддингов. Твое требование без ИИ тут не канает, потому что это не ИИ, хоть и нейросеть.