-
Die
Erfindung betrifft ein Verfahren zur Worterkennung in Sequenzen
von N Zeichen, von denen ein oder mehrere Zeichen mehrdeutig sein
können.
-
Die
elektronische Erfassung von Texten und Sprache ist inzwischen Routine
geworden. Sie ist jedoch nicht fehlerfrei, dauert zu lange, erfordert
zu viel Speicher oder ist nicht flexibel genug in bezug auf die
verwendeten Geräte oder Sprachen.
-
Eingesetzt
wird die elektronische Erfassung von Texten und Sprache z. B. bei
der Texteingabe in Tastaturen. Am effizientesten und gebräuchlichsten
ist die normale Computertastatur, die für jeden einzugebenden Buchstaben
bzw. für jedes einzugebende Zeichen eine Taste bereitstellt
oder eine Tastenkombination definiert. Andere Tastaturen haben weniger
Tasten, etwa die Tastaturen von Mobiltelefonen für das
Versenden von SMS oder von PDAs für die Termineingabe,
Spezialtastaturen wie QWERTY-Tastaturen, Tastaturen für
Behinderte oder Tastaturen von Spezialgeräten. Bei der
Texteingabe in solche Tastaturen kommt es notwendigerweise zu Mehrfachbelegungen
der Tasten, so dass die Tasten meist mehrfach gedrückt
werden müssen, um den gewünschten Buchstaben zu
aktivieren (Mulitap-Methode). Im Falle eines herkömmlichen
Mobiltelefons z. B. gibt es eine ge meinsame Taste für A
B C Ä 2 und wenn etwa das Wort "baumhaus" eingegeben wird,
muss die Tastenfolge 222886442887777 (in Ziffern angegeben) gedrückt
werden, die dann aber ein eindeutiges Wort ergibt. Unter der Annahme
eines üblichen deutschen Ausgabealphabets ohne Groß-/Kleinschreibung
- O(2) = {a, ä, b, c}
- O(3) = {d, e, f}
- O(4) = {g, h, i}
- O(5) = {j, k, l}
- 0(6) = {m, n, o, ö}
- O(7) = {p, q, r, s, ß}
- O(8) = {t, u, ü, v}
- O(9) = {w, x, y, z}
ergeben sich für das
Wort "baumhaus" (Ziffernfolge 22864287) 4·4·4·4·3·4·4·5
= 61.440mögliche Buchstabenkombinationen, wenn für
jeden Buchstaben des eingegebenen Wortes jede Taste nur einmal gedrückt
wird. Diese Buchstabenkombinationen gehen von "aatmgatw" über
"baumhaus" bis "ccvöicvß". Unter diesen müssen
unmögliche Kombinationen wie "ääüöiäüq"
(ebenfalls Ziffernfolge 22864287) ausgeschlossen werden und eine
sinnvolle Liste von möglichen Wörtern (Hypothesen)
angeboten werden, z. B. für die Ziffernfolge 343 "die",
"ehe", "eid", wobei die erstgenannte Möglichkeit am häufigsten
vorkommt. Dies ist die Aufgabe von Worterkennungsverfahren.
-
Bei
der Spracheingabe gibt es ebenso Mehrdeutigkeiten, beispielsweise
bei schwierigen Lauten wie "s" und "f", deren Formantenfrequenzen
größtenteils außerhalb von 3,4 kHz (obere
Grenze der Telefonübertragungsfrequenz) liegen. Auch kann
es zu ein und demselben Phonem unterschiedliche Schreibweisen geben,
d. h. wenn geschrieben wird, wie gesprochen wird, fallen Zuordnungs-
und Auswahlentscheidungen an (/f/ → f, v, ph, /a/ → a,
aa, ah). Es sind bereits Phonem-Wörterbücher zum
Einsatz gekommen.
-
Auch
beispielsweise beim Lesen von elektronischen Textdateien, etwa wenn
diese eingegebenen Text oder Sprache enthalten oder es sich um digitale
Dokumente handelt, können sich praktisch vergleichbare
Probleme beim Erkennen dieser Dateien ergeben, bis die Wörter
aufgelöst sind.
-
Die
nachfolgende Darstellung des Standes der Technik und der Erfindung
bezieht sich schwerpunktsmäßig auf die Texterkennung
bei der Eingabe in Tastaturen, für die die Erfindung zunächst
vorgesehen war. Die Erfindung ist jedoch nicht auf diesen Anwendungsbereich
beschränkt, sondern auch auf die oben dargestellten und
andere Bereiche der Texterkennung und -analyse bzw. Spracherkennung
anwendbar.
-
Für
die Worterkennung sind zur Behebung der Mehrdeutigkeiten verschiedene
Zeichen-Disambiguierungsmethoden eingesetzt worden. Einige basieren
auf der Verwendung sogenannter n-Gramme, d. h. von zusammenhängenden
Zeichen-Sequenzen mit n Zeichen. n-Gramme sind bei der Analyse großer
Datenmengen auf bestimmte Kontexte (oder Wortgruppen) beispielsweise
durch den Geheimdienst zum Einsatz gekommen, so bei der Durchsuchung
von E-Mails auf ausgewählte Themengebiete etc.. Sie dienen
auch zur Satzerkennung aufgrund vorgegebener Wortfolgen, der n-Gramme
in diesem Kontext. Bei der Worterkennung mittels n-Grammen werden
Zeichensequenzen (auch: Strings) mit n-Grammen verglichen, die unterschiedliche
Längen haben können. Eine Kombination unterschiedlich
langer n-Gramme hat sich als nützlich erwiesen, wobei die
kürzeren n-Gramme Alternativprädiktionen liefern
und die längeren n-Gramme eine größere
Eindeutigkeit herbeiführen, aber einen hohen Speicherbedarf
haben, so dass n > 6
in der Praxis nicht vorkommt. Durch die unterschiedliche Länge
der n-Gramme werden die Häufigkeiten der einzelnen Buchstaben,
von Bigrammen, Trigrammen und auch kurzen Wörtern berücksichtigt.
Nachteilig erweist es sich bei der Anwendung der n-Gramm-Methode,
wenn die Dokumente nur sehr kurz sind. Große Beachtung
hat die bereits 1992 erschienene Veröffentlichung "Probalistic
Character Disambiguation for Reduced Keyboards Using Small Text
Samples" von J. L. Arnott und M. Y. Javed, AAC Augmentative and
Alternative Communication, Vol. 8, Seiten 215 bis 223 gefunden.
-
Zerlegt
man beispielsweise das Wort "baumhaus" in n-Gramme der Längen
2 bis 5, so ergeben sich folgende n-Gramme Vn(baumhaus):
| n =
2 | V2(baumhaus)
= {ba, au, um, mh, ha, au, us} |
| n =
3 | V3(baumhaus)
= {bau, aum, umh, mha, hau, aus} |
| n =
4 | V4(baumhaus)
= {baum, aumh, umha, mhau, haus} |
| n =
5 | V5(baumhaus)
= {baumh, aumha, umhau, mhaus} |
-
Ausgezählt
ergeben sich für einige ausgewählte n-Gramme folgende
Häufigkeiten:
W2(au) = 2
W3(aum) = 1
W4(baum)
= 1
W5(baumh) = 1
n-Gramme, die nicht beobachtet wurden,
haben selbstverständlich eine Häufigkeit von 0,
z. B. W3(lqü) = 0.
-
Alle
bekannten Wörter einer Sprache lassen sich nun aus n-Grammen
zusammensetzen. Insgesamt gibt es z. B. im Deutschen (ohne Berücksichtigung
von Groß-/Kleinschreibung) 30 Buchstaben, was die Maximalanzahl
möglicher n-Gramme begrenzt:
| n =
2 | 900 |
| n =
3 | 27.000 |
| n =
4 | 810.000 |
| n =
5 | 24.300.000 |
-
Bei
der Spezialanwendung Mobiltelefon der intelligenten Textsysteme,
ohne deren Einsatz die Texteingabe nach der Multitap-Methode erfolgt,
gibt es nur wenige auf dem Markt eingeführte Entwicklungen.
-
Sehr
verbreitet ist das T9-Verfahren der Firma Tegic Communications,
Inc. zur Disambiguierung eingegebener Zeichen-Sequenzen, das in
der
US 6 307 549 B1 beschrieben
ist. Eine eingebene Zeichen-Sequenz wird mit gespeicherten Vokabular-
bzw. Wortmodulen auf Entsprechung verglichen. Gibt es mehrere Alternativen,
werden diese in einer Auswahlliste präsentiert und eine
Alternative vom Benutzer ausgewählt. Für die Vokabular-
bzw. Wortmodule kann eine Baum-Datenstruktur vorgesehen sein. Jeder
Knoten dieser Struktur stellt eine bestimmte eingegebene Zeichen-Sequenz
dar, von der mehrere Alternativ-Sequenzen bzw. mögliche
ASCII-Zeichenfolgen abzweigen, die auf der Grundlage einer festen
Tastenbelegung definiert sind. Wo es keinen Pfad zwischen Knoten
gibt, gibt es keine gültige Zeichen-Sequenz. Für
die Erweiterung des Vokabulars ist ein Extra-Wörterbuch
vorgesehen. Das Disambiguierungsprinzip wird daher auch als Wörterbuch-basierte
Disambiguierung bezeichnet.
-
Die
US 2002/0183100 A1 beschreibt
ein Verfahren zur Buchstabenauswahl bei der Eingabe beispielsweise
von SMS-Nachrichten. Bei der Anzeige wird jeweils als Folgezeichen
abhängig von der vorhergehenden Eingabe, d. h. der bereits
eingegebenen Zeichen-Sequenz, ein Zeichen angezeigt, das statistisch
die höchste Wahrscheinlichkeit als Folgezeichen hat. Die
bereits eingegebene Zeichenfolge ist fest und wird nicht variiert. Das
Folgezeichen wird anhand einer statistischen Datenbank berechnet.
Für die Zeichenauswahl wird dabei auf Wörterbücher
zurückgegriffen, von denen eines Wortanfänge und
Wörter mit bis zu drei Zeichen, das andere Wörter
ab vier Zeichen beispielsweise enthält. Verfahren dieses
Typs werden als Präfix-basierte Disambiguierung bezeichnet.
-
Ebenfalls
einen statistischen Ansatz für den Folgebuchstaben nutzt
ein in der
EP 0 924
594 A2 beschriebenes Verfahren, bei dem auf eine zweidimensionale
Tabelle auf der Grundlage eines vorhergehenden Buchstabens sowie
auf eine dreidimensionale Trigramm-Tabelle auf der Grundlage von
zwei vorhergehenden Buchstaben zurückgegriffen wird.
-
Auch
bei dem Disambiguierungsverfahren gemäß
WO 2004/003953 A1 (eZiText-Verfahren
der Firma Zi Corporation of Canada, Inc.) werden die ersten beiden
Buchstaben eines Wortes eindeutig vom Benutzer eingeben und bestätigt.
Am Wortanfang werden die Häufigkeiten von Bi- und Trigrammen
genutzt. Für die Prädiktion dient ein Benutzerwörterbuch,
das bevorzugt ganze Wörter und deren Häufigkeit
enthält.
-
Aus
der
EP 1 710 668 A1 ist
ein Disambiguierungsverfahren bekannt, bei dem ein Speicher mit
Wörtern und ferner n-Gramm-Objekten sowie deren Häufigkeiten
verwendet wird. Die n-Gramm-Objekte können Wörter
oder Wortteile sein und umfassen Mono-, Bi- und Trigramme.
-
Der
Erfindung liegt die Aufgabe zugrunde, ein Verfahren zur Worterkennung
in Zeichen-Sequenzen zu schaffen, das sich für den Einsatz
bei Zeichenmehrdeutigkeiten eignet und bei dem die Worterkennung
rasch erfolgt.
-
Diese
Aufgabe ist erfindungsgemäß bei einem Verfahren
mit den Merkmalen des Anspruchs 1 gelöst. Vorteilhafte
Weiterbildungen des erfindungsgemäßen Verfahrens
sind Gegenstand der Unteransprüche.
-
Bei
dem erfindungsgemäßen Verfahren zur Worterkennung
in Sequenzen von N Zeichen, von denen ein oder mehrere Zeichen mehrdeutig
sein können, werden somit ein Speicher, eine Anzeige und
eine Prozessoreinrichtung verwendet. Der Speicher enthält
n-Gramme (Zeichenketten mit der Länge n) und den Zeichenketten
zugeordnete Häufigkeitswerte, wobei als Häufigkeitswert
eines n-Gramms die Gesamtzahl aller n-Gramme in ei ner für
die Worterkennung verwendeten Sprachstichprobe verwendet wird. Die
Anzeige zeigt ausgewählte n-Gramme und/oder erkannte Wörter
an, wobei die Prozessoreinrichtung mit dem Speicher und der Anzeige
verbunden ist. Aus einer betrachteten Zeichensequenz wird eine Liste
L von Wörtern mit N Zeichen erstellt, die aus der N-Zeichen-Sequenz
unter Berücksichtigung der Mehrdeutigkeiten der in dieser
enthaltenen einzelnen Zeichen gebildet werden können. Aus
der Liste L der möglichen Wörter werden alle Wörter entfernt,
deren Wort-Wahrscheinlichkeit Null ist, wobei die Wort-Wahrscheinlichkeit
p = Π pn aus den in der Zeichensequenz enthaltenen n-Grammen
mit n = 1 bis N – 1 bestimmt wird. Von der Anzeige werden
die verbliebenen Wörter der Liste L der möglichen
Wörter angezeigt.
-
Ein
wesentlicher Vorteil des erfindungsgemäßen Verfahrens
besteht darin, dass es unabhängig von der verwendeten Sprache
und Tastenbelegung Zuordnungsprobleme von Zeichenketten und -sequenzen
löst, wobei sich sinnvolle Worthypothesen ergeben. Dies
liegt daran, dass keine Wörter, sondern n-Gramme verwendet
werden, um die Worterkennung in Zeichenfolgen durchzuführen.
Die Liste wahrscheinlicher Worthypothesen wird nach jedem Tastendruck
bei der Eingabe eines Wortes neu erzeugt, so dass eine mit dem Tippen Schritt
haltende kontinuierliche Aktualisierung der Hypothesen erfolgt.
Aus dieser Liste, falls sie mehr als eine Worthypothese enthält,
kann der Benutzer sein korrektes Wort aussuchen, falls er das Wort
bereits komplett getippt hat. Die Art und Weise, wie die Auswahl
realisiert wird, ist beliebig. Ist das Wort noch nicht komplett getippt,
wird der Benutzer weiterhin neue Zeichen eingeben.
-
Das
erfindungsgemäße Erkennungsverfahren kann auf
beliebige Sprachen, juristische, technische Bereiche etc. angewendet
werden, indem der jeweilige Wortschatz in die Statistik integriert
wird. Auch die Zuordnung von Buchstaben oder anderen Zeichen zu
den Tasten, d. h. die Ausgabealphabete, bzw. Tastenbelegungen sind
frei wählbar, ohne dass irgendwelche Änderun gen
oder Anpassungen des Verfahrens notwendig werden. Bereits verwendete
Sprachstichproben können unverändert übernommen
werden, d. h. eine einmal erstellte Sprachstichprobe kann ohne Aufwand
auf Geräte mit anderen Tastenanordnungen bzw. -zuordnungen übertragen
werden. Die Anpassung an beliebige Sprachen mit ihren individuellen
Zeichen wie der Akzent im Französischen, hebräische,
kyrillische, griechische etc. Zeichen können einfach eingesetzt
werden. Die Auszählung einer kompletten Sprachstichprobe
dauert nur einige Minuten.
-
Das
Verfahren gemäß der Erfindung ist in der Lage,
unter konkurrierenden Zeichen (Buchstaben aufgrund Tastendruck oder
Phoneme aufgrund Spracheingabe oder digitalen Datensätzen)
und den sich ergebenden Mehrdeutigkeiten mögliche Wörter
zu isolieren, die ein gültiges bzw. sinnvolles Wort sein
können. Dabei werden bei jedem neuen getippten oder gesprochenen
Buchstaben die möglichen erkannten Einzelbuchstaben permutiert,
und bei jedem hinzugekommenen Buchstaben können sich dann
wieder andere Mehrdeutigkeiten ergeben, die aufgelöst werden.
-
Für
Wortketten ohne Zwischenräume kann es bei Anwendung des
erfindungsgemäßen Verfahrens auf die Wortketten
Mehrdeutigkeiten geben, wobei sich gültige Auflösungen
dann ergeben, wenn alle entstehenden Wörter entweder gültige
Ganzwörter sind oder gültige Wörter sind
und zugleich einen gültigen Wortanfang oder ein gültiges
Wortende besitzen. Dies soll das folgende Beispiel veranschaulichen,
bei dem folgende Bezeichnungen verwendet werden:
(G) gültiges
Ganzwort
(W) gültiger Wortanfang, gültiges
Wortende, gültige Wörter im Sinne von pA, pE,
pW (später erläutert)
(X) weder (G), noch
(W), d. h. ungültiges Wort
-
Beispiel:
daswetteristhervorragend Auflösungsversuche:
-
-
Bei
der Anwendung des erfindungsgemäßen Verfahrens
auf die Texteingabe wird üblicherweise eine Tastatur verwendet,
die Tasten umfasst, welchen mehreren Zeichen zugeordnet sind, und
die mit der Prozessoreinrichtung verbunden ist. Bei der Texteingabe
der N-Zeichen-Sequenzen wird dementsprechend ein Worterkennungsverfahren
angewendet, das nach der Erfindung arbeitet.
-
Wenn
das erfindungsgemäße Verfahren für die
Spracheingabe verwendet wird, wird eine Sprachaufnahmeinrichtung
verwendet und bei der Spracheingabe der Phoneme oder Phonem-Sequenzen
erfolgt eine Umwandlung in N-Zeichen-Sequenzen, insbesondere von
Textzeichen. Auf die N-Zeichen-Sequenzen wird ein Worterkennungsverfahren
angewendet, das nach der Erfindung arbeitet.
-
Das
erfindungsgemäße Verfahren lässt sich
auch vorteilhaft beim Lesen beispielsweise digital vorliegender
Textdokumente mit Zeichensequenzen anwenden. Hierzu wird eine Leseeinheit
für das Erfassen der N-Zeichen-Sequenzen benutzt und bei
dem Lesen der N-Zeichen-Sequenzen ein Worterkennungsverfahren angewendet.
Durch die Erfindung können Wörter in den gespeicherten
Zeichensequenzen sehr rasch und zuverlässig aufgefunden
und identifiziert werden.
-
Bei
einer vorteilhaften Variante des erfindungsgemäßen
Verfahrens werden als Ganzwort-n-Gramme die Wörter aus
der Sprachstichprobe bestimmt, deren Länge der n-Gramm-Länge
entspricht, und bei der Anzeige der verbliebenen Wörter
der Liste L werden zuerst alle Wörter sortiert nach der
Ganzwort-Wahrscheinlichkeit pG = GN/NG angezeigt, wobei GN die Ganzwort-n-Gramm-Häufigkeit
und NG die Gesamtzahl aller Ganzwort-n-Gramme der Sprachstichprobe
ist. Somit sind die Ganzwort-n-Gramme meist kurze Wörter,
die wie ein Lexikon für kurze Wörter unter Berücksichtigung
der Auftretenshäufigkeiten fungieren und eine sinnvolle
Sortierung von Worthypothesen für kurze Wörter
nach der Güte (wie "die", "ehe", "eid") unterstützen.
Im Falle einer Sprachstichprobe mit den Wörtern "baumhaus",
"hallo", "du", "der" ergeben sich das Bigram "du", Trigramm "der"
und das 5-Gramm "hallo" und als Ganzwort n-Gramme
G2(du) =
1, G3(der) = 1, G5(hallo) = 1
-
Nicht
beobachtete n-Gramme haben die Häufigkeit 0, z. B. G3(lqü)
= 0. In der Sprachstichprobe werden die Gesamtzahlen NG(n) aller
Ganzwort-n-Gramme berechnet. Diese ergeben sich aus der Summe aller Häufigkeiten
der Ganzwort-n-Gramme der jeweiligen Länge.
-
Bei
einer vorteilhaften Ausführung des erfindungsgemäßen
Verfahrens werden als Wortanfangs-n-Gramme die n-Gramme bestimmt,
die den Anfang eines Wortes bilden. Die Wortanfangs-Wahrscheinlichkeit
pA = Π An/NA wird bestimmt, wobei An die Wortanfangs-n-Gramm-Häufigkeit
und NA die Gesamtzahl aller Wortanfangs-n-Gramme der Sprachstichprobe
ist. Bei der Anzeige der verbliebenen möglichen Wörter werden
zuerst alle Wörter sortiert nach der Ganzwort-Wahrscheinlichkeit
pG = GN/NG angezeigt, wobei GN die Ganzwort-n-Gramm-Häufigkeit
und NG die Gesamtzahl aller Ganzwort-n-Gramme der Sprachstichprobe ist
und die Sortierung nach pA pW erfolgt.
-
Im
Falle der erwähnten Sprachstichprobe mit den Wörtern
"baumhaus", "hallo", "du", "der" ergeben sich die Bigramme "ba",
"ha", "du", de", die Trigramme "bau", "hal", "der", die 4-Gramme
"baum", "hall" und die 5-Gramme "baumh" sowie "hallo". Ausgezählt
ergeben sich die folgenden Häufigkeiten der Wort anfangs-n-Gramme:
| A2(ba)
= 1 | A2(ha)
= 1 | A2(du)
= 1 | A2(de)
= 1 |
| A3(bau)
= 1 | A3(hal)
= 1 | A3(der)
= 1 | |
| A4(baum)
= 1 | A4(hall)
= 1 | | |
| A5(baumh)
= 1 | A5(hallo)
= 1 | | |
-
Bevorzugt
werden auch Wortend-n-Gramme verwendet, wobei als Wortend-n-Gramme
die n-Gramme bestimmt werden, die das Ende eines Wortes bilden.
Die Wortend-Wahrscheinlichkeit pE = Π En/NE wird bestimmt,
wobei En die Wortend-n-Gramm-Häufigkeit und NE die Gesamtzahl
aller Wortend-n-Gramme der Sprachstichprobe ist. Bei der Anzeige
der verbleibenden möglichen Wörter werden zuerst
alle Wörter sortiert nach der Ganzwort-Wahrscheinlichkeit
pG = GN/NG und der Wortanfangs-n-Gramm-Wahrscheinlichkeit pA = Π An/NA
angezeigt, wobei GN die Ganzwort-n-Gramm-Häufigkeit, NG
die Gesamtzahl aller Ganzwort-n-Gramme der Sprachstichprobe ist,
An die Wortanfangs-n-Gramm-Häufigkeit und NA die Gesamtzahl aller
Wortanfangs-n-Gramme der Sprachstichprobe ist und die Sortierung
nach pA·pW·pE erfolgt.
-
Im
Falle der erwähnten Sprachstichprobe mit den Wörtern
haus", "hallo", "hallo", "du", "der" ergeben sich als Wortend-n-Gramme
die Bigramme "us", "lo", "du", "er", Trigramme "aus", "llo", "der",
4-Gramme "haus", "allo" und die 5-Gramme "mhaus", "hallo". Ausgezählt
ergeben sich damit folgende Häufigkeiten:
| E2(us)
= 1 | E2(lo)
= 1 | E2(du)
= 1 | E2(er)
= 1 |
| E3(aus)
= 1 | E3(llo)
= 1 | E3(der)
= 1 | |
| E4(haus)
= 1 | E4(allo)
= 1 | | |
| E5(mhaus)
= 1 | E5(hallo)
= 1 | | |
-
Vorteilhaft
wird bei dem erfindungsgemäßen Verfahren für
eine N-Zeichen-Sequenz mit jedem weiteren eingegebenen Zeichen die
Wörter-Liste L neu erstellt, d. h. es erfolgt eine kontinuierliche
Aktualisierung der Hypothesen. Aus der Liste L, falls sie mehr als
eine Worthypothese enthält, kann der Benutzer das korrekte Wort
aussuchen, falls er das Wort bereits komplett getippt hat. Wie die
Auswahl aus einem Vorschlagsangebot realisiert wird, ist beliebig.
-
In
den bisherigen Erläuterungen wurden für die n-Gramme
Werte von n = 2, n = 3, n = 4, n = 5 verwendet. Diese Werte sind
nicht starr festgelegt, sondern können nach den Gegebenheiten
angepasst werden. Vorzugsweise werden bei Anwendung des erfindungsgemäßen
Verfahrens für die n-Gramme Werte von n = 2, n = 3 verwendet,
für die der Speicherbedarf deutlich geringer als im Falle
längerer n-Gramme ist. Es können je nach Anwendungsfall
auch n-Gramme mit n = 1 (d. h. einzelne Buchstaben) eingesetzt werden.
-
Bevorzugt
werden für die n-Gramme auch Werte von n = 4 und/oder n
= 5 verwendet. Je länger die maximalen n-Gramme gewählt
werden (d. h. größere maximale Werte für
n), desto besser werden die vorgeschlagenen Worthypothesen. Es werden
aber auch umfangreichere Sprachstichproben nötig.
-
Im
Speicher kann eine Liste von Zeichen oder Zeichensequenzen und von
diesen zugeordneten Austauschzeichen, Austauschzeichensequenzen
oder Austausch-n-Grammen gespeichert sein. Auf diese Weise erfolgt
eine Anpassung an die Gewohnheiten eines Benutzers, bestimmte Zeichen
oder Wörter (z. B. "spatz" und nicht "rsätz"),
bestimmte Kurzformen (Englisch: "dont" → "don't", Französisch:
"cest" → "c'est"), Sonderzeichen (z. B. Smiley) zu verwenden,
an einen Spezialwortschatz etc.. Die Kurzformen müssen
dann aber auch in ihrer Kurzform in der Sprachstichprobe mit eingegeben
werden.
-
Auch
kann zweckmäßig vorgesehen werden, dass die n-Gramme
im Speicher ergänzt werden, um das Erkennen von neuen Wörtern
oder Spezialeingaben zu ermöglichen. Die Eingabe unbekannter
Wörter ist dabei nicht notwendig. Ausreichend ist die Aktualisierung
entsprechender n-Gramme (Wortanfangs-n-Gramme, Wort-n- Gramme, Wortend-n-Gramme,
Ganzwort-n-Gramme). Es ist nicht sinnvoll, alle möglichen
Häufigkeiten der n-Gramme An(∙), Wn(∙),
En(∙) und Gn(∙) zu speichern (z. B. gibt es für
n = 5 über 24 Millionen mögliche n-Gramme). Das
ist auch nicht nötig. Nur wenige dieser n-Gramme treten
in der Sprache auf, d. h. die Häufigkeit der meisten n-Gramme
ist 0. Auf deren Speicherung kann verzichtet werden.
-
Wortend-n-Gramme
bringen die Aussage mit sich, dass es sich um ein gültiges
komplettes Wort handelt, und andere Merkmale können im
Sinne der erfassten Sprachdaten ein Wort als solches erkennen. Um die
einzelnen Wörter zu isolieren, ist es insbesondere für
Anwendungen mit Lesen von Dateien auch nützlich, wenn Wortgrenzen,
insbesondere Wortenden, zusätzlich eingegeben werden, um
die Wortkette in einzelne jeweils komplette Wörter, z.
B. "baumhaus" auch in "baum haus", zu teilen.
-
Das
erfindungsgemäße Verfahren kann auch mit einer
Wortvorhersage ausgestattet werden. Diese kann so ablaufen, dass
anhand einer eingegebenen N-Zeichen-Sequenz eine Worterkennung für
eine Zeichen-Sequenz mit einer angenommenen Länge von N
+ (1 bis l) Zeichen durchgeführt wird, wobei l die Vorhersagelänge,
d. h. die Zahl der vorausgesagten Eingabeschritte ist. Nach Erstellung
der Liste L wird aus dieser eine weitere Liste L' erstellt, die
alle Wörter der Liste L enthält, wobei diese Wörter
um Zeichen oder Zeichen-Sequenzen mit der Länge 1 bis l
ergänzt sind. Aus der Liste L' werden alle Wörter
entfernt, deren Wort-Wahrscheinlichkeit Null ist, die in der Liste
L' verbliebenen Wörter werden sortiert werden und die Wörter der
Listen L und L' angezeigt. Auf diese Weise kann für ein
noch nicht vollständig eingegebenes Wort eine Vorhersage
getroffen werden daraufhin, welches Wort bzw. welche Wörter
der Benutzer bei der Eingabe im Sinn hat.
-
Zweckmäßig
bei dieser Wortvorhersage-Methode werden in der Liste L' zuerst
alle Wörter nach der Ganzwort-Wahrscheinlichkeit pG = GN/NG
sortiert, wobei GN die Ganzwort-n-Gramm-Häu figkeit und
NG die Gesamtzahl aller Ganzwort-n-Gramme der Sprachstichprobe ist.
Die Sortierung erfolgt dann nach der Anfangswort-n-Gramm- und der
Endwort-n-Gramm-Wahrscheinlichkeit nach pA·pW·pE.
-
Obenstehend
sind die Bestimmung der n-Gramme und deren Verwendung erläutert
worden. Es folgt nun eine Darstellung der Bestimmung der Wort-Wahrscheinlichkeiten.
-
Die
in den verschiedenen n-Gramm-Gruppen enthaltene Sprachstatistik
wird dazu eingesetzt, um einerseits Worthypothesen auszuschließen,
die mit größter Wahrscheinlichkeit kein Wort der
aktuellen Sprache sind, und um zum anderen die verbleibenden Hypothesen
in eine Reihenfolge entsprechend ihrer wahrscheinlichen Korrektheit
zu bringen. Dabei bezeichne im folgenden w = w1w2w3...wN ein Wort
w der Länge N, zusammengesetzt aus der Buchstabenfolge
w1w2w3...wN. Es werden folgende Auftrittswahrscheinlichkeiten bestimmt:
Für
ein Wort w berechnen sich die Wahrscheinlichkeiten, dass w ein gültiges
Wort im Sinne von n-Grammen der Länge n ist nach
-
Aus
diesen nach n-Gramm-Länge unterschiedenen Wort-Wahrscheinlichkeiten
kann eine gesamte Wortwahrscheinlichkeit des Wortes w für
die Gesamtheit aller trainierter n-Gramm-Längen berechnet
werden:
-
Sobald
auch nur eine einzige der Wort-n-Gramm-Häufigkeiten Wn(∙)
= 0 ist, ist auch die Wort-Wahrscheinlichkeit pW(w) = 0.
-
Am
Beispiel des Wortes "baumhaus" wird dies weiter erläutert.
-
Zur
Bestimmung von Bigrammen und unter der Annahme, dass es eine Gesamtzahl
NW(2) = 100 Bigramme gibt, ergibt sich: p2W(baumhaus)
= W2(ba)/NW(2)·W2(au)/NW(2)·W2(um)/NW(2)·W2(mh)/NW(2)·W2(ha)/NW(2)·W2(au)/NW(2)·W2(us)/NW(2)
=
1/100·2/100·1/100·1/100·2/100·2/100·1/100
-
Für
Trigramme ergibt sich entsprechend: p3W(baumhaus)
= W3(bau)/NW(3)·W3(aum)/NW(3)·W3(umh)/NW(3)·W3(mha)/NW(3)·W3(hau)/NW(3)·W3(aus)/NW(3)
-
Aus
diesen Ergebnissen resultiert letztendlich pW(baumhaus)
= ...·p2W(baumhaus)·p3W(baumhaus)·...
-
Eine
große Hilfe bei der Einschätzung, ob es ein Wort
w geben kann, sind die Wortanfangs-Wahrscheinlichkeiten. Denn gibt
es in der Sprachstichprobe keine Wörter mit den Wortanfangs-n-Grammen
des Wortes w, so wird dieses mit großer Wahrscheinlichkeit
kein gültiges Wort der Sprache sein. Dementsprechend berechnet
sich die Wahrscheinlichkeit dass ein Wort w im Sinne seines Wortanfangs
existiert aus
-
Sobald
auch nur eine einzige der Wortanfangs-n-Gramm-Häufigkeiten
An(∙) = 0 ist, ist auch die Wortanfangs-Wahrscheinlichkeit
pA(w) = 0.
-
Ein
Beispiel soll dies näher erläutern. Angenommen,
es soll die Wortanfangs-Wahrscheinlichkeit für n-Gramme
der Länge 2 bis 5 und das Wort w = baumhaus berechnet werden.
Es seien die Häufigkeiten aus der oben veranschaulichten
Auflistung von Wortanfangs-Bigrammen gegeben, die in diesem Beispiel
immer den Wert 1 haben. Einige beispielhafte Gesamtzahlen von Wortanfangs-n-Grammen
seien NA(2) = 12, NA(3) = 10, NA(4) = 13, NA(5) = 11. Damit ergibt
sich pA(baumhaus) = A2(ba)/NA(2)·A3(bau)/NA(3)·A4(baum)/NA(4)·A5(baumh)/NA(5)
= 1/12·1/10·1/13·1/11.
-
Eine
weitere große Hilfe bei der Einschätzung, ob es
ein Wort w geben kann, sind wie erwähnt die Wortend-Wahrscheinlichkeiten.
Gibt es in der Sprachstichprobe keine Wörter, die auf die
gleiche Buchstabenkette enden wie das Wort w, so ist dieses mit
großer Wahrscheinlichkeit kein Wort der Sprache. Berechnen
lassen sich die Wortend-Wahrscheinlichkeiten direkt aus den Wortend-n-Grammen:
-
Sobald
auch nur eine einzige der Wortend-n-Gramm-Häufigkeiten
En(∙) = 0 ist, ist auch die Wortend-Wahrscheinlichkeit
pE(w) = 0.
-
Ein
unbekanntes Wortende deutet nicht unbedingt auf eine unsinnige Worthypothese
hin, sondern kann genauso gut ein Indiz dafür sein, dass
ein Wort noch nicht komplett eingegeben ist.
-
Dies
erläutert das folgende Beispiel: Angenommen, es soll die
Wortend-Wahrscheinlichkeit für n-Gramme der Länge
2 bis 5 und das Wort w = baumhaus berechnet werden. Es seien die
Häufigkeiten aus der oben veranschaulichten Auflistung
von Wortend-Bigrammen gegeben, die in diesem Beispiel immer den Wert
1 haben, und einige beispielhafte Gesamtzahlen von Wortend-n-Grammen
seien NE(2) = 22, NE(3) = 20, NE(4) = 23, NE(5) = 21. Damit ergibt
sich pE(baumhaus) = E2(us)/NE(2)·E3(aus)/NE(3)·E4(haus)/NE(4)·E5(mhaus)/NE(5)
= 1/22·1/20·1/23·1/21
-
Für
die Ganzwort-Wahrscheinlichkeiten gilt folgendes: Ist das zu bewertende
Wort w so kurz, dass aus der Sprachstichprobe Ganzwort-n-Gramme
derselben Länge bestimmt wurden, so kann die Auftrittswahrscheinlichkeit
von w einfach angegeben werden als pG(w) = GN(w1...wN)/NG(N)
-
Ein
Beispiel soll dies näher erläutern. Angenommen,
es soll die Ganzwortwahrscheinlichkeit für die Wörter
w = der, w = du und w = lqü berechnet werden. Es seien
die Häufigkeiten aus der oben erwähnten Sprachstichprobe
(immer 1 oder 0) gegeben und einige beispielhafte Gesamtzahlen von
Ganzwort-n-Grammen seien NG(2) = 33, NG(3) = 30. Damit ergibt sich pG(der) = G3(der)/NG(3) = 1/30 pG(du)
= G2(der)/NG(2) = 1/33 pG(lqü) =
G3(der)/NG(3) = 0/30
-
Es
wird nun anhand des Beispiels "baumhaus" der konkrete Ablauf näher
beschrieben, um aus der Vielzahl der möglichen Zeichenkombinationen
für ein Wort (hier wie oben bereits angegeben: 61.440)
eine sinnvolle Liste von Wortalternativen zu erstellen.
-
Aus
der Liste L der möglichen Wörter werden alle Wörter
entfernt, deren Wahrscheinlichkeiten pW(w) = 0 oder pA(w) = 0 sind.
Diese Wörter stellen mit ziemlicher Sicherheit kein korrektes
Wort dar. Aus Performancegründen ist es sinnvoll, bereits
beim Aufbau der ersten Wortliste L dieses Kriterium anzuwenden und überhaupt
nur Wörter in die Liste aufzunehmen, für die pW(w) ≠ 0
und pA(w) ≠ 0 gilt.
-
Aus
den wenigen verbleibenden Worthypothesen wird eine sortierte Liste
erzeugt, wobei sich die Reihenfolge der einzelnen Wörter
aus folgenden drei Kriterien ergibt:
- (a) Zuerst
stehen alle Wörter mit pG(w) ≠ 0, absteigend sortiert
nach pG(w). Damit bekommen Wörter Priorität, für
die Ganzwort-n-Gramme vorhanden sind.
- (b) Danach kommen alle Wörter mit pE(w) ≠ 0,
absteigend sortiert nach pA(w)·pW(w)·pE(w). Damit
bekommen Wörter, die ein komplettes Wort repräsentieren,
Priorität vor solchen, die (bisher) nur teilweise eingegeben
sind.
- (c) Es folgen alle restlichen Wörter, absteigend sortiert
nach pA(w)·pW(w). In Vergleich zu der vorhergehenden Wortgruppe
aus (b) werden Wörter hinten angestellt, die erst teilweise
eingegeben sind. Sinnvoll wäre, dass die Eingabe von 2286428
als Hypothese zwar das Teil-Wort "baumhau" findet, aber eventuell
bessere Hypothesen bevorzugt, die nach (b) bereits ein gesamtes
Wort repräsentieren.
-
Die
Erfindung wird im folgenden anhand von Ausführungsbeispielen
und der Zeichnung weiter erläutert. In der Zeichnung zeigen:
-
1 eine
Prozessoreinrichtung zur Durchführung des erfindungsgemäßen
Verfahrens bei der Texteingabe in eine Tastatur,
-
2 eine
Prozessoreinrichtung zur Durchfürhung des erfindungsgemäßen
Verfahrens bei der Sprachaufnahme,
-
3 ein
Ablaufdiagramm des erfindungsgemäßen Verfahrens
zur Worterkennung,
-
4 ein
Ablaufdiagramm zur Ergänzung der n-Gramme im Speicher und
-
5 ein
Ablaufdiagramm zur Vorhersage von Wörtern bei bereits eingegebenen
Teilwörtern.
-
1 zeigt
eine Prozessoreinrichtung einschließlich Peripherie, mit
der das erfindungsgemäße Verfahren bei der Texteingabe
eingesetzt werden kann. Eine Tastatur 10 mit Tasten 11,
eine Anzeige 13 und ein Speicher 15 sind an eine
Prozessorein richtung 12 angeschlossen. Den Tasten 11 der
Tastatur 10 sind mehrere Zeichen zugeordnet, so dass bei
der Zeicheneingabe nicht sofort eindeutig identifizierbare Zeichenketten, Wörter
etc. entstehen. Der Speicher 15 enthält n-Gramme
und diesen n-Grammen zugeordnete Häufigkeitswerte, die
durch das Bezugszeichen 16 symbolisiert sind. Die Bildschirmanzeige 14 der
Anzeige 13 veranschaulicht die unter Benutzung der gespeicherten
n-Gramme und deren Häufigkeitswerten als mögliche
Wörter ermittelten verbliebenen Wörter, hier die
drei alternative Wörter "die", "ehe", "eid".
-
In 2 ist
eine Prozessoreinrichtung mit Peripherie für die Worterkennung
bei der Sprachaufnahme gezeigt. Eine Sprachaufnahmeeinrichtung wie
ein Mikrophon 20, eine Anzeige 13 und ein Speicher 15 sind
mit einer Prozessoreinrichtung 21 verbunden. Bei der Spracheingabe
entstehen nicht sofort eindeutig identifizierbare Phoneme bzw. hieraus
ableitbare Grapheme, N-Zeichen-Sequenzen von Strings bzw. Wörtern,
etc.. Grundsätzlich ist der Lösungsansatz analog
zu dem bei der Texteingabe. Der Speicher 15 enthält
n-Gramme und diesen n-Grammen zugeordnete Häufigkeitswerte,
die durch das Bezugszeichen 16 symbolisiert sind. Die Bildschirmanzeige 14 der
Anzeige 13 veranschaulicht die unter Benutzung der gespeicherten
n-Gramme und deren Häufigkeitswerten als mögliche
Wörter ermittelten verbliebenen Wörter, hier die
drei alternative Wörter "die", "ehe", "eid".
-
3 zeigt,
dass das Verfahren zur Worterkennung im Wesentlichen durch folgende
Verfahrensschritte gekennzeichnet ist. Im Schritt 101 steht
dem Verfahren der aktuelle Stand der Eingabe, z. B. eine Folge von N
Tastendrücken, zur Verfügung. Aus dieser Eingabe
wird im Schritt 102 die Liste L aller möglichen
Worthypothesen auf Grund der existierenden Eingabe-Mehrdeutigkeiten
durch Permutation aller Kombinationsmöglichkeiten generiert.
Im Verfahrensschritt 103 werden die Ganzwort-Wahrscheinlichkeiten
pG, die Wort-Wahrscheinlichkeiten pW, die Wortend-Wahrscheinlichkeiten
pE und die Wortanfangs-Wahrscheinlichkeiten pA für jede
Worthypothese der Liste L berech net. Basierend auf diesen Wahrscheinlichkeiten
werden im Verfahrensschritt 104 aus der Liste L alle Worthypothesen
entfernt, deren Wort-Wahrscheinlichkeiten pW oder Wortanfangs-Wahrscheinlichkeiten
pA Null ist und die damit mit großer Sicherheit kein gültiges
Wort repräsentieren. Falls eine Wortvorhersage durchgeführt
werden soll, zweigt die Abfrage 112 zur Erzeugung der in 5 dargestellten
und weiter unten näher erläuterten Erstellung
der Vorhersage-Liste L'. Falls in der Liste L gültige Ganzwörter
existieren, charakterisiert durch Hypothesen mit Ganzwort-Wahrscheinlichkeiten
ungleich Null, zweigt die Abfrage 105 in den Verfahrensschritt 106,
der alle gültigen Ganzwörter, absteigend sortiert
nach ihren Ganzwort-Wahrscheinlichkeiten, auf der Bildschirmanzeige 14 darstellt.
Verfahrensschritt 107 entfernt alle im Verfahrensschritt 106 angezeigten
Hypothesen aus der Liste L und vermeidet damit die mehrfache Ausgabe ein
und derselben Hypothese. Falls in der Liste L gültige komplette
Wörter existieren, charakterisiert durch Hypothesen mit
Wortend-Wahrscheinlichkeiten ungleich Null, zweigt die Abfrage 108 in
den Verfahrensschritt 109, der alle gültigen kompletten
Wörter, absteigend sortiert nach dem Produkt ihrer Wortend-Wahrscheinlichkeiten,
Wortanfangs-Wahrscheinlichkeiten und Wort-Wahrscheinlichkeiten,
an die bisherige Ausgabe auf der Bildschirmanzeige 14 anfügt.
Verfahrensschritt 110 entfernt alle im Verfahrensschritt 109 angezeigten
Hypothesen aus der Liste L und vermeidet damit die mehrfache Ausgabe
ein und derselben Hypothese. Alle verbleibenden Hypothesen der Liste
L werden im Verfahrensschritt 111, absteigend sortiert
nach dem Produkt ihrer Wortanfangs-Wahrscheinlichkeiten und Wort-Wahrscheinlichkeiten,
an die bisherige Ausgabe auf der Bildschirmanzeige 14 angefügt.
Falls eine Wortvorhersage durchgeführt werden soll, zweigt
die Abfrage 112 zur Ausgabe der Liste L', angefügt
an die bisherige Ausgabe auf der Bildschirmanzeige 14.
Akzeptiert der Benutzer eines der angezeigten Wörter, so
verzweigt die Abfrage 115 zu Verfahrensschritt 116,
der das gewählte Wort einer beliebigen Anwendung zur Verfügung
stellt und die aktuelle Zeichen- bzw. Eingabesequenz löscht, so
dass bei der nächsten Eingabe das Verfahren gemäß 3 im
Schritt 101 mit einer leeren Zeichensequenz, d. h. einem
neuen Wort, beginnt.
-
Die
zweckmäßige Ausgestaltung der Ergänzung
der im Speicher 15 vorgehaltenen n-Gramme durch neue Wörter
(unbekannte oder akzeptierte) ist durch die folgenden Verfahrensschritte,
dargestellt in 4, beschrieben. Im Verfahrensschritt 201 wird
als Grundlage der Ergänzung die Bestimmung aller n-Gramme
Vn(w) des in den Speicher 15 zu integrierenden Wortes w
durchgeführt. Hat das Wort w eine Länge, die durch
die Ganzwort-n-Gramme abgedeckt ist, zweigt die Abfrage 202 in
den Verfahrensschritt 203, der die Häufigkeit des
dem Wort w zugehörigen Ganzwort-n-Gramms aktualisiert.
Im Verfahrensschritt 204 wird das Wort w in die Datenbasis
der Wortanfangs-n-Gramme im Speicher 15 integriert, indem
die Häufigkeiten der Wortanfangs-n-Gramme aller n-Gramme
Vn(w) aktualisiert werden, die gültige Wortanfangs-n-Gramme
des Wortes w repräsentieren. Im Verfahrensschritt 205 wird
das Wort w in die Datenbasis der Wort-n-Gramme im Speicher 15 integriert,
indem die Häufigkeiten der Wort-n-Gramme aller n-Gramme
Vn(w) aktualisiert werden. Im Verfahrensschritt 206 wird
das Wort w in die Datenbasis der Wortend-n-Gramme im Speicher 15 integriert,
indem die Häufigkeiten der Wortend-n-Gramme aller n-Gramme
Vn(w) aktualisiert werden, die gültige Wortend-n-Gramme
des Wortes w repräsentieren.
-
5 beschreibt
die Verfahrensschritte zur Erzeugung einer Wortvorhersageliste L',
referenziert in 3, Verfahrensschritt 114.
Aus einer Liste L wird im Verfahrensschritt 301 eine neue
Liste L' erzeugt, die für jede Hypothese der Liste L alle
Konkatenation dieser Hypothese mit allen Permutationen des bekannten
Ausgabealphabets in den Längen von 1 bis l Zeichen enthält.
Aus der Liste L' werden im Verfahrensschritt 302 alle Hypothesen
entfernt, die entweder eine Wort-Wahrscheinlichkeit von Null oder
eine Wortanfangs-Wahrscheinlichkeit von Null oder eine Wortend-Wahrscheinlichkeit
von Null aufweisen. Die verbleibenden Hypothesen der Liste L' werden
im Verfah rensschritt 303 so sortiert, dass allen Hypothesen,
die ein gültiges Ganzwort repräsentieren und absteigend
nach der Ganzwort-Wahrscheinlichkeit pG sortiert sind, die weiteren
Hypothesen folgen und diese dabei absteigend nach dem Produkt ihrer
Wortend-Wahrscheinlichkeiten, Wortanfangs-Wahrscheinlichkeiten und
Wort-Wahrscheinlichkeiten sortiert sind. Die Ausgabe 304 des
Vorhersageverfahrens ist damit die sortierte Liste L'.
-
Im
folgenden wird das erfindungsgemäße Verfahren
anhand konkreter Ausführungsbeispiele in der deutschen
und lateinischen Sprache bei Benutzung einer Telefontastatur weiter
erläutert.
-
Für
erste Beispiel ist eine umfangreiche Sprachstichprobe mit 688.000
Wörtern benutzt worden, die viele zusammengesetzte Wörter
und auch Bücher aus der Trivialliteratur enthält.
Die n-Gramm-Belegung ist wie folgt: Tabelle 1
| Anzahl
der n-Grammen in der Sprachstichgrobe | n
= 2
max.
900 | n
= 3
max.
27.000 | n
= 4
max.
810.000 | n
= 5
max.
24.300.000 |
| Wort-n-Gramme | 779
(=
87%) | 9.253
(=
34%) | 47.853
(=
6%) | 121.139
(=
0.5%) |
| Wortanfangs-n-Gramme | 464
(=
52%) | 2.965
(=
11%) | 9.303
(=
1%) | 20.113
(=
0.1%) |
| Wortend-n-Gramme | 469
(=
52%) | 2.636
(=
10%) | 8.714
(=
1%) | 20.535
(=
0.1%) |
| Ganzwort-n-Gramme | 125
(=
14%) | 526
(=
2%) | 1.614
(=
0.2%) | 3.670
(=
0.01%) |
-
An
dieser Tabelle erkennt man gut, dass gerade durch die n-Gramme mit
n = 4 und n = 5 viel Wissen repräsentiert wird, da ein
Großteil (95%–99.99%) aller Vier- und Fünf-Buchstabenkombinationen
in der Sprachstichprobe nicht vorkommen.
-
Die
Worterkennungsprozedur wird nun für die Wörter
"Ist" "das" "Baumhaus" "schon" "fertig", "Abschlussball", "Bierkasten",
"Außenhandelsumsatz", "Fußballspiel" an Hand ihrer
Ziffernfolgen 478 327 22864287 72466 337844. 2272458772255, 2437527836,
287364263357867289, 387225577435 erkannt werden. Zum Vergleich sind
die Ergebnisse bei Verwendung der T9-Technologie der Firma Tegic
angegeben.
-
Die
Tabelle 2 stellt das Ergebnis dar, wobei das gesuchte bzw. eingetippte
Wort in Fettschrift dargestellt ist. Dahinter steht die jeweilige
Wort-Hypothesenliste. Tabelle 2
| Eingabe | Vorschläge
nach der Erfindung | Vorschläge
nach T9 |
| 478 | ist,
ißt, gst, gru, grt, grü | ist,
ißt, hsv |
| 327 | das,
daß, dar, faß, fas, eas, där, far, fär,
fäs | das,
daß, dar, faq, faß, dcs, fas, far, fäs,
fär, eas |
| 22864287 | baumhaus | (kein
Vorschlag, unbekanntes Wort) |
| 72466 | schon,
schön, schno, schmo, schmö, schnö | schon,
schön, schon, schmö |
| 337844 | fertig,
destig, festig, festhi | fertig,
festig |
| 2272458772255 | abschlussball,
abschlussbäll | abschlussackl |
| 2437527836 | bierlasten,
bierkarten, bierkasten, bierlastem, bierkartem, bierkastem, bierkästen,
bierlaßten, bierlaßtem, bierkästem | aidslarten
(korrektes Wort unbekannt!) |
| 287364263357867289 | außenhandelsumsatz,
außenhändelsumsatz, außenhanelsumsätz,
außenhändelsumsätz | (kein
Vorschlag, unbekanntes Wort) |
| 387225577435 | fußballspiel | fußballspiel |
-
Die
Unterschiede zwischen den beiden Worterkennungsverfahren liegen
im wesentlichen nicht bei der Bearbeitung der einfachen, gängigen
Wörter. Viele zusammengesetzte Wörter, die sich
bei Anwendung des erfindungsgemäßen Verfahrens
erschließen, können mit dem herkömmlichen
T9-Verfahren nicht gefunden werden. Dabei liegt die Rechenzeit zur
Erstellung der o. g. Worthypothesenliste im nichtmessbaren Bereich.
-
Das
folgende Beispiel bezieht sich auf Latein auf einer 6-er Tastatur
mit der folgenden Tastenbelegung:
-
Die
Buchstaben j, k, w, z kommen im Lateinischen nicht vor und entfallen
daher. Das Beispiel zeigt, wie leicht sich die Texteingabe sowohl
an neue Sprachen, als auch an andere Tastaturen anpassen lässt.
Daraus ergibt sich folgendes Ausgabealphabet:
- O(0) = {a,
b, c, d}
- O(1) = {e, f, g, h}
- O(2) = {i, l, m, n}
- O(3) = {o, p, q, r}
- O(4) = {s, t, u}
- O(5) = {v, x, y}
-
Die
Sprachstatistik wurde aus einer Sprachstichprobe bestimmt, die ausschließlich
eine Reihe von längeren lateinischen Originaltexten (z.
B. Caesar "Commentariorum Libri VII de Bello Gallico", "Commentariorum Libri
III de Bello Civili", "Libri Incertorum Auctorum") mit insgesamt
128.000 Wörtern bestand.
-
Nach
der Auszählung sind von den möglichen n-Grammen
folgende belegt: Tabelle 3
| Anzahl
der n-Gramme in der Sprachstichgrobe | n
= 2
max.
484 | n
= 3
max.
10.648 | n
= 4
max.
234.256 | n
= 5
max.
5.153.632 |
| Wort-n-Gramme | 356
(=
74%) | 2.696
(=
25%) | 10.130
(=
4%) | 19.274
(=
0.4%) |
| Wortan-fangs-n-Gramme | 205
(=
42%) | 1.177
(=
11%) | 3.049
(=
1%) | 5.117
(=
0.1%) |
| Wortend-n-Gramme | 152
(=
31%) | 931
(=
9%) | 3.160
(=
1%) | 6.465
(=
0.1%) |
| Ganzwort-n-Gramme | 54
(=
11%) | 163
(=
2%) | 540
(=
0.2%) | 1280
(=
0.02%) |
-
Aus
Tabelle 3 ist wiederum ersichtlich, dass gerade durch die n-Gramme
mit n = 4 und n = 5 viel Information geliefert wird, die die Sprachstichprobe
selbst nicht enthält.
-
Im
folgenden sollen
Multa legas facito, perlectis neglege multa.
Qualis
artifex pereo!
[Cato Maiar: "Sieh' zu, dass du viel liest,
und wenn du es gelesen hast, dann lasse vieles davon unberücksichtigt."
und "Welch großer Künstler scheidet mit mir dahin!"]
an
Hand ihrer Eingaben 24240 21104 100243, 313210424 2112111 24240.
340224 0342115 31313! erkannt werden. Es wird pro Wort jeweils die
gesamte sortierte Hypothesenliste angegeben, die korrekte Hypothese
in Fettdruck: Tabelle 4
| Eingabe | Vorschläge
nach der Erfindung |
| 24240 | multa |
| 21104 | legas,
legat, negat, nefas |
| 100243 | facito,
habito, gadito, gadisq |
| 313210424 | perlectis,
perlectit, perlectiu |
| 2112111 | neglege |
| 24240 | multa |
| 340224 | qualis,
qualit, publiu, rudimu |
| 0342115 | artifex |
| 31313 | pereo,
reper, peper, pereq, perfr, perfo, pergr |
-
ZITATE ENTHALTEN IN DER BESCHREIBUNG
-
Diese Liste
der vom Anmelder aufgeführten Dokumente wurde automatisiert
erzeugt und ist ausschließlich zur besseren Information
des Lesers aufgenommen. Die Liste ist nicht Bestandteil der deutschen
Patent- bzw. Gebrauchsmusteranmeldung. Das DPMA übernimmt
keinerlei Haftung für etwaige Fehler oder Auslassungen.
-
Zitierte Patentliteratur
-
- - US 6307549
B1 [0012]
- - US 2002/0183100 A1 [0013]
- - EP 0924594 A2 [0014]
- - WO 2004/003953 A1 [0015]
- - EP 1710668 A1 [0016]
-
Zitierte Nicht-Patentliteratur
-
- - "Probalistic
Character Disambiguation for Reduced Keyboards Using Small Text
Samples" von J. L. Arnott und M. Y. Javed, AAC Augmentative and
Alternative Communication, Vol. 8, Seiten 215 bis 223 [0007]