Jakiego algorytmu najlepiej użyć do podobieństwa ciągów?

Projektuję wtyczkę, aby jednoznacznie identyfikować zawartość na różnych stronach internetowych na podstawie adresów.

Mogę więc mieć jeden adres, który wygląda następująco:

1 someawesome street, anytown, F100 211

później mogę znaleźć ten adres w nieco innym formacie.

1 someawesome street, F100 211,

a może tak niejasne jak

someawesome street F100

Są to technicznie ten sam adres, ale z pewnym podobieństwem. Chciałbym a) wygenerować unikalny identyfikator dla każdego adresu w celu przeprowadzenia wyszukiwania, oraz b) dowiedzieć się, kiedy pojawi się bardzo podobny adres.

Na jakie algorytmy / techniki / metryki ciągów powinienem patrzeć? Odległość Levenshteina wydaje się oczywistym wyborem, ale ciekawa, czy istnieją inne podejścia, które by się tu nadawały.

Algorytm Levensteina opiera się na liczbie wstawek, usunięć i podstawień w łańcuchach.

Niestety nie bierze się pod uwagę typowego błędu pisowni, jakim jest transpozycja 2 znaków (np. Niektóre niesamowite i niektóre małe). Wolałbym więc bardziej niezawodny algorytm Damerau-Levensteina .

Nie sądzę, że dobrym pomysłem jest stosowanie odległości do całych strun, ponieważ czas gwałtownie rośnie wraz z długością porównywanych strun. Co gorsza, po usunięciu składników adresu, takich jak ZIP, zupełnie inne adresy mogą pasować lepiej (mierzone za pomocą internetowego kalkulatora Levenshtein ):

1 someawesome street, anytown, F100 211       (reference) 
1 someawesome st.,anytown                     (difference of 15, same address)     
1 otherplaces street,anytown,F100211          (difference of 13, different ddress) 
1 sameawesome street, othertown, CA98200      (difference of 13, different ddress)
anytown, 1 someawesome street                 (28 different same address)
anytown, F100 211, 1 someawesome street       (37 different same address)

Efekty te pogarszają się w przypadku krótszych nazw ulic.

Lepiej więc użyj inteligentniejszych algorytmów. Na przykład Arthur Ratz opublikował w CodeProject algorytm do inteligentnego porównywania tekstu. Algorytm nie drukuje odległości (z pewnością można go odpowiednio wzbogacić), ale identyfikuje pewne trudne rzeczy, takie jak przenoszenie bloków tekstowych (np. Zamiana między miastem a ulicą między moim pierwszym przykładem a ostatnim przykładem).

Jeśli taki algorytm jest zbyt ogólny dla twojego przypadku, powinieneś naprawdę pracować według komponentów i porównywać tylko porównywalne komponenty. Nie jest to łatwe, jeśli chcesz przeanalizować dowolny format adresu na świecie. Ale jeśli cel jest bardziej konkretny, powiedzmy w USA, z pewnością jest wykonalny. Na przykład „ulica”, „st.”, „Miejsce”, „plac” i ich zwykłe błędy ortograficzne mogą ujawnić uliczną część adresu, której wiodącą częścią byłaby w zasadzie liczba. Kod pocztowy pomógłby zlokalizować miasto lub alternatywnie jest to prawdopodobnie ostatni element adresu, a jeśli nie lubisz zgadywania, możesz poszukać listy nazw miast (np. Pobierając darmową bazę kodów pocztowych). Następnie można zastosować Damerau-Levenshtein tylko na odpowiednie składniki.

Odległość Levenshteina jest lepsza dla słów

Jeśli słowa są (głównie) poprawnie napisane, spójrz na worek słów . I może wydawać się zabić, ale tfidf i cosinus podobieństwa .

Lub możesz skorzystać z darmowej Lucene. Myślę, że robią podobieństwo cosinus.

Po pierwsze, musisz przeanalizować stronę internetową pod kątem adresów, RegEx jest napisany do wzięcia, jednak bardzo trudno jest przeanalizować adresy przy użyciu RegEx. Najprawdopodobniej musiałbyś przejrzeć listę potencjalnych formatów adresowania i świetne jedno lub więcej pasujących do nich wyrażeń. Nie jestem zbyt obeznany z analizowaniem adresów, ale polecam przyjrzeć się temu pytaniu, które podąża podobną myślą: Ogólny parser adresów dla tekstu swobodnego.

Odległość Levenshteina jest przydatna, ale dopiero po rozdzieleniu adresu na części. Rozważ następujące adresy. 123 someawesome st.i 124 someawesome st.Te adresy to zupełnie inne lokalizacje, ale ich odległość Levenshteina wynosi tylko 1. Można to również zastosować do czegoś podobnego 8th st.i 9th st.podobne nazwy ulic zwykle nie pojawiają się na tej samej stronie, ale nie jest to niespotykane. Strona szkoły może na przykład mieć adres biblioteki po drugiej stronie ulicy lub kościoła kilka przecznic dalej. Oznacza to, że jedynymi danymi, do których z łatwością można wykorzystać odległość Levenshteina, są odległości między 2 punktami danych, takie jak odległość między ulicą a miastem.

Jeśli chodzi o ustalenie, jak oddzielić poszczególne pola, jest to dość proste, gdy sami otrzymamy adresy. Na szczęście większość adresów ma bardzo specyficzne formaty. Przy odrobinie czarodziejstwa RegEx powinno być możliwe rozdzielenie ich na różne pola danych. Nawet jeśli adres nie jest dobrze sformatowany, wciąż jest nadzieja. Adresy zawsze (prawie) są zgodne z rzędem wielkości. Twój adres powinien znajdować się gdzieś na liniowej linii, takiej jak ta, w zależności od ilości dostarczonych informacji i tego, co to jest:

StreetNumber < Street < City < State < Country

Zdarza się to rzadko, jeśli w ogóle adres przeskakuje z jednego pola do nie sąsiadującego. Bardzo często nie zobaczysz ulicy niż kraju ani ulicy, a następnie miasta.

Pytasz o algorytmy podobieństwa ciągów, ale ciągi są adresami. Prześlę adresy do interfejsu API lokalizacji, takiego jak Google Place Search, i wykorzystam formatted_addressjako punkt porównawczy. To wydaje się najbardziej dokładne podejście.

W przypadku ciągów adresów, których nie można zlokalizować za pomocą interfejsu API, można wrócić do algorytmów podobieństwa.

Jeden fajny algorytm, który jest użyteczny, ale wymaga wcześniej ustalonej bazy danych wcześniejszych odpowiedzi, nazywa się: Odległość edycji linii.

Odległość edycji linii jako funkcja może zwrócić „jak bardzo różnią się te dwa słowa”.

Słowo „dogmat” i „pies”, otrzymasz wartość 3 (dla 3 dodatkowych znaków).

Lub „kot” i „kapelusz”, odzyskaj wartość 1 (dla jednej innej postaci).

(Źródło: https://en.wikipedia.org/wiki/Edit_distance )

Rzeczywiście, użycie jakiejś funkcji odległości wydaje się dobrym podejściem. Problemem jest jednak znalezienie najbliższego ciągu z podanego adresu, co wcale nie jest trywialne.

Opisujesz tutaj szeroką kategorię algorytmów. Sprawdź wyszukiwanie najbliższego sąsiada

Jak wspomniano w komentarzu, jeśli znajdziesz sposób na rozdzielenie składników adresu (nazwa ulicy, numer itp.), Znacznie ułatwi to zadanie.

LongestCommonSubsequence (z tekstu wspólnego Apache) może być innym podejściem do próby z adresami. Jeśli zdefiniujesz podobieństwo dwóch jako stosunek „ wspólnej długości podsekwencji / maksimum (długości adresów) ”, możesz zastosować próg tolerancji - np. 0,8, który zdefiniuje dopasowanie / brak dopasowania. W ten sposób możesz dopasować adresy takie jak „ 1 someawesome st., Anyown ” i „ 1 someawesome street., Anyown ”.

To nie jest super szybki algorytm, więc możesz chcieć zastosować szybkie powrotu po awarii, aby zminimalizować porównania. Przykładem może być - unikaj porównania, jeśli kody pocztowe nie pasują lub wyodrębniona cyfra różni się tylko sekwencją.