стратегии поиска повторяющихся почтовых адресов

Question

Я пытаюсь придумать метод поиска повторяющихся адресов на основе показателя сходства.Рассмотрим эти повторяющиеся адреса:

addr_1 = '# 3 FAIRMONT LINK SOUTH'
addr_2 = '3 FAIRMONT LINK S'

addr_3 = '5703 - 48TH AVE'
adrr_4 = '5703- 48 AVENUE'

Я планирую применить некоторое преобразование строк, чтобы сократить длинные слова, например СЕВЕР -> N, удалить все пробелы, запятые, тире и символы решетки.Теперь, имея этот вывод, как я могу сравнить addr_3 с остальными адресами и обнаружить схожие?Какой процент сходства будет безопасным?Не могли бы вы предоставить для этого простой код Python?

addr_1 = '3FAIRMONTLINKS'
addr_2 = '3FAIRMONTLINKS'

addr_3 = '570348THAV'
adrr_4 = '570348AV'

Благодарен,

Эдуардо

Answer 1

Во-первых, упростите строку адреса, сжимая все пробелы в один пробел между каждым словом и переводя все в нижний регистр (или верхний регистр, если хотите):

adr = " ".join(adr.tolower().split())

Затем я бы удалил такие слова, как «st» в «41-й улице» или «nd» в «42-й улице»:

adr = re.sub("1st(\b|$)", r'1', adr)
adr = re.sub("([2-9])\s?nd(\b|$)", r'\1', adr)

Обратите внимание, что вторая функция sub() будет работать с пробелом между «2» и «nd», но я не настраивал для этого первую функцию;потому что я не уверен, как можно отличить «41 St Ave» от «41 St» (второе сокращенно — «41 Street»).

Обязательно прочтите всю справку по модулю re;это мощно, но загадочно.

Затем я бы разделил то, что у вас осталось, на список слов и применил алгоритм Soundex, чтобы составить список элементов, которые не похожи на числа:

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

http://wwwhomes.uni-bielefeld.de/gibbon/Forms/Python/SEARCH/soundex.html

adrlist = [word if word.isdigit() else soundex(word) for word in adr.split()]

Затем вы можете работать со списком или объединить его обратно в строку по своему усмотрению.

Вся идея Soundex заключается в обработке адресов с ошибками.Возможно, это не то, что вам нужно, и в этом случае просто проигнорируйте идею Soundex.

Удачи.

Answer 2

Удаление пробелов, запятых и тире будет неоднозначным.Лучше будет заменить их одним пробелом.

Возьмем, к примеру, этот адрес

56 5th avenue

И это

5, 65th avenue

с вашим методом они оба будут:

565THAV

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

Алгоритм может выглядеть следующим образом:

1. замените все запятые и тире пробелами.Используйте он переводить метод для этого.
2. Составьте словарь со словами и их сокращенной формой.
3. Удалить TH часть, если она следовала за номером.

Answer 3

Это должно быть полезно при составлении словаря сокращений:

http://www.usps.com/ncsc/lookups/usps_abbreviations.html

Answer 4

Чтобы сделать это правильно, вам необходимо стандартизировать свои адреса в соответствии со стандартами USPS (примеры ваших адресов, похоже, основаны на США).Существует множество поставщиков услуг прямого маркетинга, которые предлагают КАСС (Система поддержки точности кодирования) сертификация почтовых адресов.Процесс CASS стандартизирует все ваши адреса и добавит к ним zip + 4.Любые адреса, которые невозможно доставить, будут помечены, что еще больше снизит ваши расходы на почтовую пересылку, если вы этого хотите.Как только все ваши адреса будут стандартизированы, устранение дубликатов станет тривиальной задачей.

Answer 5

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

Если у вас большой набор данных, вам захочется использовать реализацию Левенштейна на C, а не на Python.У меня их было несколько десятков тысяч, и я думаю, что на их пробег ушла большая часть дня.

Answer 6

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

Что мне больше всего помогло, так это очистить и токенизировать адреса (избавиться от знаков препинания, разделить слова на слова), а затем просто посмотреть, сколько токенов совпадает.Поскольку адреса обычно имеют несколько токенов, вы можете повысить уровень уверенности с точки зрения комбинации (1) количества совпавших токенов, (2) количества числовой токены были сопоставлены и (3) сколько жетонов доступно.Например, если все токены с более коротким адресом находятся в более длинном адресе, вероятность совпадения довольно высока.Аналогично, если вы сопоставляете 5 токенов, включая хотя бы один числовой, даже если в каждом адресе по 8, это все равно совпадение с высокой степенью достоверности.

Определенно полезно внести некоторые изменения, например заменить некоторые распространенные сокращения.Списки USPS помогают, хотя я бы не стал с энтузиазмом пытаться реализовать их все, а некоторые из наиболее ценных замен не включены в эти списки.Например, «JFK» должно соответствовать «JOHN F KENNEDY», и существует несколько распространенных способов сократить «MARTIN LUTHER KING JR».

Возможно, это само собой разумеется, но я все равно скажу это для полноты картины:Не забудьте просто выполнить прямое сравнение строк по всему адресу, прежде чем приступать к более сложным вещам!Это должен быть очень дешевый тест, и, следовательно, его первый проход, вероятно, не составит труда.

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