Соответствие разнородных строк

Question

Предположим, два набора строк:

[ "Mr. Jones", "O'Flaherty", "Bob", "Rob Jenkins" ]
[ "Maxwell O'Flaherty", "Robert Jenkins", "Mrs. Smith" ]

Очевидно, что эти два набора имеют общего Максвелла О'Флаэрти и Роберта Дженкинса.

Есть ли какой-нибудь алгоритм, который позволит намделать такое сопоставление программно?Я думаю написать что-то, что будет проходить через каждый элемент в массиве строк и пытаться найти любую подстроку, которая уникальна и не содержится ни в каком другом элементе ни в одном из наборов, а затем использовать это как своего рода хэш каждого элементачтобы соответствовать двум сетам.

Answer 1

Может оказаться полезным расстояние Левенштейна . Если вы делаете это, когда неясно, насколько точна информация, есть библиотеки для устранения неоднозначности строк. (Не «очевидно», что Роб и Роберт идентичны - действительно, первым может быть Робин.

Answer 2

Один из подходов, которые я использовал в прошлом для решения таких проблем, как Роберт против Боба, - это запросы к интернет-источникам, которые могут выявить сходства.

Например, я не знаю о Wolfram Alphaполитика автоматического поиска (хотя я думаю, что в какой-то момент они работали над API), но поиск Роберта (http://www.wolframalpha.com/input/?i=robert) определил бы, что его следует сопоставить с именем «Роб».

Кроме того, это совсем не программно, но я обнаружил, что умное использование Amazon Mechanical Turk творит чудеса для такого рода проблем, если ваш набор данных имеет разумные ограничения по размеру.

Answer 3

Если это пример из реальной жизни, и вам нужно точное совпадение имени или фамилии, то выполните синтаксический анализ всей строки во втором массиве и создайте новый массив со всеми проанализированными подстроками и сохраните индекс для элементов исходного массива, частью которых является подстрока:

[{"Maxwell", 0}, {"O'Flaherty", 0}, {"Robert", 1}, {"Jenkins", 1}, {"Mrs.", 2}, {"Смит ", 2}]

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