Насколько строки похожи

#алгоритм #строки

Делаю модерацию сообщений в чате. Нужно выяснить, насколько сообщение похоже на то,
которое юзер отправил ранее. 

Например:

сколько это может продолжаться и cкoлькo этo мoжeт прoдoлжaтьcя выглядят идентично,
однако, во втором случае буквы o, a, e, c и подобные заменены на аналогичные из другого
языка.

А также другой пример:

моя служба никогда не закончится и моя служба не скоро закончится по сути, один и
тот же смысл, только заменено одно слово.

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

И вопрос состоит в том, как должен выглядеть алгоритм нахождения процента схожести
сообщений?
    

Ответы

Ответ 1

В теории, можно посмотреть на алгоритм расстояния Damerau-Levenshtein, но все равно,
потребуется предобработка, т.к. его результат для ситуации из 


  сколько это может продолжаться и cкoлькo этo мoжeт прoдoлжaтьcя выглядят идентично,
однако, во втором случае буквы o, a, e, c и подобные заменены на аналогичные из другого
языка.


будет некорректным для Вас. Вы можете сделать замену и потом вычислить дистанцию
по предложенному алгоритму. 

Не уверен, что предложенный алгоритм шинглов будет работать лучше - все же, без предобработки
(замены "похожих" букв, как минимум) он выдаст разные хэши. Но, тут стоит проверить.

P.S. можно посмотреть вот эту библиотеку, как стартовую точку - https://github.com/feature23/StringSimilarity.NET

P.S. @rdorn выше описал ранее тоже самое