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

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


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

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

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


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

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, что напомнил разбить строки на слова %)
  • Вопрос задан
  • 13708 просмотров
Решения вопроса 1
dmitryim
@dmitryim
Дополнительно, после разбиения строки на слова, их можно сравнивать с помощью levinshtein(). Потом с учетом длины слова получать коэффициент похожести. Таким образом можно с довольно точно определять схожесть, даже если допущена опечатка в слове, или если оно написано немного иначе.
Ну и дополнительный бонус — транслитерация строки и очистка ее от мусора.
Ответ написан
Пригласить эксперта
Ответы на вопрос 5
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 есть описания и ссылки на реализации. Выбери подходящий.
Ответ написан
по вашему алгоритму получается, что строки «Джей Джей Йохансон» и «Джей Кью Йохансон» равны. нужно исключать из массивов строк уже совпавшие
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы
CSort Барнаул
от 40 000 до 90 000 руб.
Migo group Ростов-на-Дону
от 60 000 до 90 000 руб.
23 мая 2019, в 04:22
500 руб./в час
22 мая 2019, в 23:03
15000 руб./за проект
22 мая 2019, в 22:44
1000 руб./за проект