4.2.  Tokenizing

Tokenizing ist die zentrale Aufgabe in der Vorverarbeitung. Das Resultat der Tokenisierung ist eine Liste von Tokens, z.B. als Liste im technischen Sinn, oder als Abfolge von durch Zeilenumbrüche getrennten Tokens (sog. “vertikalisierter Text”)¹ Zugehörigkeit zu einer Tokenklasse, siehe 4.2.1 auf Seite 17 ) anhängen.

Der Tokeniser muss eine ganze Reihe von Einzel-Aufgaben erfüllen, deren korrekte Sequenzierung nicht einfach ist. Die folgende Aufzählung stellt nicht die korrekte Abfolge der einzelnen Schritte dar.

Genau so wie bei der Vorverarbeitung insgesamt kann man beim Tokenisieren in besonders schwierigen Fällen diese Aufgaben gar nicht streng sequentiell durchführen; dann müssen die einzelnen Funktionen verflochten ausgeführt werden.

4.2.1.  Einzelne Aufgaben des Tokenizing

Die grundlegende Vorgehensweise beim Durchführen der zentralen Aufgabe des Tokenisierens besteht in der Zerlegung der Eingabekette an bestimmten Zeichen.

Grundsätzlich müssen dafür “white space characters” (Blank, Tab, Line Feed und/oder Carriage Return) durch den Token-Trenner (also durch “newline” oder den Listenelement-Separator) ersetzt und Interpunktions-, Satz- und Sonderzeichen abgetrennt resp. isoliert werden.

Das Problem liegt in den Spezialfällen. Die Behandlung solcher Fälle kann entweder durch Isolieren² erfolgen (dann wirken die Trennungsprinzipien im Innern solcher Ausdrücke nicht) oder durch Re-Gruppieren getrennter Elemente (wir werden die erste Option wählen).

Im einzelnen müssen folgende Dinge geleistet werden (aber nicht notwendigerweise in dieser Reihenfolge!):

1. Abkürzungen erkennen und isolieren
2. Interpunktionen und Sonderzeichen erkennen
3. kontrahierte Formen expandieren
4. komplexe Tokens erkennen und isolieren
5. ggf. Tokens normalisieren
6. ggf. Tokens klassifizieren (d.h. Tokenklassen bilden)

Abkürzungen erkennen

Das Erkennen von Abkürzungen ist u.a. deshalb wichtig, weil Abkürzungspunkte natürlich nicht Satzendmarker sind (siehe 4.3 auf Seite 19 Wenn man also Abkürzungen nicht erkennt, wird man ganz falsche Satzenden setzen. Oft wird man Abkürzungen, wenn einmal erkannt, als solche klassifizieren (siehe 4.2.1 auf Seite 17 ).

Prinzipiell lassen sich Abkürzungen einfach erkennen: Man listet sie auf, und matcht den Eingabe-String dagegen (das funktioniert, weil Abkürzungen in aller Regel keine Beugung zulassen). In der Praxis ist das aber sehr schwierig. Erstens muss man diese Auflistungen zuerst mal haben - und sie sind nicht einfach zu beschaffen (nur die aller-allgemeinsten werden in Wörterbüchern vorkommen). Zweitens sind Abkürzungen sehr bereichsspezifisch (A.I. heisst einerseits Artificial Intelligence, anderseits auch Artificial Insemination). Das ist für das Erkennen unwichtig, aber nicht für das eventuell durchgeführte Normalisieren (siehe 4.2.1 auf Seite 15 ).

Interpunktionen und Sonderzeichen erkennen

Die Abtrennung der Interpunktionen und sonstiger Satz-/Sonderzeichen ist ebenfalls sehr schwierig. Satzzeichen sind in manchen Fällen als “Quasi-Wörter” (genauer: “Quasi-Wortformen”) zu markieren, denn oft haben sie selbst eine Bedeutung: z.B. ? vs. . vs. ! drücken verschiedene Sprechakte aus - und die sind (auch) in der automatischen Verarbeitung von Sprache zu unterscheiden. Analoges gilt für Kommata, Semikola und Auslassungspunkte (...). Sie alle verdienen es, als eigene Tokens dargestellt zu werden, denn sie spielen im Satz eine eigene Rolle (syntaktisch und semantisch).

Besondere Probleme schaffen Klammern, Schrägstriche und diverse Sonderzeichen (@, #, $ etc.). Sie sind meist Teil von Tokens und dürfen daher nicht isoliert werden (siehe 4.2.1 auf Seite 13 ).

Kontraktionen behandeln

Ein unerwartetes Problem ergibt sich beim vermeintlich einfachen Problem der Expansion von Kontraktionen:

l’auto  la auto
du frère  de le frère

Komplexe Tokens erkennen

Ein ganz schwieriges Feld sind die komplexen Tokens, d.h. solche Tokens, welche üblicherweise als Worttrenner verwendete Zeichen enthalten, z.B. 

• allgemeine Zahlen (1 000 000)
• Telefonnummern ((0155) 374 366),
• Daten und Zeitangaben (4. August und 13.20)
• URLs (www.cl.unizh.ch)
• E-Mail-Adressen (info@cl.unizh.ch)

Dass man diese Ausdrücke zu Tokens zusammenfassen sollte, ist recht klar, aber das waren nur die einfachsten Fälle. Sind auch die folgenden Ausdrücke alle je ein einziges Token?

• 13. Jahrestagung
• Euro 300,-
• 12 Milliarden Pfund
• Bill Gates
• Bill Gates, CEO of Microsoft
• Bill Gates, Chief Executive Officer of Microsoft
• Kohlendioxid(CO2)
• Kohlendioxid(CO2)-Problematik

Letzlich hängt die Entscheidung, was alles zu einem einzigen Token gehören soll, davon ab, was man mit dem analysierten Text machen will:

• Wenn man z.B. einen Text automatisch übersetzen will, wird es wenig sinnvoll sein, Bill Gates, CEO of Microsoft (und auch Bill Gates, Chief Executive Officer of Microsoft) als ein einziges Token zu behandeln, denn der Ausdruck CEO of Microsoft kann (und muss) nach den ganz normalen Regeln der Übersetzung behandelt werden und sollte weder für sich als Token behandelt werden noch zusammen mit Bill Gates.

  Ausdrücke wie Euro 300,- wären in einem derartigen Anwendungszusammenhang hingegen besser als einzelnes Token zu behandeln (und vermutlich auch noch nach Tokenklasse zu kategorisieren; siehe 4.2.1 auf Seite 17 ), denn hier kommen vermutlich sehr spezifische, nur für genau diese Art von Ausdruck relevante, Übersetzungsregeln zum Tragen (je nach dem Locale, in der Terminologie der Textverarbeitung).

• Wenn man über einem Text Informationsextraktion betreiben will, wäre es hingegen durchaus sinnvoll, Bill Gates, CEO of Microsoft (und Bill Gates, Chief Executive Officer of Microsoft) als ein einziges Token zu behandeln, denn dieser Ausdruck bezieht sich in der realen Welt ja als Ganzes auf ein bestimmtes Objekt (hier: eine bekannte Person), und in der Informationsextraktion geht es primär darum, Beziehungen zwischen solchen Objekten zu ermitteln (“Wer übernahm wen wann für wieviel?”).
• Wenn das Ziel Antwortextraktion ist, dürfte es hingegen besser sein, Bill Gates einerseits und CEO of Microsoft anderseit je als ein Token zu behandeln, denn es dürfte in einer derartigen Anwendung wichtig sein, dass die Funktion von Bill Gates, die des CEO, in der logischen Repräsentation explizit dargestellt werden kann.

Bei diesen Fragen befinden wir uns an der Grenze zu zwei wichtigen weiteren Operationen in der Verarbeitung natürlicher Sprache, und zwar zur sog. named entity recognition um zur Erkennung von Mehrwort-Einheiten.

1. Die oben genannten Ausdrücke sind nämlich alle in ihrer Funktion den Eigennamen insofern ähnlich, als sie auf einmalige Objekte in der Welt referieren. Dazu gehören neben den Namen von Personenen natürlich auch Bezeichnungen für politische und wirtschaftliche Organisationen und für geographische Objekte, aber eben auch Mass-, Währungs- und Zeitangaben u.dgl.m., wie oben angeführt. Tatsächlich kann man auch eine Massangabe (16 cm) oder eine Zeitangabe (4-8-97) so sehen: Man verweist auf ein abstraktes, aber einmaliges Objekt (es gibt ja z.B. nicht verschiedene Instantiationen des vierten Tags im August 1997). Deshalb nennt man die Aufgabe, derartige Ausdrücke zu identifizieren, oft “named entity recognition”. Siehe dazu (insbes. zu den Techniken, die man anwenden kann) mehr innerhalb der Lerneinheit  “Reguläre Ausdrücke”.
2. Ob man schliesslich auch Mehrwort-Einheiten als komplexe Tokens behandeln will, ist ebenfalls eine nicht-triviale Frage. Bei Ausdrücken, die allein mit Hilfe eines Lexikons erfasst werden können (weil sie indeklinabel sind), wie en passant, im Folgenden, on line usw., wäre das relativ einfach zu realisieren. Wäre es aber auch sinnvoll?

   Aber soll man Mehrwortterme (wie Chief Executive Officer und air traffic controller) ebenfalls als komplexe Tokens zu erfassen versuchen? Es ist schwieriger, weil sie in einem allgemeinsprachlichen Wörterbuch vermutlich nicht aufgeführt sind, und weil sie in verschiedenen Beugungsformen vorkommen, was einen einfachen Lexikon-Lookup ohnehin unmöglich macht. Und erneut: Wäre das sinnvoll?

Die Abgrenzung der Tokenisierung zu named entity recognition und zur Erkennung von Mehrwort-Einheiten ist letzlich nur pragmatisch zu machen: Ist es einfacher, übersichtlicher und effizienter zu implementieren, wenn man diese Funktionen trennt oder wenn man sie in einem einzigen Modul zusammenfasst?

Tokens normalisieren

Die Wortnormalisierung dient vor allem dazu, in der (späteren) Phase (z.B. des part-of-speech-tagging oder Parsing) die Erkennung der Wortart sicherzustellen. Hierfür ist es ggf. nötig, 

• produktive Konstruktionen wie Zahlwörter auf eine einheitliche, unveränderliche Repräsentationsform abzubilden (da sonst prinzipiell unendlich viele entsprechende Lexikoneinträge vorhanden sein müssten)
• in verschiedenen Formen vorkommende Tokens zu vereinheitlichen, z.B.
  1. Abkürzungen:

     {U.S.A. | USA | U.S. of America}  U.S.A.
  2. Datums-, Zeit- und Massangaben:

     4. 8.       | 1997
     4. Aug.     |  97
     4. August   | ’97
     
     4.8.97, 4-8-97, 4/8/97, 8/4/97 (US-Version!)
     (resp. 1997, 97, ’97)

     13.20, 13:20, 1.20 pm
     
     60.8^∘ F
     16^∘ C
     16^∘
     
     16 cm
     0.16 m
     6.2992 in
     6.2992"
     0.5249 ft
  3. aber auch Zahlen an sich, die in verschiedenen Ländern bekanntlich ganz verschieden geschrieben werden:

     19000, 19’000, 19 000, 19,000
     
     2,5
     2.5
     2.500

  Die verschiedenen Formen dieser Tokens müssen nicht nur auf eine einheitliche (eben: kanonische) Form reduziert werden, sondern es wird oft sinnvoll sein, sie gleich auch noch zu kategorisieren, d.h. Tokenklassen zu bilden. Siehe gleich anschliessend.

Tokenklassen bilden

Wie wir gesehen haben, sind nicht alle Tokens Wortformen im engeren Sinne. Da dieTokenisierung sowieso eine intensivere Analyse der Eingabekette erfordert, lohnt es sich in vielen dieser Fälle, gleich noch eine Klassifizierung der Tokens in Tokenklassen vorzunehmen. Dies kann vor allem die Verarbeitung in nachfolgenden Modulen massiv vereinfachen.

Besonders klar wird das im Fall von Zahlausdrücken. Es bringt nichts, folgende Normalisierung durchzuführen

drei  3

drei  nbr(3)

Mögliche Kandidaten für weitere Tokenlassen sind ABBR für Abkürzungen, TIME resp. DATE für Zeit- und Datumsangaben oder CURRENCY für Währungsangaben, TEMP und LENGTH für Temperatur- und Längenangaben u.v.a.m.

Dies würde dann etwa für folgende Sätze

(1)

Diese Schuhe haben sFr. 147.- gekostet."

(2)

Wir treffen uns am 24. April um 15 Uhr."

folgende Resultate ergeben:³

dreier  nbr(3,det,gen,plur,Gender)

Manchmal muss die Kategorisierung von Wortformen ggf. sogar via typographische u.ä. Merkmale im Druckbild erfolgen. So heisst z.B. in Unix-Manuals der Fettdruck in cp “Kommandobezeichnung”, und diese Information wird man für nachfolgende Verarbeitungsschritte verfügbar machen wollen. In ExtrAns sieht das dann so aus:

cp   cp.com

4.2.2.  Sequenzierung der Aufgaben beim Tokenisieren

Nicht nur die Art der Einzelschritte, sondern auch die Reihenfolge, in der die verschiedenen Schritte zur Tokenisierung vorgenommen werden, ist ganz entscheidend für den Erfolg. Hier warten allerhand Überraschungen auf den Tokeniser.

Versuchen Sie, in der (ILAP) (Experiment) Tokenisierung zu ermitteln, wie die optimale Reihenfolge für den vorgegebenen Text aussieht. Das ist gar nicht so einfach. Und experimentieren Sie danach auch mit eigenen Texten!

Wenn Sie glauben, Sie hätten die optimale Reihenfolge gefunden, testen Sie Ihr Wissen im Satzergänzungstest (SET) Tokenisierungsoperationen ordnen.

Sie können hier zwei fertige Tokeniser ausprobieren. Versuchen Sie durch die Eingabe sinnvoll gewählter Ketten zu ermitteln, welche Prinzipien diese zwei Programme anwenden und wodurch sie sich unterscheiden! (ILAP) (Demo) Zwei Prolog-Tokeniser im Vergleich

Und zum Schluss können Sie Ihr Wissen zur Tokenisierung in folgendem Selbsttest testen: (QUIZ) Tokenisierung