Ich schreibe eine Anwendung zur Plagiatserkennung in großen Textdateien. Nachdem ich viele Artikel darüber gelesen hatte, entschied ich mich dafür, Winnowing-Algorithmus zu verwenden (mit Karp-Rabin-Rolling-Hash) Funktion), aber ich habe ein paar Probleme damit.
Daten:
Ich habe zwei einfache Textdateien - die erste ist größer, die zweite ist nur ein Absatz von der ersten.
Verwendeter Algorithmus:
Dies ist ein Algorithmus, mit dem ich meine Fingerabdrücke aus allen Hashes ausgewählt habe.
%Vor%Um festzustellen, ob wir den gleichen Text in beiden Dateien haben, vergleiche ich die Fingerabdrücke von beiden Texten, um zu überprüfen, ob es Übereinstimmungen gibt. Um also Plagiate zu erkennen, muss der Algorithmus Hashes verwenden, die exakt an der gleichen Stelle im Text beginnen, zum Beispiel:
Text1: A tu run | t ^ sein mein check dein.
Text2: Mein bla lol | t ^ sein mein dasd Hühnchen.
Um richtige Hashes zu erhalten, die die gleichen Werte haben (was auch bedeutet, dass wir denselben Text haben), sollte der Algorithmus Fingerabdrücke von Orten nehmen, auf die ich mit '|' oder '^' (ich nehme an, dass wir 5 Zeichen brauchen, um Hash zu berechnen, ohne Leerzeichen). Es kann keinen Hash von '|' in Text 1 und '^' in Text 2, weil diese zwei Hashes unterschiedlich sind und Plagiate nicht erkannt werden.
Problem:
Um festzustellen, ob dieser Absatz von Text Nummer 1 kopiert wurde, muss ich zwei gleiche Fingerabdrücke irgendwo in beiden Texten haben. Problem ist Algorithmus wählen Sie diese Fingerabdrücke, die nicht zueinander passen, ich meine, sie vermissen nur, selbst in viel größeren Texten.
Frage:
Hast du irgendwelche Ideen, wie ich diesen Algorithmus verbessern kann (was tatsächlich zur Korrektur des Algorithmus der Takin-Fingerabdrücke führt), dass es eine größere Wahrscheinlichkeit hätte, Plagiate zu finden?
Meine Gedanken:
Ich dachte über Run Winnow-Funktion Paarzeiten, für verschiedene Fenstergrößen (die dazu führen, dass verschiedene Hashes genommen werden würde), aber für große Texte, auf denen dieses Programm arbeiten muss (wie 2MB nur Text) wird dies auch dauern viel Zeit.
Wenn Sie ein laufendes Fenster haben, über das Sie den Hash berechnen, können Sie den Hash-Wert in konstanter Zeit aktualisieren, wenn sich das Fenster bewegt. Die Methode heißt Rabin-Fingerabdruck ( siehe auch ). Damit können Sie alle Fingerabdrücke der Größe X in O (n) Laufzeit berechnen (n ist die Größe eines Eingabedokuments). Ich denke, das von Ihnen zitierte Papier ist eine erweiterte Erweiterung dieser Methode, und wenn es korrekt implementiert wird, sollte es Ihnen auch eine ähnliche Laufzeit geben. Der Schlüssel ist, den Hash zu aktualisieren, nicht neu zu berechnen.
Tags und Links algorithm c++ plagiarism-detection