Porównanie inteligentnych ciągów znaków

Question

Szukam biblioteki/klasy, która umożliwia inteligentną porównywanie dwóch ciągów. W najlepszym przypadku dałoby to w wyniku procent tego, jak dwa łańcuchy są podobne. Porównywuję nazwy firm, adresy rejestrowane w różnych repozytoriach, co powoduje wiele błędów ortograficznych lub niespójności w nazwach.

Przykładowe ciągi do porównania:

"Good Company Ltd." vs. "GoodCompany" 
"Baker Street 2" vs. "Baker Str. 2" 

Gdybym uzyskać wynik w procentach alikeness, niż może to być wejście do inteligentnego scalenia tych danych.

Czy znasz jakieś dobre biblioteki, które umożliwiłyby porównywanie takich inteligentnych ciągów?

Answer 1

Levenshteina nie jest odpowiednie w tym przypadku. "Good Company Ltd" i "GoodCompany", jeśli przycięte mają odległość = 3, natomiast "Good Company Ltd" i "Food Company Ltd" mają odległość 1, ale mają zupełnie inne znaczenie. Sugeruję algorytm Metaphone or Double Metaphone.

Korzystanie online metaphone comparer wyniki są następujące:

Good Company Ltd = KTKMPNLTT 
GoodCompany = KTKMPN 
Food Company Ltd = FTKMPNLTT 
GoodCompanyLLC = KTKMPNLK 

W ten sposób wiesz, że GoodCompany, Good Company Ltd i GoodCompanyLLC są podobne, natomiast Food Company jest błędnie lub całkowicie nie związane (KTKMPN zawarty jest zarówno w KTKMPNLTT i KTKMPNLK, ale nie w FTKMPNLTT).

Poszukaj innych porównań algorytmów: here.

Answer 2

Być może zechcesz poszukać implementacji Levenshtein Distance. Pokazuje liczbę wstawień/delecji i zastąpień znaków, aby dwa ciągi były równe.

Oto post o bibliotekach w C#, które implementują Levenshtein Distance i inne algorytmy porównywania tekstu: .NET library for text algorithms?.

Jednak myślę, że będziesz musiał użyć jakiejś kombinacji metod, ponieważ użycie Levenshtein powie Ci, że "Good Company Ltd." jest bardziej podobny do "Bad Company Ltd." niż do "GoodCompany".

Być może będziesz musiał zrobić kilka preprocessing przez rozszerzenie "str." do "ulicy" i usunięcia "Ltd." jako słowo "bez znaczenia" w kategoriach porównywania ciągów.

UPDATE 1

Francesco De Lisi suggests używać algoritms fonetycznych. Wygląda na to, że lepiej nadają się do porównywania błędnych nazw. Nadal będziesz musiał podzielić adresy na części fonetyczne/niefonetyczne (takie jak numery budynków) i porównać je oddzielnie.

UPDATE 2

Co do porównania adresów, ten post suggests to use Google Maps API do tego celu i innym poście omówiono address parsing. Domyślam się, że Google może uzyskać wiarygodne wyniki, ponieważ ma bazę danych adresów ulic, w których może znaleźć najbardziej poprawną pisownię nazw ulic. Bez listy poprawnych nazw ulic/firm możesz napotkać dziwną nazwę, która jest nieprawidłowa, jednak wiele różnych poprawnych nazw byłoby do niej podobnych.

Answer 3

Co szukasz jest Levenshtein distance (Wikipedia):

... odległość Levenshteina jest ciągiem metryki do pomiaru różnicy między dwiema sekwencjami. Nieformalnie odległość Levenshteina dwóch słów jest minimalna ilość modyfikacje pojedynczych znaków (insercji, delecji, substytucji) wymagane do zmiany jednego słowa w drugiej