Illegal Borrowing ist eine mehrköpfige Hydra, ein Feind, der ständig sein Gesicht ändert. Unsere besten privaten Ermittler sind bereit, sich an jedes Verbrechen dieses Feindes zu klammern. Der Feind schläft jedoch nicht, er ist gerissen und tückisch: Er ersetzt offensichtlich eine Sache und fegt unglaublich geschickt Spuren in anderen. Manchmal schafft er es, mit Hilfe unseres flinksten Mitarbeiters - Suffix Massiv . Manchmal zögert der Feind und die sorgfältige, aber gemächliche Suche nach Paraphrase schafft es, seinen Standort zu berechnen. Aber das Böse ist heimtückisch, und wir brauchen ständig neue Kräfte, um es zu bekämpfen .
Heute werden wir über unseren neuen Spezialdetektiv namens Fuzzy Search sowie über seine erste Begegnung mit Fuzzy-Anleihen sprechen.
Machen Sie sich mit Ihrem Detektivbüro Antiplagiarism auf den Fall Mysterious Opponent gefasst
Bildquelle : pxhere.comSzene
Bei der Überprüfung des Gebiets (Dokuments) prüft das Anti-Plagiat , ob Anrufe wegen eines möglichen Verbrechens in dem Gebiet vorliegen. Die Augenzeugen, die uns über das Verbrechen informieren, sind der Shingles Index .
"Eine Schindel ist ein Textstück mit einer Größe von einigen Wörtern." Jedes dieser Teile wird gehasht, und Dokumente mit Schindeln mit denselben Hashes wie im zu prüfenden Dokument werden im Index durchsucht.
Ein Augenzeuge, der einen Zufall im Hasch von zwei Schindeln sieht, ruft uns mit einer Nachricht über das Verbrechen an. Leider kann der Gürtelrose-Index nicht für einen falschen Anruf bestraft werden, er ist immun gegen Sanktionen, weshalb es viele Anrufe gibt. Die Agentur ermittelt die Dokumente mit der größten Anhäufung solcher Anrufe - dem Ort eines potenziellen Verbrechens.
ZwischenspielTrotz der Tatsache, dass wir im Kontext der Geschichte die Verbrechen der geliehenen Gelder nennen, kann das geliehene Geld in Wirklichkeit legitim sein oder durch falsch positive Ergebnisse verursacht werden. Obwohl das Antilpagiate in der Lage ist, Zitate zu extrahieren, muss die endgültige Entscheidung vom Prüfer getroffen werden.
Erster Hinweis
Jetzt bist du ein Detektiv, mein Sohn.
Von nun an ist es dir verboten, an Zufälle zu glauben.
© „Der dunkle Ritter: Wiederbelebung der Legende“ („Der dunkle Ritter steigt auf“, Regie K. Nolan, 2012).
Detective Fuzzy Search kam am Tatort an. Kriminelle, die groß genug sind, bleiben nicht unbemerkt, denn je größer das Ausmaß des Verbrechens ist, desto wahrscheinlicher ist es, dass es einen Hinweis hinterlässt. Für die Fuzzy-Suche sind solche Leads kurze Übereinstimmungen fester Länge. Es scheint, dass unserem Detektiv ein großer Teil der gekonnt gekehrten Spuren von Kriminellen fehlt, aber nur 5% der Angreifer hinterlassen keinen solchen Hinweis. Es ist wichtig, keine Kriminellen zu verlieren, daher scannt der Detektiv den Bereich schnell mit einer speziellen Technik zum Erkennen von Übereinstimmungen.
Das Tagebuch des Detektivs über die Arbeitsweise. Erste Stufe
Wir werden zwei Funktionen der Aufgabe verwenden:
- Wir sind an klaren Duplikaten fester Länge interessiert.
- In einem guten Dokument wird derselbe Stein nicht zu oft dupliziert.
Die zweite Bedingung ist erforderlich, um die Anzahl der gefundenen eindeutigen Duplikate zu begrenzen. In der Tat ergibt eine einzelne, die 1000-mal im Dokument und in der Quelle vorkommt, 1.000.000 Übereinstimmungspaare. Solche häufig wiederholten Schindeln sind nur in ungereinigten Dokumenten mit Crawling-Versuchen zu sehen.
Ein von Crawls befreites Dokument wird als Folge von Wörtern dargestellt. Wir bringen die Wörter in die normale Wortform und hashen sie dann. Wir erhalten eine Folge von ganzen Zahlen (auf dem GIF - eine Folge von Buchstaben). Alle Schindeln dieser Sequenz werden gehasht und mit dem Wert der Position des Anfangs des Teilstrings in die Hash-Tabelle eingegeben. Dann werden für jeden Schindel im Kandidatendokument Übereinstimmungen in der Hash-Tabelle gefunden. Dadurch werden eindeutige Duplikate mit fester Länge erstellt. Tests zeigen eine dreifache Beschleunigung bei Verwendung der neuen Methode im Vergleich zum Suffix-Array.
BemerkungBitte beachten Sie, dass wir im Gegensatz zum Suffix-Array, das alle maximalen (nicht erweiterbaren) Duplikate findet, alle Duplikate mit fester Länge gefunden haben. Dies ist etwas schlimmer, aber trotzdem müssen Sie Duplikate verteilen, aber eine solche Suche verbraucht weniger Ressourcen und ist leichter zu verstehen / zu implementieren. Bonus: Sie können die Anzahl der Aufnahmen eines häufig wiederholten Duplikats begrenzen, um die Linearität gigantischer Dokumente aufrechtzuerhalten.
Wir berechnen den Verbrecher
- Gibt es noch andere Punkte, auf die ich achten sollte?
"Das seltsame Verhalten des Hundes in der Nacht des Verbrechens."
- Hunde? Aber sie hat sich in keiner Weise benommen!
"Das ist seltsam", sagte Holmes.
© Arthur Conan-Doyle, „Silber“ (aus der Serie „Notizen zu Sherlock Holmes“)
So fand Fuzzy Search mehrere Hinweise, anhand derer Kriminelle identifiziert werden konnten. Unser Held nutzt seine deduktiven Fähigkeiten in vollen Zügen, um nach und nach das Image des Verbrechers nach den gefundenen Hinweisen wiederherzustellen. Der Detektiv erweitert schrittweise das Bild des Geschehens, ergänzt es durch neue Details und entdeckt immer mehr Beweise, bis dieses Bild endgültig ist. Unser Detektiv wird manchmal hereingebracht, und er muss vom Himmel auf die Erde gesenkt werden und davon überzeugt sein, dass wir die Identität des Verbrechers und nicht die Biographie seines Cousins brauchen. Fuzzy Search murrt, schränkt das Bild aber demütig auf den gewünschten Maßstab ein.
Das Tagebuch des Detektivs über die Arbeitsweise. Zweite Stufe
Bildquelle : pixabay.com
In der zweiten Stufe werden Duplikate links und rechts über das Dokument verteilt. Die Verteilung erfolgt aus den "Zentren" - eindeutige Duplikate gefunden. Um die Suffixe zu vergleichen, verwenden wir den Levenshtein-Abstand - die minimale Anzahl von Löschungen / Ersetzungen / Einfügungen von Wörtern, die erforderlich sind, um eine Zeile in eine andere zu bringen. Die Entfernung kann dynamisch für doppelte Suffixe unter Verwendung des Wagner-Fisher-Algorithmus berechnet werden , basierend auf der rekursiven Bestimmung der Levenshtein-Entfernung. Dieser Algorithmus ist jedoch quadratisch komplex und erlaubt keine Steuerung des Fehleranteils. Ein weiteres Problem ist die genaue Definition der Grenzen von Duplikaten. Um diese Probleme anzugehen, verwenden wir mehrere einfache, aber dennoch wirksame Verfahren.
In diesem Schritt wird vorgeschlagen, zuerst die Levenshtein-Distanzmatrix für Suffixe eines Fuzzy-Duplikats auszufüllen (dann ähnlich für Präfixe). Da wir Suffixe auf „Ähnlichkeit“ prüfen, sind wir nur an Werten nahe der Diagonale dieser Matrix interessiert (der Levenshtein-Abstand ist größer oder gleich der Differenz der Linienlängen). Dies ermöglicht eine lineare Komplexität. Nachdem wir den maximal zulässigen Levenshtein-Abstand festgelegt haben, füllen wir die Tabelle aus, bis wir auf eine Spalte mit Werten stoßen, die größer als die zulässigen sind. Eine solche Spalte zeigt an, dass unser Fuzzy-Duplikat kürzlich beendet wurde und die Wörter fast vollständig übereinstimmten. Nachdem wir das vorherige optimale für jede gefüllte Zelle gespeichert haben, steigen wir mit einer minimalen Strafe in der kritischen Spalte von der Zelle ab, bis wir mehrere Übereinstimmungen finden, wonach der Fehler stark zuzunehmen begann. Dies sind die Grenzen des gefundenen Fuzzy-Duplikats.
Damit sich keine Fehler ansammeln, wird außerdem eine Prozedur eingeführt, die die Anzahl der Fehler zurücksetzt und die Ausbreitung erneut startet, wenn wir aufgrund aufeinanderfolgender Zufälle auf eine „Insel“ stoßen.
Bande von Kriminellen
- Morgen wollen wir uns mit Klassenkameraden treffen!
- In einem großen Klassenkameraden?
- Was?
© Bashorg
Die Fuzzy-Suche ist eine einfache Aufgabe geblieben: die am selben Ort gefangenen Kriminellen zu Banden zu vereinen, die unschuldigen Verdächtigen zu rechtfertigen und die Ergebnisse zusammenzutragen.
Bildquelle : pixabay.com
Das Verkleben von Duplikaten löst sofort 3 Probleme. Erstens absorbiert die zweite Stufe der „Verteilung von Duplikaten“ Änderungen von Wörtern und Phrasen, jedoch nicht ganze Sätze. Wenn Sie die "Ausbreitungsfähigkeit" des Algorithmus erhöhen, beginnt er sich über Zufälle zu verteilen, die in zu großer Entfernung gefunden wurden, und die Grenzen von Duplikaten werden schlechter bestimmt. So verlieren wir die für uns so wichtige Präzision, die eine klare Suche hatte.
Zweitens erkennt die zweite Stufe die Permutation von zwei Duplikaten nicht. Ich möchte, dass die Permutation der beiden Sätze an einigen Stellen eine Phrase in der Nähe des Originals bildet, aber für eine Zeile mit eindeutigen Zeichen führt die Permutation des Präfixes und des Suffix an einigen Stellen zu einer Zeile, die so weit wie möglich vom Original entfernt ist (in der Levenshtein-Metrik). Es stellt sich heraus, dass in der zweiten Phase beim Neuanordnen der Sätze zwei Duplikate nebeneinander gefunden werden, die Sie zu einem kombinieren möchten.
Und der dritte Grund ist Granularität oder Granularität. Granularität ist eine Metrik, die die durchschnittliche Anzahl von Duplikaten bestimmt, die in einem echten Darlehen gefunden wurden, das wir gefunden haben. Mit anderen Worten, die Granularität zeigt, wie gut wir die gesamte Ausleihe finden, anstatt die wenigen Teile, die sie abdecken. Die formale Definition der Granularität sowie die Definition der mikro-gemittelten Genauigkeit und Vollständigkeit finden Sie im Artikel „Ein Bewertungsrahmen für die Erkennung von Plagiaten“ .
Gifka zeigt, dass manchmal zwei Duplikate erst geklebt werden können, nachdem eines davon am dritten Duplikat haftet. Dementsprechend funktioniert nur ein Durchgang von links nach rechts auf dem Dokument nicht, um das Kleben zu vervollständigen.
AlgorithmusDie Liste der Duplikate am Eingang wird nach dem linken Rand im Dokument sortiert.
Wir versuchen, das aktuelle Duplikat mit mehreren der engsten Kandidaten davor zu verkleben.
Wenn sich herausstellt, versuchen Sie es erneut zu kleben. Wenn nicht, fahren Sie mit dem nächsten Duplikat fort.
Da die Anzahl der Duplikate nicht größer als die Länge des Dokuments ist und jede Überprüfung die Anzahl der Duplikate um 1 verringert und in konstanter Zeit durchgeführt wird, beträgt die Komplexität dieses Algorithmus O (n).
In der Regel wird ein Satz mehrerer Parameter zum Kleben von Duplikaten verwendet. Wenn wir jedoch die Mikrooptimierung der Qualität vergessen, kleben wir die Duplikate, für die das Maximum der Abstände in Dokument und Quelle klein genug ist.
Die Klebestelle liefert O (1) -Duplikate, auf die das aktuelle Duplikat geklebt werden kann.
Anfängertraining
Der Detektiv musste sich an die Besonderheiten unserer Stadt anpassen, sich an das Gelände anpassen, einen Spaziergang durch die unauffälligen Straßen machen und seine Bewohner besser kennenlernen. Zu diesem Zweck nimmt ein Anfänger an einem speziellen Trainingskurs teil, in dem er ähnliche Situationen auf einem Trainingsgelände studiert. Der Detektiv in der Praxis untersucht die Hinweise, den Abzug und den Aufbau sozialer Bindungen für die effektivste Festnahme von Kriminellen.
Das parametrische Modell musste optimiert werden. Zur Bestimmung der optimalen Modellparameter wurde das PlagEvalRus-Beispiel verwendet .
Die Stichprobe ist in 4 Sammlungen unterteilt:
- Generated_Copypast (4250 Paare) - wörtlich generierte Anleihen
- Generated_Paraphrased (4250 Paare) - schwach und mittelmodifizierte Anleihen, die von der Maschine unter Verwendung des Rauschens der ursprünglichen Passagen generiert werden (willkürliche Ersetzungen / Löschungen / Einfügungen)
- Manuell_Paraphrasiert (713 Paare) Handgeschriebene Texte mit verschiedenen Arten von Anleihen, meist schwache und mittelmodifizierte Anleihen (ersetzt durch nicht mehr als 30% der Wörter im Duplikat)
- Manuell_Paraphrasiert 2 (198 Paare) Handgeschriebene Texte mit mittleren und stark modifizierten Anleihen (mehr als 30% Wörter)
Die Stichprobe enthält auch die Art jeder Ausleihe.- DEL - Löschen Sie einzelne Wörter (bis zu 20%) aus dem ursprünglichen Satz.
- HINZUFÜGEN - Fügen Sie dem ursprünglichen Satz einzelne Wörter (bis zu 20%) hinzu.
- LPR - Änderung von Formen (Änderung von Anzahl, Groß- und Kleinschreibung, Form und Zeitform eines Verbs usw.) einzelner Wörter (bis zu 30%) des ursprünglichen Satzes.
- SHF - Ändern der Reihenfolge von Wörtern oder Teilen eines Satzes (Wendungen, Teile eines einfachen Satzes als Teil eines Komplexes) ohne wesentliche Änderungen „innerhalb“ der neu angeordneten Teile.
- CCT - Kleben Sie zwei oder mehr Sätze des Quelltextes in einen Satz.
- SEP / SSP - Aufteilen des anfänglichen komplexen Satzes in zwei oder mehr unabhängige Sätze (möglicherweise mit einer Änderung der Reihenfolge ihrer Reihenfolge im Text).
- SYN - Ersetzen einzelner Wörter oder einzelner Begriffe durch Synonyme (z. B. „Salz“ - „Natriumchlorid“), Ersetzen von Abkürzungen durch ihre vollständige Entschlüsselung und umgekehrt, Aufdecken der Initialen Ihres vollständigen Namens und umgekehrt, Ersetzen des Vornamens durch die Initialen usw.
- HPR - Starke Verarbeitung des ursprünglichen Satzes, bei dem es sich um eine Kombination aus vielen (3-5 oder mehr) Arten der obigen Textänderung handelt. Der gleiche Typ setzt eine starke Änderung des Quelltextes durch Periphrase unter Verwendung von Redewendungen, komplexen synonymen Konstruktionen, Permutation von Wörtern oder Teilen eines komplexen Satzes usw. voraus. Tricks, die es zusammen schwierig machen, die Entsprechung zwischen der Originalquelle und dem geänderten Text zu bestimmen.
Die Suche nach den optimalen Modellparametern wurde mit der Multi-Start-Abstiegsmethode durchgeführt. Maximiert messen mit (Betonung auf Genauigkeit). Hier sind die wichtigsten optimalen Parameter.
Fallgeschichte
Die Testphase unserer Fuzzy-Suche ist abgelaufen. Vergleichen wir die Produktivität mit der eines anderen Detektivs, dem Suffix Array. Der Schulungskurs Fuzzy Search fand im Programm Manually_Paraphrased statt.
Auf dem Gebiet zeigte der Neuankömmling eine signifikante Überlegenheit in Bezug auf den Anteil der gelösten Fälle. Die Geschwindigkeit seiner Arbeit kann sich auch nur freuen. Unserer Agentur fehlte ein so wertvoller Mitarbeiter.
Beim Vergleich der Qualität des Modells mit dem Suffix-Array stellen wir eine signifikante Verbesserung der Granularität sowie eine bessere Erkennung mittlerer und stark modifizierter Anleihen fest.
Beim Testen von Dokumenten mit einer Größe von bis zu 10 bis 7 Wörtern überprüfen wir die Linearität beider Algorithmen. Auf dem i5-4460-Prozessor verarbeitet das Programm ein Paar "Dokumentquellen" mit einer Länge von einer Million Wörtern in weniger als einer Sekunde.
Nachdem wir Texte mit einer großen Anzahl von Anleihen erstellt haben, sind wir davon überzeugt, dass die Fuzzy-Suche (blaue Linie) nicht langsamer ist als das Suffix-Array (rote Linie). Umgekehrt leidet ein Suffix-Array bei großen Dokumenten unter zu vielen Duplikaten. Wir haben die Leistung mit einer minimalen doppelten Länge von 5 Wörtern verglichen. Für eine ausreichende Kreditaufnahme verwenden wir jedoch eine eindeutige Suche mit einer minimalen doppelten Länge von 3 Wörtern, was bei gigantischen Dokumenten zu einem erheblichen Produktivitätsverlust führt (orange Linie). Es ist erwähnenswert, dass gewöhnliche Dokumente weniger Ausleihen enthalten, und in der Praxis ist dieser Effekt viel weniger ausgeprägt. Ein solches Experiment ermöglicht es uns jedoch, die Erweiterung der Anwendbarkeit der Modelle mit einer neuen Fuzzy-Suche zu verstehen.
Beispiele:
Es ist ersichtlich, dass der Algorithmus trotz des geringen Rechenaufwands die Erkennung von Ersetzungen / Löschungen / Einfügungen bewältigt, und der dritte Schritt ermöglicht es Ihnen, Ausleihen mit der Permutation von Sätzen und ihren Teilen zu erkennen.
Nachwort
Fuzzy Search arbeitet in einem Team mit unseren anderen Tools: Schnelle Suche nach Kandidatendokumenten, Extrahieren der Dokumentformatierung, umfangreiches Abfangen von Bypass-Versuchen. Mit diesem Befehl können Sie potenzielle Plagiate schnell finden. Fuzzy Search hat in diesem Team Wurzeln geschlagen und führt seine Suchfunktionen qualitativer und vor allem schneller aus als das Suffix-Array. Unsere Agentur wird ihre Aufgaben noch besser bewältigen, und skrupellose Autoren werden bei der Verwendung von nicht originalem Text auf neue Probleme stoßen .
Kreieren Sie mit Ihrem eigenen Verstand!