Zerlegung von Webuser-Kommentaren

Zerlegung von Webuser-Kommentaren
Seminararbeit
von Simon Rüppel
Institut für theoretische Informationstechnik (TI) der RWTH Aachen
Betreuender Professor: Prof. Dr. Gerhard Dikta
Betreuerin (TI): Melanie Neunerdt
S. 1
1 Einleitung ................................................................................................................................. 3
1.1 Aufgabenstellung .............................................................................................................. 3
1.2 Zusammenfassung ............................................................................................................ 4
2 Tokenisierung .......................................................................................................................... 5
2.1 Stand der Technik ............................................................................................................. 5
2.2 Tokenisierung für Webkommentare ................................................................................ 6
2.3 Match Kriterien ................................................................................................................. 8
2.4 Problemklassen............................................................................................................... 13
3 POS-Tagging ........................................................................................................................... 14
3.1 Stand der Technik ........................................................................................................... 14
3.2 Vorverarbeitung für POS-Tagging ................................................................................... 14
3.3 Korrektur von Umlauten und Mehrfachbuchstaben ...................................................... 15
3.3.1 Pseudocode .............................................................................................................. 15
3.3.2 Beispiel ..................................................................................................................... 17
3.4 Groß-/Kleinschreib-Korrektur ......................................................................................... 18
3.4.1 Pseudocode .............................................................................................................. 18
3.4.2 Beispiel ..................................................................................................................... 19
4 Benutzung des Tokenizers ..................................................................................................... 20
5 Fazit ....................................................................................................................................... 20
6 Literatur ................................................................................................................................. 21
S. 2
1 Einleitung
Um Texte automatisiert analysieren zu können, ist eine komplexe Regelung zur Zerlegung
der Kommentare in Tokens erforderlich. Ein Tokenizer ist ein Programm, das einen Text in
sinnvolle Tokens (Stücke) zerlegt. Sinnvoll heißt dabei, dass nach bestimmten Regeln Teile
von Zeichen zusammengehalten oder getrennt werden. Zum Beispiel werden Satzzeichen
von übrigem Text getrennt.
Nachdem mit Hilfe eines Tokenizers alle Zeichensequenzen eingeteilt wurden, kann der
nächste Schritt der Webkommentaranalyse, das „Part of Speech Tagging“ (POS-Tagging)
durchgeführt werden. Beim POS-Tagging wird jedem Token ein „Tag“, welches z.B. ein
Nomen, ein Verb, ein Adverb, ein Satzzeichen o.ä. beschreibt, zugewiesen.
1.1 Aufgabenstellung
Es soll ein Tokenizer für Webkommentare entwickelt werden, dessen Ausgabe insbesondere
die Voraussetzungen für adäquates POS-Tagging erfüllt.
Zu beachten ist, dass man bei Webkommentaren mit Umgangssprache und Schreibfehlern
rechnen muss. Daher sollen Verfahren zur Korrektur implementiert werden. Außerdem
tauchen ganz neue Tokens, wie z.B. Emoticons, URLs, Dateinamen, Usernamen usw. auf, die
erkannt werden müssen. Demzufolge, muss der Tokenizer mit web-spezifischen Texten
umgehen können.
Die Ergebnisse des Tokenizers dienen als Input für das POS Tagging.
S. 3
1.2 Zusammenfassung
Die folgende Seminararbeit ist wie folgt gegliedert: Kapitel 2 beschreibt die Tokenisierung
und Kapitel 3 die Vorverarbeitung für das POS-Tagging. Kapitel 1 beinhaltet die Einleitung
und Kapitel 4 eine stichpunktartige Zusammenfassung der Funktionsweise des Tokenizers
mit abschließendem Fazit (Kapitel 5).
Im Kapitel der Tokenisierung wird zunächst auf den aktuellen Stand der Technik (2.1)
eingegangen – also welche Tokenizer gibt es bereits und welche Eigenschaften haben diese.
Außerdem werden die Anforderungen an den Tokenizer konkretisiert. Im nächsten Abschnitt
(2.2) wird beschrieben, wie der implementierte Tokenizer funktioniert und mit welcher
Technik Kriterien umgesetzt werden. Dazu sind zwei Pseudocodes aufgeführt. Es folgt der
Abschnitt „Match-Kriterien“ (2.3), in dem anhand einer Liste die vom Tokenizer benutzten
Matches/Kriterien aufgeführt werden. Im Abschnitt 2.4 „Problemklassen“ werden in einer
Tabelle Beispiele für Input-Strings angezeigt und die dazugehörigen Tokens als Beispiel für
eine Tokenisierung. Damit ist Kapitel 2 (Tokenisierung) abgeschlossen.
Kapitel 3 gibt zunächst den „Stand der Technik“ (3.1) bezüglich POS-Tagging wieder.
Abschnitt 3.2 beschreibt, welche Anforderungen an die Vorverarbeitung der Tokens für das
POS-Tagging gestellt werden. Folglich wird in 3.3 detailliert die Korrektur von
Mehrfachbuchstaben und Umlauten sowie die Korrektur von Rechtschreibfehlern in 3.4
abgehandelt. Beide Punkte sind mit Pseudocodes und Beispielen versehen.
S. 4
2 Tokenisierung
In diesem Kapitel wird kurz auf den aktuellen Stand der Technik von Tokenizern
eingegangen. Danach wird der entwickelte Tokenizer mittels Pseudocode detailliert
vorgestellt. Eine Tabelle für Matches/Kriterien und Problemklassen wird ebenfalls
vorgestellt.
2.1 Stand der Technik
Bisher gibt es nur wenige Tokenizer. Die einfachste Methode ist ein „Whitespace-Tokenizer“,
der Tokens an Leerzeichen trennt. Für Zeitungsartikel reicht ein „Whitespace-Tokenizer“ mit
Erkennung von Satz-Ende-Zeichen (z.B. TreeTagger). Webkommentare benötigen dagegen
komplexere Tokenizer. Durch die fehlende Standardisierung von Webkommentaren, gibt es
insbesondere keine eindeutige Tokenisierung. Dies veranschaulicht das folgende Beispiel.
Beispielsatz: Hallo wie geht’s :-)??
Gewünschte Tokenisierung:
Hallo
wie
geht
‘s
:-)
??
Whitespace-Tokenizer:
Hallo
wie
geht’s
:-)??
TreeTagger-Tokenizer:
Hallo
wie
geht’s
:-
)
?
?
Whitespace- und Treetagger-Tokenizer liefern keine adäquate Tokenisierung für POS
Tagging.
Es gibt Ansätze zur Tokenisierung solcher Texttypen. Dazu zählen Tokenizer für TwitterKommentare [1] und ein Tokenizer, der speziell Emoticons erkennt („Sentiment-Tokenizer“
[2]). Allerdings gibt es für Webkommentare allgemein noch keinen Tokenizer, der den
Anforderungen der POS-Annotation entspricht.
S. 5
2.2 Tokenisierung für Webkommentare
Zur Implementierung des Tokenisierungs-Algorithmus wird die Programmiersprache JAVA
verwendet.
Zunächst werden reguläre Ausdrücke initialisiert und drei Listen eingelesen, welche zur
Konstruktion von drei regulären Ausdrücken benötigt werden. Nach der Initialisierung
beginnt der eigentliche Algorithmus. Es wird ein UTF-8-kodierter Zeichenstrom eingelesen.
Dieser wird zeilenweise in ein String-Array gespeichert, welches an den Tokenizer übergeben
wird.
Zunächst trennt der Tokenizer an jedem Leerzeichen, Tabulator und Zeilenumbruch (JavaFunktion: „split“ – siehe „Algorithmus 1“). So wird ein Start-Array erstellt. Für jedes ArrayElement wird dann der eigentliche Tokenizer-Algorithmus aufgerufen – eine rekursive
Funktion (siehe „Algorithmus 2“).
Es wird eine rekursive Funktion genutzt, um partielle Matches effektiv zu implementieren.
Die rekursive Funktion wendet eine Reihe von Kriterien auf den Eingabe-String an. Die
Matches dienen dazu, die Zeichenfolgen entweder an den richtigen Stellen zusammen zu
halten oder genau an der richtigen Stelle zu trennen. Dabei unterscheidet man zwischen
partiellen und exakten Matches.
Ein exakter Match prüft, ob der Input-String einer Zeichenfolge entspricht – ein partieller
Match sucht den Input-String nach einem Muster ab und gibt einen Bereich, in dem der
partielle Match gefunden wurde, zurück (partieller Match gibt „Start“ und „End“-Punkt
zurück). Somit erhält man drei Bereiche. Erstens den Bereich, der dem partiellem Match
entspricht, dann den Teil vor dem gematchten Teilstring und nach dem gematchten
Teilstring. Die beiden Teilstrings vor und nach dem gematchten String werden rekursiv
weiterverarbeitet. Hierbei ist die Reihenfolge der Tokens zu beachten. Der Algorithmus läuft
„inorder“ ab, was zur Folge hat, dass die Tokens in der richtigen Reihenfolge in die finale
Liste gespeichert werden.
Partielle Matches werden mit Hilfe der JAVA-Klasse „Matcher“ durchgeführt. Diese bietet
Funktionen wie „find()“, „start()“ und „end()“ an. „Matcher“ wird ein „Pattern“ übergeben
und Pattern wird mit „Pattern.compile(String regex)“ initialisiert. Das Pattern/der reguläre
Ausdruck muss so nur einmal bei der Initialisierung des Tokenizers kompiliert werden.
Exakte Matches werden mit der Funktion „String.matches(String regex)“ durchgeführt. Es
kommt auch vor, dass ein exakter Match als Bedingung verwendet wird und dann zum
Suchen noch ein partieller Match hinterher gestellt wird. Die einzelnen Kriterien, die durch
Matches realisiert werden, werden in Tabelle 1 im Kapitel 2.3 aufgeführt.
Es gibt außerdem noch eine weitere Eigenschaft die jeder String und Teilstring hat – das
Zeichen, das vor und nach dem String/Teilstring steht. Dabei ist ein Leerzeichen Platzhalter
S. 6
für Zeilenumbrüche und String-Anfang beziehungsweise String-Ende. So kann man zum
Beispiel sicherstellen, dass bei Emoticons, welche mit einem Buchstaben anfangen, kein
partieller Match auf ein Emoticon stattfindet, wenn genau vor dem Emoticon noch ein
weiterer Buchstabe steht. Betrachtet man das Beispiel „Bild:“ (ohne diese Eigenschaft)
würde der Emoticon „d:“ erkannt werden. Es gibt noch weitere Fälle dieser Form, bei denen
ein Kriterium von dem davor/danach gestelltem Zeichen abhängt.
Wenn ein Kriterium erfüllt wird, wird ein String als Token in eine finale Liste eingetragen. Am
Ende des Algorithmus, bekommt man ein Array mit allen Tokens zurück.
Die Klasse „Tokenize“ schreibt das finale Array zeilenweise in einen UTF-8-kodierten
Zeichenstrom auf Standard-Output. Da Webkommentare durch eine Vielzahl an
verwendeten Sonderzeichen charakterisiert sind, ist es wichtig, diese korrekt weiterzuleiten.
Der Tokenizer arbeitet mit folgenden Sonderzeichen: öäüÖÄÜ߀“„’´»«…
Algorithm 1
Function: tokenize(st)
Input: String-Array st
Output: final Token-Array finalStrings
split Tokens at whitespaces and call function rekusiveStep()
for each String s from input
spilt = split s at „ „
for each String s2 from split
finalStrings <- rekursiveStep(s2)
end for
end for
return finalStrings
Algorithm 2
Function: rekursiveStep(s)
Input: String s
Output: no return value, save final Strings in Token-Array finalStrings.
Do recursive function for String s
for each Criteria c
if s matches exactMatch(c) then
find partialMatch(c) with start and end
if character at start-1 fullfil condition and character at end+1 fullfil condition
then
(wl, wm, wr) ← „partieller match“
rekursiveStep(wl)
add wm to finalStrings
rekursiveStep(wr)
end if
end if
end for
S. 7
2.3 Match Kriterien
Im Folgenden sind die einzelnen Trennkriterien im rekursiven Algorithmus tabellarisch
aufgeführt. Ein Kriterium ist eine Regel, die mit einem regulären Ausdruck arbeitet und
Zeichenstücke als finale Tokens speichern und/oder Zeichenstücke rekursiv
weiterverarbeiten kann. Die Kriterien wurden iterativ in Anlehnung an gegebene
Trainingsdaten entwickelt. Mit Trainingsdaten sind hier manuell tokenisierte Daten gemeint.
In der ersten Spalte befindet sich eine Beschreibung des Trennkriteriums – also nach
welchen Kriterien Tokens getrennt oder zusammen gehalten werden. Zusatzbedingungen die
sich auf Buchstaben vor oder nach dem Match beziehen werden in dieser Spalte ebenfalls
aufgeführt. In der zweiten Spalte wird auf die Form des Matches eingegangen. Es wird
beschrieben, ob ein exakter, ein partieller Match oder beide Formen von Matches genutzt
werden. In der dritten Spalte werden genutzte reguläre Ausdrücke angegeben. Außerdem
wird auf Bedingungen in der Beschreibung hingewiesen (If-Abfragen). Spalte vier zeigt ein
Beispiel für den Match. Die letzte Spalte enthält die Tags, welche für das POS-Tagging von
Bedeutung sind. Diese Tags werden nach dem Tokenisierungsvorgang in POS-Tags übersetzt.
Tabelle 1: Match Kriterien
Beschreibung
Match
1
Trenne Wörter mit
umgangssprachlichen „s“ anstelle von
„es/das“. Zwei
Tokens als Resultat.
Exakter Match auf
eine Liste von
Wörtern, bei denen
ein
umgangssprachliches „s“ am Ende
steht.
2
@ am Anfang eines Partieller Match auf
Wortes abtrennen. ein @-Zeichen als
ersten Buchstaben.
3
URL zusammenhalten.
S. 8
Regulärer Ausdruck Beispiel
/ If-Abfragen
gehts →
geht + s
Tags
s bekommt
ABKUERZUNG
@heise
@ bekommt
→@+
ZEICHEN
rek(heise)
Partieller Match auf (http://)?(www.)?[a www.hall WWW
eine URL
-zA-Z0-9/@_\.~o.de
]*(\.com|\.net|\.or
g|\.info|\.[a-z][az]($|/))[a-zA-Z09!#\$%&'\(\)*+,/:;=
?@\[\]_\.~-]*
Beschreibung
Match
4
Dateinamen
zusammenhalten.
Partieller Match auf .*(\.jpg|.txt|.html|. Hallo.zip
einen Dateinamen. xml|\.css|\.doc|\.gi
f|\.avi|\.bin|\.mp3
|\.iso|\.exe|\.mpg|
\.png|\.zip|\.rar|\.j
ar)
DATEI
5
Einheiten mit „/“
zusammenhalten.
Partieller Match auf (((m|k|g|t)?b(it|yte km/h
eine Einheit.
)?|(m|c|k|µ)?m)|(k
|m|µ)?g|t|n|j|µ?w
|k?cal|v|c|a|l|1|d
|h|min|s)(²|³)?/(s|
min|h|d|y|(k|m|µ)
?g|t|l|(m|c|k|µ)?
m)(²|³)?
EINHEIT
ABKUERZUNG
6
Aufzählung/Datum Partieller Match auf
zusammenhalten. eine
Vorher steht ein
Aufzählung/Datum.
Leerzeichen oder
nichts, Nachher
steht keine Zahl.
7
Aufzählung
zusammenhalten.
Vorher steht ein
Leerzeichen oder
nichts.
Partieller Match auf ((i|v|x)+|(I|V|X)+)(\ 5)
eine Aufzählung.
.|\)|\.\))|\d{1,2}\.?\
) Außerdem ifAbfrage für
Buchstabe vorher
8
Abkürzungen mit
Punkt aus Liste
zusammenhalten.
Vorher steht kein
Buchstabe und
keine Zahl, Vorher
und Nachher steht
kein Bindezeichen.
Partieller Match auf If-Abfrage für
eine Liste von
Buchstabe
Abkürzungen.
vorher/hinterher
9
Abkürzungen ohne Partieller Match auf If-Abfrage für
Punkt aus Liste
eine Liste von
Buchstabe
zusammenhalten. Abkürzungen.
vorher/hinterher
Vorher und
Nachher steht kein
Buchstabe, keine
Zahl und kein
Bindezeichen. Nicht
case-sensitiv.
S. 9
Regulärer
Ausdruck/IfAbfrage
Beispiel
\d{1,2}\. Außerdem 31.
if-Abfrage für
Buchstabe
vorher/hinterher
Tags
AUFZAEHLUNGO
DERDATUM
AUFZAEHLUNG
bzw. usw. ABKUERZUNG
mp3
ABKUERZUNG
Beschreibung
Match
Regulärer
Ausdruck/IfAbfrage
Beispiel
10 Umgangssprachlich
e Wörter mit
Apostroph
zusammenhalten.
Nachher steht kein
Buchstabe.
Partieller Match auf
den Teil des Wortes
nach dem
Apostroph.
('|’|´|`)(s|nen|ne|n 'nen
)
Außerdem ifAbfrage für
Buchstabe nachher.
11 Datum
zusammenhalten.
Vorher steht kein
Buchstabe.
Partieller Match auf (\d{1,2}\.){1,2}\d*
ein Datum.
Außerdem ifAbfrage für
Buchstabe vorher.
10.11.12
DATUM
12 Emoticon mit
anführenden
Buchstaben
zusammenhalten.
Vorher steht kein
Buchstabe.
Partieller Match auf [dDpP@][\ein solches
o\*\']?[:;][<>]?
Emoticon.
Außerdem ifAbfrage für
Buchstabe vorher.
d:
SMILEY
SATZENDE
13 SonderfallPartieller Match auf \)+[\-o\*\']?[:;][<>]? ):
Emoticon ):
ein solches
zusammenhalten. Emoticon.
Vorher steht weder
Buchstabe noch
Zahl
SMILEY
SATZENDE
14 Emoticon mit
Partieller Match auf
Buchstabe am Ende ein solches
zusammenhalten. Emoticon.
Nachher steht kein
Buchstabe.
SMILEY
SATZENDE
[<>]?[:;][\:D
o\*\']?[dDpP@]
Außerdem ifAbfrage für
Buchstabe nachher
15 Buchstabe als
Aufzählung
zusammenhalten.
Vorher steht kein
Zeichen (nur
Leerzeichen
erlaubt).
Partieller Match auf ^[a-zAeiner solchen
ZäöüÄÖÜß]\)
Aufzählung.
16 Emoticon ohne
Buchstabe
zusammenhalten.
Partieller Match auf [<>]?[:;][\:-)
o\*\']?([\]\[/\}\{\|\\]|
ein solches
\)+|\(+)|(\(+|[\]\[/\}\{
Emoticon.
ABKUERZUNG
AUFZAEHLUNG
SMILEY
SATZENDE
\|\\])[\o\*\']?[:;][<>]?
17 Sonderfallemoticon Partieller Match auf \[\+\+\]|,\s zusammenhalten. ein solches
\)|\^\^|==|-\.Emoticon.
S. 10
a)
Tags
^^
SMILEY
SATZENDE
Beschreibung
Match
Regulärer
Ausdruck/IfAbfrage
Beispiel
Tags
4:39
ZEIT
18 Uhrzeit
zusammenhalten.
Partieller Match auf \d+:\d+
eine Uhrzeit.
19 Zahlen als
kombinierte
Abkürzung
zusammenhalten.
Partieller Match auf \d+(st\.|j\.|jähr.*|t 2te
eine solche
äg.*|te(l|s)|ste(s|l)
Abkürzung.
|fach|%ig|prozenti
g|er|en|ling|th|XT)
ABKUERZUNG
20 Kommazahl
zusammenhalten.
Partieller Match auf \d+[,\.]\d+
eine Kommazahl.
5,1
ZAHL
21 Preisangaben
zusammenhalten.
Partieller Match auf \d+,eine Preisangabe.
5,-
ZAHL
22 Mehrfache
Satzendzeichen
zusammenhalten.
Partieller Match auf [.!?]{2,}|…
mehrfache
Satzendzeichen.
!!?
MULTIZEICHEN
SATZENDE
800x600
x bekommt
VERBUND
23 Zahlen, die duch x Exakter Match auf *\d+[xX]\d+.* und
getrennt werden, in ein Gebilde der
[xX]
3 Teile aufteilen.
Form 10x10.
Partieller Match auf
das x.
24 Satzzeichen
abspalten.
Partieller Match auf [»«~,#;<>|!?^)(*.:=\ !
ein Satzzeichen.
[\]\\+]
ZEICHEN
bei . ? oder !
SATZENDE
25 Zahl+Einheit
trennen.
Exakter Match auf
Zahl+Einheit.
Partieller Match auf
die Einheit.
Einheit bekommt
EINHEIT
\d+[a-zA10Euro
ZäöüÄÖÜß%$€][azAZäöüÄÖÜß%$€/²³&
_-]* und [a-zAZäöüÄÖÜß%$€][azAZäöüÄÖÜß%$€/²³&
_-]*
26 Wort+Zahl trennen. Exakter Match auf [a-zAWort+Zahl.
ZäöüÄÖÜß_]+\d+
Partieller Match auf und \d+
die Zahl.
Peter199 Zahl bekommt
0
ZAHL
27 Unterstrich vor
Buchstabe nach
Zahl trennen.
1990_Pet Zahl bekommt
er
ZAHL
S. 11
Exakter Match auf
\d+_[a-zAZahl+_+Wort.
ZäöüÄÖÜß.]+ und
Partieller Match auf \d+
die Zahl
Beschreibung
Match
Regulärer
Ausdruck/IfAbfrage
Beispiel
Tags
-20
- bekommt
ZEICHEN
28 Minus+Zahl
trennen.
Exakter Match auf - -\d.*
+Zahl. Partieller
Match auf das -
29 Zusammengesetzte
Worte zusammenhallten. Jedes
Verbindungszeichen
muss an eine NichtZahl grenzen. Gibt
es eine gerade
Anzahl an
Anführungszeichen,
benutze diese nicht
als Trennkriterium
(Beispiel: „Test“Version). Zahl vor
Bindestrich am
Ende, _ und & am
Ende immer
abtrennen. _ und &
am Anfang immer
abtrennen.
Exakter Match auf
zusammengesetztes
Wort. Danach
partieller Match auf
zusammengesetztes
Wort.
30 Weitere
Satzzeichen
abspalten.
Partieller Match auf [&_/"’'´`”„“-]
ein Satzzeichen.
„
ZEICHEN
31 Zahl als Zahl
deklarieren.
Exakter Match auf
eine Zahl.
\d+
55
ZAHL
32 Produktnamen als
Produkt
deklarieren.
Exakter Match auf
ein Produkt.
(\d?[a-zAPCG-C1
ZäöüÄÖÜß]+\d+([azAZäöüÄÖÜß]|\d)*)|(
\d+[a-zAZäöüÄÖÜß]+)
S. 12
*([a-zASuper&M VERBUND
ZäöüÄÖÜß'\"„”“.][& ega-Toll Bei Entsprechung
_-]|[&_-][a-zAeines weiteren
ZäöüÄÖÜß'\"„”“.]).*
regulären
und ([a-zAAusdrucks
ZäöüÄÖÜß'\"„“”.][&
PRODUKT
_][\\wäöüÄÖÜß'\"„“”
.]|[&_-][a-zAZäöüÄÖÜß'\".]|[\\w
äöüÄÖÜß'\"”„“.])+-?
Außerdem ifAbfragen um alle
Bedingungen in der
Beschreibung zu
erfüllen
PRODUKT
2.4 Problemklassen
In Tabelle 2 werden einige Probleme dargestellt, die mit einem Standardtokenizer nicht
abgehandelt werden können. Der neu entwickelte Tokenizer behandelt diese Probleme
richtig. In der ersten Spalte wird die Problemklasse beschrieben, in der zweiten Spalte wird
ein Inputstring angegeben, der dem Problem der Problemklasse entspricht und in der dritten
Spalte werden die Tokens des entwickelten Tokenizers durch Leerzeichen separiert
angegeben.
Tabelle 2: Problemklassen
Problem
Datum, Uhrzeit,
Leerzeichen
vergessen
Emoticon direkt
nach Satzende,
Punkt nach
Abkürzung, 'es'
mit 's' abgekürzt
Leerzeichen
vergessen oder
URL?
Inputstring
Aachen,den20.04.2012(13:49
):
Tokens
Aachen , den
20.04.2012 ( 13:49 )
:
Was gibts denn so??;)
(bzw. wie geht´s?)
Was gibt s denn so ??
;) ( bzw. wie geht ´s
? )
schau.mal auf
hallo12345.de^^ oder
hallo12345.de/index.php
schau mal auf
hallo12345.de ^^ oder
hallo12345.de/index.p
hp
"Test"-Verfahren und
" Test-Verfahren "
"Test"-Verfahren und
Anführungszeiche
"Test-Verfahren"
n bei
Bindewörtern
Lach- und Sach&FachZusammengeGeschichten
setzte
Bindewörter
Zusammenhalten a) lalal(a) (ergebnis): ):
:D :Das bild: d: bild:)
bei Konflikten
zwischen
Emoticons,
Satzzeichen,
Aufzählungen
Tariq81 1,99€ 2,- Zahlenangaben
2,478Meter
1280x1024
und Einheiten
1280*1024 12km/h
Aufzählung,
Rechnungen,
Produktnamen
:
S. 13
1. 65,3-50.3=30/2 65xt-50
Lach- und Sach&FachGeschichten
a) lalal ( a ) (
ergebnis ) : ): :D :
Das Bild : d: bild :)
Tariq81 1,99 € 2,- 2,478 Meter 1280 x
1024 1280 * 1024 12
km/h
1. 65,3 - 50.3 = 30 /
2 65xt-50
3 POS-Tagging
POS-Tagging beschreibt die Zuordnung von Wortarten zu Wörtern und Satzzeichen (Tokens).
Dabei wird auch der Kontext eines Tokens berücksichtigt, indem vorher stehende Tokens zu
Entscheidungen beitragen. Unter Wortarten versteht man zum Beispiel „Nomen“, „Adjektiv“
oder „Satzfinales Zeichen“.
3.1 Stand der Technik
Das Tagging ist ein automatisiertes Verfahren, welches mit überwachtem oder
unüberwachtem maschinellen Lernen umgesetzt werden kann. Hier werden überwachte
Verfahren implementiert, bei denen das deutsche „Stuttgart-Tübingen-Tagset“ (STTS) mit 54
Tags verwendet wird. Bekannte Tagger für das Deutsche sind der TreeTagger [3], der
Standford-Tagger [4], [5] und der TnT-Tagger [6]. Die beschriebenen Tagger basieren in der
Regel auf einem Markov Model (Tree-Tagger) oder einem „Maximum Entropy“-Ansatz [7]
(Standford-Tagger).
Ein Beispiel zum POS-Tagging lautet:
Wort
Tag
Peter
NE
backt
VVFIN
einen
ART
leckeren
ADJA
Kuchen
NN
.
$.
3.2 Vorverarbeitung für POS-Tagging
Unter Verwendung einiger Kriterien (beschrieben in Tabelle 1) werden POS TagInformationen für ausgewählte Tokens a priori erzeugt. Zum Beispiel werden für das „Part of
Speech Tagging“ alle Produkt-Bezeichnungen als sogenannte „Named Entity“ (NE) getaggt.
Weiterhin wird eine lexikon-basierte Bereinigung der Tokens durchgeführt.
Das Lexikon wird als sortierte Liste eingelesen und kann dann als binärer Suchbaum
durchsucht werden. Dafür steht bereits eine Funktionalität in JAVA zur Verfügung. Die
Suchfunktionalität wird durch die Klasse „Woerterbuch.java“ bereitgestellt.
Es gibt drei Arten von Korrekturen:
1. Korrektur von Mehrfachbuchstaben
2. Korrektur von Umlauten ae, ue, oe und ss statt ß
3. Korrektur von Groß- und Kleinschreibung
Dabei ist 1. und 2. zusammen implementiert und 3. separat.
S. 14
3.3 Korrektur von Umlauten und Mehrfachbuchstaben
Bei Webkommentaren kommt es gelegentlich vor, dass Benutzer versehentlich oder
absichtlich durch gedrückt halten einer Taste Buchstaben wiederholt hintereinander gereiht
schreiben. Zum Beispiel „Hallooo“. Beim POS-Tagging führt aber „Hallooo“ zur fehlerhaften
Annotation. Es sollte „Hallo“ annotiert werden.
Es wird ein rekursiver Algorithmus implementiert, der prüft, ob Wörter mit x gleichen
Buchstaben auch mit nur einer oder zwei Wiederholungen in einem Lexikon stehen. Gibt es
mehr als drei Wiederholungen eines Buchstabens und wird kein Lexikoneintrag gefunden, so
wird trotzdem auf drei Buchstaben reduziert. Der detaillierte Ablauf ist im Pseudocode
aufgeführt.
Im selben Zug wird noch geprüft, ob Wörter, die mit „ss“ geschrieben sind auch mit „ß“ im
Wörterbuch stehen und ob Wörter mit jeweils „ae oe ue Ae Oe Ue“ auch mit je „ä ö ü Ä Ö
Ü“ im Wörterbuch stehen. Der Grund für die Korrektur von „ss“ ist die Vermischung von
alter und neuer Rechtschreibung. Das verwendete Lexikon beinhaltet nur alte
Rechtschreibung, daher werden alle Wörter auf diese gemappt.
3.3.1 Pseudocode
Algorithm 3
Function: correctMultiLetters(tokens)
Input: Token-Array tokens
Output: modified Tokens
for each Token t of tokens
alternativeTokenList ← rekursiveSearch(String(t), 0, 1, 0)
if size(alternativeTokenList) == 1
then replace String of t with Element of alternativeTokenList
end if
end for
Algorithm 4
Function: rekursiveSearch(s, pos, last, count)
Input: String s, actuall position pos, character last, integer count
Output: Modified tokens saved in alternativeTokenList
if last == 0
then return //cancel recursive run
end if
S. 15
if pos >= length(s) //String ends
then actchar = 0
else actchar = charAt(s, pos)
end if
if actchar == last //If same letter: increase count
then rekursiveSearch(s, ++pos, actchar, ++count)
else if count == 0
then rekursiveSearch(s, ++pos, actchar, 0)
else
if count > 0 then
newString = s with only one letter of last
if Woerterbuch has newString
then add newString to alternativeTokenList
end if
rekursiveSearch(newString, pos+1-count, actchar, 0)
end if
if count >1 then
newString = s with two letters of last
if Woerterbuch has newString
then add newString to alternativeTokenList
end if
rekursiveSearch(newString, pos+2-count, actchar, 0)
end if
end if
if count >3 and size(alternativeTokenList) == 0 then //max. 3x same letter
newString = s with three letters of last
add newString to alternativeTokenList
end if
if count >0 and last == 's’ then
ssString = s with 'ß' instead of „ss“
if Woerterbuch has ssString
then add ssString to alternativeTokenList
end if
rekursiveSearch(ssString, pos+1-count, 'ß', 0)
end if
if count == 0 and (actchar == 'e' or actchar == 'E') then
chars = {'u', 'U', 'o', 'O', 'a', 'A'}
replacechars = {'ü', 'Ü', 'ö', 'Ö', 'ä', 'Ä'}
for each char c from chars
if last == c then
modString = s with replacechar[i] instead of char[i]
if Woerterbuch has modString then
add modString to alternativeTokenList
end if
rekursiveSearch(modString, pos, actchar, 0)
end if
end for
end if
S. 16
3.3.2 Beispiel
Das Wort „Baeummeee“ wird als Token eingelesen. Es werden im rekursiven Algorithmus
alle Permutationen von „ä statt ae“ „m statt mm“, „e statt eee“ und „ee statt eee“ auf einen
Eintrag im Lexikon geprüft.
Folgende Tabelle zeigt die Permutationen die durch die Rekursion durchlaufen werden:
ä statt ae
X
X
X
X
m statt mm
X
X
e statt eee
X
X
X
X
X
X
Permutation
Bäume
Bäumeee
Bäumme
Bäummeee
Baeume
Baeumeee
Baeumme
Baeummeee
Es wird also geprüft ob „Bäummeee“ , „Bäumeee“, Bäumme“, „Bäume“ , „Baeummeee“,
Baeumeee“, „Baeumme“ oder „Baeume“ im Lexikon steht. Wird nur ein Eintrag im Lexikon
gefunden kann das Token „Baeummeee“ zu „Bäume“ korrigiert werden.
S. 17
3.4 Groß-/Kleinschreib-Korrektur
Bei Webkommentaren wird oft die Groß- und Kleinschreibung vernachlässigt. Mit Hilfe des
Lexikons findet eine Groß-/Kleinschreib-Korrektur statt.
Zunächst gilt: Steht ein Wort nicht im Wörterbuch, wird eine Groß-/Kleinschreib-Korrektur
durchgeführt. Falls ein Wort genau einmal mit Abweichungen in der Groß-/Kleinschreibung
im Wörterbuch steht, wird das Wort mit dem aus dem Wörterbuch ersetzt. Steht ein Wort
mehr als einmal mit Abweichung der Groß-/Kleinschreibung im Wörterbuch, wird das Wort
so korrigiert, dass der erste Buchstabe groß und der Rest klein geschrieben wird. Steht ein
Wort nicht mit Abweichung der Groß-/Kleinschreibung im Wörterbuch, wird keine Korrektur
durchgeführt.
In der Umsetzung wird auf Hashmaps zurückgegriffen, um eine exakte Zuweisung eines
Strings in Kleinschreibung zum korrigierten String durchzuführen. Die Groß- und
Kleinschreibung des Input-Strings ist unbedeutend für die Zuweisung in der Hashmap. Sie ist
nur bedeutend für die Überprüfung, ob ein String schon im Wörterbuch steht (dann wäre
keine Korrektur notwendig).
3.4.1 Pseudocode
Algorithm 5
Function: createMapping(w)
Input: Wörterbuch w
Output: Map m
for each String s from Wörterbuch w
if Map m not contains key lowercase(s)
then put in m „lowercase(s) → s“
else
put in m „lowercase(s) → uppercase(beginning letter of s)
+lowercase(rest of s)“
end if
end for
S. 18
Algorithm 6
Function: correction(tokens)
Input: Tokens tokens
Output: no return value. Tokens get modified.
for each Token t in tokens
s = String(t)
if (Wörterbuch w has not s and Map m contains key lowercase(s))
then set String of t = get value of Map-key „lowercase(s)“
end if
end for
3.4.2 Beispiel
Im Wörterbuch steht „Essen“. Wenn „Essen“ klein geschrieben wird (also „essen“), wird das
Token zu „Essen“ korrigiert. Steht aber „Essen“ und „essen“ im Wörterbuch, tritt der Fall ein,
dass mehr als eine Korrektur gefunden wurde und der String auf die Schreibweise mit ersten
Buchstaben groß und den Rest klein gesetzt wird (also auf „Essen“).
Ein Beispiel mit dem Inputstring „ESSEN“
„Essen“ steht im Wörterbuch
Ja
Ja
Nein
Nein
S. 19
„essen“ steht im Wörterbuch
Ja
Nein
Ja
Nein
Output-String
Essen
Essen
essen
ESSEN
4 Benutzung des Tokenizers
Der Tokenizer wird mit dem Konsolenaufruf „java –jar Tokenizer.jar“ aufgerufen. Es werden
dann folgende Dinge durchgeführt:
1.
2.
3.
4.
5.
Whitespace-Tokenisieurng
Komplexer Algorithmus des Tokenizers (rekursiv)
Korrektur von Mehrfachbuchstaben/Umlauten/ss->ß
Korrektur von Groß- und Kleinschreibung
Übersetzung der Tags des Tokenizers in POS-Tagger-Tags / Generieren des Inputs für
POS-Tagger
Der Output dient als Input für den POS-Tagger und ist in UTF8 kodiert!
5 Fazit
Mit der Tokenisierung und den Korrekturen liegt eine gute Vorbereitung für ein POS-Tagging
vor. Der Tokenizer arbeitet die Kriterien der Liste (2.3) ab und kann einfach erweitert
werden. Die Korrekturen funktionieren nur mit einem fehlerfreien Lexikon und sollen zu
einem besseren POS-Tagging führen.
S. 20
6 Literatur
[1] O. Owoputi, B. O’Connor, C. Dyer, K. Gimpel, and N. Schneider. Part-of-Speech Tagging
for Twitter: Word Clusters and Other Advances. Technical report, School of Computer
Science, Carnegie Mellon University, 2012.
[2] C. Potts. Sentiment Symposium Tutorial: Tokenizing. Stanford Linguistics, USA, 2011.
[3] H. Schmid. Improvements in Part-of-Speech Tagging With an Application to German. In
Proceedings of the ACL SIGDAT-Workshop, pages 47–50, 1995.
[4] K. Toutanova, D. Klein, C. D. Manning, and Y. Singer. Feature-rich Part-of-Speech Tagging
With a Cyclic Dependency Network. In Proceedings of Human Language Technology
Conference, pages 173–180, 2003.
[5] K. Toutanova and C. D. Manning. Enriching the Knowledge Sources Used in a Maximum
Entropy Part-of-Speech Tagger. In Proceedings of the Joint SIGDAT Conference on Empirical
Methods in Natural Language Processing and Very Large Corpora, pages 63–70, 2000.
[6] T. Brants. TnT – A Statistical Part-of-Speech Tagger. In Proceedings of the 6th Applied
Natural Language Processing Conference, pages 224–231, 2000.
[7] A. Ratnaparkhi. A Maximum Entropy Model for Part-Of-Speech Tagging. In Proceedings of
the Empirical Methods in Natural Language Processing, pages 133–142, 1996.
S. 21