Dasher für Android implementieren

Moderne Smartphones sind heute mit hochauflösenden Sensorbildschirmen ausgerüstet, die geradezu danach verlangen, die Texteingabe via Finger durchzuführen. Dasher ist eine Android Applikation, welche diese neue Art der Interaktion unterstützt.

Die Entwicklung von Dasher erfolgte ursprünglich in der Inference-Gruppe von David MacKay an der Universität Cambridge [1]. Das Programm stellt ein Texteingabe-Interface zur Verfügung, das mit natürlichen, kontinuierlichen Zeigegesten geführt wird. Klassisch steuert man Dasher aber mit der PC-Maus: Das Schreiben fühlt sich an, als ob man einen (virtuellen) Wagen auf dem Bildschirm steuern würde. Der Benutzer "fährt" stets in die Richtung des Buchstabens, den er als nächsten seinem Text hinzufügen möchte (siehe Abbildung 1). Um das Schreiben zu vereinfachen und somit zu beschleunigen, benutzt Dasher ein prediktives Sprachmodell, das laufend den nächstfolgenden Buchstaben im gegebenen Text-Kontext vorschlägt.

Textvoraussage

Ward, Blackwell und MacKay [1] haben die arithmetischen Kodierungs- und statistischen Modellierungsmethoden, die ursprünglich zur Textkomprimierung entwickelt wurden, sehr elegant an die Berechnung der Wahrscheinlichkeit des nächsten im Text vorkommenden Buchstabens angepasst (siehe [3] für eine gute Einführung). Das hierfür benutzte Sprachmodell basiert auf dem Prediction Partial Matching (PPM) Algorithmus [4]. Dieser schlägt die nächsten Buchstaben anhand des vorangehenden Kontextes, d. h. der n vorherigen Buchstaben, vor. So steigt z. B. die Wahrscheinlichkeit, dass das nächste Zeichen entweder "b", "g", "p" oder "v" ist, wenn man auf Englisch "the pro" geschrieben hat. Die Voraussage der nachfolgenden Buchstaben ist damit von der jeweiligen Sprache und der Länge n des Kontexts abhängig. Der PPM-Algorithmus verwendet zur Berechnung aber nicht nur den Kontext der n letzten Buchstaben, sondern auch all die kürzeren Kontexte, d. h. auch diejenigen der Länge 0 bis (n-1) werden in die Kalkulation der Wahrscheinlichkeiten miteinbezogen. Die längeren Kontexte haben allerdings mehr Gewicht. Dasher ist ein adaptiver Prozess, der einerseits anhand eines typischen Textes in der gewünschten Sprache vortrainiert werden kann, der sich anderseits aber auch von Null dem Schreibstil des Endbenutzers anpasst. Empirische Studien haben gezeigt [5], dass im Fall der englischen Sprache die besten Resultate mit einem Kontext von 5 Buchstaben (PPM-5) erzielt werden.

Dasher und mobile Geräte

Das Originalprogramm ist in C++ geschrieben, später aber auf Java von Chris Smowton portiert [2]. Inzwischen ist es für PocketPC, Apple iOS/iPhone erhältlich und zurzeit steht auch eine Version für Android zur Verfügung [6].

Wir haben Dasher für Android von Grund auf neu programmiert, weil wir sowohl die Grenzen der Hardware ausloten als auch deren optimale Nutzung ohne Ballast von früheren Randbedingungen testen wollten. Unser besonderes Augenmerk galt dem Interface mit dem Benutzer: Wir nahmen an, dass dieser (wie heute üblich) nur mit den Fingerbewegungen direkt auf dem Bildschirm mit der Applikation interagieren möchte. Wie aus Abbildung 1 ersichtlich, haben wir keinen virtuellen Zeiger (wie in der Originalversion) programmiert. Stattdessen fährt in unserer Version der Finger des Benutzers in die gewünschte Richtung. Aus diesem Grund überwachen wir kontinuierlich die Fingerbewegungen auf dem Sensorbildschirm.

Ebenfalls neu ist die Vereinfachung des ursprünglichen PPM-Algorithmus [7]. Dessen Aufgabe ist es, eine sehr komplexe Baumstruktur (die das Sprachmodell abbildet) zu erstellen, und daraus die Buchstabenwahrscheinlichkeiten zu berechnen. Die Baumstruktur benötigt viel Speicherplatz und wird in der Dasher-Originalversion beim Start anhand einer Trainingsdatei stets neu erstellt.

Wir haben eine andere Strategie gewählt: Der User soll Dasher zuerst mit speziell dafür entwickelten Tools auf einem gewöhnlichen Desktop gründlich trainieren, bevor das daraus resultierende Sprachmodell in einer Datenbank (SQLite) gespeichert wird. Diese Datenbank wird in einer zweiten Phase auf Android heruntergeladen. Unser Dasher holt dann die Daten für die kontextabhängige Buchstabenvorhersage direkt aus dieser Datenbank. Diese Strategie hat den Vorteil, dass die Daten sehr schnell aus der SQLite Datenbank mit einfachen SQL-Anweisungen geholt werden können, anstatt speicherfressende Baumstrukturen zu durchsuchen. Zum Speichern der Daten benützen wir einfache Tabellen, welche sich sehr gut an die Struktur der SQLite-Datenbank angepasst anpassen lassen. Aus Platzgründen haben wir den suboptimalen, aber doch sehr effizienten PPM-4-Algorithmus (n=4) zum Erstellen des Sprachmodells gewählt.

In diesem Artikel werden wir die Wahl der Datenstruktur, des Algorithmus und des Datenbankmodells erklären, da alle drei eng miteinander verknüpft sind. Ferner werden wir die Datenstruktur, den Zugriff auf die Datenbank und die Berechnung der Wahrscheinlichkeit des nächsten Buchstabens erläutern. In einem nachfolgenden Artikel werden wir die eigentliche Android Implementation näher untersuchen; insbesondere werden wir die Programmierung der visuellen und taktilen Komponenten des Dasher auf Android unter die Lupe nehmen.

Architektur

Unsere Dasher Implementation besteht aus drei Schichten (Abbildung 2). Die erste Schicht (Android View Layer in Abbildung 2) fasst alle Android Elemente zusammen, die der Benutzer beim Interagieren mit der Applikation wahrnimmt. Es sind dies zum Beispiel: Die Detektion der Richtung und Geschwindigkeit der Fingerbewegungen; die Konstruktion der Kästchen, deren Fläche die Wahrscheinlichkeit des nächsten Buchstabens optisch wiedergibt und die Kontrolle des Sensors, der die horizontale bzw. vertikale Lage des Handys misst. Die zweite Schicht (Dasher Controller Layer in Abbildung 2) erweitert die Palette der Input-Methoden der Android-Plattform um eine Service-Komponente. So kann man durch langes Antippen eines Texteingabe-Fensters den Dasher als Eingabemethode auswählen, nachdem man diesen über die Funktion Setting eingeschaltet hat. Die letzte Schicht (Language Model Layer in Abbildung 2) implementiert das ganze Zusammenspiel zwischen dem PPM-Algorithmus und der Datenbank. Diese Schicht liefert schliesslich die berechneten, kontextabhängigen Wahrscheinlichkeiten, damit diese in der ersten Schicht graphisch dargestellt werden können.

Sprachmodell-Datenstruktur und SQLite Datenbankformat

In der Tabelle 1 sind die rohen Daten für einen fiktiven Trainingstext eingetragen, welche der PPM-4 Algorithmus liefert, um die Symbolvoraussagen zu berechnen. Diese Daten werden dann in der SQLite Datenbank des Androids gespeichert. Tabelle 1 enthält alle Sprachmodelle, welche eine Kontextlänge von 0 bis 4 Symbolen haben. In der Literatur spricht man von Modellen der Ordnung n (in unserem Fall 0 <= n <= 4). Die erste Spalte enthält die Kontexte nach Ordnungszahl sortiert. Die zweite gibt die totale Anzahl der jeweiligen Kontexte im Trainingstext an und die dritte, wie oft ein Symbol nach dem jeweiligen Kontext vorgekommen ist. Diese letzte Spalte bezeichnen wir mit [SH].

Wie PPM-4 die Tabelle mit Werten füllt, kann am Besten anhand eines kleinen Beispiels erklärt werden. Wir gehen vom einfachen Text ABCABDABE aus, der als Trainingstext gedacht ist. Der folgende Algorithmus beschreibt das Verfahren:

• Schritt 1: Eingabe: A;

Kontext " "(Ordnung 0) -> +=1 und [SH} -> A +=1

• Schritt 2: Eingabe: AB;

Kontext A (Ordnung 1) -> +=1 und [SH] -> B+=1
@LiKontext " " (Ordnung 0) -> +=1 und [SH] -> B +=1

• Schritt 3: Eingabe ABC:

Kontext AB (Ordnung 2) -> +=1 und [SH] -> C+=1
Kontext B (Ordnung 1) -> +=1 und [SH] -> C+=1
Kontext " " (Ordnung 0) -> +=1 und [SH] -> C +=1

• Schritt 4: Eingabe ABCA:

Kontext ABC (Ordnung 3) -> +=1 und [SH] -> A+=1
Kontext BC (Ordnung 2) -> +=1 und [SH] -> A+=1
Kontext C (Ordnung 1) -> +=1 und [SH] -> A+=1
Kontext " " (Ordnung 0) -> +=1 und [SH} -> A +=1

• Schritt 5: Eingabe ABCAB:

Kontext ABCA (Ordnung 4) -> +=1 und [SH] -> B+=1
Kontext BCA (Ordnung 3) -> +=1 und [SH] -> B+=1
Kontext CA (Ordnung 2) -> +=1 und [SH] -> B+=1
Kontext A (Ordnung 1) -> +=1 und [SH] -> B+=1
 Ohne update exclusion:         Kontext " " (Ordnung 0) -> +=1 und [SH} -> B +=1
 Mit update exclusion:          Kontext " " (Ordnung 0) -> +=0 und [SH} -> B +=0

Die weiteren Schritte sind analog und sind hier nicht mehr weitergeführt. Die Daten aus dieser Trainingsphase werden dann benutzt, um die wahrscheinlichsten Symbole vorzuschlagen. Die statistische Theorie dazu ist in [1] behandelt. Mit der PPM-4 Variante "update exclusion" wird die Anzahl des aufgetretenen Symbols nur im Modell der höchsten Ordnung erhöht. Somit erhalten Modelle höherer Ordnung automatisch mehr Gewicht gegenüber denen niedriger Ordnung. Da zum Beispiel der Buchstabe B im ABCABDABE immer auf A folgt, wird B nur für das erste AB sowohl im Modell von Ordnung 0 als auch von Ordnung 1 gezählt. Später wird die Anzahl von B nur für Ordnung 1 erhöht, da es immer als AB vorkommt. Des Weiteren gibt es noch ein Modell von Ordnung -1, das nötig ist, damit auch denjenigen Symbolen, die nie im Trainingstext vorgekommen sind, eine kleine Wahrscheinlichkeit zugewiesen werden kann.

Anhand der Tabellen werden dann die Wahrscheinlichkeiten für alle Ordnungen des jeweiligen Kontextes berechnet, die gewichtet, zusammen die Vorhersage für die einzelnen Symbole ergeben (siehe [1]). In unserer SQLite Implementation haben wir für jede Ordnung eine Tabelle realisiert.

SQLite Datenbankformat

Die Einschränkung auf Kontextlänge 4 und Kleinbuchstaben (was für die englische Sprache sinnvoll ist), hält den Speicherplatzbedarf der Datenbank noch in vernünftigen Rahmen, sodass diese leicht auf einem Handy Platz hat. Der Speicherplatz wird weiter vermindert, indem nur jene Symbolfolgen in der Tabelle gespeichert werden, die tatsächlich im Trainingstext vorgekommen sind. Dies stellt einen Kompromiss zwischen guter Vorhersage und effizientem Umgang mit der Datenbank dar.

Das Datenbankschema (siehe Listing 1) besteht aus drei Komponenten: Einem INTEGER PRIMARY KEY, der sowohl einen bestimmten Textkontext darstellt, als auch als Zeilenidentifikationsnummer dient; einer Zahl, welche die Häufigkeit des Textkontextes abbildet; und schliesslich aus einem BLOB (Binary Large Object). Sein Wert wird aus der Häufigkeit der einzelnen Symbole gebildet, die als 16-Bits aufeinander folgend in ein Byte Array verpackt werden.

CREATE TABLE <ModelName > (
ctxID INTEGER PRIMARY KEY,
ctxOccur INTEGER,
symOccur BLOB
;

Das Abspeichern der Daten für alle Symbole in einem BLOB benötigt zwar zusätzlich dessen Kodierung und Dekodierung, erhöht aber die Geschwindigkeit, mit der man auf die Information zugreifen kann. Ein ganz simples Beispiel wird nun zeigen, wie die Textinformation in die SQLite Tabellen eingefügt wird. Nehmen wir ein Alphabet an, das nur aus drei Symbolen [‚A‘, ‚B‘, ‚C‘] besteht.

• 1. Die Einzel-Sequenz ‚A‘ im untersuchten Text ist bisher 12-mal registriert worden, darauf folgte 4-mal ein ‚C‘ und 8-mal ein weiteres ‚A‘.
• 2. Die Sequenz ‚AA‘ ist bisher 8-mal registriert worden, darauf folgte 5-mal ein ‚A‘ und 3-mal ein ‚C‘.
• 3. Die Sequenz ‚AC‘ ist bisher 4-mal registriert worden, darauf folgte 3-mal ein ‚A‘, und 1-mal ein ‚B‘.

Die Tabellen (hier in einer einzelnen zusammengefasst) in der SQLite Datenbank sehen für dieses Beispiel, wie folgt aus (die Werte in den Spalten ctxID und symOccur sind der Einfachheit halber in hexadezimalem Format dargestellt); die Buchstaben ‚A‘, ‚B‘, ‚C‘ werden durch die Zahlen ‚1‘, ‚2‘, und ‚3‘ kodiert.

Die Konstruktion des INTEGER PRIMARY KEY

Der schnellste Zugriff auf einen Record in der Datenbank erfolgt über den INTEGER PRIMARY KEY. Deshalb kodieren wir statt VARCHAR oder BLOB die Symbolfolgen direkt als Primärschlüssel INTEGER (64 bit). Aus demselben Grund haben wir für unsere PPM-Implementation auf der Android-Plattform den PPM-4-Algorithmus ausgewählt, was die Kontext-Zeichenkette auf maximal vier Symbole beschränkt. Pro Symbol haben wir somit 16-Bit für dessen Kodierung zur Verfügung; dies limitiert die Alphabetgrösse auf den Wert von 65’535 (= Character.MAX_VALUE - 1), was sogar für die chinesische Sprache ausreichen sollte. Die 4 Symbole des Kontextes werden via byte shifting aneinandergehängt und ergeben so den Primärschlüssel, mit dem auf die einzelnen Datenbankeinträge zugegriffen wird (siehe Listing 2).

Ein Problem ist noch offen: Die Symbole sind zero based. Betrachten wir noch einmal das alte Beispiel mit dem Alphabet [‚A‘, ‚B‘, ‚C‘], um dies zu erklären: Die Indizes für diese Symbole sind 0, 1 und 2. Wir kodieren nun die Symbolfolge ‚ABC‘ mit dem beschriebenen Algorithmus. Wenn wir einfach die Indizes zur Kodierung der Symbole benutzen würden, würden wir den folgenden Primärschlüssel in Hexadezimal 0x 00 00 01 02 erhalten. Der Wert 0x00 an der ersten Stelle zeigt, dass die Symbolfolge nur 3 Zeichen lang ist und daher darf diese Stelle nicht überschrieben werden. Dieser Schlüssel ist allerdings identisch mit demjenigen, welchen wir auch für die Symbolfolge ‚AABC‘ oder ‚BC‘ erhalten würden. Dies würde zu zweideutigen Kodierungen führen, die man vermeiden muss. Deshalb wird der Index jedes Symbols um 1 erhöht, bevor dieser an den Schlüssel angefügt wird. So erhalten wir nun one based kodierte Symbole und können 0x00 als Platzhalter reservieren. Die Symbolfolge ‚ABC‘ wird somit also in den Primary Key 0x 00 01 02 03 umgewandelt. Die 0x00 ist dabei klar als Platzhalter zu verstehen. Zum Vergleich würde die Symbolfolge ‚AABC‘ zu 0x 01 01 02 03 und ‚BC‘ entsprechend zu 0x 00 00 02 03 als Primary Key führen. So sind die Primary Keys nicht nur eindeutig, sondern liefern auch die Symbolfolge auf einfache Weise zurück.

Diese Methode ermöglicht nicht nur eine einfache Kodierung und Dekodierung des Primärschlüssels eines gegebenen Kontextes, sondern erlaubt auch das Primary Key aller Kontexte niedrigerer Ordnung aus dem Primärschlüssel des Kontextes der höchsten Ordnung herzuleiten. Dadurch wird für jeden Eintrag in den Tabellen das Speichern des Primärschlüssels des nächst niedrigen Kontextes überflüssig (im Gegensatz zu [3]).

/* INTEGER PRIMARY KEY aus der Symbolfolge erstellen
 * (jedes Symbol ist durch einen 16 Bit Integer dargestellt)
 * Bedingung: - maximal 65535 Symbole erlaubt
 * - die Symbol-Array enthält nicht mehr als 4 Symbole
 */
int64 getKeyForSymbolString (int16[] symbols) {
  if (symbols.length == 0) {
  return 0;
  }
  int64 key = 0;
  for (int16 symbol in symbols) {
  // Symbol dem Key zufügen
  key << 16;
  key = key + (symbol + 1);
  }
  return key;
}

Kodierung der Symbolhäufigkeiten

Auf eine ähnliche Weise werden die Häufigkeiten aller Symbole zusammen in ein BLOB umgewandelt. Der SQLite BLOB-Typ wird benötigt, um ein langes Array von Bytes in eine einzelne Spalte der Datenbank zu speichern. Hierfür wandeln wir zuerst die einzelnen Integer-Werte in jeweils 4 Bytes um, die dann in der Bytes-Array aneinandergereiht werden und so den BLOB bilden (siehe Listing 3).

byte[] bytes = new byte[array.length * 4];
int index = 0;
for (int value : array) {
   bytes[index + 3] = (byte) value;
   bytes[index + 2] = (byte) (value >>> 8);
   bytes[index + 1] = (byte) (value >>> 16);
   bytes[index] = (byte) (value >>> 24);
   index += 4;
}

Zusammenfassung

Die Portierung von komplexen Algorithmen auf Smart Phones führt zwangsläufig zu kniffligen Problemen, da Speicher und Zugriffszeiten einige Grössenordnungen kleiner sind, als diejenigen eines Desktop. Am Beispiel eines Textvorhersage-Algorithmus haben wir gezeigt, wie man solche Probleme anpacken kann. Im nächsten Android User lesen Sie, wie sich die taktile GUI des Dasher auf Android effizient implementieren lässt.