Алгоритм сопоставления адресов

Question

У меня есть список адресов в двух отдельных таблицах, которые немного не совпадают, и мне нужно иметь возможность сопоставлять их. Например, один и тот же адрес может быть введен несколькими способами:

• 110 Test St
• 110 тест св.
• 110 Test Street

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

Например. ключ может быть «11TEST» - первые два из 110, первые два из Test и первые два из уличного варианта. Ключ полного соответствия также должен включать первые 5 почтовых индексов, поэтому в приведенном выше примере полный ключ может выглядеть как «11TEST44680».

Я ищу идеи для эффективного алгоритма или ресурсов, на которые я могу обратить внимание при разработке этого. Любые идеи могут быть псевдокодом или на выбранном вами языке.

Мы занимаемся только адресами США. На самом деле, мы рассматриваем только адреса из 250 почтовых индексов из Огайо и Мичигана. У нас также нет доступа к любому почтовому программному обеспечению, хотя мы были бы открыты для идей относительно экономически эффективных решений (по сути, это было бы одноразовое использование). Пожалуйста, помните, что это начальный дамп данных из правительственного источника, поэтому предложения о том, как пользователи могут его очистить, полезны, когда я создаю приложение, но я хотел бы получить наилучшую начальную версию, какую только возможно, благодаря возможности сопоставлять адреса как как можно лучше.

Answer 1

Я работаю над аналогичным алгоритмом, как мы говорим, он должен обрабатывать адреса в Канаде, США, Мексике и Великобритании к тому времени, как я закончу. Проблема, с которой я сталкиваюсь, заключается в том, что они находятся в нашей базе данных в формате открытого текста из 3 полей [кто бы ни подумал, что , что - это хорошая идея, это должно быть застрелено ИМХО], поэтому стараюсь обрабатывать сельские маршруты, общие поставки, приемники большого объема, несколько стран, провинция или штат, округ, почтовые индексы и почтовые индексы, орфографические ошибки - это не маленькая или простая задача.

Одни только орфографические ошибки были немалым подвигом - особенно когда вы добираетесь до стран, которые используют французские имена - сопоставление святых, святых, святых, святых, святых, святых, святых, великих, гранд, грандов, гранд с или без периода или переносы большей части имени не вызывают проблем с производительностью, особенно когда St может означать улицу saint или и может или не может быть введен в правильном контексте (то есть женский или мужской). Что делать, если адрес в основном введен правильно, но имеет неправильный провинцию или почтовый индекс?

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

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

Приветствия - [Бен в афсинк точка ча]

Answer 2

Если вы предпочитаете не разрабатывать и не использовать готовый продукт, в котором используются многие из упомянутых здесь технологий, см .: http://www.melissadata.com/dqt/matchup-api.htm

Отказ от ответственности: Я принимал участие в его разработке и работе в компании.

Answer 3

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

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

Answer 4

Если бы я попытался это сделать, я бы преобразовал каждую строку адреса в дерево, используя предопределенный порядок операций.

Например. 110 Test Street Apt 3. Anywhere California 90210 =>

1. Получить тип адреса. Например, адреса улиц имеют разные форматы, чем адреса сельских маршрутов, и это зависит от страны.
2. Учитывая, что это адрес улицы, получите строку, которая представляет тип улицы, и преобразуйте ее в перечисление (eBoulevard, eRoad и т. Д.)
3. Учитывая, что это адрес улицы, вытащите название улицы (сохраните в нижнем регистре)
4. Учитывая, что это адрес улицы, вытащите номер улицы

5. Учитывая, что это адрес улицы, найдите любой номер квартиры (может быть перед номером улицы с тире, может быть после "Apt." И т. Д.)

      eStreet  //1.an enum of possible address types eg. eStreet, eRuralRoute,...
         |
      eStreet        //2.an enum of street types eg. eStreet, eBlvd, eWay,...
      /   |   \
   

   Имя Номер Апт | | | тест 110 3

Например. RR # 3 Anywhere California 90210 =>

1. Получить тип адреса: сельский маршрут

2. Учитывая, что это адрес сельского маршрута, получите номер маршрута

      eRuralRoute 
         |
         3
   

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

Затем сравните получившиеся деревья.

Это делает сравнение очень простым, однако код для генерации деревьев очень сложен. Вы бы хотели проверить это на тысячах и тысячах адресов. Ваша проблема проще, если вас интересуют только адреса США; Британские адреса, как уже упоминалось, довольно разные, и в канадском адресе может быть французский (например, Place D'Arms, Rue Laurent и т. Д.) *

Answer 5

В Великобритании мы будем использовать:

• Название или номер дома (если название включает номер квартиры для многоквартирных домов)
• Почтовый индекс

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

Ваш пример не будет различать 11 Тест-стрит, 110 - 119 Тест-стрит и т. Д.

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

Answer 6

используйте идентификатор для первичного ключа , он всегда будет уникальным и упростит объединение дубликатов позже.

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

есть два процесса "сохранить"

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

очистить данные. Попробуйте удалить слова "улица", "улица", "диск" и т. Д. И сохранить его как символ StreetType (1), который использует FK для таблицы, содержащей правильные сокращения, чтобы вы могли построить улицу.

посмотрите на SOUNDEX и DIFFERENCE

Я работал в крупных компаниях, которые ведут списки рассылок, и они не пытались делать это автоматически, они использовали людей, чтобы отфильтровывать новое от дураков, потому что это очень сложно сделать. Запланируйте функцию слияния, чтобы вы могли вручную объединять дубликаты при их возникновении и распределять значения через PK.

Вы можете заглянуть в API карт Google и посмотреть, сможете ли вы передать свой адрес и получить ответный матч. Я не знаком с этим, это просто предположение.

Answer 7

Если вы не решили использовать существующую систему, одна из идей заключается в следующем:

• Извлечение чисел из адресной строки
• заменить обычные уличные слова пробелами
• создать строку соответствия

т.е.: "555 Canal Street":

• Номер выписки дает "555" + "Улица канала"
• Замена уличных слов дает "555" + "Канал"
• Создание строки совпадения дает "555Canal"

"Канал St 555" даст ту же строку соответствия.

Под уличными словами я подразумеваю слова и сокращения «улица» в вашем языке, например, «st», «st.», «Blv», «ave», «avenue» и т. Д. И т. Д., Все они удаляются из строки .

Извлекая числа и отделяя их от строки, не имеет значения, являются ли они первыми или последними.