Textähnlichkeitsalgorithmus

Question

Ich habe zwei Untertiteldateien. Ich brauche eine Funktion, die zeigt, ob sie denselben Text darstellen oder der ähnliche Text

Manchmal gibt es Kommentare wie "Der Wind bläst ... die Musik spielt" nur in einer Datei. 80% des Inhalts werden jedoch gleich sein. Die Funktion muss True zurückgeben (Dateien repräsentieren denselben Text). Und manchmal gibt es Fehlspellings wie 1 anstelle von L (ein - l) wie hier:Sie 1Eft das Gepäck. Natürlich bedeutet dies, dass die Funktion wahr zurückgeben muss.

Meine Kommentare:
Die Funktion sollte den Prozentsatz der Ähnlichkeit von Texten zurückgeben - stimmen zu

"Alle Leute waren glücklich" und "Alle Leute waren nicht glücklich" - hier, die als Rechtschreibfehler betrachtet werden, so gilt das als der gleiche Text. Um genau zu sein, der Prozentsatz der Funktionsrendite ist niedriger, aber hoch genug, um zu sagen, dass die Phrasen ähnlich sind

Überlegen Sie, ob Sie Levenshtein auf eine ganze Datei oder nur eine Suchzeichenfolge anwenden möchten - nicht sicher über Levenshtein, aber der Algorithmus muss auf die gesamte Datei angewendet werden. Es wird jedoch eine sehr lange Saite sein.

Answer 1

Levenshtein -Algorithmus: http://en.wikipedia.org/wiki/levenshtein_distance

Alles andere als ein Ergebnis von Null bedeutet, dass der Text nicht "identisch" ist. "Ähnlich" ist ein Maß dafür, wie weit/in der Nähe sie sind. Ergebnis ist eine Ganzzahl.

Answer 2

Für das Problem, das Sie beschrieben haben (dh große Zeichenfolgen), können Sie verwenden Kosinusähnlichkeit, die eine Zahl zwischen 0 (völlig anders) auf 1 (identisch) zurückgeben, basieren auf dem Begriffsfrequenz Vektoren.

Vielleicht möchten Sie mehrere Implementierungen ansehen, die hier beschrieben werden: Kosinusähnlichkeit

Answer 3

Sie erwarten hier zu viel, es sieht so aus, als müssten Sie eine Funktion für Ihre spezifischen Bedürfnisse schreiben. Ich würde empfehlen, mit einer vorhandenen Dateivergleichsanwendung zu beginnen (möglicherweise diff Hat bereits alles, was Sie brauchen) und verbessern Sie es, um gute Ergebnisse für Ihre Eingabe zu erzielen.

Answer 4

Sich ansehen ungefähre Grep. Es könnte Ihnen Zeiger geben, obwohl es fast sicher ist, dass es auf große Textbrocken wie über von Ihnen sprechen.

Bearbeiten: Die Originalversion von Agrep ist nicht Open Source, daher erhalten Sie möglicherweise Links zu OSS -Versionen von http://en.wikipedia.org/wiki/agrp

Answer 5

Es gibt viele Alternativen zur Levenshtein -Entfernung. Zum Beispiel die Jaro-Winkler-Entfernung.

Die Wahl für einen solchen Algorithmus ist abhängig von der Sprache, der Art der Wörter, die von Menschen eingegebenen Wörter und vielem mehr ...

Hier finden Sie eine hilfreiche Implementierung mehrerer Algorithmen in einer Bibliothek