Ähnlichkeiten in Strings erkennen

Question

Ich arbeite an einem System, mit dem importierte Dateien in andere Sprachen lokalisiert werden können.

Dies ist meist ein privates Projekt, um MVC3, EntityFramework, LINQ, usw. in den Griff zu bekommen. Deshalb mag ich einige verrückte Dinge, um das Endergebnis aufzupeppen, eines dieser Dinge wäre die Erkennung ähnlicher Strings.

Stellen Sie sich die folgende Liste von Strings haben - von einem Spiel geliehen ich in der Vergangenheit gearbeitet habe:

• Megabeth: Holy Roller Uniform - Mit Kopf, Torso und Beine
• Megabeth: Holy Roller Uniform Kopf
• Megabeth: Holy Roller Uniform Beine
• Megabeth: Holy Roller Uniform Torso
• Megabeth: PAX East 2012 Uniform - Mit Kopf, Torso und Beine
• Megabeth: PAX East 2012 Uniform Kopf
• Megabeth: PAX East 2012 Uniform Beine
• Megabeth: PAX East 2012 Uniform Torso

Wie Sie sehen können, sobald der Benutzer die ersten 4 Strings übersetzt haben, die folgenden 4 teilen sich eine Menge von Ähnlichkeiten, in diesem Fall:

• Megabeth
• Uniform
• Ist mit Kopf, Torso und Beine
• Kopf
• Beine
• Torso

Betrachten Sie die ersten 4 Strings sind in der Tat bereits übersetzt, wenn ein Benutzer die fünfte Saite aus der Liste auswählt, welche Art von Algorithmus oder Technik kann ich verwenden, um dem Benutzer die erste Zeichenfolge (und möglicherweise andere) unter einer Unterüberschrift "Ähnliche Zeichenfolgen" zu zeigen?

Bearbeiten - Ein kleiner Kommentar zum Levenshtein Entfernung: Ich bin derzeit auf 10k Strings in der Datenbank. Levenshtein Distance vergleicht String pro String, also in diesem Fall 10k x (10k -1) mögliche Kombinationen. Wie würde ich das auf eine machbare Weise angehen? Gibt es eine bessere Lösung für diesen speziellen Algorithmus?

Answer 1

Sie könnten in die Levenshtein Distance suchen. Diejenigen unterhalb einer bestimmten Schwelle werden als ähnlich angesehen. Zwei identische Strings haben einen Abstand von Null.

Es gibt eine C# -Implementierung, unter anderem Rosetta Code.

Answer 2

Dies hängt von der Größe der Daten und davon ab, wie reich das Vokabular ist. Hier ist der erste Gedanke: erstellen Sie eine Karte von Wörtern zu Strings dann eine andere Karte von Wortpaaren zu Strings und vielleicht, wenn Daten nicht riesige Karte von String-Triplets zu Strings ist. Entfernen Sie Zuordnungen, die auf eine einzelne Zeichenfolge zeigen (dies reduziert die Anzahl der Triplet-Zuordnungen erheblich). Speichern Sie das resultierende Wörterbuch auf der Festplatte oder in einer Datenbank, wenn es Zeit braucht.

nun eine Zeichenfolge angegeben, sollten Sie, Wortpaare und Triolen und schauen sich auf alle Saiten bezogen, um es in Worte zu teilen Sie es schnell in der Lage sein. Sie müssen mit einem Gewicht spielen, das zu einem passenden Dreierpaar passt. I.e. ist „Ich bin ein alter Mann“ näher oder „den alten Hund mit einem Pfeil Mann getötet“ „ein alter Mann, der eine Karotte gegessen“ (klingt wie Triplett-Spiel wichtiger ist).

UPDATE: Wenn dies in einer Microsoft SQL Server-Datenbank können Sie mit Volltextsuche spielen. Ich habe es aber nie versucht. Sie sollten auch einen Blick auf Lucene werfen.