Indexgestützte Textanalyse mit symmetrischen kompakten direkten azyklischen Wortgraphen

Englmeier, Tobias (2020): Indexgestützte Textanalyse mit symmetrischen kompakten direkten azyklischen Wortgraphen. Dissertation, LMU München: Faculty for Languages and Literatures

Abstract

Ein symmetrischer direkter azyklischer Wortgraph (SCDAWG) ist eine komplexe String-Indexstruktur, die alle Infixe einer Textmenge und deren Inversen effizient abspeichert. In der vorliegenden Arbeit wird aufgezeigt, wie sich diese Indexstruktur für unterschiedliche Aufgaben aus dem Bereich der Textanalyse anwenden lässt. Im ersten Teil der Arbeit werden die Relationen zwischen verschiedenen String-Indexstrukturen und ihre effiziente Berechnung behandelt. Das Ende dieses Abschnitts bildet die formale Beschreibung der SCDAWG-Struktur. Der zweite Teil beinhaltet die ausführliche Darstellung einer eigenen Implementierung der SCDAWG-Struktur sowie Implementierungsdetails grundlegender Suchfunkionen, die die Struktur zu einer invertierten Datei erweitern. Im dritten Teil steht das Auffinden längster gemeinsamer Teilwörter im Fokus, wobei dort verschiedene Anwendungsmöglichkeiten, die auf diesen basieren, diskutiert werden. Einen Kernpunkt stellt ein kombiniertes Verfahren zur globalen Alignierung zweier Strings dar. Schließlich wird im letzten Teil eine Methode zur Identifikation charakteristischer minimaler Teilwörter erörtert und deren Einsatzmöglichkeit bei der überwachten Dokumentenklassifikation behandelt.

• Item Type: Theses (Dissertation, LMU Munich)
• Keywords: String-Indexstrukturen, historische OCR, Alignment, Dokumentenklassifikation
• Faculties: Faculty for Languages and Literatures
• Language: German
• Date of oral examination: 10. July 2020
• 1. Referee: Schulz, Klaus U.
• Signature of the printed copy: 0001/UMC 27350