NSA im eigenen Auftrag

Ich habe eine neue Möglichkeit entdeckt, Notizen zu machen, nämlich indirekt durch jegliche Eingaben ins Handy. Ich ergoogle ja mein ganzes Leben. Deshalb will ich meine Eingaben protokollieren und zu meinem Pi senden. Sozusagen NSA in eigener Regie. Am Ende des Jahres eine Statistik ansehen können, was ich das Jahr lang im Herzen gehabt habe. Und mit solchen ganz nebenbei erstellten Notizen kann ich ja etwas anfangen, z.B. automatisiert Nachrichten oder Filme suchen. Unter Android kann man die Software-Tastatur selbst programmieren. Ich lade mir den Quellcode von Gingerbread-Keyboard herunter. Nachdem ich den nativen Teil mit dem Android NDK kompiliert habe, kann ich das Projekt mit Eclipse auf meinem Handy installieren und den Quellcode ändern. Ich finde verschiedene Methoden, um den Text zu unterschiedlichen Zeitpunkten aus dem Ziel-TextView zu lesen. Alle Methoden muten frickelig an. Es ist also eine interessante, aber weniger übliche Anwendung eines InputMethodService. Wenn sich das Tastaturfenster nach der Eingabe wieder schließt, wird der eingegebene Text verschlüsselt an meinen Raspberry Pi gesendet und in die Datenbank eingetragen. Ein Problem liegt darin, dass nicht alle Eingaben im Ziel-TextView landen. Bei Autocomplete-TextViews wird ein vervollständigtes Wort direkt ausgewählt statt erst im Zielfenster ankommen zu müssen. Allerdings kann man gerade in meinem wichtigsten Eingabefenster, der Adresseingabe des Chrome-Browsers den autovervollständigten Text zuerst ins Zielfenster schubsen um dann darauf aufbauend weitere Vervollständigungen der Suchphrase zu erhalten. Mit etwas Disziplin schneidet man dann doch den gesamten eingegebenen Text mit.

Sommer, Sonne, Englischtest

Die Schulferien beginnen, die Sonne strahlt und meine Kinder müssen was lernen, so in der ersten Tageshälfte. Jetzt, da ich meine fantastische Textanalysesoftware geschrieben habe, und meine Tochter dringend Nachhilfe in  Englisch braucht, probiere ich mal aus, ob ich die Software auch einfach mit den englischen linguistischen Modellen initialisieren kann, um Sätze zu zerlegen und POS-Tags, Lemmas und Nominalphrasen zu bestimmen, so dass ich dann auch englische Lückentexe erzeugen kann. Ja, es geht tatsächlich.

Originaltext:

The ball is on the floor. It is a red ball. It is a rubber ball. The baby looks at the ball. The cat looks at the ball. The cat is black. The cat walks over to the ball. The cat hits the ball with its paw. The ball rolls on the floor. The baby smiles.

Lückentext:

The ball ——— on the ———. It ——— a red ball. It ——— a rubber ball. The baby looks at the ———. The ——— looks at the ———. The cat is black. The ——— walks over to the ———. The cat ——— the ball with its paw. The ——— ——— on the ———. The baby smiles.

Ich habe meinen Generator angewiesen, jedes x-te Nomen und jedes y-te Verb auszulassen, wobei x und y Zufallszahlen sind. Die Betweenness Centrality kann bei solch kurzen Texten nicht berücksichtigt werden. In diesem Text hätte Ball als einziges Wort einen solchen Wert, alle anderen Wörter nicht. Es kann also nur ein einziges Wort unter Einbeziehung der Betweenness Centrality berücksichtigt werden.

mate-tools

Das nächste Vorstellungsgespräch findet wieder in Java statt. Meine Textanalyse war bisher Forschung. Ich habe Bibliotheken gesucht und Möglichkeiten gefunden, diese Java-Bibliotheken zu .NET-Assemblies zu kompilieren. Da ich ja mit IKVM so elegant zwischen den beiden Welten Java und .NET umschalten kann, kann ich ja jetzt mit Java weiter machen und den Code dann, wenn ich Lust habe, in C# umschreiben. Soll keiner denken, ich sei nur auf .NET fixiert und lasse Java links liegen. Wichtig ist ja auch, dass ich voran komme und ob mit C# oder Java ist erst einmal egal.

Das Letzte, was mir zu meiner Textanalyse noch fehlt, ist ein Lemmatisierer. Um einen Graphen aus Text-Knoten aufzubauen, möchte ich z.B. Haus, Häuser, Häusern auf das Lemma Haus abbilden. Das letzte Mal habe ich dafür den IMS Tree Tagger verwendet. Jetzt lese ich aber, dass dieser gar nicht kommerziell nutzbar ist. Da ich ja einen Kassenschlager entwickeln will, kommt er für mich nicht in Frage. Ich finde die mate-tools (Tools for Natural Language Analysis, Generation and Machine Learning). Sie sind so gut wie gar nicht dokumentiert, aber im Quellcode selbst finde ich dann doch ein Beispiel.

Insgesamt sind die linguistischen Tools gerade für die deutsche Sprache nicht perfekt. Jedes macht so seine Fehler. Da können die Modelle noch so gut antrainiert worden sein. Aber gerade bei der deutschen Grammatik, die so extrem viele Ausnahmen und Merkmale aufweist, kann von einer Verarbeitung durch den Computer keine Perfektion erwartet werden. Mit der Verarbeitung meines Beispieltextes in Worte, POS-Tags, Lemmas und Zugehörigkeiten zu Nominalphrasen, bin ich also so halbwegs zufrieden. Die Nominalphrasen werde ich aber mit einer zusätzlichen Logik noch bestimmter herausarbeiten.

Das Ergebnis der Analyse meines Beispieltextes kann ich für meine Tests benutzen, mittels derer ich nun die Berechnung der Betweenness Centrality der einzelnen Lemmas vorantreibe.

Dies ist der Beispieltext:

Die großen Häuser in reichen Gegenden stehen oft unter Beobachtung von Einbrecher. Ein größeres Haus in einer armen Gegend hingegen wird von Einbrechern meist ignoriert. Einbrecher Hugo hat einen großen Hund namens Bello. Hugo wohnt in der Gegend von Emden.

Ich schreibe mir das Erbebnis der linguistischen Verarbeitung als XML heraus, damit ich die vielen Dinge nicht händisch für meine Tests definieren muss:


<code><?xml version="1.0" encoding="UTF-8" standalone="no"?>
<Root>
  <Word>
    <Text>Die</Text>
    <POS>ART</POS>
    <Chunk>B-NP</Chunk>
    <Lemma>der</Lemma>
  </Word>
  <Word>
    <Text>großen</Text>
    <POS>ADJA</POS>
    <Chunk>I-NP</Chunk>
    <Lemma>groß</Lemma>
  </Word>
  <Word>
    <Text>Häuser</Text>
    <POS>NN</POS>
    <Chunk>I-NP</Chunk>
    <Lemma>haus</Lemma>
  </Word>
  <Word>
    <Text>in</Text>
    <POS>APPR</POS>
    <Chunk>O</Chunk>
    <Lemma>in</Lemma>
  </Word>
  <Word>
    <Text>reichen</Text>
    <POS>ADJA</POS>
    <Chunk>B-NP</Chunk>
    <Lemma>reich</Lemma>
  </Word>
  <Word>
    <Text>Gegenden</Text>
    <POS>NN</POS>
    <Chunk>I-NP</Chunk>
    <Lemma>gegend</Lemma>
  </Word>
  <Word>
    <Text>stehen</Text>
    <POS>VVFIN</POS>
    <Chunk>O</Chunk>
    <Lemma>stehen</Lemma>
  </Word>
  <Word>
    <Text>oft</Text>
    <POS>ADV</POS>
    <Chunk>O</Chunk>
    <Lemma>oft</Lemma>
  </Word>
  <Word>
    <Text>unter</Text>
    <POS>APPR</POS>
    <Chunk>O</Chunk>
    <Lemma>unter</Lemma>
  </Word>
  <Word>
    <Text>Beobachtung</Text>
    <POS>NN</POS>
    <Chunk>B-NP</Chunk>
    <Lemma>beobachtung</Lemma>
  </Word>
  <Word>
    <Text>von</Text>
    <POS>APPR</POS>
    <Chunk>O</Chunk>
    <Lemma>von</Lemma>
  </Word></code>

Mit diesen Daten kann ich jetzt meine Berechnung füttern und in Tests Erwartungen an diese stellen. Ich erwarte, dass Haus, groß und Einbrecher zentrale Begriffe und miteinander verbunden sind.

Aus JUNG mach .NUNG

Warum eigentlich immer der Performance wegen C++ mit herumschleppen? Wenn es nicht sein muss, erhöht es nur die Komplexität. Also erstmal die netzwerktechnischen Analysen in C# versuchen. Wenn die Geschwindigkeit nicht ausreicht, kann ich immer noch C++-Code hinzu addieren. Ich habe eine Java-API namens JUNG (Java Universal Network/Graph Framework) gefunden. Sie berechnet die Betweenness Centrality schon anhand des effizienteren Algorithmus von Brandes. Und auf Effizienz kommt es schließlich an, und nicht auf die Sprache. Wenn C++ schon nicht unbedingt sondern lediglich naturgemäß schneller ist als Java oder .NET-Sprachen, so ist es erst recht nicht schneller, wenn die Implementierung des Algorithmus nicht effizienter ist. Nachdem ich mir in der JUNG-Doku durchgelesen habe, welche Unterprojekte ich in Eclipse einbinden müsste, um die JUNG-API zu nutzen, kompiliere ich alle entsprechenden .jar-Dateien zu einer .NET-DLL:

C:\Users\bileser\Downloads\ikvmbin-7.2.4630.5\ikvm-7.2.4630.5\bin>ikvmc.exe -tar
get:library jung-api-2.0.1.jar jung-algorithms-2.0.1.jar colt-1.2.0.jar collect
ions-generic-4.01.jar jung-graph-impl-2.0.1.jar jung-io-2.0.1.jar jung-samples-2
.0.1.jar jung-visualization-2.0.1.jar concurrent-1.3.4.jar
IKVM.NET Compiler version 7.2.4630.5
Copyright (C) 2002-2012 Jeroen Frijters

http://www.ikvm.net/

note IKVMC0002: Output file is "jung-api-2.0.1.dll"

Welch schlanker Befehl! Ein Glück achtet IKVM nicht auf die Reihenfolge der voneinander abhängigen .jar-Archive bzw. erledigt das für mich. Als Resultat erhalte ich eine DLL namens jung-api-2.0.1.dll. Aus JUNG hätte ich hiermit NUNG (.NET Universal Network/Graph Framework) gemacht.

Den Code aus dem JUNG-Tutorial muss ich mir etwas in C# umschreiben:

// Graph<V, E> where V is the type of the vertices 
// and E is the type of the edges
Graph g = new SparseMultigraph();
// Add some vertices. From above we defined these to be type Integer.
g.addVertex(1);
g.addVertex(2);
g.addVertex(3); 
// Add some edges. From above we defined these to be of type String
// Note that the default is for undirected edges.
g.addEdge("Edge-A", 1, 2); // Note that Java 1.5 auto-boxes primitives
g.addEdge("Edge-B", 2, 3); 
// Let's see what we have. Note the nice output from the
// SparseMultigraph<V,E> toString() method

System.Console.Write("The graph g = " + g.ToString());


// Note that we can use the same nodes and edges in two different graphs.
Graph g2 = new SparseMultigraph();
g2.addVertex(1);
g2.addVertex(2);
g2.addVertex(3); 
g2.addEdge("Edge-A", 1,3);
g2.addEdge("Edge-B", 2,3, EdgeType.DIRECTED);
g2.addEdge("Edge-C", 3, 2, EdgeType.DIRECTED);
g2.addEdge("Edge-P", 2,3); // A parallel edge
System.Console.Write("The graph g2 = " + g2.ToString());

Funktioniert!

Stanford Parser unter .NET

Warum eigentlich .NET? Wie oft habe ich mich gefragt, in welche Richtung ich gehen will. Ich habe mich einmal mehr für .NET entschieden. Von meiner beruflichen Erfahrung her, habe ich die meiste Erfahrung im Desktop-, also im Windows-Bereich gesammelt. Nun will ich eine Textanalyse-Software entwickeln. Diese Software sehe ich auch eher im Desktopbereich. Hier braucht man volle Rechenpower. Es geht um private Texte, die man vielleicht nicht einem fremden Server anvertrauen möchte. Oder man möchte sein eigenes Blog analysieren und will der Cloud keine Zugangsdaten anvertrauen. Im Desktopbereich ist Microsoft bisher bei weitem immer noch unschlagbar. Doch unter .NET bin ich dank Mono gar nicht von Microsoft abhängig. C# ist eine standardisierte Sprache, genauso wie die Common Language Runtime (CLR) ECMA-Standard ist. Gut, mit Mono habe ich nicht den allerneuesten heißesten Scheiß, aber allemal eine stabile, plattformunabhängige Laufzeitumgebung. Mono bietet z.B. kein WPF oder WCF, weil dies keine offenen Standards sind. Will man aber eine Oberfläche entwickeln, macht man das sowieso am besten nativ. Meine Textanalyse wird also plattformunabhängig laufen und ob ich jetzt die darauf laufende Oberfläche nativ in WPF entwickele oder direkt plattformunabhängig in Gtk# oder Winforms, kann ich mir immer noch überlegen. Wahrscheinlich WPF. Für mich ist nur wichtig, dass ich strategisch und langfristig plattformunabhängig sein kann.

Weitestgehend unterstützt Mono auch ASP.NET MVC, allerdings nur Version 2, da die Oberflächensprache Razor, welche HTML- und Javascript-Code sehr komfortabel anhand des Viewmodels erzeugen lässt und der Version 3 angehört, ebenfalls reine Microsoft-Technologie ist. Ich habe also auch hier die Möglichkeit meine Analysesoftware als Service plattformunabhängig ins Web zu bringen und entweder unter Windows oder Linux laufen zu lassen. Ich fühle mich mit der Entscheidung für .NET also in keiner Hinsicht eingeengt und habe viel mehr die Nähe zum Desktop als unter Java. Java Swing ist für den Desktop ja nicht sonderlich beliebt und bis heute fühlen sich Java-Anwendungen auf dem Desktop zäh an.

Bisher war für mich die Natural Language Processing-Ecke eine Java-Domäne gewesen. Viel Code ist in diesem Bereich in Java geschrieben worden, z.B. der Stanford Parser. Als ich nach dessen Portierung für .NET suchte, habe ich IKVM gefunden. Mit IKVM kann man ein Java-Archiv in eine .NET-Assembly verwandeln, die dann auf verschiedenen Betriebssystemen lauffähig ist.

Das geht sehr einfach:

ikvmc.exe stanford-parser.jar

Die resultierende DLL ist damit allerdings nur ungetypt. Unter C# muss man sich also mittels des Schlüsselwortes var bedienen, um Objekte von der DLL im Empfang zu nehmen.

Will man eine getypte DLL, muss man zusätzlich noch dieses ausführen:

ildasm.exe /all /out=stanford-parser.il stanford-parser.dll
ilasm.exe /dll /key=myKey.snk stanford-parser.il

Ein Beispielprogrämmchen in C# sieht so aus:


LexicalizedParser lp = LexicalizedParser.loadModel(@"C:\Users\bileser\Documents\Visual Studio 2010\Projects\ConsoleApplication1\ConsoleApplication1\germanFactored.ser.gz");
string[] sent = { "Das", "ist", "ein", "einfacher", "Satz", "." };
List rawWords = Sentence.toCoreLabelList(sent);
Tree parse = lp.apply(rawWords);
parse.pennPrint();

String sent2 = "Als ich das Progrämmchen schrieb und bei der nächsten Vorstellung präsentierte, habe ich auf saubere Objektorientierung geachtet, nämlich Codeabschnitte mit hoher Kohäsion zu einer Klasse zusammen zu fassen.";

TreebankLanguagePack tlp = new PennTreebankLanguagePack();

Tokenizer toke = tlp.getTokenizerFactory().getTokenizer(new StringReader(sent2));

List rawWords2 = toke.tokenize();
Tree parse2 = lp.apply(rawWords2);

parse2.pennPrint();

Eine Datenbankanwendung für Android

ASP.NET MVC – C++/CLI

Nachdem ich so eine tolle Möglichkeit gefunden habe, mit Boost in C++ so schön und schnell die Betweenness Centrality der Nomen eines Textes zu berechnen, könnte ich doch meine Studienbibel, die ich in ASP.NET MVC verfasst habe, mit dieser Möglichkeit erweitern. Bei meinem letzten Job hatte ich schon einmal die Verknüpfung von C# und C++ über C++/CLI gemeistert und ich will an diesen Erfolg anknüpfen. Auf meinem Rechner klappt das super. Ich erstelle eine gemischte managed/unmanaged DLL, welche über ein managed Interface für die C#-Assembly verfügt und darüber nativen Code ausführen kann. Aber als ich meine Anwendung auf den Server veröffentlichen will, wird beim Start der Ausführung aber eben jene gemischte DLL vermisst. Je mehr ich im Internet zu dem Problem recherchiere, desto mehr Lösungsmöglichkeiten eröffnen sich. Darunter finden sich doch recht viele Meinungen, wie höllisch kompliziert die Mischung C++ und c# mittels C++/CLI doch sei. Nachdem ich einen Sonntag geopfert habe und sich noch mehr Möglichkeiten und Unklarheiten auftun, halte ich inne. Das ist eben doch ein Nachteil an Microsoft. Wäre so ein Server frei, könnte ich ihn mir einfach herunterladen und in einer virtuellen Maschine laufen lassen und den ausgeführten Code auf dem Server per Debugger untersuchen. Die vielen einfachen Lösungsmöglichkeiten hatte ich natürlich ausprobiert, aber um hier weiter zu kommen, brauche ich mehr als spielerisches Interesse an technischen Herausforderungen. Ich bin eben doch kein Technokrat. Was will ich eigentlich? Muss ich unbedingt der Welt zeigen, dass ich ein C++/CLI-Spezialist sein könnte? Sinnlos! Ich will eine Studienbibel programmieren und cool wäre das doch eigentlich für Android! Dann wäre ich nicht vom Internet abhängig und könnte auch im Wald oder in sonstiger Natur die Bibel auf besondere und komfortable Weise lesen. Eben überall, wo ich gerade bin.

Android NDK

Ich probiere ein Hello-World-NDK-Beispiel unter Android aus. Um SQLite nativ zum Laufen zu bringen, muss ich die riesige SQLite C-Datei meinem Makefile hinzufügen und neu kompilieren. Dazu gibt es Beispiele und nach einigem Gefummel habe ich SQLite und die Boost/Graph-Bibliothek nativ unter Android am Laufen. Der Nachteil von nativen Programmen unter Android ist aber die Geschwindigkeit. Während es an meinem Desktop-Rechner eine halbe Sekunde dauert jedes Wort eines Bibelbuches inklusive seiner 10 Parameter aus der Datenbank einzulesen und aus den Worten der Nominalphrasen einen Graphen aufzubauen und die Betweenness-Centrality sowohl der Kanten als auch der Knoten des Graphes auszurechnen, sind es auf meinem schon betagten Nexus S ca. 30 Sekunden. Diese Geschwindigkeit ist nicht akzeptabel. Auch hier wieder: Was soll der Spieltrieb? Tatsächlich sagt auch die Android Developer-Doku, dass man schon einen triftigen Grund haben sollte, um nativ unter Android zu programmieren, da es mit Sicherheit die Komplexität der Entwicklung erhöht, nicht aber unbedingt die Geschwindigkeit der Ausführung. Muss es also unbedingt dynamisch sein? Es reicht doch, wenn ich vorher die Betweennes Centrality für Kanten und Knoten ausrechne und die Ergebnisse in der Datenbank festhalte. Bei der Bibel handelt es sich schließlich um statischen Inhalt und es ist nicht damit zu rechnen, dass noch mehr Inhalt hinzugefügt wird. Was seit tausenden von Jahren penibelst vor Veränderungen geschützt wurde, wird wahrscheinlich nicht plötzlich geändert werden. Wenn ich vorher die Zentralitäten ausrechne, kann ich dies sogar für die gesamte Bibel tun. Ich kann alle ca. 800.000 Worte der Bibel einlesen und einen Graphen über die gesamte Bibel aufbauen und errechne mir damit Worte, die bibelweit zentral sind. Wenn ich diese Zentralitäten für meine Studienbibel benutze, helfe ich dem Benutzer die Bibel im Überblick zu behalten.

Normalisiert vs. Unormalisiert

Soll ich nun meine Datenbank normalisieren oder unnormalisiert lassen. An jeder Informatik-Uni lernt man, dass man Daten in der Datenbank natürlich normalisieren sollte. Aber das gilt nur für Daten, die sich vermehren. Eine unnormalisierte Datenbank verschlingt zuviel Platz, da Einträge vielfach vorkommen können und die Datenbank schlecht gewartet werden kann. Andererseits spart man sich auch komplizierte Join-Anfragen. Wenn ich wirklich meine Datenbank normalisieren würde, würde ich aus der zentralen Tabelle 5 Tabellen machen und müsste damit über ein 5-fach verschlachteltes Join-Statement 5 Tabellen abfragen. Ich habe gehört, dass sich das nicht sonderlich positiv auf die Performance auswirkt. Allerdings werde ich das noch ausprobieren. Denn der Benutzer lädt sich auch nicht gerne 100 MB herunter. Allerdings muss ich meine SQLite-DB indexieren. Wenn ich einen Index über häufig gefragte Spalten erstelle, antwortet SQLite in akzeptabler Geschwindigkeit auf eine Abfrage. Andernfalls dauert es einige Sekunden, bei jeder Anfrage erneut 800.000 Datensätze durchsuchen zu müssen.

Centering Resonance Analysis

Während ich noch auf das Modell für den stanfordschen Dependenzparser warte, welcher mir ermöglichen soll, aus einem Satz möglichst genau und schnell Subjekt, Prädikat und Objekt herausfinden zu können, suche ich anderweiting schon einmal nach anderen Möglichkeiten, Text zu analysieren und zu visualisieren. Ich stoße auf die Bachelorarbeit von Julia Blumental, die sie dem Thema Netzwerk-Textanalyse widmete. Dort geht es hauptsächlich um die Centering Resonance Analyse. Im Rahmen dieser Analyse wird ein Text in eine Kette von Nominalphrasen zerlegt. Die Worte der Nominalphrasen werden mit einander verbunden. Zusätzlich wird das letzte Wort einer Nominalphrase mit dem ersten Wort der nächsten Nominalphrase verbunden. Auf diese Weise entsteht ein ungerichteter Multigraph. Damit nicht zu viele unwichtige Knoten entstehen, werden die Worte, die die Knoten des Graphen bilden, auf das Lemma oder die Grundform abgebildet. Auch das POS (Part of Speech)-Tag eines Wortes wird verwendet, um die Knotenmenge zu reduzieren, indem nur Nomen, Namen und Adjektive verwendet werden. Nun gibt es verschiedene Maße der Zentralität eines Knoten, darunter die sogenannte Betweenness Centrality, die als besonders wichtig erachtet wird. Bei Gelegenheit schaue ich auch nach, was das auf Deutsch bedeutet. Nach diesem Maß ist ein Knoten umso zentraler, je mehr kürzeste Wege von jedem anderen Knoten zu jedem anderen Knoten im Graphen verlaufen.
Ich finde sofort eine passende Boost-Implementierung des Algorithmus, nämlich in der Bibliothek graph. C++ könte hier Speicher- und Geschwindigkeitsvorteile bieten, besonders wenn massenweise Text analysiert und eine gute Übersicht darüber geboten werden soll.
Als ersten muss ich aber meinen Text mit dem Stanford Parser parsen und meine Bibelwörter in der Datenbank als zu einer Nominalphrase zugehörig kennzeichen. Der Stanford Parser beinhaltet eine Vielzahl von Parsern darunter zwei für die deutsche Sprache, nämlich den GermanPCFG.ser.gz und den GermanFactored.ser.gz. Der GermanFactored Parser soll genauer sein, nur braucht er zu viel Speicher und ist darüber hinaus zu langsam. Um meinem kleinen Progrämmchen, welches die Worte der Datenbank mit ihrer Zugehörigkeit zu einer Nominalphrase kennzeichnet, den nötigen Speicher zu gönnen, brauche ich leider ersteinmal einen 64 Bit breiten Datenbanktreiber. Microsoft stellt seinen JDBC Treiber nur als 32 Bit zur Verfügung, der nicht gut mit 64 Bit Java zusammenarbeitet, welches ich brauche, damit ich mehr als zwei GB Arbeitsspeicher adressiert bekomme. Von Microsoft sollte man ja wissen, dass Interoperabilität nur halbherzig geschieht, ein bisschen enttäuscht bin ich aber schon. Schließlich ist es immer eine große Fummelei, den Connectionstring aus einer bestimmten Sprache heraus zu einer bestimmten Datenbank herauszufinden und die Verbindung zu konfigurieren. Der freie JTDS Treiber zur Verbindung von Java mit MSSQL gibt dann aber die gewünschte 64-Bittigkeit und damit hat meine Anwendung genug Speicher. Jedenfalls bin ich nicht bereit, mehr als 4 GB Speicher zu investieren, ich bin Spartaner. Mit dem GermanFactored komme ich aber trotzdem nicht weiter. Irgendwann wird auch dem mit -mx2000m gestarteten Programm der Arbeitsspeicher knapp. Das Parsen von biblischen Sätzen des Paulus aus dem neuen Testament bringt ihn sehr in Verlegenheit und er brütet viele Minuten lang über einen Satz mit 80 Wörtern, bis Java sich schließlich meldet, es sei kein Speicher mehr verfügbar. Genauer wird das Ergebnis mit dem GermanFactored im Vergleich zum GermanPCFG auch nicht. Letzterer tut jedoch seinen Dienst und analysiert mir die Nominalphrasen von 10 Bibelbüchern in einer halben Stunde.
Mit dem Visualisierungsprogramm Gephi kann ich nun meinen Graphen ansehen, welchen mir Boost als .dot Datei schreiben kann. Die Zentralitäten, welche mir Gephi berechnet stimmen mit Boost überein, das ist beruhigend. Das Ergebnis freut mich, denn es bringt wirklich Übersicht in einen Text:

Subjekt, Prädikat, Objekt

Die Wortart (POS – Part of Speech), das Lemma und die Stammform eines Wortes in einem Satz zu kennen, schien mir computerlinguistisch noch nicht genug zu sein, um schöne und bedeutungsvolle Visualisierungen daraus zu generieren. Ich stelle mir vor, dass ich weiter komme, wenn ich Subjekt, Prädikat und Objekt eines Satzes maschinell bestimmen kann. Dann kann ich einen gerichteten Graphen aus den Sätzen eines Textes erstellen und Beziehungen zwischen Subjekten, Prädikaten und Objekten herstellen. Visuell gesehen könnte ein Knoten desto zentraler sein, je häufiger er im Text vorkommt. Die Stammform hilft mir dabei, gleichartige Kandidaten zu einem Knoten zusammen zu fassen. Aber erst einmal muss ich einen Parser finden, der es mir ermöglicht, diese drei wichtigsten grammatikalischen Ausdrücke zu ermitteln. Dazu brauche ich einen sogenannten Dependency Parser. Der Stanford Parser bietet mir dergleichen aber leider nur für Englisch und Chinesisch. Er kann mir einen deutschen Satz nur ein einen Baum von Phrasen verwandeln, darunter Nominalphrasen, welche Subjekte oder Objekte sind.

So ein Baum sieht etwa so aus:

Dependenzparser, die das Deutsche beherrschen sind aber der ParZu und der JWCDG. Der ParZu ist sehr schnell, aber auch sehr ungenau. Während er für manche Sätze zuverlässig Subjekte sogar in Relativsätzen und per und verknüpfte Subjekte, Verben und Objekte erkennt, versagt er bei anderen Sätzen auch völlig, z.B. hier:

Viel besser, aber auch viel langsamer schlägt sich der JWCDG. Er erkennt, dass sich das Genitiv des ersten Relativsatzes nicht auf das Subjekt oder das Objekt bezieht aber dass sich das Wort im Nominativ im zweiten Relativsatz auf das Subjekt des Satzes bezieht. Der Parser erkennt auch, dass das letzte und das eine Prädikat mit dem anderen verbindet. Daraus kann man folgern, dass sich die Prädikate das Subjekt teilen. Er erkennt nicht, dass sich es auf das Objekt Jerusalem bezieht. Nachfolgend kann man die Ausgabe lesen:

000 SYN: im( 0- 1) — PP–> kam_third_-(10-11)
002 SYN: dritten_sg_gen_dat_weak( 1- 2) –ATTR–> Jahre_sg( 2- 3)
004 SYN: Jahre_sg( 2- 3) — PN–> im( 0- 1)
006 SYN: der_ART_sg_dat( 3- 4) — DET–> Regierung( 4- 5)
008 SYN: Regierung( 4- 5) — APP–> Jahre_sg( 2- 3)
010 SYN: Jojakims,_FM( 5- 6) — APP–> Regierung( 4- 5)
012 SYN: des_ART_neut( 6- 7) — DET–> Königs_NE_sg_gen( 7- 8)
014 SYN: Königs_NE_sg_gen( 7- 8) –GMOD–> Jojakims,_FM( 5- 6)
016 SYN: von( 8- 9) — PP–> Königs_NE_sg_gen( 7- 8)
018 SYN: Juda,_FM( 9-10) — PN–> von( 8- 9)
020 SYN: kam_third_-(10-11) — S–> NIL
022 SYN: Nebukadnezar,_FM(11-12) –SUBJ–> kam_third_-(10-11)
024 SYN: der_ART_sg_nom(12-13) — DET–> König_NE(13-14)
026 SYN: König_NE(13-14) — APP–> Nebukadnezar,_FM(11-12)
028 SYN: von(14-15) — PP–> König_NE(13-14)
030 SYN: Babel,_NN(15-16) — PN–> von(14-15)
032 SYN: vor_APPR_acc(16-17) — PP–> kam_third_-(10-11)
034 SYN: Jerusalem_Nachname(17-18) — PN–> vor_APPR_acc(16-17)
036 SYN: und(18-19) — KON–> kam_third_-(10-11)
038 SYN: belagerte_VVFIN_third_past(19-20) — CJ–> und(18-19)
040 SYN: es._FM(20-21) –OBJA–> belagerte_VVFIN_third_past(19-20)

Parse ich also mit dem JWCDG die Bibel durch – mein Vorhaben – dauert das Jahre. Wie ich von einem Bekannten erfahren habe, der zur Zeit seine Masterarbeit auf dem Gebiet schreibt, kann kein Parser derzeit erkennen, worauf sich in einem Satz es oder ihr oder ihm, sehr häufige Worte, beziehen. Hier kann man schon sehen, dass mein Vorhaben delikat ist. Kein Parser ist ihm gewachsen und ich muss noch ein paar Jahre warten. Aber was soll der Perfektionismus. Dieser Bekannte möchte mir ein Modell für den Maltparser geben, der immerhin so genau wie der JWCDG aber wesentlich schneller sein soll. Und dann wird eben herausgelesen, was geht. Ein nettes Angebot, wie ich finde, und bis dahin habe ich ja noch andere Dinge zu tun.

Lückentext

XML vs. SQL

Mein Ziel ist es, einen Lückentext aus einem Text zu generieren. Zufällig sollen Worte aus dem Text herausgepickt werden. Ist das auserwählte Wort ein Nomen, soll eine Auswahl der im Text vorkommenden Nomen angeboten werden. Die für die Lücke angebotene Auswahl an Wörtern sollen die selbe Wortart wie das fehlende Wort haben. Welche Datengrundlage soll ich mir für mein Vorhaben zusammen zimmern? Mir fällt sofort XML ein. Allerdings denke ich sofort danach an Effizienz. Soll meine Lösung auch auf einem Smartphone laufen, muss meine interne Datenstruktur sofort aus den Daten aufgebaut worden sein. Beim Parsen von XML gibt es zwei Möglichkeiten, nämlich DOM oder SAX. Wenn ich XML als DOM einlese, werden die XML Daten vollständig in einer internen Objektstuktur abgebildet. Wenn ich aber meine 40 MB großes XML Datei dermassen vollständig einlese, dauert das mindestens ein paar Sekunden. Per SAX wird XML eingelesen, indem ich benachrichtigt werde, wenn der Parser ein neues Element erreicht hat und wenn das alte Element verlassen wird. Ich habe dann die Möglichkeit, mir meine Datenstruktur selbst aufzubauen. Die Datenstruktur kann dann genau passend erzeugt werden, während ich unter Verwendung von DOM noch einmal hingehen und mir meine benötigten Daten aus dem DOM holen muss. Aber auch hier muss ich Aufwand betreiben, um die vorhanden Daten in eine interne Struktur zu bringen. Richtig flexibel ist man aber mit einer Datenbank. Die Daten können in der Datenbank bleiben und ich kann bequem per SQL darauf zugreifen. Ich entscheide mich für SQLite. Meine Datenbank muss in Java erzeugt werden, da der Stanfort POS Tagger, welcher auch deutsche Texte beherrscht, nur für Java existiert. Ich importiere die Bibliothek SQLJet und es klappt wunderbar. Um die Geschwindigkeit des Datenzugriffs zu erhöhen, erzeuge ich mir einen Index über die am häufigsten nachgefragten Spalten in meiner Tabelle.

Suche nach dem Layout für Qt

Nun, da ich meine Datenbank erzeugt habe geht es wieder in C++ und Qt weiter. Qt bietet selbst eine Zugriffsmöglichkeit für SQLite. Alles läuft problemlos, bis ich meinen Lückentext dann auch auf der Oberfläche sehen will. Die Lücken will ich als QComboBox und den übrigen Text als QLabel Objekte darstellen. Qt bitete mir aber nur eine spärliche Auswahl an Layouts an, nämlich gerade einmal drei. Ich will die Sätze meines Lückentextes in einem QVBoxLayout und die Wörter der Sätze in einem QHBoxLayout unterbringen. Aber diese Layouts scheinen für meine Zwecke nicht gemacht worden zu sein. Mein Vorhaben sprengt die Möglichkeiten dieser Layouts, so dass ich ganz komische Effekte beim generieren meiner Lückentexte erlebe. Qt geht hin und berechnet für jedes Label allerhand und will das Zeug ja irgendwie in Boxen darstellen. Ich bin ratlos und schicke ein Gebet zum Himmel: Oh Gott, wie soll es weitergehen? Lasse mich nicht im Stich! Qt hat ein Interface QLayout vorgesehen, um selbst Layouts implementieren zu können. Doch es scheint mir zu aufwendig für meine einfache Anwendung. Ich entdecke das FlowLayout, ein von Qt als Beispiel gedachtes Layout, welches genau das tut, was ich brauche, nämlich einfach nur Controls hintereinander zu zeichnen. Warum muss man so etwas Einfaches selbst programmieren? In Qt scheint man einiges selbst machen zu müssen. Ich wollte eigentlich den Test so programmieren, dass ich beim Ende per Email benachrichtigt werde. Aber eine Email zu schreiben ist auch kein Einzeiler. Nun gebe ich wie vorher meine Sätze in ein QHBoxLayout, aber die einzelnen Wörter in das FlowLayout. Wenn ein neuer Lückentext erzeugt wird, muss ich zuerst die alten QWidgets aus dem obersten Layout löschen. Da in Qt jedes Widget seine beinhalteten Elemente selbst löscht, brauche in nur die erste Ebene meiner Widgets in dem obersten Layout zu löschen:

    QLayout* hLayout = clozeWidget->layout();

    // Delete all the existing buttons in the layout
    QLayoutItem *wItem = hLayout->takeAt(0);
    while (wItem != 0){
        delete wItem->widget();
        delete wItem;
        wItem = hLayout->takeAt(0);
    }

clozefoto

POS-Tags und Lemmatisierung

Richtig zufrieden bin ich mit dem Porter-Stemmer-Algorithmus nicht. Er erkennt den gemeinsamen Wortstamm sehr gut, aber so habe ich es mir nicht vorgestellt. Er macht aus z.B. Töchterchen, Tochter, Töchter den Stamm tocht, und aus Brüder, Bruder, brüderlich, brüderlicherseits den Stamm brud, aber aus sehen macht er seh und aus sahen und sah wird sah. Ich wünsche mir aber Worte, die ich auch im Wörterbuch nachschlage und wenn ich nach sah oder sahen suche, schaue ich unter sehen. Oder wenn ich nach sprechen oder gesprochen oder sprach suche, schaue ich unter sprechen. Diese Grundformen nennt man aber Lemma und es existieren Programme, nämlich Lemmatisierer, um Wörter auf ihre Grundform, ihre Wörterbuchform, zurück zu führen. Außerdem will ich es jetzt wirklich wissen und mich interessieren auch die POS (Part of Speech)-Tags eines Satzes. Diese Tags sagen mir, ob ein Wort ein Nomen, ein Name oder eines von 10 Arten von Verben oder ein bestimmtes Adjektiv oder Adverb ist. Jetzt, wo ich schon am Thema NLP (Natural Language Processing) bin, kann ich mir das Gebiet ja auch zu Nutze machen. Als POS-Tagger, die für deutsche Sätze funktionieren habe ich nur den Stanford POS-Tagger und den IMS Tree Tagger gefunden. Nur der IMS Tree Tagger vermag es aber, mir auch das Lemma eines Wortes zu geben.

Im nachfolgenden Codebeispiel, zerlegt mir der Stanford POS-Tagger einen Satz in Tokens gibt dann für jedes Token dessen POS-Tag aus. Die Quellcodebeispiele sind alle in Java, welches die vorherrschende Sprache im NLP zu sein scheint. Es muss wohl doch keine so langsamen Sprache sein. Allerdings erledigen alle Programme, die ich gefunden habe, die Arbeit statisch. Sie sind nicht in andere Software eingebunden, sondern ein Text wird durch NLP-Software rechenintensiv verarbeitet und mit dem Ausgabetext kann man dann machen, was man will.

import java.io.BufferedReader;
import java.io.ByteArrayInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

import edu.stanford.nlp.ling.Sentence;
import edu.stanford.nlp.ling.TaggedWord;
import edu.stanford.nlp.ling.HasWord;
import edu.stanford.nlp.tagger.maxent.MaxentTagger;

class TaggerDemo {

  public static void main(String[] args) throws Exception {

    MaxentTagger tagger = new MaxentTagger("models/german-hgc.tagger");
	String s = "Aber alle Griechen nahmen Sosthenes, den Synagogenvorsteher, mit sich und schlugen ihn vor dem Richterstuhl. Und Gallio kümmerte sich um keinen dieser (Vorgänge).";    
	InputStream is = new ByteArrayInputStream(s.getBytes());
	BufferedReader br = new BufferedReader(new InputStreamReader(is));
    
    List<List<HasWord>> sentences = tagger.tokenizeText(br);

    for (List<HasWord> sentence : sentences) {
      ArrayList<TaggedWord> tSentence = tagger.tagSentence(sentence);
      System.out.println(Sentence.listToString(tSentence, false));
    }
  }

}

Die Ausgabe:
Aber/KON alle/PIDAT Griechen/NN nahmen/VVFIN Sosthenes/NE ,/$, den/ART Synagogenvorsteher/NN ,/$, mit/APPR sich/PRF und/KON schlugen/VVFIN ihn/PPER vor/APPR dem/ART Richterstuhl/NN ./$.
Und/KON Gallio/NE kümmerte/VVFIN sich/PRF um/APPR keinen/PIAT dieser/PDAT -LRB-/TRUNC Vorgänge/NN -RRB-/TRUNC ./$.

Schade, dass es für den Stanford POS Tagger keinen Lemmatisierer gibt. Den Tokenizer, welcher mir Sätze in Tokens zerlegt kann ich aber gebrauchen. So etwas muss ich ja nicht selbst programmieren. Im nachfolgenden Codeschnipsel tut der IMS Tree Tagger seinen Dienst und gibt sowohl Lemmas als auch POS-Tags aus.

import static java.util.Arrays.asList;

import org.annolab.tt4j.TokenHandler;
import org.annolab.tt4j.TreeTaggerWrapper;

public class tt4j {
        public static void main(String[] args) throws Exception {
                // Point TT4J to the TreeTagger installation directory. The executable is expected
                // in the "bin" subdirectory - in this example at "/opt/treetagger/bin/tree-tagger"
                System.setProperty("treetagger.home", "/home/bileser/Downloads/IMSTreeTagger/tree-tagger-linux-3.2");
                TreeTaggerWrapper<String> tt = new TreeTaggerWrapper<String>();
                try {
                        tt.setModel("/home/bileser/Downloads/IMSTreeTagger/tree-tagger-linux-3.2/german.par:iso8859-1");
                        tt.setHandler(new TokenHandler<String>() {
                                public void token(String token, String pos, String lemma) {
                                        System.out.println(token + "\t" + pos + "\t" + lemma);
                                }
                        });
                        
                        
                        String[] list = new String[] {
                        		"Und",
                        		"Gott",
                        		"sah",
                        		",",
                        		"dass",
                        		"es",
                        		"gut",
                        		"war",
                        		"."
                        		
                        };
                        
                        tt.process(asList(list));
                }
                finally {
                        tt.destroy();
                }
        }
}

Die Ausgabe:
Und KON und
Gott NN Gott
sah VVFIN sehen
, $, ,
dass KOUS dass
es PPER es
gut ADJD gut
war VAFIN sein
. $. .

Durch POS-Tags und Lemmatisierung habe ich vor, Lückentexte zu generieren und rechnerisch die wichtigsten Sätze von Texten anhand der Häufigkeiten der Lemmas von Nomen, Verben und anderen Satzbestandteilen zu ermitteln. Zu den Themen automatische Generierung von Zusammenfassungen oder Fragen findet man im Netz allerhand Papers. So tief will ich denn in die Wissenschaft nicht eintauchen.