Rozpoznawanie podobieństwa w łańcuchach znaków

Question

Pracuję nad systemem, który pozwala na importowanie plików do innych języków.

To jest głównie prywatny projekt, w którym można zdobyć MVC3, EntityFramework, LINQ, etcetera. Dlatego lubię robić szalone rzeczy, aby urozmaicić efekt końcowy, jedną z tych rzeczy będzie rozpoznawanie podobnych ciągów.

Wyobraź sobie następującą listę ciągów - pożyczone od gry, z którymi pracowałem w przeszłości:

• Megabeth: Holy Roller Uniform - obejmuje Głowa, tułów i nogi
• Megabeth: Holy Roller Uniform Szef
• Megabeth: Holy Roller Jednolite Nogi
• Megabeth: Holy Roller Uniform Torso
• Megabeth: PAX East 2012 Uniform - Zawiera Głowa, tułów i nogi
• Megabeth: PAX East 2012 Uniform Szef
• Megabeth: PAX East 2012 Jednolite Nogi
• Megabeth: PAX East 2012 Uniform Torso

Jak widać, gdy użytkownicy nie przetłumaczone pierwsze 4 struny, 4 następujących udział wiele podobieństw, w tym przypadku:

• Megabeth
• Uniform
• zawiera głowy, tułowia i nóg
• głowicy
• Nogi
• Torso

Rozważmy pierwsze 4 łańcuchy są rzeczywiście już przetłumaczony, kiedy użytkownik wybiera 5th ciąg z listy, jaką algorytmu lub techniki można użyć, aby pokazać użytkownikowi 1 ciąg (i potencjalnie inne) pod sub nagłówek "podobne ciągi"?

Edytuj - Mały komentarz na temat Levenshtein Odległość: Obecnie szukam ciągów 10k w bazie danych. Levenshtein Distance porównuje łańcuch na łańcuch, czyli w tym przypadku 10k x (10k -1) możliwych kombinacji. Jak podejść do tego w możliwy sposób? Czy istnieje lepsze rozwiązanie tego konkretnego algorytmu?

Answer 1

Można zajrzeć do Levenshtein Distance. Te poniżej pewnego progu będą uważane za podobne. Dwa identyczne łańcuchy będą miały odległość zero.

Istnieje implementacja C#, między innymi, na Rosetta Code.

Answer 2

To będzie zależeć od wielkości danych i tego, jak bogate jest słownictwo. Oto pierwsza myśl: zbuduj mapę słów na ciągi znaków , a następnie kolejną mapę par słów do ciągów znaków i być może, jeśli dane nie są ogromną mapą trojaków łańcuchowych na ciągi. Usuń odwzorowania, które wskazują jeden ciąg (spowoduje to znaczne zmniejszenie liczby odwzorowań tripletów). Zapisz wynikowy słownik na dysku lub w bazie danych, jeśli budowanie go zajmuje czas.

Teraz podany ciąg powinien być w stanie szybko podzielić go na słowa, pary słów i triole i wyszukać wszystkie powiązane z nim ciągi. Będziesz musiał grać z podaniem wagi trójce pasującej do dopasowania 4 słów. To znaczy. jest "Jestem starcem", bliższym "staruszkowi zjadł marchewkę" lub "człowiekiem zabił starego psa ze strzałą" (brzmi jak mecz trójki jest ważniejsze).

AKTUALIZACJA: Jeśli w bazie danych Microsoft SQL Server można odtwarzać z funkcją wyszukiwania pełnotekstowego. Jednak nigdy tego nie próbowałem. Powinieneś również rzucić okiem na Lucene.