Как сделать нечеткое совпадение почтовых адресов?

Я хотел бы знать, как сопоставить почтовые адреса, когда их формат отличается или когда один из них введен неправильно.

Пока я нашел разные решения, но думаю, что они довольно старые и не очень эффективные. Я уверен, что существуют лучшие методы, так что если у вас есть ссылки для чтения, я уверен, что эта тема может заинтересовать несколько человек.

Решение, которое я нашел (примеры в R):

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

  agrep("acusait", c("accusait", "abusait"), max = 2, value = TRUE) ## [1] "accusait" "abusait"

• Сравнение фонем

  library(RecordLinkage) soundex(x<-c('accusait','acusait','abusait')) ## [1] "A223" "A223" "A123"

• Использование корректора орфографии (в конечном итоге байесовского типа, как у Питера Норвига) , но, по-моему, не очень эффективно по адресу.

• Я думал об использовании предложений Google предложить, но аналогично, это не очень эффективно на личных почтовых адресах.

• Вы можете вообразить, что используете подход с машинным обучением, но вам нужно хранить неверные запросы пользователей, что для меня не вариант.

Поскольку вы используете R, вы можете захотеть взглянуть на пакет stringdist и метрику расстояния Джаро-Винклера, которую можно использовать в вычислениях. Это было разработано в Бюро переписей США для связи.

Для получения дополнительной информации о расстоянии Jaro и Jaro-Winkler в этом журнале .

Для сравнения различных методов сопоставления, прочитайте эту статью

Есть много умных способов увеличить расстояние Левенштейна, чтобы дать более полную картину. Краткое введение в довольно полезный модуль (для python) под названием « Fuzzy Wuzzy » находится здесь командой SeatGeek.

Пара вещей, которые вы можете сделать, это частичное сходство строк (если у вас есть строки различной длины, скажем, m & n с m <n), то вы подходите только для m символов. Вы также можете разделить строку на токены (отдельные слова) и посмотреть, как наборы токенов совпадают или расположить их в алфавитном порядке и упорядочить.

Другой популярный метод обнаружения частичных совпадений строк (хотя, как правило, на уровне документа) - это шипение . По сути, это подход с движущимся окном, который извлекает набор n-грамм для целевого слова / документа и сравнивает их с наборами n-грамм для других слов / документов с помощью коэффициента Жакара . Мэннинг и коллеги (2008) обсуждают близкие дубликаты и опоясывающий лишний в контексте информационного поиска.

Я написал общий вероятностный нечеткий сопоставитель в Python, который будет выполнять разумную работу по сопоставлению данных любого типа:

https://github.com/robinl/fuzzymatcher

Он находится в памяти, так что вы, вероятно, не хотите использовать его для сопоставления наборов данных, которые превышают около 100 тыс. Строк.

Я также написал аналогичный проект специально для адресов в Великобритании, но это предполагает, что у вас есть доступ к Addressbase Premium. Этот не находится в памяти, поэтому использовался против 100-метровых адресов Великобритании. Посмотреть здесь:

https://github.com/RobinL/AddressMatcher

Если вы хотите ускорить процесс, я бы рекомендовал использовать libpostal для нормализации ваших адресов, а затем направить их в мой общий fuzzymatcher ( pip install fuzzymatcher).

Вы можете найти примеры использования здесь .