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: Fakultät für Sprach- und Literaturwissenschaften

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.

• Dokumententyp: Dissertationen (Dissertation, LMU München)
• Keywords: String-Indexstrukturen, historische OCR, Alignment, Dokumentenklassifikation
• Fakultäten: Fakultät für Sprach- und Literaturwissenschaften
• Sprache der Hochschulschrift: Deutsch
• Datum der mündlichen Prüfung: 10. Juli 2020
• 1. Bericht­erstatter:in: Schulz, Klaus U.