Algorithmen und Datenstrukturen

Praktische Einführung und Programmierung

Stefan Bosse

Universität Koblenz - FB Informatik

1 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung ::

Textverarbeitung

Wie werden Texte maschinell verarbeitet?

2 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung ::

Textverarbeitung

Wie werden Texte maschinell verarbeitet?

Welche Algorithmen und Datenstrukturen werden gebraucht?

3 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung ::

Textverarbeitung

Wie werden Texte maschinell verarbeitet?

Welche Algorithmen und Datenstrukturen werden gebraucht?

Was sind reguläre Ausdrücke und wie und wofür verwendet man sie?

4 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung :: Anwendungen für Textverarbeitung

Anwendungen für Textverarbeitung

Übersetzer

  • Übersetzung einer natürlichen Sprache in eine andere natürliche
  • Übersetzung einer natürlichen Sprache in eine maschinelle Speache oder Notation (symbolische Repräsentation, symbolische KI)
  • Übersetzung einer maschinellen (Programmier-) Sprache in eine andere
    • Meistens Reduktion der Ausdrucksfähigkeit und Komplexität
    • Beispiel: C++ in konkrete Maschinensprache eines Mikroprozessors (strukturiert und hierarchisch auf lineare Struktur)
    • Beispiel: Java in abstralte Maschinensprache einer Virtuellen Maschine

Suche

  • Bisher haben wie in strukturierten Daten gescuht. Jetzt Suche un unstrukturierten Daten - den Texten.
    • Ein Text besteht aus Zeichen mit einem Alphabet, ggfs. unterteilt uin Worte mit Trennzeichen
  • Suche in Texten bedarf vor allem effiziente Algorithmen, häufig mit Zustandsautomaten verbunden.
5 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung :: Reguläre Ausdrücke

Reguläre Ausdrücke

https://files.ifi.uzh.ch/cl/hess/classes/le/regex.0.l.pdf

Wozu braucht man RA?

  • Die Verwendung regulärer Ausdrücke (RA) ist heute weit verbreitet im Bereich grundlegender, einfacherer Verfahren der Computerlinguistik (z.B. Tokenisierung und Tagging), Suchmaschinen oder in einfachen Interpretern, der sogenannten flachen Textverarbeitung.
  • Mit Hilfe von regulären Ausdrücken lassen sich Muster für einfache sprachliche Ausdrücke spezifizieren, nach denen automatisch in Texten gesucht werden kann.
  • Ein Beispiel hierfür, umgangssprachlich ausgedrückt, wäre "Wort, das mit einem Grossbuchstaben anfängt und mit einem 'k' aufhört".
    • Je nach Textkorpus, in dem man sucht, lässt sich damit das Wort "Computerlinguistik" finden.
    • Die gefundenen Instanzen (Matches) eines solchen Mustervergleichs (Pattern matching) stehen dann zum Teil direkt der weiteren Verarbeitung zur Verfügung.
6 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung :: Reguläre Ausdrücke

Woher kommen RA?

  • Die Verwendung regulärer Ausdrücke ist vor allem durch Suchfunktionen (egrep) und Skriptsprachen (lex und flex) auf Unix-Ebene sowie durch plattformübergreifende Skriptsprachen (vor allem Perl, JavaScript) bekannt geworden
  • Mittlerweile können RA in vielen gängigen Programmiersprachen verwendet werden.

Was sind RA?

  • Reguläre Ausdrücke sind zunächst einmal einfach zu spezifizieren.
    • Einfach heisst dabei nicht unbedingt leicht verständlich, ganz im Gegenteil!, sondern gemäss formaler Kriterien wie Repräsentations- und Verarbeitungskomplexität einfach - das macht sie so attraktiv.
    • Entsprechend lassen sich Sprachen, die RA beschreiben (sogenannte reguläre Sprachen), mithilfe des einfachsten Grammatiktyps (sogenannten Typ-3-Grammatiken) beschreiben.
    • Solche Sprachen können nachweislich in effizient zu verarbeitende Strukturen (sogenannte Endliche Automaten) übersetzt werden, die durch RA spezifizierte Ausdrücke schnell aufspüren.
7 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung :: Reguläre Ausdrücke

Was kann man mit RA machen?

  • Programmiersprachen, die die Verwendung von RA implementieren, bieten in der Regel mindestens die folgenden Möglichkeiten:
    • checken, ob ein RA in einem Text vorkommt
    • angeben, wo ein RA in einem Text vorkommt
    • den Zugriff auf Teile eines Matches im Text
    • den Zugriff auf alle zu findenden Matches im Text
    • die Möglichkeit zur Ersetzung eines (oder aller) Vorkommen in einem Text durch etwas anderes
    • die Möglichkeit zur Zerlegung eines Textes an den Stellen, an denen ein gegebener RA vorkommt.
8 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung :: Reguläre Ausdrücke

Konstruktion regulärer Ausdrücke

  • Im folgenden sollen die wesentlichen Möglichkeiten zur Konstruktion von RA vorgestellt werden.
  • Hierzu werden RA in den Beispielen stets durch Schrägstriche ("/") (slashes) eingerahmt (wie es z.B. in Perl oder JavaScript üblich ist).
  • Anhand eines solchermassen angegebenen Suchmusters wird ein Text von Anfang bis Ende durchsucht und es wird der zuerst gefundene Match als Ergebnis geliefert.
  • Im Folgenden gehen wir davon aus, dass jeweils alle Ergebnisse gesammelt werden.

Direkte Angabe von Zeichenketten

Direkte Angabe von Zeichenketten, also Abfolgen von Zeichen, sind der einfachste Fall:

/einzig/
/einzig|winzig/

Suche nach dem Vorkommen von "einzig" im Text oder alternativ durch "|" getrennt nach "einzig" und "winzig" (Disjunktion).

9 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung :: Reguläre Ausdrücke

Zeichenklassen

  • Zeichenklassen ("character classes") sind eine wichtige Möglichkeit, reguläre Ausdrücke kürzer zu formulieren
    • In "[]" eingeschlossen lassen sich Zeichen ange-ben, die an einer bestimmten Position auftreten sollen/dürfen.
    • Sie dienen im wesentlichen der Vereinfachung von RA (um nicht jeweils die Zeichenalternativen an einer Position explizit angeben zu müssen).
  • weitere Möglichkeiten, Zeichenklassen zu spezifizieren:
    • /[A-Z]/ ein beliebiger Grossbuchstabe (aber ohne Umlaute, ß und Buchstaben mit Akzenten)
    • /[A-Za-z]/ ein beliebiger Gross- oder Kleinbuchstabe (ditto)
    • /[0-9]/ eine beliebige Ziffer
    • Mischungen und Teilbereichsangaben sind möglich, z.B. /[ab17G-K]/
    • Ausschluss: /[^abc]/ passt auf alle Zeichen außer a,b und c.

Man kann bei der Suche das Flag "g" hinter den Ausdruck setzen. Dann wird dieser mehrfach angewendet und liefert alle passenden Ergebnisse.

10 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung :: Reguläre Ausdrücke

Wiederholungen

  • Häufig sollen Muster mehrfach expandiert werden, d.h. z.B. würde /a/ nur ein Zeichen "a" im Text "aabbba" suchen.

  • Sollen Sequenzen von Zeichen die aus einzelnen Teilen zusammengesetzt sind gesucht werden braucht man Wiederholungen.

  • Quantifikatoren geben an, wie häufig das direkt vorangehende Zeichen bzw. die direkt vorangehende Gruppe oder Zeichenklasse vorkommen können soll.

  • Es gibt einige allgemeine und eine Reihe von numerischen Wiederholungen.
  • Allgemeine Wiederholungen sind:
    • * Keinmal oder beliebig oft
    • + Mindestens einmal
    • ? Einmal oder keinmal

Beispiel:

s="aabbba"
match(/a+|b+/g,"abbaab") => [ 'a', 'bb', 'aa', 'b' ]
11 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung :: Reguläre Ausdrücke

+

12 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung :: Reguläre Ausdrücke und Automaten

Reguläre Ausdrücke und Automaten

Reguläre Ausdrücke bzw. deren Anwendung ist i.A. zustandslos und kontextfrei.

Folgendes Beispiel:

if a=0 then a=1 end

Das "then" ist nur nach einem "if" zulässig, dazwischen befindet sich ein Ausdruck. Es gibt also einen Kontext. Das Gleichheitszeichen hat hier zwei Bedeutungen: Vergleich und Zuweisung (wie z.B. in der Programmiersprache Basic). Es gibt also einen Kontext. Ist = in einem Ausdruck dann ist es ein Vergleich und liefert einen Booleschen Wert, ist es Bestandteil einer Anweisung dann ist es eine Zuweisung. Das kann ein regulärer Ausdruck nicht unterscheiden.

13 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung :: Reguläre Ausdrücke und Automaten

Reguläre Ausdrücke und Automaten

Mit einer Ausnahme:

Rückverweise sind ein sehr mächtiges Instrument beim Schreiben von regulären Ausdrücken.

  • Für gruppierte (d.h. in runde Klammern eingeschlossene) Teilmuster werden systematisch Register angelegt, so dass mit Hilfe von Variablen der Form "$i" (mit i aus [1-9]) ein Rückbezug auf Matches dieser Teilstrukturen möglich ist.
  • Dies ist insbesondere bei Ersetzungen sehr hilfreich.

Innerhalb des RA kann mit "\i" auf Teilmuster(matches) zurückverwiesen werden:

/\b([egin]{3,3}).*?\b\s\1/

Suche nach dem Vorkommen einer Zeichenkette, die mit einer Wortgrenze beginnt, gefolgt von genau 3 Zeichen, die jeweils entweder "e", "g", "i" oder "n" sind (dieses Muster wird als erstes Muster gespeichert), gefolgt von beliebigen Zeichen bis zur ersten Wortgrenze, gefolgt von einem white space, gefolgt vom ersten Muster

14 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung :: Reguläre Ausdrücke und Automaten

Reguläre Ausdrücke und Automaten

Man kann jeden regulären Ausdruck in einen Endlichen Zsutandsautomaten übersetzen. RA sind aber viel mächtiger und ausdrucksstärker. RA können Graphen beschreiben!

Endlicher Automat zum regulären Ausdruck 0+1(0+1)*

15 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung :: Suche in Texten

Suche in Texten

Jetzt wollen wir uns einen Algorithmus für eine Suche eines einfachen Musters in einem Text anschauen.

Brute-Force

function BruteForceSearch (text, pat) {
  // Eingabe: zu durchsuchender Text text der Länge n,
  // gesuchtes Muster pat der Länge m
  for (i= 0; i<= n − m;i++) {
    j = 0;
    while (j < m && pat[j] == text[i + j]) {
      j = j + 1
    }
    if (j >= m) return i
  }
  return −1
}

Zwei geschachtelte Schleifen für die Brute-Force-Suche in Texten

16 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung :: Suche in Texten

Suche in Texten

addp Ablauf beim Brute-Force-Algorithmus

  • Die Laufzeitkomplexität beträgt im ungünstigsten Fall O((n − m) m) = O(nm) bei einer Textlänge n und einer Musterlänge m, der zusätzliche Platzbedarf ist aber konstant und damit O(1).
  • Insbesondere für lange Muster wünscht man sich daher eine Verbesserung der Laufzeitkomplexität, gegebenenfalls auch bei einer Verschlechterung des Platzbedarfs.
17 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung :: Suche in Texten

Suche in Texten

Das Problem des Brute-Force-Verfahrens ist im Wesentlichen, dass bei Feststellen einer Nichtübereinstimmung sowohl der Zeiger im Muster als auch der Zeiger im Text zurückgesetzt werden.

An dieser Stelle setzt der Algorithmus von Knuth, Morris und Pratt an, der die Suche mit einer Komplexität von O(n + m) ermöglicht. 

function KMPSearch (text, pat) {
  // Eingabe: zu durchsuchender Text text der Länge n,
  // gesuchtes Muster pat der Länge m
  j = 0;
  for (i = 0;i<n;i++) {
    while (j >= 0 && pat[j] != text[i]) j = next[j]
    j = j + 1;
    if (j = m) return i − m + 1
  }
  return -1
}

Zwei geschachtelte Schleifen für die Brute-Force-Suche in Texten. Es wird ein voraus berechnetes Hilfsfeld next verwendet was Rücksrpungpositionen bei Nichtübereinstimmung angibt

18 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung :: Suche in Texten

Suche in Texten

function initNext (pat) {
  i = 0, j = − 1
  next[0] = − 1
  while (i < pat.length() − 1) {
    while (j > = 0 && pat[i] != pat[j])
      j = next[j]
    i++; j++
    next[i] = j
  }
  return next;
}

Berechung des Hilfsfeldes next

Die Anzahl der zu verschiebenden Stellen ist dabei nur vom Muster abhängig. Der Knuth-Morris-Pratt-Algorithmus (kurz »KMP«) nutzt dies aus, indem in einem Vorverarbeitungsschritt die Struktur des Musters analysiert wird. Daraus kann abgeleitet werden, wie weit im Fall einer Nichtübereinstimmung zurückgegangen werden muss. Diese Informationen werden in einem Feld gespeichert, das als next- bzw. border-Feld oder manchmal auch als Fehlerfunktion bezeichnet wird. Es enthält für jede Position des Musters die Distanz für eine sichere Verschiebung. Diese Werte werden bestimmt, indem für jedes j das längste Präfix des Musters pat ermittelt wird, das auch Suffix von pat[1… j] ist.

19 / 20

Stefan Bosse - Algorithmen und Datenstrukturen - Modul X Textverarbeitung :: Suche in Texten

Suche in Texten

Berechnung des next Feldes für das Muster ABCAAB

20 / 20