Tag Archives: odin

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

Advertisements

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! (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.

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

1 Feb

Mit der Near copy detection Anwendung sollen großen Mengen an Publikationen untersucht werden können. Um dies zu gewährleisten habe ich mich für Apache Hadoop als Paralellisierungsframework entschieden. Hadoop ist eine Opensource Framework dass das Map Reduce Paradigma von google umsetzt. Hierzu benötigt wird außerdem ein verteiltes Dateisystem das in Form von HDFS ( Hadoop Distributed File System) mitgeliefert wird.

Map-Reduce: Das Map-Reduce Pattern wurde von Google (link) beschrieben, es handelt sich hierbei um eine Methode zur Verarbeitung großer Datenmengen in einem Cluster von Rechnern. Map Reduce verarbeitet die Daten in zwei Hauptschritten (Map und Reduce) die durch einige generische Schritte gekoppelt sind:

  • Map: Die Daten werden von dem Speichermedium eingelesen und in Splits an die Map Prozesse verteilt. Splits sind eine Teilmenge der Daten, zum Beispiel 64MB Blöcke, die an die einzelnen Map Instanzen verteilt werden. Der Map Prozess verarbeit den Split und erzeugt eine Map als Ergebnis. Am Beispiel eines Wordcounts enthält diese Map als Key jedes Wort und als Value das aufkommen des Wortes in diesem Split.
  • Shuffel and Sort: Die ergebniss Mengen werden auf alle Reducer verteilt (Shuffel). Dies kann zum Beispiel mit einer Hashfunktion passieren. Da es wahrscheinlich mehr Mapinstanzen geben wird als Reduceinstanzen bekommt jede Reduceinstance 1 bis #Mapinstanzen viele Ergebnismaps. Diese werden in einen merge Schritt vereinigt und sortiert. Dieser Schritt stell auch sicher das das ein Key nur zu einem bestimmten Reducer kommt,  es ist also ausgeschlossen das zwei Reducer des gleichen Key erhalten.
  • Reduce: Der Reduceschritt bekommt als Eingabe eine Map, also beim Wordcount Beispiel mit den Wörtern als Key und einer Liste über aller Value Ergebnisse der Mapper als Value. Die Reducerinstance kann nun alle values zusammen addieren und erhält die Anzahl eines Wortes der kompletten Eingabedaten.

Durch diese Aufteilung können die behandelten Probleme gut mit der Anzahl der Rechner im Cluster skaliert werden.

HDFS: Das verteile Filesystem von Hadoop ist optimiert auf das ausführen von Map-Reduce-Jobs. Große Files werden in Blocke eingeteilt (Standard 64MB). Dies Blöcke werden über alle Datanodes im System verteilt. Hier durch wird eine hohe Parallelität bei Lesen gewährleistet. Die Datanodes sollten zusammen mit den Rechennodes auf den gleichen Rechnern liegen. Sodass das verarbeiten der Daten möglichst Datenlokal geschieht, also kein Netzwerkverkehr benötigt wird.

Als Testinstance habe ich ein 5 Knoten großes Cluster aufgebaut das in Wolles Büro steht. Dieses Cluster verfügt über einen Masterknoten (Dual Core Pentium 4), vier Rechenknoten (3xquadcore Pentium4 und 6 Cores von Imhotep XEON Pentium4). Die Rechenknoten haben dann insgesamt 18 Cores, 30GB RAM, 2.8TB HDD.