Взвешенный алгоритм поиска, чтобы найти как контакты

Question

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

Company A, 123 Any Street Suite 200, Anytown, AK 99012
Comp. A, 123 Any St., Suite 200, Anytown, AK 99012
CA, 123 Any Street Ste 200, Anytown, AK 99012

Я смотрел на расстояние Левенштейна по Имени, но это не кажется хорошим инструментом, так как они могли сокращать имя. Я ищу то, что соответствует максимально возможной информации.

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

Answer 1

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

1) Сократите список совпадений, используя (первые шесть символов) почтовый индекс. В основном вам нужно будет вычислить расстояние Левенштейна для двух струн и выбрать те, которые имеют расстояние не более 1 или 2. Вы можете заранее вычислить таблицу почтовых индексов и их «соседей Левенштейна», если вам действительно нужно ускорить поиск.

http://en.wikipedia.org/wiki/Levenshtein_distance

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

https://www.usps.com/send/official-abbreviations.htm

3) Преобразовать адрес в короткий код, используя алгоритм метафона. Это избавит от наиболее распространенных орфографических ошибок. Просто убедитесь, что ваша реализация может исключить все несловарные символы, передать номера без изменений и обработать несколько слов (убедитесь, что каждое слово отделено одним пробелом):

http://en.wikipedia.org/wiki/Metaphone

4) Получив результат с метафона, сравните адресные строки, используя расстояние Левенштейна. Рассчитайте процент от оценки изменения, разделив результат на количество символов в более длинной строке.

5) Повторите шаги 3 и 4, но теперь используйте адреса вместо адресов.

6) Рассчитайте оценку для каждой записи, используя следующую формулу: (Вес для адреса * Оценка адреса) + (Вес для имени * Оценка имени). Выберите свой вес в зависимости от того, что важнее. Я бы начал с .9 для адреса (поскольку адрес более конкретен) и .1 для имени, но вес может зависеть от вашего приложения. Выберите запись с самым низким счетом. Если оценка слишком высокая (скажем, выше .15, вы можете объявить, что совпадений нет).

Answer 2

Сейчас я не совсем понимаю, как это сделать, но все крупные компании-поставщики (FedEx, USPS, UPS), похоже, имеют способ сопоставления введенного вами адреса со своей базой данных и преобразования его в нормализованную форму. Поскольку я видел, что это происходит на нескольких веб-сайтах (на ум приходит Amazon), я предполагаю, что у этой функции есть API, но я не знаю, где ее искать и подходит ли она для ваших целей.

Просто мысль, хотя.

РЕДАКТИРОВАТЬ: Я нашел USPS API

Answer 3

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

@ RyanDelucchi, - это забавная проблема, но только после того, как вы ее решите. Итак, @SteveBering, я бы порекомендовал отправить ваш список контактов в службу обработки списка , которая будет отмечать дубликаты на основе адреса - в соответствии с рекомендациями USPS.

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

Answer 4

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

Я предполагаю, что этот человек предоставит имя, почтовый адрес, название города, название штата и почтовый индекс.

Если почтовый индекс указан в 9 цифрах или содержит дефис, я бы сократил его до 5 цифр. Я бы искал в базе данных все адреса, которые имеют этот почтовый индекс. [Запрос 1] Тогда я бы сравнил письмо о состоянии с письмом из базы данных. Если это не совпадение, я бы сказал об этом пользователю. То же самое касается названия города.

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

Так что я бы сделал регулярное выражение для поиска чисел и следующего пробела или запятой рядом с ним. Затем найдите позицию первого слова, которое не имеет точки (.) Или заканчивается запятой. У меня есть часть названия улицы, поэтому я мог бы сравнить строки, извлеченные ранее, или изменить запрос на имя улицы LIKE% streetName%.

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

Answer 5

Может быть, вместо того, чтобы использовать Левенштейна только для имени, это может быть полезно при использовании со всем строковым представлением контакта. Например, расстояние вашего первого примера до второго равно 7, а до третьего 9. Учитывая, что строки имеют длины 54, 50 и 45, это, по-видимому, относительно полезная и довольно простая мера подобия.

Answer 6

Для начала я бы, наверное, выполнил поиск по индексу. Это будет означать два этапа:

автономный режим: создание индекса всех адресов по их ключевым словам. Например, «Компания», «А» и «123» станут ключевыми словами для адреса, который вы указали выше. Вы могли бы сделать некоторую остановку, что означало бы для слов как "улица", Вы также добавили бы слово "st" в его индекс.

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

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

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

Answer 7

Дан и Брэдстрит делают это. Они берут деньги, потому что это действительно сложно. Там нет "стандартного" решения. В основном это болезненный выбор между такими услугами, как D & B или собственной.

Answer 8

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