Dopasowany odmienne ciągi

Załóżmy dwa komplety strun:Dopasowany odmienne ciągi

[ "Mr. Jones", "O'Flaherty", "Bob", "Rob Jenkins" ] 
[ "Maxwell O'Flaherty", "Robert Jenkins", "Mrs. Smith" ]

Jest oczywiste, że te dwa zespoły mają Maxwell O'Flaherty i Robert Jenkins wspólnego.

Czy istnieje algorytm, który pozwoli nam na takie programowanie? Zastanawiam się nad napisaniem czegoś, co przejdzie przez każdy element w szeregu ciągów znaków i spróbuję znaleźć dowolny podciąg, który jest unikalny i nie jest zawarty w żadnym innym elemencie żadnego z zestawów, a następnie użyć go jako swego rodzaju hash każdego elementu aby dopasować dwa zestawy.

Źródło

2010-11-13 devprog

Należy ujawnić, jakie nazwy należy traktować tak samo. Ponieważ nie znam angielskich nazwisk, nie jest dla mnie oczywiste, że "te dwa zestawy mają wspólne cechy Maxwella O'Flaherty'ego i Roberta Jenkinsa". I nie oczywiste dla kompilatora C#. Jeśli chodzi o ciebie, to nie jest oczywiste, że "Sasha Iwanow" i "Aleksander Pietrowicz Iwanow" jest taki sam, ale nie taki sam jak "Aleksiej Iwanow". – Vovanium

Zgadzam się, komputer miałby najmniejszą szansę na dopasowanie Sashy i Alexandra, ponieważ pasowałoby do Richarda i Dicka. Problemem nie są nazwiska, ale po prostu dopasowanie podobnych ciągów. – devprog

Prawdopodobnie jest to duplikat: [http://stackoverflow.com/questions/83777/are-there-any-fuzzy-search-lub-symilar-functions-libraries-written-for-c](http:/ /stackoverflow.com/questions/83777/are-there-any-fuzzy-search- or-string-similarity-functions-libraries-written-for-c) –

Możesz odszukać odległość Levenshtein użyteczną. Jeśli robisz dużo tego, gdzie nie jest jasne, jak dokładne są te informacje, istnieją biblioteki do ujednoznaczniania ciągów znaków. (To nie jest "oczywiste", że Rob i Robert są identyczni - w rzeczywistości pierwszy może być Robin.

Źródło

2010-11-13 14:27:37

Patrzę na odległości levenshtein według pierwszej odpowiedzi. Rozumiem jednak, że mogą jedynie powiedzieć, jak blisko są struny i nie mogą zagwarantować, że ludzki sens Roba to Robert, a nie Robin. Będę musiał znaleźć sposób porównania odległości pomiędzy wszystkimi elementami zestawu, aby ustalić średnią, poniżej której coś nie może być uznane za dopasowanie. – devprog

Jeśli jest to przykład z prawdziwego świata i potrzebujesz dokładnego dopasowania na nazwisko lub nazwisko, a następnie sparsuj cały łańcuch w drugiej tablicy i stwórz nowa tablica ze wszystkimi przeanalizowanymi podciągami i indeksem magazynu do oryginalnych elementów tablicy, których częścią jest fragment:

[{"Maxwell", 0}, {"O'Flaherty", 0}, {"Robert", 1} { "Jenkins", 1}, { "Pani", 2}, { "Smith", 2}]

teraz można znaleźć dokładne dopasowanie i wiem, do czego człowiek się odnosi.

Źródło

2010-11-13 14:57:55 Dialecticus

Element imię i nazwisko jest tylko przykładem, mogą to być dowolne ciągi, więc nie chciałem polegać na identyfikacji pojedynczych elementów, takich jak imiona i nazwiska. Dziękuję za odpowiedź. – devprog

One podejście I'v W przeszłości stosowano takie rozwiązania, jak Robert vs Bob, poprzez wysyłanie zapytań do źródeł internetowych, które mogą zidentyfikować podobieństwa.

Na przykład, nie wiem o automatycznych zasadach wyszukiwania Wolframa Alphy (chociaż myślę, że pracowali nad API w pewnym momencie), ale poszukiwanie Roberta (http://www.wolframalpha.com/input/?i=robert) wskazywałoby, że powinno ono być dopasowane do nazwa "Rob".

Nie jest to programowanie automatyczne, ale zauważyłem, że inteligentne wykorzystanie mechanizmu Mechanical Turk firmy Amazon działa cuda w przypadku tego typu problemów, jeśli zbiór danych jest dość ograniczony.

Źródło

2010-11-14 17:49:39

Dopasowany odmienne ciągi

Odpowiedz

Powiązane problemy