Logo Logo
Help
Contact
Switch language to German
Indexgestützte Textanalyse mit symmetrischen kompakten direkten azyklischen Wortgraphen
Indexgestützte Textanalyse mit symmetrischen kompakten direkten azyklischen Wortgraphen
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.
String-Indexstrukturen, historische OCR, Alignment, Dokumentenklassifikation
Englmeier, Tobias
2020
German
Universitätsbibliothek der Ludwig-Maximilians-Universität München
Englmeier, Tobias (2020): Indexgestützte Textanalyse mit symmetrischen kompakten direkten azyklischen Wortgraphen. Dissertation, LMU München: Faculty for Languages and Literatures
[img]
Preview
PDF
Englmeier_Tobias.pdf

6MB
[img] ZIP
Englmeier_container.zip

38MB

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.