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

StackOverflow https://stackoverflow.com/questions/824588

Вопрос

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

  • 110 Тестовый Ст
  • 110 Тестовая Ул.
  • Тестовая улица , 110

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

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

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

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

Это было полезно?

Решение

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

Одни только орфографические ошибки были немалым подвигом - особенно когда вы попадаете в страны, использующие французские названия - сопоставление Saint, Saintes, St, Ste, Saints, Saintes, Sts, Stes, Grand, Grande, Гранды, Grandes с точкой или переносом в большей части имени или без них вызывает бесконечные проблемы с производительностью - особенно когда St может означать святой или улица и могут быть введены , а могут и не быть введены в правильном контексте (т.е.женское начало противмужской).Что делать, если адрес в основном был введен правильно, но имеет неправильную провинцию или почтовый индекс?

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

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

Приветствия - [бен в afsinc dot, Калифорния]

Другие советы

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

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

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

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

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

В вашем примере не было бы различий между 11 Тестовой улицей, 110 - 119 Тестовой улицей и т.д.

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

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

Например.Тестовая улица, 110, квартира 3.Где угодно, Калифорния 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 В любом месте Калифорнии 90210 =>

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

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

       eRuralRoute 
      |
      3

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

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

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

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

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

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

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

ie:"Канал-стрит, 555":

  • Номер выписки дает "555" + "Канал-стрит".
  • Замена уличных слов дает "555" + "Канал".
  • Строка Create match выдает "555Canal"

"Canal st 555" выдал бы ту же строку соответствия.

Под уличными словами я подразумеваю слова и сокращения для обозначения "street" на вашем языке, например "st", "st.", "blv", "ave", "avenue" и т.д. И т.п. Все они удалены из строки.

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

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

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

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

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

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

посмотрите на SOUNDEX и РАЗНИЦУ

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top