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

14

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

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

Решение, которое я нашел (примеры в 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 предложить, но аналогично, это не очень эффективно на личных почтовых адресах.

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

Стефани С
источник
Я бы предложил использовать реальную базу данных, которая поддерживает нечеткое сопоставление строк: posgres . Это будет эффективно.
Эмре
Только для США, Канады, Великобритании, Франции, Японии, нескольких стран ...? Предположительно для каждого вы сначала определяете / угадываете, какой это язык и страну, а затем применяете классификатор для конкретной страны? Есть ли у вас учебный комплект и, если да, как он распределяется по странам?
smci
Где вы в конечном итоге с этим? Решение, которое мы разработали, состояло в том, чтобы вычистить и обогатить адреса и географические названия, использовать геокодирование Google и разместить веб-API, а затем выполнить некоторые грубые вычисления, чтобы определить правильный результат по сравнению с необработанными данными. Это немного неуклюже, но работает, но должен быть более элегантный способ нормализовать адреса и места / местоположения.
Крис Смит

Ответы:

9

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

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

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

phiver
источник
4

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

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

DMB
источник
4

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

Брэндон Лудермилк
источник
4

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

https://github.com/robinl/fuzzymatcher

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

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

https://github.com/RobinL/AddressMatcher

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

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

RobinL
источник
Привет, Робин, мне интересна твоя библиотека AddressMatcher. У вас есть документация о том, как его использовать? У меня есть именно эта проблема - нужно сопоставить 1 набор адресов (грязный) с другим (официальные почтовые адреса). Спасибо
SCool
1
к сожалению, с сопоставителем адресов это совсем не тривиально, и у меня нет хорошей документации. Главное, что вам нужно - загрузить коммерческий продукт addressbase premium, в postgresql.
RobinL
Хорошо, спасибо, что вернулся ко мне. Я работаю с, я полагаю, ирландской версией Premium Addressbase под названием Eircode, которая будет несовместима. Как вы думаете, нечеткий сопоставитель будет соответствовать задаче сопоставления адресов в производственной среде? Я просто хочу добавить почтовые индексы к адресам в моих данных, в которых их нет, например, выполнить поиск в базе данных Eircode '1 Main Street, Some Town, County'и, если я найду совпадение, вернуть почтовый индекс.
SCool
1
Нечеткое совпадение - да, я определенно думаю, что стоит попробовать. он должен работать достаточно хорошо, чтобы небольшой список адресов находился в большом списке аутентификационных адресов (например, eircode) на сложной машине. Другой вариант - это pakakge fastlink в R
RobinL