Jak wykonać dopasowanie rozmyte adresów pocztowych?

Chciałbym wiedzieć, jak dopasować adresy pocztowe, gdy ich format różni się lub gdy jeden z nich jest źle zapisany.

Do tej pory znalazłem różne rozwiązania, ale myślę, że są one dość stare i niezbyt wydajne. Jestem pewien, że istnieją lepsze metody, więc jeśli masz dla mnie referencje, jestem pewien, że jest to przedmiot, który może zainteresować kilka osób.

Rozwiązanie, które znalazłem (przykłady znajdują się w R):

• Odległość Levenshteina, która jest równa liczbie znaków, które musisz wstawić, usunąć lub zmienić, aby przekształcić jedno słowo w drugie.

  agrep("acusait", c("accusait", "abusait"), max = 2, value = TRUE) ## [1] "accusait" "abusait"

• Porównanie fonemów

  library(RecordLinkage) soundex(x<-c('accusait','acusait','abusait')) ## [1] "A223" "A223" "A123"

• Zastosowanie korektora pisowni (ostatecznie bayesowskiego, takiego jak Peter Norvig) , ale wydaje mi się , że nie jest zbyt wydajny pod adresem.

• Myślałem o skorzystaniu z sugestii Google, ale podobnie nie jest to bardzo skuteczne w przypadku osobistych adresów pocztowych.

• Możesz sobie wyobrazić stosowanie podejścia nadzorowanego przez uczenie maszynowe, ale musisz zapisać błędnie napisane żądania użytkowników, co nie jest dla mnie opcją.

Kiedy używasz R, możesz zajrzeć do pakietu strunistycznego i metryki odległości Jaro-Winklera, którą można wykorzystać w obliczeniach. Zostało to opracowane w US Census Bureau do łączenia.

Więcej informacji na temat odległości Jaro i Jaro-Winkler w tym czasopiśmie .

Aby porównać różne techniki dopasowania, przeczytaj ten artykuł

Istnieje wiele sprytnych sposobów na zwiększenie odległości Levenshteina, aby uzyskać pełniejszy obraz. Krótkie wprowadzenie do bardzo przydatnego modułu (dla pytona) o nazwie „ Fuzzy Wuzzy ” jest tutaj autorstwa zespołu SeatGeek.

Kilka rzeczy, które możesz zrobić, to częściowe podobieństwo ciągów (jeśli masz ciągi o różnej długości, powiedz m & n za pomocą m <n), to dopasowujesz tylko dla m znaków. Możesz również podzielić ciąg na tokeny (pojedyncze słowa) i sprawdzić, jak zestawy tokenów pasują do siebie lub ułożyć je alfabetycznie i uporządkować.

Inną popularną techniką wykrywania częściowych dopasowań ciągów (choć zwykle na poziomie dokumentu) jest półpasiec . Zasadniczo jest to podejście z ruchomym oknem, które wyodrębnia zestaw n-gramów dla docelowego słowa / dokumentu i porównuje je z zestawami n-gramów dla innych słów / dokumentów za pomocą współczynnika Jaccard . Manning i współpracownicy (2008) omawiają prawie duplikaty i półpasiec w kontekście wyszukiwania informacji.

W Pythonie napisałem ogólny probabalistyczny program do porównywania rozmytych danych, który wykona rozsądną pracę dopasowując dowolny typ danych:

https://github.com/robinl/fuzzymatcher

Jest w pamięci, więc prawdopodobnie nie chcesz go używać do dopasowywania zestawów danych powyżej około 100 000 wierszy.

Napisałem również podobny projekt dotyczący adresów w Wielkiej Brytanii, ale zakłada to, że masz dostęp do Addressbase Premium. Ten nie jest w pamięci, więc został użyty na około 100m adresów w Wielkiej Brytanii. Spójrz tutaj:

https://github.com/RobinL/AddressMatcher

Jeśli chcesz szybko to zrobić, polecam użycie libpostal do normalizacji adresów, a następnie umieszczę je w moim ogólnym programie fuzzymatcher ( pip install fuzzymatcher).

Przykłady użycia można znaleźć tutaj .