Есть ли простое и быстрое решение определить, что фраза изменена незначительно?

Question

[Андрей]

Начну с примеров, было - стало
ишка - мишка
мышка - мишка
сходразвал - сход-развал
окумулятор - аккумулятор
малая медведица - большая медведица
и так далее. В основном необходимо проверять слова и фразы из 2-3 слов.

Вопрос такой - как проще и быстрее алгоритмически определять, как сильно изменилась фраза? Мне необходимо определять - малое ли это изменение (исправление опечатки, первые четыре примера) или значительное (последняя фраза).

Пока есть только одна идея - считать как часто встречается каждая буква и сравнивать насколько изменилась частота.

Comments

[Dmitrii]

Если у вас есть база часто используемых слов. Тогда если у вас появилось слово, крайне редкое, а отличие от известного слова составляет 1-2 буквы, то можно предположить, что очепятка имеет место.

Предложение пальцем в небо

Answer 1

[Adamos]

https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D...

Comments

[rPman]

докину к ответу, что реализации ее поддержки в базах данных обычно очень эффективные (например у postgres как то используются индексы)

Answer 2

[Николай Савельев]

это классическая задача. Решается через расстояние Левенштейна

Comments

[Everything_is_not_so_bad]

Или же Расстояние Дамерау — Левенштейна

Является модификацией расстояния Левенштейна: к операциям вставки, удаления и замены символов, определённых в расстоянии Левенштейна добавлена операция транспозиции (перестановки) символов.

Answer 3

[mayton2019]

Можно вести подсчет триграмм. (Троек символов). И если разница в небольшом числе триграмм - тогда
считаем что слова равны с "допуском". Величину допуска можно установить экспериментально исходя
из тестовых выборок.

Для случая сходразвал сход-развал.
сходразвал: схо ход одр дра раз азв вал
для слова с дефисом из триграмм выпадают
одр дра
следовательно допуск равен двум.

Можно использовать би-граммы или четерех-граммы. Это вопрос эксперимента. Что лучше подойдет на
данном наборе исходных данных.