Как определить соответствие между двумя списками имен?

Question

У меня есть: 1 миллион имен студентов университетов и 3 миллиона имен клиентов банков

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

Можно ли добиться этого с помощью ICC?Как работает двусторонняя случайная выборка ICC?

Пожалуйста, ответьте как можно скорее, поскольку мне это необходимо срочно.

Answer 1

Этот вид разрешения сущностей и т. Д. Обычно прост, но я удивлен подходом хеширования.Хеширование теряет информацию, которая имеет решающее значение для разрешения сущности.Поэтому, если это возможно, вам не следует использовать хеш, а скорее исходные строки.

Предполагая, что использование исходных строк является опцией, вы захотите сделать что-то вроде этого:

Список A (1M), список B (3M)

// First, match the entities that match very well, and REMOVE them.
for a in List A
  for b in List B
    if compare(a,b) >= MATCH_THRESHOLD   // This may be 90% etc
       add (a,b) to matchedList
       remove a from List A
       remove b from List B

// Now, match the entities that match well, and run bipartite matching
// Bipartite matching is required because each entity can match "acceptably well"
// with more than one entity on the other side
for a in List A
  for b in List B
    compute compare(a,b)
    set edge(a,b) = compare(a,b)
    If compare(a,b) < THRESHOLD // This seems to be 60%
       set edge(a,b) = 0

// Now, run bipartite matcher and take results

Временная сложность этого алгоритма составляет O (n1 * n2), что не очень хорошо.Есть способы избежать этой стоимости, но они зависят от вашей конкретной функции разрешения сущности.Например, если фамилия должна совпадать (для сокращения на 60%), вы можете просто создать списки в A и B, которые разделены первой парой символов фамилии, и просто запустить этот алгоритм между соответствующимисписок.Но вполне возможно, что фамилия «Nuth» должна совпадать с «Knuth» и т. Д. Итак, некоторые локальные знания о том, что такое функция сравнения имен, могут помочь вам лучше разделить и победить эту проблему.