Алгоритм сравнения текстовых строк?

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


'Иван Иваныч Иванов' = 'Иванов Иван Иваныч'

'Иван Иваныч' ~ 'Иванов Иваныч'

'Иван Иваныч Иванов с утра ходит без штанов' != 'Иванов Иван Иваныч одевает штаны на ночь'


То есть, нужно найти коэффициент похожести строк, с учетом того, что слова в строке могут быть поменяны местами.

UPD: Кажется придумал:

a — массив слов первой строки

b — массив слов второй строки


n — количество слов первой строки

m — количество слов второй строки


Сij — коэффициент похожести слов a[i] и b[j] (можно использовать soundex или Levenshtein distance)


K = (С11 + С12 +… + С1m + C21 + C22 +… + C2m +… + Cnm) / ((n + m) / 2)


Итого для примера, пусть Cij считается как a[i] == b[j] ? 1 : 0


a = ['Иван', 'Иваныч', 'Иванов']

b = ['Иванов', 'Иван', 'Иваныч']


K = (0 + 1 + 0 + 0 + 0 + 1 + 1 + 0 + 0) / ((3 + 3) / 2) = 3 / 3 = 1 — строки одинаковы


a = ['Иван', 'Иваныч']

b = ['Иванов', 'Иваныч']


K = (0 + 0 + 0 + 1) / ((2 + 2) / 2) = 1 / 2 = 0.5 — похожи, но не равны


Вроде логично.


Спасибо hamMElion, что напомнил разбить строки на слова %)
  • Вопрос задан
  • 13469 просмотров
Решения вопроса 1
dmitryim
@dmitryim
Дополнительно, после разбиения строки на слова, их можно сравнивать с помощью levinshtein(). Потом с учетом длины слова получать коэффициент похожести. Таким образом можно с довольно точно определять схожесть, даже если допущена опечатка в слове, или если оно написано немного иначе.
Ну и дополнительный бонус — транслитерация строки и очистка ее от мусора.
Ответ написан
Пригласить эксперта
Ответы на вопрос 4
hamMElion
@hamMElion
1. Разбить обе строки на массивы слов (split)
2. Цикл поиска элементов одного массива в другом (подсчет совпадений = k)
3. Нахождение числа совпадений для второго массива из пропорции k1/n1=k2/n2 (n — число элементов массива)
4. Разница |k1-k2| и есть коэффициент похожести
Ответ написан
tyomitch
@tyomitch
Алгоритмов — хоть антилопой жуй.
На staffwww.dcs.shef.ac.uk/people/S.Chapman/stringmetrics.html есть описания и ссылки на реализации. Выбери подходящий.
Ответ написан
по вашему алгоритму получается, что строки «Джей Джей Йохансон» и «Джей Кью Йохансон» равны. нужно исключать из массивов строк уже совпавшие
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы