Разбор человеческих имен и сопоставление их в Ruby

Я думаю, что одним из вариантов было бы использование рубиновой реализации расстояния Левенштейна

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

Затем вы можете определить, что имена с расстоянием меньше X (будучи X числом, которое вам нужно будет настроить) принадлежат одному и тому же человеку.

РЕДАКТИРОВАТЬ Путем небольшого поиска мне удалось найти другой алгоритм, основанный на фонетике, под названием Метафон

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

Это немного поздно (и бессовестная затычка для загрузки), но, чего бы это ни стоило, я написал парсер человеческих имен во время проекта GSoC, который можно установить с gem install namae. Очевидно, что он не обнаруживает ваши дубликаты надежно, но помогает вам в таких задачах.

Например, вы можете проанализировать имена в своем примере и использовать форму отображения с использованием инициалов для обнаружения имен, чьи инициалы идентичны, и так далее и тому подобное:

names = Namae.parse('J.R. Smith and John R. Smith and John Smith and John Roy Smith and Johnny Smith ')
names.map { |n| [n.given, n.family] }
#=> => [["J.R.", "Smith"], ["John R.", "Smith"], ["John", "Smith"], ["John Roy", "Smith"], ["Johnny", "Smith"]]
names.map { |n| n.initials expand: true }
#=> ["J.R. Smith", "J.R. Smith", "J. Smith", "J.R. Smith", "J. Smith"]

Что-то вроде:

1: преобразовать имена в массивы:

irb> names.map!{|n|n.scan(/[^\s.]+\.?/)}
["J.", "R.", "Smith"]
["John", "R.", "Smith"]
["John", "Smith"]
["John", "Roy", "Smith"]
["Johnny", "Smith"]

2: Некоторая функция идентичности:

for a,b in names.combination(2)
    p [(a&b).size,a,b]
end
[2, ["J.", "R.", "Smith"], ["John", "R.", "Smith"]]
[1, ["J.", "R.", "Smith"], ["John", "Smith"]]
[1, ["J.", "R.", "Smith"], ["John", "Roy", "Smith"]]
[1, ["J.", "R.", "Smith"], ["Johnny", "Smith"]]
[2, ["John", "R.", "Smith"], ["John", "Smith"]]
[2, ["John", "R.", "Smith"], ["John", "Roy", "Smith"]]
[1, ["John", "R.", "Smith"], ["Johnny", "Smith"]]
[2, ["John", "Smith"], ["John", "Roy", "Smith"]]
[1, ["John", "Smith"], ["Johnny", "Smith"]]
[1, ["John", "Roy", "Smith"], ["Johnny", "Smith"]]

Или вместо & вы можете использовать .permutation + .zip + .max, чтобы применить некоторую настраиваемую функцию, которая определяет, являются ли части имен идентичными.

UPD:

aim = 'Rob Bobbie Johnson'
candidates = [
    "Bob Robbie John",
    "Bobbie J. Roberto",
    "R.J.B.",
]

$synonyms = Hash[ [
    ["bob",["bobbie"]],
    ["rob",["robbie","roberto"]],
] ]

def prepare name
    name.scan(/[^\s.]+\.?/).map &:downcase
end

def mf a,b # magick function
    a.zip(b).map do |i,j|
        next 1 if i == j
        next 0.9 if $synonyms[i].to_a.include?(j) || $synonyms[j].to_a.include?(i)
        next 0.5 if i[/\.$/] && j.start_with?(i.chomp '.')
        next 0.5 if j[/\.$/] && i.start_with?(j.chomp '.')
        -10 # if some part of name appears to be different -
            # it's bad even if another two parts were good
    end.inject :+
end

for c in candidates
    results = prepare(c).permutation.map do |per|
        [mf(prepare(aim),per),per]
    end
    p [results.transpose.first.max,c]
end

[-8.2, "Bob Robbie John"]  # 0.9 + 0.9 - 10 # Johnson != John # I think ..)
[2.4, "Bobbie J. Roberto"] # 1 + 0.9 + 0.5 # Rob == Roberto, Bobbie == Bobbie, Johnson ~~ J.
[1.5, "R.J.B."]            # 0.5 + 0.5 + 0.5

Для любого, кто пытается сопоставить человеческие имена из разных источников данных, это ОЧЕНЬ сложная проблема. Использование комбинации из трех драгоценных камней кажется вполне подходящим вариантом.

У нас есть приложение, в котором у нас есть миллион человек в списке А, и нам нужно сопоставить их с десятками различных источников данных. (И несмотря на то, что утверждают некоторые из более педантичных комментариев, это не «недостаток дизайна», который является характером работы с беспорядочными данными «реального мира».)

Единственное, что, как мы обнаружили, работает достаточно хорошо до сих пор, - это использование комбинации гема namae (для разбора имен на стандартизированное первое, среднее, последнее, суффиксное представление) и гема text для вычисления левенштейна, звукового индекса, метафона и портера. оценки, И также fuzzy-string-match, который вычисляет оценку JaroWinkler (которая часто является лучшей из всех).

1. разобрать в стандартный формат, разделив последний, первый, средний суффикс, используя намаэ. Мы предварительно обрабатываем регулярное выражение для извлечения псевдонимов в форматах John "JJ" Doe или Samuel (Sammy) Smith.
2. подсчитайте ВСЕ оценки на очищенной версии полного имени (все заглавные буквы, убрать пунктуацию, фамилия первая) ... jarowinkler, soundex, levenshtein, metaphone, white, porter. (JaroWinkler и Soundex часто делают лучше всех.)
3. объявлять совпадение, если N баллов превышают индивидуально установленные пороговые значения. (Мы используем любые 2, которые проходят как проход)
4. если совпадений нет, попробуйте еще раз, используя только фамилию, имя, отчество инициалы с более высокими пороговыми значениями (например, более строгим соответствием).
5. По-прежнему нет совпадения, замените имя псевдонимом (если есть) и повторите попытку.

После некоторой настройки пороговых значений для каждого метода оценки мы получаем довольно хорошие результаты. YMMV.

Кстати, указание фамилии на первом месте очень важно, по крайней мере для JaroWinkler, поскольку обычно меньше вариаций в фамилиях (Смит почти всегда Смит, но имя может быть Том или Томми или Томас в разных источниках данных), и начало строка является наиболее "чувствительной" в JaroWinkler. Для "ROB SMITHE / ROBIN SMITHE" расстояние ДжароВинклера составляет 0,91, если вы сначала указываете имя, и 0,99, если вы сначала указываете фамилию.

Лучше всего, что вы, вероятно, найдете для этого кода, это драгоценный камень, который только что называется «текст».

https://github.com/threedaymonk/text

Он имеет ряд алгоритмов сопоставления: Расстояние Левенштейна, Метафон, Soundex и другие.

Я не думаю, что такая библиотека существует.

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

У Ruby есть очень хороший гем под названием text, и я сам обнаружил, что Text::WhiteSimilarity очень хорош, но он также реализует множество других тестов.

Первая попытка создания надежного решения для сопоставления человеческих имен / кластеризации в Ruby: https://github.com/adrianomitre/match_author_names