Archiv | Plagiarismus RSS feed for this section

Masterarbeit: Near Copy Detection in large text corpora (ODIN): Was bisher geschah! (Stemming, Stopword, Numberremoval, Symbolremoval)

2 Mrz

Dies ist der vorerst letzte Artikel zum Thema Textvorverarbeitung. Hier werden kurz die Techniken Stemming, Stopworts, Numberremoval und Symbolremoval, die ebenfalls als API und Hadoop Map-Reduce implementiert sind, beschrieben. Die folgenen Artikel werden sind mehr mit dem Detectieren von kopierten stellen und der Verarbeitung mittels Hadoop  zu tun haben.

Weiterlesen

Werbeanzeigen

Masterarbeit: Near Copy Detection in large text corpora (ODIN): Was bisher geschah! (Wordnet;Synonym findung)

27 Feb

In dem nächsten spannenden Teil meiner Blogserie „ODIN! Was bisher geschah!“ widme ich mich dem Desynonymifizieren (entfernen von Synonymen wegen der Aussprache). Oft werden kopierte Textstellen abgewandelt um die Herkunft zu verschleiern. Diese Abwandlungen können sein, dass Umstellen von Sätzen, das Entfernen oder Hinzufügen von Worten, das Ändern von numerischen Werten oder das austauschen von Worten gegen Synonyme. Die letzte Möglichkeit ist Thema diese Blogposts.
Weiterlesen

Kurzmitteilung

Masterarbeit: Near Copy Detection in large text corpora (ODIN): Benchmark

21 Feb

In diesem Blog wollte ich ein paar Zwischenergebnisse des Hadoop Clusters auflisten. Das Cluster besteht momentan aus 4 Workernodes mit insgesamt 18 Cores (4,4,4,6 / Core2 2,8GHz) die alle ungefähr gleich schnell sind. Die Rechner sind mit insgesamt 7 Platten (3,3,3,1) ausgestattet und haben pro Core 2GB Ram. Der Testdatensatz umfasst ca. 43.000 PDFs mit einer gesamt Größe von ca. 27GB. Die aufgelisteten Werte drücken die Bearbeitungszeit eines Dokuments auf einen Core aus, dahinter die Bearbeitungszeit eines Dokuments auf den gesamten Cluster (geteilt durch die Anzahl der Cores).

PDFToText+Hyphenationremoval+Footer-Headerremoval: 0,074 Sekunden/Core/Dokument | 0,00411 Sekunden/Dokument

Sentence+Tokensplitting+POS: 1,828 Sekunden/Core/Dokument | 0,1015 Sekunden/Dokument

Lemmatizer: 11,554 Sekunden/Core/Dokument | 0,64189 Sekunden/Dokument

Stemmen+Stopword+Numberremoval+Symbolremoval: 0,111 Sekunden/Core/Dokument | 0,00617 Sekunden/Dokument

Daraus ergibt sich eine gesamt Zeit von 0,75367 Sekunden pro Dokument. Diese Zeit wird dominiert durch das Lemmatisieren was API-bedingt ist.

Masterarbeit: Near Copy Detection in large text corpora (ODIN): Was bisher geschah! (Textumformungen)

20 Feb
Als weiteren Schritt zur near copy detection habe ich einige Algorithmen zur Textumformung implementiert. Diese Algorithmen dienen zur Vereinfachung der Texte sowie dem leichteren zerlegen in einzelne Fragmente wie Worte, Satzzeichen oder Zahlen. Im folgenden werden die acht Schritte kurz beleuchtet die ich hierzu umgesetzt habe:
  1. Language Detektion: Die Bestimmung der Sprache eines Textes wird von vielen weiteren Komponenten benötigt, da sie zum Beispiel auf Wörterbüchern oder speziell für eine Sprache trainierte maschinellelern Ansätze aufbauen. Die Sprachenbestimmung wird durch die API language-detection durchgeführt, die in der Lage ist 53 verschiedene Sprachen durch ngram Frequenzen zu identifizieren.
  2. Satz- und Tokenbestimmung: Um weitere Strukturen in die Fließtexte zu bekommen müssen Satzgrenzen und die einzelnen Bausteine des Satzes bestimmt werden. Die ist nötig um weitere Algorithmen anwenden zu können die auf Satzebene arbeiten, wie zum Beispiel der Lemmatizer oder Fuzzyset Ähnlichkeitsvergleiche. Die Sätze werden anschließend weiter, in Tokens zerlegt. Hierbei bildet jedes Wort und jedes Satzzeichen ein Token. Dezimalzahlen die mit Komma unterteilt sind werden beachtet und bilden nur ein Token, was wiederum wichtig ist für das Numberremoval. Nach diesem Schritt steht ein Dokumentobjekt zur Verfügung indem jedes Element im „Chunk“ Feld ein Satzbaustein enthält. Außerdem ist das Feld „Sentences“ mit den Startoffsets der Sätze gefüllt. Für diesen Schritt habe ich die Apache OpenNLP API verwand.
Die nächsten Schritte verändern das Documentobjekt nicht mehr direkt sondern erstellen entweder Substitutions- oder Removelist Objekte. Eine Substitutionlist enthält eine Map die als Key einen Offsetwert und als Value einen String beinhaltet der den Orginalstring aus dem Documentobjekt an dem Offset ersetzt. Eine Removelist enthält nur eine Liste an Offsets die aus dem Documentobjekt entfernt werden sollen. Die beiden Objekte werden separat von einander und von dem Documentobjekt gespeichert und ermöglichen so ein freies zusammensetzten von beliebigen Algorithmen.
  1. Lemmatisierung: Hier werden alle Worte eines Textes auf ihre Grundform zurückgeführt. Hierbei werden auch verschiedene Zeitformen beachtet. Also wird das englische Wort „went“ in seine Grundform „go“ zurückgeführt. Dies wird mit der Mate-Tools API bewerkstelligt. Diese API bietet Lemmatisierung für verschiedene Sprachen, hierfür wird auf einen maschinellenlernen Ansatz zurückgegriffen der mit unterschiedlichen trainierten Modellen mit einer Wissensbasis versorgt wird. Die API ist leider relativ langsam sodass, als eine zukünftige Tätigkeit, der Austausch dieser API gegen eine schnellere anstehen sollte. Die erzeugten Lemmata finden in der Synonymfindung eine Rolle und könne auch besser als Stemming in z.B. Wordclouds verwendet werden. Die Ergebnisse aus dem lemmatisieren werden in einer Substitutionlist abgelegt.
  2. Stemming: Ähnlich zum Lemmatisieren wird beim Stemmen versucht Worte auf einen gemeinsame Form zurückzuführen. Diese Form muss dabei aber kein korrektes Wort oder gar die Grundform eines Wortes sein. Das stemmen ist ein algorithmischer Ansatz der mit einen Satz von Umformungsregeln, die Sprachabhängig sind, arbeitet. Es wird keine komplexes Model verwand, was das stemmen um ein vielfaches schneller macht als das lemmatisieren. Die Ergebnisse sind zwar nicht so gut wie beim lemmatisieren können aber trotzdem zu Verallgemeinerung von Texten helfen. Das Stemmen wird mithilfe von der Analyse API von Apache Lucene durchgeführt und die Ergebnisse werden als eine Substitutionlist abgelegt.
  3. Part of speech: Das Erkennen der Satzstellung eines Wortes wird Part of Speech (POS) genannt. Jedem Wort eines Satzes wird hierbei seiner Bedeutung im Satz (Nomen, Verb, Adjektiv, Adverb, Eigennamen …) zugeordnet. Dies geschied mit der Apache OpenNLP API die auch hierbei trainierte Modelle als Input verwendet. Das Ergebnis ist ein Substitutionlist.
  4. Stopwordremoval: Stopworte (der, die, das, und, auf …) tragen nur geringe semantische Bedeutung, weshalb sie für viele Techniken ignoriert werden können. Dies reduziert den Rechenaufwand zum Beispiel bei Ähnlichkeitsberechnungen drastisch. Andere Techniken wie zum Beispiel die near copy detection auf Stopworten benutzt ausschließlich Stopworte. Die Detektion von Stopworten ist sehr einfach, es gibt Listen für sehr viele Sprachen. In Odin werden Liste aus der Analyse API von Apache Lucene benutzt. Das Ergebnis ist ein Removelist.
  5. Numberremoval: Das Entfernen oder austauschen von Zahlen gegen einen einheitlichen Wert, kann das Erkennen von kopierten Stellen vereinfachen. Wenn beim Kopieren von Textpassagen nur Zahlenwerte verändert werden, ergeben sich durch das entfernen oder generalisieren der Zahlen eine höhere Ähnlichkeit der beiden Textpassagen. In einer Substitutionlist werden alle Zahlenwerte eines Dokuments durch einen Stringidentifier „//NumberRemoved\\“ ersetzt.
  6. Symbolremoval: Hier werden alle Satzzeichen, Klammern und alle nicht alphanumerischen Zeichen in eine Removelist eintragen und damit aus dem Dokument entfernt.

Diese Algorithmen wurden alle implementiert und in Map Reduce Jobs für Hadoop verpackt und auf einen Testsatz von PDFs (43.000) ausgeführt. Der nächste Blogeintrag wird ein kleines Benchmark enthalten.

Masterarbeit: Near Copy Detection in large text corpora (ODIN): Was bisher geschah! (Text preprocessing)

8 Feb

Die Hauptaufgabe des Systems ist es Wissenschaftlichearbeiten zu verarbeiten und als Hintergrundkorpus für die Suche nach ähnlichen Textstellen zu verwenden. Als Eingabeformat sollen erstmal PDF-Daten herangezogen werden. In weiteren sollen aber auch andere Formate benutzbar sein, wie zum Beispiel ein Wikipediadump, um auch Textstellen aus dieser Quellen identifizieren zu können.

Texte die als PDF-Dateien zur Verfügung stehen haben aber einige Nachteile für die automatisierte Verarbeitung, so müssen nach der Textextraktion noch einige cleaning Schritte vollzogen werden, die ich im folgenden ein wenig Beschreibe:

  1. PDFToText: Den Volltext aus einer PDF-Datei zu extrahieren ist recht einfach. Hierzu gibt es eine Vielzahl an Tools die diese Aufgabe übernehmen können. Ich habe mich für Apache PDFBox entschieden, da diese API in JAVA implementiert ist und ich sie so direkt in Hadoop Map-Reduce Jobs verwenden kann. Mit PDFBox ist es möglich neben den Volltext als ganzes auch seitenweise Text zu extrahieren, auch ist es möglich die Grafiken auf den Seiten und die Seiten als Thumbnails zu extrahieren. Diese Möglichkeiten werden noch nicht benötigt, aber sie sind potenziell verwendbar um auch Kopien der Grafiken zu detektieren.
  2. Speichern der Texte: In der weiteren Verarbeitung können Textstellen entfernt, hinzugefügt oder geändert werden. Ich möchte aber gern die Positionen im Verhältnis zum Ausgangszustand beibehalten. Hierfür habe ich ein Speicherformat entwickelt das mir dies ermöglicht. Dieses Format kann in JSON ausgedrückt werden und sieht dann so aus:{„chunks“: {„0“: „text text“,“10″: „more text“},“pages“: [0,3119,6708],“sentences“: [0,15,33,67],“lines“: [0,100,219,322]}Das Feld „chunks“ beinhaltet hierbei einzelne Textteile, zum Anfang sind das die einzelnen Zeilen des Dokuments. Jeder Chunk ist mit einem Offset versehen das die Zeichenweise Position im Ursprungsdokument angibt. Das Feld „pages“ enthält die Startoffsets der einzelnen Seiten des Dokuments, gleiches gilt für die Felder „sentences“ und „lines“.
  3. Header-Footer-Removal: Die nächsten Cleaningschritte habe ich speziell für die Eigenarten von Printmedien entwickelt, das Entfernen von Header und Footer. Wenn auf zwei oder mehr Seiten die ersten, respektive die letzten Zeilen ähnlich sind wurde eine Kopf- bzw. Fußzeile gefunden. Ähnlich bedeutet hierbei die Textzeilen sind gleich bis auch einen numerischen Part der hoch zählt (also die Seitenzahl). Der Algorithmus beachtet dabei auch unterschiedliche Kopf- oder Fußzeilen in einem zwei seitigen Format.
  4. Hyphenation-Removal: Hier sollen Silbentrennung am Zeilenende entfernt werden. Dafür suche ich ein Bindestrich am Zeilenende, wird einer gefunden wird noch untersucht ob er direkt an einem Wort steht, wenn ja dann wird der Bindestrich entfernt und das erste Wort in der nächsten Zeilen an die neue Position geschoben. Dieser Algorithmus kann Fehler erzeugen, wenn zum Beispiel zusammengesetzte Worte wie „Meier-Schultze-Friese“ über zwei Zeilen getrennt wird, könne Wortkonstruktionen wie „Meier-SchultzeFries“ oder „MeierSchultze-Friese“ entstehen. Dies kann noch mit einer Rechtschreibprüfung abgefangen werden, indem geprüft wird ob das neue Wort korrekt ist. Dies ist aber (noch) nicht implementiert.
Die Ergebnisse aus diesen Schritten werden als JSON in HBASE gespeichert. Hier entspricht eine Zeile einem PDF-Dokument und jede Spalte einen Verarbeitungsschritt. Dementsprechend werden bis jetzt die Spalten „PDF“, „extractedFulltext“, „removeFooter“, „removedFooterAndHeader“ und „fulltext“ das alle ob Beschriebenen Schritte vereint und für die weitere Bearbeitung benutzt wird.