DE69806780T2

DE69806780T2 - System zur unterdrückung der vieldeutigkeit in einer verringerten tastatur

Info

Publication number: DE69806780T2
Application number: DE69806780T
Authority: DE
Inventors: P Flinchem; L Grover; Cheryl Grunbock; T King; A Kushler
Original assignee: Tegic Communications Inc
Current assignee: Tegic Communications Inc
Priority date: 1997-09-25
Filing date: 1998-09-24
Publication date: 2003-03-13
Anticipated expiration: 2018-09-25
Also published as: JP2001517823A; CN1271433A; ES2182363T3; CN101149645A; CN100334530C; EP1018069B1; DE69806780D1; EP1018069A2; CN100594470C; BR9814032A; WO1999015952A2; AU9669098A; KR20010024309A; AU746674B2; DK1018069T3; CA2302595C; HK1032458A1; CA2302595A1; RU2214620C2; ATE221222T1

Description

Technisches Gebiet der Erfindung

Die Erfindung betrifft allgemein eingeschränkte Tastatursysteme, insbesondere eingeschränkte Tastatursysteme, die zur Klärung mehrdeutiger Tastaturanschläge die Begriffsklärung auf Wortebene verwenden.

Technischer Hintergrund der Erfindung

Tragbare Computer werden seit vielen Jahren kleiner und kleiner. Die wichtigste, die Größe begrenzende Komponente im Zusammenhang mit den Bemühungen, kleinere tragbare Computer herzustellen, ist die Tastatur. Wenn Tasten in der Standard-Schreibmaschinengröße verwendet werden, muß der tragbare Computer mindestens ebenso groß wie die Tastatur sein. Für tragbare Computer wurden bereits Miniatur-Tastaturen verwendet, aber die Tasten der Miniaturtastaturen erwiesen sich für eine leichte und schnelle Betätigung durch die Benutzer als zu klein.
Der Einbau einer Tastatur in voller Größe in einen tragbaren Computer schränkt den Gebrauch des tragbaren Computers als uneingeschränkt tragbares Gerät ein. Die meisten tragbaren Computer können nicht betrieben werden, ohne daß der Computer auf eine flache Arbeitsfläche gestellt wird, um dem Benutzer das Schreiben mit beiden Händen zu ermöglichen. Ein Benutzer kann einen tragbaren Computer nicht auf einfache Weise im Stehen oder während einer Bewegung benutzen. Bei der letzten Generation von kleinen tragbaren Computern, den sogenannten Personal-Digital-Systems (PDAs) haben Unternehmen versucht, dieses Problem durch Einbauen einer Handschrift-Erkennungssoftware in die PDAs zu lösen. Ein Benutzer kann unmittelbar Text durch Schreiben auf eine Sensoranzeige oder einen Sensorbildschirm eingeben. Dieser handgeschriebene Text wurde dann durch die Erkennungssoftware in digitale Daten umgewandelt.
Neben der Tatsache, daß das Drucken oder Schreiben mit einem Stift im allgemeinen langsamer als Tippen vor sich geht, ist die Genauigkeit und Geschwindigkeit der Handschrift-Erkennungssoftware bis heute alles andere als zufriedenstellend. Erschwerend kommt hinzu, daß die heutigen, in einer Hand haltbaren und eine Texteingabe erfordernden Computer-Geräte immer noch kleiner werden. Die kürzlich erzielten Fortschritte bei Funkrufgeräten mit Hin- und Rückkanal, bei zellulärem Telefon und bei anderen tragbaren Geräten führten zur Nachfrage nach kleinen und tragbaren Nachrichtensystemen mit Hin- und Rückkanal und insbesondere nach Systemen, die elektronische Post ("e-mail") sowohl senden als auch empfangen können.
Es ist daher von Vorteil, wenn eine Tastatur zur Eingabe von Text in einen Computer entwickelt wird, die sowohl klein als auch mit einer Hand bedienbar ist, während der Benutzer den Computer in der anderen Hand hält. Frühere Entwicklungsarbeiten haben eine Tastatur in Betracht gezogen, die eine beschränkte Zahl von Tasten aufweist. Wie von der Gestaltung des Tastenfelds eines Telefons mit Tonwahlverfahren nahegelegt, haben viele beschränkte Tastaturen ein Feld von 3 · 4 Tasten. Jede Taste in dem Tastenfeld umfaßt mehrere Buchstaben. Daher liegt eine Mehrdeutigkeit vor, wenn der Benutzer eine Tastenfolge eingibt, da jeder Tastenanschlag einen von mehreren Buchstaben bedeuten kann. Es wurden mehrere Ansätze vorgeschlagen, um die Mehrdeutigkeit der Tastenanschlagsfolgen aufzulösen.
Ein vorgeschlagener Ansatz zur eindeutigen Kennzeichnung der auf einer eingeschränkten Tastatur angegebenen Buchstaben, erfordert zur Kennzeichnung jedes Buchstabens zwei oder mehr Tastenanschläge des Benutzers. Die Tastenanschläge können entweder gleichzeitig (Eingabe von Akkorden = "chording") oder nacheinander (Mehrfach-Eingabe-Spezifikation) ausgeführt werden. Weder die Eingabe von Akkorden noch die Mehrfach-Eingabe- Spezifikation hat zu einer Tastatur geführt, die auf angemessene Weise einfach und effizient zu bedienen ist. Die Mehrfach-Eingabe-Spezifikation ist ineffizient und die Eingabe von Akkorden ist schwierig zu lernen und anzuwenden.
Weitere vorgeschlagene Ansätze, um die korrekte Buchstabenfolge zu bestimmen, die einer mehrdeutigen Tastenanschlagsfolge entspricht, sind in dem Artikel "Probabilistic Character Disambiguation for Reduced Keyboards Using Small Text Samples" zusammengefaßt, der von John L. Arnott und Muhammad Y. Javad in dem Journal of International Society for Augmentative and Alternative Communication veröffentlicht wurde (nachfolgend: "Arnott-Artikel"). Der Arnott- Artikel führt aus, daß die Mehrzahl von Ansätzen zur Begriffsklärung bekannte Statistiken von Buchstabenfolgen in der betreffenden Sprache verwendet, um die Buchstabenmehrdeutigkeit in einem gegebenen Kontext aufzulösen. Das bedeutet, daß vorhandene Begriffsklärungssysteme die mehrdeutigen Tastenanschlagsgruppen während der Eingabe durch den Benutzer analysieren, um die richtige Interpretation der Tastenanschläge zu bestimmen. Der Arnott- Artikel führt ferner aus, daß einige Begriffsklärungssysteme versucht haben, die Begriffsklärung auf Wortebene zum Dekodieren von Text von einer beschränkten Tastatur durchzuführen. Die Begriffsklärung auf Wortebene klärt die Bedeutung ganzer Worte, indem die Folge von empfangenen Tastenanschläge auf mögliche Übereinstimmung in einem Wörterbuch überprüft wird, nachdem ein eindeutiger das Wortende kennzeichnender Buchstabe empfangen wurde. Der Arnott-Artikel diskutiert zahlreiche Nachteile der Begriffsklärung auf Wortebene. Beispielsweise gelingt es der Begriffsklärung auf Wortebene häufig nicht, ein Wort korrekt zu dekodieren, da die Fähigkeiten beim Identifizieren unüblicher Wörter begrenzt sind und da diese im Wörterbuch enthaltene Wörter nicht dekodieren kann. Aufgrund der Einschränkungen beim Dekodieren führt das Dekodieren auf Wortebene nicht zu einem fehlerfreien Dekodieren eines von Einschränkungen freien englischen Textes mit einer Effizienz von einem Tastenanschlag pro Buchstabe. Der Arnott- Artikel konzentriert sich daher mehr auf die Begriffsklärung auf Buchstabenebene als auf die Begriffsklärung auf Wortebene und führt aus, daß die Begriffsklärung auf Buchstabenebene, die am vielversprechendste Technik für die Begriffsklärung zu sein scheint.
Ein weiterer vorgeschlagener Ansatz, der auf der Begriffsklärung auf Wortebene beruht, ist in dem Buch mit dem Titel "Principals of Computer Speech" von I. H. Witten, Akademie Press, 1982, (nachfolgend "Witten-Ansatz") beschrieben. Witten diskutiert ein System zum Reduzieren der Mehrdeutigkeit von Text, der über die Tastatur eines Telefons eingegeben worden ist. Witten stellt fest, daß für ungefähr 92% der Wörter in einem 2400 Worte umfassenden Wörterbuch keine Mehrdeutigkeit besteht, wenn die Tastenanschlagsfolgen mit dem Wörterbuch verglichen werden. Falls jedoch Mehrdeutigkeiten auftreten, dann müssen diese gemäß Witten interaktiv aufgelöst werden, indem das System die Mehrdeutigkeit dem Benutzer präsentiert und indem das System den Benutzer bittet, eine Auswahl zwischen der Anzahl von mehrdeutigen Einträgen zu treffen. Am Ende jedes Worts muß der Benutzer daher auf die Vorhersage des Systems antworten. Solch eine Antwort verringert die Effizienz des Systems und vergrößert die Zahl der zur Eingabe eines bestimmten Textsegments erforderlichen Tastenanschläge.
Die Begriffsklärung einer mehrdeutigen Tastenanschlagsfolge ist weiterhin ein anspruchsvolles Problem. Wie in der obigen Diskussion ausgeführt wurde, gelingt es nicht, mit zufriedenstellenden Lösungen, die die Zahl der für die Eingabe eines Textsegments erforderlichen Zahl von Tastenanschlägen minimieren, die notwendige Effizienz für einen akzeptablen Gebrauch einer eingeschränkten, Begriffe klärenden Tastatur in einen tragbaren Computer zu erzielen. Eine wesentliche Herausforderung, der jede Anwendung zur Begriffsklärung auf Wortebene gegenübersteht, ist, diese erfolgreich auf der Art von Hardware- Plattformen zu implementieren, auf der der Gebrauch die meisten Vorteile bietet. Wie oben erwähnt, sind solche Geräte Funkrufgeräte mit Hin- und Rückkanal, zelluläre Telefone und weitere in der Hand haltbare, drahtlose Kommunikationsgeräte. Diese Systeme werden aus einer Batterie gespeist und werden infolgedessen bei der Gestaltung der Hardware und bei der Verwendung der Resourcen möglichst einfach ausgelegt. Zur Ausführung auf solchen Systemen vorgesehene Anwendungen müssen daher die Beanspruchung der Prozessorbandbreite und die Anforderungen an den Speicher minimieren. Diese beiden Faktoren stehen im allgemeinen im Widerspruch zueinander. Da Begriffsklärungssysteme auf Wortebene eine große Wortdatenbank benötigen, um zu funktionieren, und da sie auf Tastenanschläge schnell reagieren müssen, um eine zufriedenstellende Benutzerschnittstelle zu bieten, würde es ein großer Vorteil sein, wenn die erforderliche Datenbank komprimiert werden könnte, ohne die zu deren Gebrauch erforderliche Rechenzeit zu beeinflussen.
Eine weitere Herausforderung, der jede Anwendung zur Begriffsklärung auf Wortebene gegenübersteht, ist, daß dem Benutzer über die eingegebenen Tastenanschläge eine ausreichende Rückmeldung gegeben werden muß. Bei einer gewöhnlichen Schreibmaschine oder Textverarbeitung stellt jeder Tastenanschlag einen bestimmten Buchstaben dar, der nach der Eingabe dem Benutzer angezeigt werden kann. Aber bei einer Begriffsklärung auf Wortebene ist dies oft nicht möglich, da jeder Tasteanschlag mehrere Buchstaben bedeuten kann und jede Folge von Tastenanschläge mit zahlreichen Wörtern oder Wortstämmen übereinstimmen kann. Dies ist insbesondere dann ein Problem, wenn der Benutzer einen Schreib- oder Tippfehler macht, da der Benutzer nur dann sicher ist, daß ein Fehler aufgetreten ist, wenn die vollständige Tastenfolge eingegeben wurde und das gewünschte Wort nicht erscheint. Frühere Systeme mit Begriffsklärung auf Wortebene liefern erst dann eine Rückmeldung, wenn eine Taste ausgewählt wird, die wie ein Leerzeichen vom System als Taste für das Wortende erkannt wird. Darüber hinaus sind vor kurzem erfolgte Veröffentlichungen von der Begriffsklärung auf Wortebene abgerückt und haben sich auf Begriffsklärungstechniken auf Buchstabenebene konzentriert. Es wäre daher wünschenswert, ein Begriffsklärungssystem zu entwickeln, das die Mehrdeutigkeit von eingegebenen Tastenanschlägen minimiert und das die Effizienz maximiert, mit der der Benutzer während der Eingabe von Text auftretende Mehrdeutigkeiten auflösen kann.

Zusammenfassung der Erfindung

Die vorliegende Erfindung stellt eine eingeschränkte Tastatur zur Verfügung, die zur Auflösung von Mehrdeutigkeiten bei Tastenanschlägen eine Begriffsklärung auf Wortebene verwendet. Eine Ausführungsform des Systems umfaßt eine Anzeigeneinheit, die berührungsempfindlich ist und bei der ein Kontakt mit der Oberfläche der Anzeigeeinheit ein mit dem Ort des Kontakts übereinstimmendes Eingabesignal für das System erzeugt. Bei einer abgewandelten Ausführungsform kann die Tastatur mit mechanischen Tasten in voller Größe hergestellt werden.
Bei einer bevorzugten Ausführungsform sind neun Symbol- und Buchstabentasten zusammen mit drei bis sechs zusätzlichen speziellen Funktionstasten in einem Feld mit 3 · 3 Elementen angeordnet. Eine Vielzahl von Buchstaben und Symbolen werden einigen der Tasten zugewiesen, so daß die Tastenanschläge dieser Tasten (nachfolgend "Datentasten") mehrdeutig sind. Ein Benutzer kann eine Folge von Tastenanschlägen eingeben, wobei jeder Tastenanschlag der Eingabe eines Buchstabens eines Worts entspricht. Da die einzelnen Tastenanschläge mehrdeutig sind, kann die Folge von Tastenanschlägen potentiell mit mehr als einem Wort mit derselben Zahl von Buchstaben übereinstimmen. Die Tastenanschlagsfolge wird von Wörterbuchmodulen verarbeitet, die die Folge mit entsprechenden gespeicherten Wörtern oder anderen Interpreationen zur Übereinstimmung bringen. Wörter oder Wortstämme, die mit der Tastenanschlagsfolge übereinstimmen werden dem Benutzer nach jedem empfangenen Tastenanschlag auf einer Auswahlliste präsentiert.
Bei einer speziellen Ausführungsform der Erfindung ist einer der Tasten eine Vielzahl von Satzzeichen zugeordnet. Bei einer bevorzugten Ausführungsform ist der Punkt".", der Bindestrich "-" und der Apostroph "'" einem der Tasten zugewiesen. Der Benutzer kann eines der Zeichen tippen, indem er die Taste an einer Stelle betätigt, an der das Satzzeichen gewünscht wird. Da eine Vielzahl von Satzzeichen der Taste zugewiesen ist, ist der Tastenanschlag mehrdeutig. Das System der vorliegenden Erfindung bestimmt aus den vorhergehenden und den nachfolgenden Tastenanschlägen, welches Satzzeichen beabsichtigt worden ist und erzeugt dieses automatisch. Die alternativen Interpretationen der Tastenanschlagfolge können dem Benutzer ebenfalls in der Auswahlliste zur Verfügung gestellt werden.
Gemäß einem weiteren Merkmal der Erfindung werden die Wortinterpretationen mit absteigender Gebrauchshäufigkeit dargestellt, wobei die häufigsten Wörter zuerst dargestellt werden. Die Elemente in der Auswahlliste werden durch einfaches oder mehrfaches Drücken der Auswahltaste (Select-Taste) ausgewählt. Tastenanschläge können durch Drücken der Rücktaste (Backspace-Taste) gelöscht werden.
Gemäß einem weiteren Merkmal der Erfindung drückt der Benutzer eine Auswahltaste, um eine eingegebene Tastenanschlagsfolge zu begrenzen. Nach dem Empfang der Auswahltaste wählt das Begriffsklärungssystem das am häufigsten verwendete Wort aus und fügt das Wort dem zu erzeugenden Satz hinzu. Die Auswahltaste wird zur Begrenzung einer eingegebenen Tastenanschlagsfolge verwendet. Eine separate explizite Leerzeichentaste wird zum Erzeugen eines Leerzeichens verwendet und dient ferner zum Begrenzen einer eingegebenen Tastenanschlagsfolge. Bei einer weiteren bevorzugten Ausführungsform ist die Auswahltaste mit einer zweiten Funktion insofern "überladen", als diese auch dazu dient, nach einem ausgewählten Wort ein Leerzeichen zu erzeugen; das bedeutet, daß das Begriffsklärungssystem für eingeschränkte Tastaturen automatisch die richtigen Leerzeichen zwischen Worten einfügt.
Gemäß einem weiteren Merkmal der Erfindung wird die Auswahltaste auch dazu verwendet, weniger häufige Worte aus der dem Benutzer präsentierten Auswahlliste auszuwählen. Wenn das dem Benutzer zuoberst in der Auswahlliste präsentierte Wort nicht das gewünschte Wort ist, drückt der Benutzer die Auswahltaste erneut, um von dem häufigsten Wort zu dem zweithäufigsten Wort vorzurücken, und drückt diese erneut, um zu dem dritthäufigsten Wort zu gelangen, und so weiter. Diese Ausführungsform des Begriffsklärungssystem für eine eingeschränkte Tastatur verfügt über keine spezielle "Ausführungs-" oder "Bestätigungs"-Taste, um auf einen Eintrag nach dessen Auswahl einzuwirken. Nachdem ein gewünschtes Wort vom Benutzer ausgewählt worden ist, wird es automatisch für die Ausgabe "akzeptiert" und wird beim Empfang des nächsten Symbols oder Zeichentastenanschlags dem aufzubauenden Satz hinzugefügt.
Gemäß einem weiteren Merkmal der Erfindung enthält die zum Klären der Tastenanschläge verwendete linguistische Datenbank Informationen, die es dem System erlauben, als erstes Objekt ein Wort- oder Wortstammobjekt zu präsentieren, das, obwohl es nicht das häufigste Wort ist, das dem der gegenwärtigen Tastenanschlagsfolge entsprechenden Knoten zugeordnet ist, den Stamm eines längeren Worts oder eine Vielzahl von Worte bildet, deren Gesamthäufigkeit größer ist als diejenige des dem gegenwärtigen Knoten zugeordneten häufigsten Worts. Dieses Merkmal der "Stammbevorzugung" ist insbesondere bei Systemen mit begrenzter Anzeigefläche nützlich, bei denen die Auswahlliste nicht aktuell am Bildschirm angezeigt werden kann und wo der Benutzer lediglich das am Einfügepunkt angezeigte Wort erkennen kann, das auch das erste Objekt auf der Auswahlliste ist. Das Ergebnis ist, dass sich das Objekt tendenziell weniger häufig von Tastenanschlag zu Tastenanschlag ändert, so daß eine weniger "sprunghafte" und infolgedessen weniger ablenkende und verwirrende Schnittstelle präsentiert wird.
Gemäß einem weiteren Merkmal der Erfindung werden mehrfache Interpretationen der Tastenanschlagsfolge dem Benutzer in der Auswahlliste zur Verfügung gestellt. Die Tastenanschlagsfolge wird als ein Wort oder mehrere Worte bildend interpretiert und diese entsprechenden Worte werden in der Auswahlliste angezeigt. Gleichzeitig kann die Tastenanschlagsfolge als eine Zahl interpretiert werden und diese Zahl wird ebenso als eine der Gegenstände der Auswahlliste angezeigt. Zusätzlich kann eine Tastenanschlagsfolge als ein mit einem eindeutigen Buchstabierverfahren eingegebenes Wort, als der Stamm eines unvollständigen Worts oder als Systembefehl interpretiert werden. Diese mehrfachen Interpretationen werden dem Benutzer zur gleichen Zeit nach dem Empfang jedes vom Benutzer eingegebenen Tastenanschlags präsentiert. Der Benutzer kann aus den verschiedenen Interpretationen durch wiederholtes Drücken der Auswahltaste oder durch unmittelbares Berühren der gewünschten Interpretation in der auf einem Sensorbildschirm präsentierten Auswahlliste auswählen.
Gemäß einem weiteren Merkmal der Erfindung werden Worte in einem Vokabularmodul mit Hilfe einer Baumstruktur gespeichert. Worte, die einer bestimmten Tastenanschlagsfolge entsprechen, werden konstruiert, indem eine Menge von Worten oder Wortstämmen verwendet wird, die der unmittelbar vorausgegangenen Tastenanschlagsfolge zugeordnet sind (d. h. der jeweiligen Tastenanschlagsfolge ohne den letzten Tastenanschlag). Indem Worte auf diese Weise konstruiert werden, reduziert sich der Speicherplatz des Vokabularmoduls, da Wortstämme nur einmal an der Spitze der Baumstruktur gespeichert werden und da sie allen aus diesen konstruierten Wörtern gemeinsam sind.
Die Baumstruktur verringert auch im großem Umfang die Verarbeitungsanforderungen, da kein Suchvorgang durchgeführt werden muß, um gespeicherte Objekte zu finden. Die in der Baumdatenstruktur gespeicherten Worte und Wortstämme können Häufigkeits- oder andere Ranginformationen enthalten, die angeben, welcher Eintrag dem Benutzer zuerst angezeigt werden soll, was die Rechenanforderung weiter reduziert. Darüber hinaus wird die Datenstruktur mit Hilfe eines speziellen Algorithmus modifiziert, der die für die Datenbank erforderliche Gesamtgröße weiter komprimiert, ohne eine zusätzliche Rechenlast zu erzeugen, wenn diese zum Abrufen der den Tastenanschlagsfolgen zugeordneten Objekte verwendet wird. Ein weiteres Merkmal der abgewandelten Baumstruktur ist das automatische Erstellen von allgemeinen Regeln, um Tastenanschlagsfolgen Objekten zuzuordnen. Mit solchen Regeln kann das Vokabularmodul mit großer Erfolgswahrscheinlichkeit Tastenanschlagsfolgen Wort- oder Wortstammobjekten zuordnen, die urspünglich bei dessen Aufbau nicht verwendet worden sind.
Die interne, logische Darstellung der Tasten bei der bevorzugten Ausführungsform muß nicht der physischen Anordnung der Beschriftungen auf den tatsächlichen Tasten entsprechen. In einer zur Darstellung eines französischen Vokabulars konstruierten Datenbank können drei zusätzliche Symbole ( ) auch mit der Taste ABC verknüpft sein, die dem Schriftzeichen ohne Akzent zugeordnet ist. Dies gestattet dem Benutzer, Worte aufzurufen und zu tippen, die spezielle Schriftzeichen mit Akzent enthalten, indem der Benutzer lediglich eine Taste pro Schriftzeichen betätigt, was durch Betätigen der logisch zugeordneten physischen Taste für das Schriftzeichen mit Akzent geschieht.
Der kombinierte Effekt der mehrfachen Zuweisung von Buchstaben zu Tasten, die Begrenzung von Worten mit Hilfe einer Auswahltaste, die Präsentation der am häufigsten auftretenden Worte oder Wortstämme als erste Worte in der Auswahlliste, das Einfügen von mehrfachen Interpretationen in die Auswahlliste, das automatische Hinzufügen eines ausgewählten Worts zu einem Satz mit Hilfe des ersten Tastenanschlags des folgenden Worts, das automatische Hinzufügen von Leerzeichen, die Fähigkeit eine große Datenbank zu komprimieren, ohne dafür einen wesentlich höheren Preis beim Rechenvorgang zu zahlen, die Fähigkeit, Worte mit Schriftzeichen zu erzeugen, die Akzente aufweisen, indem die dem Schriftzeichen ohne Akzent zugeordnete Taste betätigt wird, und die Fähigkeit, zwischen vielfachen, einer einzelnen Taste zugeordneten Satzzeichen auf der Grundlage des Kontextes des Tastenanschlags zu unterscheiden, hat ein überraschendes Ergebnis zur Folge: für viele Sprachen können über 99% der Worte, die in einem repräsentativen Korpus von Textmaterial vorkommen, in das System mit extrem hoher Effizienz eingetippt werden. Für ungefähr 95% dieser Worte ist die gleiche Zahl von Tastenanschlägen erforderlich, um ein Wort mit Hilfe der eingeschränkten Tastatur mit Begriffsklärungssystem einzugeben, wie für die Eingabe mit einer herkömmlichen Tastatur. Wenn die Worte Buchstaben mit Akzenten umfassen, kann die Eingabe häufig mit weniger Tastenanschlägen durchgeführt werden als mit einer herkömmlichen Tastatur. Wenn die Worte entsprechend ihrer Gebrauchshäufigkeit präsentiert werden, ist das gewünschte Wort meistens das erste präsentierte Wort und häufig das einzige präsentierte Wort. Der Benutzer kann dann mit der Eingabe des nächsten Wortes mit nicht mehreren als der üblichen Zahl von Tastenanschlägen fortfahren. Auf diese Weise kann eine Eingabe von Text mit hoher Geschwindigkeit mit Hilfe einer Tastatur durchgeführt werden, die eine kleine Zahl von Tasten in voller Größe aufweist.
Das hier beschriebene Begriffsklärungssystem für eingeschränkte Tastaturen verringert die Größe des Computers oder eines weiteren Geräts, das das System integriert. Die reduzierte Anzahl von Tasten gestattet ein Gerät zu konstruieren, das vom Benutzer in der einen Hand gehalten werden kann, während es mit der anderen Hand bedient wird. Besonders vorteilhaft ist das beschriebene System beim Gebrauch im Zusammenhang mit PDAs, Funkrufgeräten mit Hin- und Rückkanal oder anderen kleinen elektronischen Geräten, die von einer genauen Hochgeschwindigkeitstexteingabe profitieren. Das System komprimiert eine große Datenbank zur Begriffsklärung von Tastenanschlagsfolgen, ohne daß zusätzliche Rechenbandbreite beim Gebrauch der komprimierten Datenbank erforderlich ist. Das System ist sowohl effizient als auch einfach, wenn es in einem Gerät mit einem Sensorbildschirm oder einem Gerät mit einer begrenzen Zahl von mechanischen Tasten und mit einer möglicherweise begrenzten Anzeigefläche implementiert wird.

Kurze Figurenbeschreibung

Die oben genannten Merkmale und die zahlreiche Vorteile der Erfindung werden durch die nachfolgende detaillierte Beschreibung anhand der beigefügten Zeichnung noch verständlicher und deutlicher, wobei:
Fig. 1 eine schematische Darstellung einer bevorzugten Ausführungsform eines tragbaren Computers mit einem erfindungsgemäßen Begriffsklärungssystem für eine eingeschränkte Tastatur ist;
Fig. 2 ein Blockdiagramm der Hardware des Begriffsklärungssystems für eingeschränkte Tastaturen aus Fig. 1 ist;
Fig. 3 ein Flußdiagramm einer bevorzugten Ausführungsform der Begriffsklärungssoftware für ein Begriffsklärungssystem für eingeschränkte Tastaturen ist;
Fig. 4 ein Flußdiagramm einer bevorzugten Ausführungsform einer Software ist, die bestimmt, welches Textobjekt als vorgegebenes Objekt in jedem Knoten einer Baumstruktur eines Begriffsklärungssystems für eingeschränkte Tastaturen verwendet werden soll;
Fig. 5a und Fig. 5b zeigen ein Flußdiagramm einer bevorzugten Ausführungsform eines Softwarevorgangs, der nach jedem Tastenanschlag ausgeführt wird, um ein beabsichtigtes Satzzeichen und eine Vielzahl von Satzzeichen, die einer Taste des Begriffsklärungssystems für eine eingeschränkte Tastatur zugeordnet sind, eindeutig zu bestimmen; Fig. 5a zeigt die nach dem ersten Empfang eines Tastenanschlags ausgeführten Verarbeitungsschritte und Fig. 5b zeigt die Verarbeitungsschritte, die ausgeführt werden, wenn alle anderen Verarbeitungsschritte des Tastenanschlags ausgeführt worden sind;
Fig. 6 vergleicht die physische Zuordnung von Symbolen zu einer Taste mit einem Fall einer logischen Zuordnung, die zusätzliche Abwandlungen der auf der physischen Taste dargestellten Buchstaben mit Akzenten umfaßt;
Fig. 7 ist ein Beispiel für eine Tabelle, die logische Symbole Tastenindices zuordnet;
Fig. 8a zeigt eine bevorzugte interne Anordnung von Daten in einem Knoten eines Baums eines Vokabularmoduls;
Fig. 8b stellte die semantischen Komponenten einer bevorzugten Ausführungsform eines Befehls dar;
Fig. 9 zeigt vier Beispiel für mögliche interne Dateneinheiten in der Knotenstruktur einer bevorzugten Ausführungsform;
Fig. 10 stellt die bevorzugte Baumstruktur eines unkomprimierten Vokabularmoduls dar;
Fig. 11 zeigt ein Beispiele für Zustände der Objektliste, die die bevorzugte Ausführungsform für das Zwischenspeichern von Objekten während des Abrufvorgangs im Vokabularmodul sind;
Fig. 12 ist ein Flußdiagramm einer bevorzugten Ausführungsform eines Softwarevorgangs, um auf der Grundlage einer Liste von gedrückten Tasten Textobjekte von einem Vokabularmodul abzurufen;
Fig. 13 ist ein Flußdiagramm einer bevorzugten Ausführungsform eines Softwarevorgangs, um die Baumstruktur des Vokabularmoduls anhand eines einzelnen Tastendrucks zu durchlaufen und um den Zustand der Objektliste zu ändern;
Fig. 14 ist ein Flußdiagramm einer bevorzugten Ausführungsform eines Softwarevorgangs zum Aufbau eines gefalteten, komprimierten Vokabularmoduls;
Fig. 15 ist ein Flußdiagramm einer bevorzugten Ausführungsform eines Softwarevorgangs, um die Baumstruktur eines Vokabularmoduls zu falten;
Fig. 16 ist ein Flußdiagramm einer bevorzugten Ausführungsform eines Softwarevorgangs, um in dem Baum eines Vokabularmoduls einen zweiten Knoten zu finden, der im Vergleich zu einem bestimmten Knoten die größte Redundanz aufweist,
Fig. 17 ist ein Flußdiagramm einer bevorzugten Ausführungsform eines Softwarevorgangs um die Redundanz zwischen zwei Knoten eines Baums im Vokabularmoduls zu berechnen;
Fig. 18a bis 18k sind schematische Darstellungen der bevorzugten Ausführungsform des Begriffsklärungssystems für eingeschränkte Tastaturen während einer typischen Anwendung.

Detaillierte Beschreibung des Ausführungsbeispiels

I. Systemaufbau und grundlegende Funktionsweise

In Fig. 1 ist ein Begriffsklärungssystem 50 für beschränkte Tastaturen dargestellt, das gemäß der vorliegenden Erfindung aufgebaut ist und in einen auf einer Handfläche tragbaren Computer 52 integriert ist. Der tragbare Computer 52 umfaßt eine eingeschränkte Tastatur 54, die auf einem Sensorbildschirm 53 implementiert ist. Im Rahmen dieser Anmeldung ist der Begriff "Tastatur" so breit zu verstehen, daß er jedes Eingabegerät mit definierten Flächen, einschließlich einen Sensorbildschirm mit definierten Flächen für Tasten, diskrete mechanische Tasten, Membrantasten usw. umfaßt. Die Tastatur 54 verfügt über eine beschränkte Zahl von Dateneingabetasten der QWERTY-Standardtastatur. Eine bevorzugte Ausführungsform der Tastatur umfaßt 16 Standardtasten in voller Größe, die in vier Spalten und vier Zeilen angeordnet sind. Genauer gesagt, umfaßt die bevorzugte Tastatur neun in einem 3 · 3-Feld angeordnete Datentasten 56, einschließlich einer Satzzeichentaste 63, eine links angeordnete Spalte mit drei Systemtasten 58, einschließlich einer Auswahltaste 16 (Select- Taste), einer Umschalttaste 62 (Shift-Taste), einer Leerzeichentaste 64 (Space- Taste) und einer Zurücktaste 65 (BackSpace-Taste) in der oberen Reihe 59 zum Löschen vorangegangener Tastenanschläge. Die obere Reihe der Systemtasten 59 umfaßt auch drei MODE-Tasten, die mit "Accent", "Numbers" und "Symbols" beschriftet sind, um jeweils Betriebszustände zum Tippen von Buchstaben mit Akzenten, Zahlen und Symbolen einzugeben.
In Fig. 1 ist eine bevorzugte Anordnung der Buchstaben auf jeder Taste der Tastatur 54 dargestellt. Fig. 1 zeigt auch eine bevorzugte Anordnung der mit den mehrdeutigen Datentasten 63 in der Tastatur 54 für die englische Sprache verbundenen Satzzeichen.
Über Tastenanschläge auf der eingeschränkten Tastatur werden Daten in das Begriffsklärungssystem eingegeben. Wenn ein Benutzer eine Tastenanschlagsfolge mit Hilfe der Tastatur eingibt, wird Text auf der Anzeige 53 des Computers dargestellt. In der Anzeige sind zwei Bereiche zur Anzeige von Informationen für den Benutzer vorgesehen. Ein oberer Textbereich 66 stellt den vom Benutzer eingegebenen Text dar und dient als Puffer für die Eingabe und Edition von Text. Ein unterhalb des Textbereichs angeordneter Auswahllistenbereich 70 stellt eine Liste von Worten und weiteren Interpretationen zur Verfügung, die der vom Benutzer eingegebenen Tastenanschlagsfolge entspricht. Wie nachfolgend noch im einzelnen beschrieben werden wird, unterstützt der Auswahllistenbereich 70 den Benutzer beim Auflösen der Mehrdeutigkeit der eingegebenen Tastenanschläge. Bei einer weiteren bevorzugten Ausführungsform kann das System auf einem Gerät mit begrenzter Anzeigefläche implementiert sein und lediglich das derzeit ausgewählte oder wahrscheinlichste Wort am Einfügepunkt 88 des zu erzeugenden Text anzeigen.
Ein Blockdiagramm der Hardware des Begriffsklärungssystems für eine eingeschränkte Tastatur ist in Fig. 2 dargestellt. Die Tastatur 54 und die Anzeige 53 sind über eine geeignete Schnittstellenschaltung an einen Prozessor 100 angeschlossen. Wahlweise ist auch ein Lautsprecher 102 an den Prozessor angeschlossen. Der Prozessor 100 empfängt die Eingabe von der Tastatur und steuert die gesamte Ausgabe an die Anzeige und den Lautsprecher. Der Prozessor ist an einen Speicher 104 angeschlossen. Der Speicher umfaßt eine Kombination von temporären Speichermedien, wie z. B. "Random Access Memory" (RAM) und permanenten Speichermedien wie z. B. ein "Read Only Memory" (ROM), Disketten, Festplatten oder CD-ROMs. Der Speicher 104 enthält alle zum Steuern der Systemoperationen notwendigen Routinen. Der Speicher enthält vorzugsweise ein Betriebssystem 106, eine Software 108 zur Begriffsklärung und ein zugehörige Vokabularmodule 110, die nachfolgend im Detail diskutiert werden. Der Speicher kann wahlweise auch ein oder mehrere Anwendungsprogramme 112, 114 enthalten. Beispiele für Anwendungsprogramme sind Textverarbeitungsprogramme, Software-Wörterbücher und Übersetzungsprogramme für fremde Sprachen. Als Anwendungsprogramm kann auch eine Software zur Sprachsynthese vorgesehen sein, so daß das Begriffsklärungssystem mit eingeschränkter Tastatur die Funktion einer Kommunikationshilfe haben kann.
Zurück zu Fig. 1: das Begriffsklärungssystem 50 für eine eingeschränkte Tastatur erlaubt dem Benutzer, Text oder andere Daten schnell mit nur einer einzigen Hand einzugeben. Die Daten werden mit Hilfe der Datentasten 56 eingegeben. Jede der Datentasten hat eine mehrfache Bedeutung, die auf der Oberseite der Tasten durch eine Vielzahl von Buchstaben, Zahlen und anderen Symbolen dargestellt sind. (Im Rahmen dieser Beschreibung wird jede Datentaste durch die Symbole in der mittleren Reihe der Datentaste bezeichnet; z. B. DEF für die Datentaste oben rechts.) Da die einzelnen Tasten mehrfache Bedeutungen haben, sind Tastenanschlagsfolgen bezüglich ihrer Bedeutung mehrdeutig. Wenn der Benutzer Daten angibt, werden die verschiedenen Interpretationen der Tastenanschläge in mehreren Bereichen der Anzeige dargestellt, um den Benutzer bei der Auflösung der Mehrdeutigkeit zu unterstützen. Bei Systemen mit ausreichender Anzeigenfläche wird eine Auswahlliste 76 von möglichen Interpretationen der Tastenanschläge dem Benutzer im Auswahllistenbereich 70 zur Verfügung gestellt. Der erste Eintrag 78 in der Auswahlliste wird als vorgegebene Interpretation ausgewählt und im Textbereich 76 am Einfügepunkt 88 angezeigt. Bei der bevorzugten Ausführungsform wird diese Eingabe sowohl in der Auswahlliste 66 als auch am Einfügepunkt 88 in einem Kasten mit durchgezogenen Linien dargestellt. Diese Formatierung erzeugt einen visuell erkennbaren Zusammenhang zwischen dem Objekt am Einfügepunkt und der Auswahlliste und deutet darauf hin, daß dieses Objekt implizit aufgrund der Tatsache ausgewählt wurde, daß es das am häufigsten auftretende Objekt in der aktuellen Auswahlliste ist. Bei einer abgewandelten Ausführungsform wird keine Auswahlliste zur Verfügung gestellt und lediglich das vorgegebene Objekt (das Objekt, das vor dem Betätigen der Auswahltaste zuerst in der Auswahlliste dargestellt wird) oder das aktuell ausgewählte Objekt, wenn vorhanden, wird am Einfügepunkt 88 dargestellt.
Die Auswahlliste 76 der möglichen Interpretationen der eingegebenen Tastenanschläge kann auf eine Vielzahl von Arten geordnet werden. Im normalen Betriebszustand werden die Tastenanschläge zunächst als Eingabe von Buchstaben interpretiert, um ein Wort zu buchstabieren (nachfolgend "Wortinterpretation"). Die Einträge 78, 79 und 80 in der Auswahlliste sind daher Worte, die der eingegebenen Tastenanschlagsfolge entsprechen, wobei die Einträge so angeordnet sind, daß die häufigsten, der Tastenanschlagsfolge entsprechenden Worte als erste aufgelistet werden. Wie in Fig. 1 dargestellt wurde z. B. eine Tastenanschlagsfolge ABC, GHI und DEF von einem Benutzer eingegeben. Während der Eingabe der Tasten wird gleichzeitig ein Nachschlagen im Vokabularmodul ausgeführt, um die Worte mit übereinstimmender Tastenanschlagsfolge zu finden. Die vom Vokabularmodul identifizierten Worte werden dem Benutzer in der Auswahlliste 76 angezeigt. Die Worte werden gemäß ihrer Gebrauchshäufigkeit sortiert, wobei die häufigsten Worte zuerst aufgelistet werden. In dem Beispiel für die Tastenanschlagsfolge werden die Worte "age", "aid" und "bid" vom Vokabularmodul als die häufigsten mit der Tastenanschlagsfolge übereinstimmenden Worte identifiziert. Von den drei identifizierten Worten ist "age" häufiger als "aid" oder "bid", so daß dieses als erstes in der Auswahlliste aufgelistet wird. Das erste Wort wird auch als vorgegebene Interpretation verwendet und vorläufig als Text am Einfügepunkt 88 eingefügt. Vor dem Drücken der Auswahltaste 60 wird das für die vorgegebene Interpretation verwendete Wort am Einfügepunkt 88 und in der Auswahlliste 76 in identischer Formatierung dargestellt. Wie in Fig. 1 dargestellt, erscheint das Wort beispielsweise als Text in einem mit durchgezogenen Linien gezeichnetem Kasten, der gerade groß genug ist, um das Wort aufzunehmen. In Systemen ohne ausreichende Anzeigefläche zur Darstellung der aktuellen Auswahlliste auf dem Bildschirm wird die Liste der potentiell passenden Worte nach der relativen Häufigkeit der passenden Textobjekte sortiert im Speicher aufbewahrt.
Bei einer bevorzugten Ausführungsform drückt der Benutzer nach der Eingabe der dem gewünschten Wort entsprechenden Tastenanschlagsfolge einfach die Leerzeichentaste 64. Das vorgegebene Wort (das erste Wort in der Auswahlliste) wird sofort am Einfügepunkt ausgegeben, die Auswahlliste wird gelöscht und ein Leerzeichen wird sofort im Textbereich am Einfügepunkt 88 ausgegeben. Bei einer abgewandelten Ausführungsform kann jedes andere Mittel, das explizit einen eindeutigen Buchstaben erzeugt, wie beispielsweise das Umschalten in den Symbolmodus und das Drücken einer Taste, die im Symbolmodus eindeutig mit einem einzelnen spezifischen Buchstaben verbunden ist, dazu benutzt werden, das gleiche Ergebnis zu erzielen, abgesehen davon, daß der spezifische eindeutige Buchstabe (und nicht das Leerzeichen) an das ausgegebene Wort am Einfügepunkt 88 angehängt wird. In Abwandlung dazu kann die Satzzeichentaste 63 zum Erzeugen eines Punkt, Bindestrichs oder Apostrophs, wie nachfolgend erläutert, gedrückt werden.
Wenn der erste Eintrag in der Auswahlliste nicht die gewünschte Interpretation der Tastenanschlagsfolge ist, kann der Benutzer durch die Einträge in der Auswahlliste durch wiederholtes Drücken der Auswahltaste 60 durchlaufen. Das Drücken der Auswahltaste zeigt den ersten Eintrag in der Auswahlliste in einem mit gestrichelten Linien gezeichneten Kasten an und stellt auch den ersten Eintrag am Einfügepunkt 88 mit einem identisch formatierten Kasten um den Eintrag dar. Vom Konzept her zeigt der Übergang von einem Kasten mit durchgezogenen Linien zu einem Kasten mit gestrichelten Linien an, daß der Text der Übergabe an den erzeugten Text näher gerückt ist, indem der Benutzer diesen explizit durch Drücken der Auswahltaste ausgewählt hat. Wenn der erste Eintrag in der Auswahlliste die gewünschte Interpretation der Tastenanschlagsfolge ist, gibt der Benutzer als nächstes mit Hilfe der Datentasten 56 das nächste Wort ein. Wenn die Auswahltaste zusätzlich mit einer Funktion zum Erzeugen der Leerzeichen versehen ist, wird ein Leerzeichen vor dem Einfügen des Textes für das nächste Wort erzeugt. Anderenfalls wird der Beginn des nächsten Worts mit dem Ende des aktuellen Worts ohne dazwischenliegendes Leerzeichen verknüpft. Bei jedem Drücken der Auswahltaste wird der nächste Eintrag in der Auswahlliste in einem Kasten mit gestrichelten Linien dargestellt und eine Kopie des Eintrags in einem Kasten mit gestrichelten Linien am Einfügepunkt vorläufig eingefügt (und dabei das zuvor eingefügte Wort ersetzt). Das vorläufige Einfügen des nächsten Eintrags in den Textbereich gestattet dem Benutzer die Aufmerksamkeit weiterhin auf den Textbereich zu richten, ohne auf die Auswahlliste blicken zu müssen. Auf Wunsch des Benutzers kann das System auch so konfiguriert werden, daß beim ersten Drücken der Auswahltaste das vorläufig am Einfügepunkt eingefügte Wort (in vertikaler oder horizontaler Richtung) expandiert, um eine Kopie der aktuellen Auswahlliste anzuzeigen. Der Benutzer kann die maximale Anzahl der in dieser Kopie der Auswahlliste angezeigten Worte auswählen. In Abwandlung dazu kann der Benutzer die Auswahl treffen, daß die Auswahlliste immer, selbst vor der ersten Betätigung der Auswahltaste, am Einfügepunkt angezeigt wird. Das Begriffsklärungssystem interpretiert den Beginn des nächsten Wortes (der durch das Betätigen einer mehrdeutigen Datentaste 56 oder das Erzeugen eines expliziten eindeutigen Buchstabens signalisiert wird) als Bestätigung, daß der gegenwärtig ausgewählte Eintrag der gewünschte Eintrag ist. Das gewählte Wort verbleibt daher am Einfügepunkt als vom Benutzer ausgewählt, der umgebende Kasten verschwindet vollständig und das Wort wird erneut im normalen Text ohne spezielle Formatierung angezeigt.
Wenn der zweite Eintrag in der Auswahlliste das gewünschte Worte ist, fährt der Benutzer nach zweimaligem Drücken auf der Auswahltaste fort, das nächste Wort einzugeben und das Begriffsklärungssystem fügt den zweiten Eintrag automatisch im Textbereich als normalen Text ein. Wenn der zweite Eintrag nicht das gewünschte Wort ist, kann der Benutzer die Auswahlliste überprüfen und die Auswahltaste zur Auswahl des gewünschten Eintrags so häufig wie gewünscht drücken, bevor er zur Eingabe des nächsten Worts übergeht. Wenn das Ende der Auswahlliste erreicht wird, veranlaßt ein weiteres Drücken der Auwahltaste ein Verschieben der Auswahlliste und neue Einträge werden am Ende der Auswahlliste zugefügt. Die Einträge im oberen Bereich der Auswahlliste werden aus der dem Benutzer angezeigten Liste entfernt. Der durch mehrfaches Drücken der Auswahltaste ausgewählte Eintrag wird automatisch in den Textbereich eingefügt, wenn der Benutzer eine der Datentasten 56 drückt, um die Texteingabe fortzusetzen. Bei einem abgewandelten Ausführugsbeispiel kann der Benutzer nach der Eingabe der dem gewünschten Wort entsprechenden Tastenanschlagsfolge das gewünschte Wort aus der Auswahlliste auf einfache Weise auswählen, indem er dieses berührt. Das ausgewählte Wort wird ohne Hinzufügen eines Leerzeichens sofort am Einfügepunkt ausgegeben und die Auswahlliste wird gelöscht. Der Benutzer kann dann die Leerzeichentaste drücken, um ein Leerzeichen zu erzeugen, das sofort im Textbereich am Einfügepunkt 88 ausgegeben wird.
Bei der Mehrzahl von Texteingaben beabsichtigt der Benutzer mit der Tastenanschlagsfolge Buchstaben für ein Wort einzugeben. Es sei jedoch angemerkt, daß die zahlreichen jeder Taste zugeordneten Buchstaben und Symbole mehrere Interpretationen der einzelnen Tastenanschläge und Tastenanschlagsfolgen zulassen. Bei dem bevorzugten Begriffsklärungssystem für eingeschränkte Tastaturen werden, während die Tastenanschlagsfolge interpretiert und dem Benutzer als Wortliste angezeigt wird, mehrere verschiedene Interpretationen automatisch bestimmt und dem Benutzer zur gleichen Zeit angezeigt.
Beispielsweise wird die Tastenanschlagsfolge im Sinne von Wortstämmen interpretiert, die möglichen gültigen Buchstabenfolge entsprechen, die ein Benutzer eingeben kann (nachfolgend "Stamminterpretation"). Im Gegensatz zu Wortinterpretationen sind Wortstämme unvollständige Worte. Durch die Angabe der möglichen Interpretation der letzten Tastenanschläge gestatten die Wortstämme dem Benutzer auf einfache Weise die Überprüfung, ob die korrekten Tastenanschläge eingegeben wurden, oder das Wiederaufnehmen des Tippens, wenn er oder sie in der Wortmitte abgelenkt worden ist. Wie in Fig. 1 dargestellt, wurden die Tastenanschlagsfolgen ABC GHI DEF als gültige Stämme "ehe" (was zu den Wörtern "check", "cheer" usw. führt) und "ahe" (was zu den Worten "ahead", "ahem" usw. führt) interpretiert. Die Stamminterpretation werden daher als Einträge 81 und 82 in der Auswahlliste zur Verfügung gestellt. Die Stamminterpretationen werden vorzugsweise nach der Gesamthäufigkeit der Menge aller derjenigen möglichen Worte sortiert, die aus jedem Stamm durch zusätzliche Tastenanschläge auf den Datentasten erzeugt werden können. Die maximale Zahl und die minimale Gesamthäufigkeit der anzuzeigenden Einträge kann vom Benutzer ausgewählt oder im System konfiguriert werden, so daß einige Stamminterpretationen nicht dargestellt werden. Im vorliegenden Beispiel werden die Stämme "bif" (der zu dem Wort "bifocals" führt), "cid" (der zu dem Wort cider" führt) und "bie" (der zu dem Wort "biennial" führt) nicht dargestellt. Wenn eine Stamminterpretation in der Auswahlliste aufgelistet wird, wird der Stamm ausgelassen, wenn eine Stamminterpretation ein in der Auswahlliste dargestelltes Wort dupliziert. Wenn der Stamm ausgelassen wird, wird das dem ausgelassenen Stamm entsprechende Wort mit einem Symbol markiert, um anzuzeigen, daß längere Wörter existieren, die dieses Wort als Stamm besitzen. Die Stamminterpretationen liefern dem Benutzer eine Rückmeldung, indem sie bestätigen, daß die korrekten Tastenanschläge für die Eingabe eines gewünschten Worts eingegeben worden sind.
Der Betrieb des Begriffsklärungsystem für eine eingeschränkte Tastatur wird durch die Begriffsklärungsoftware 108 gesteuert. In einer bevorzugten Ausführungsform des Systems ist die Auswahltaste "überladen" ("overloaded"), so daß diese sowohl die Auswahlfunktion des gewünschten Objekts aus der Auswahlliste ausführt als auch, falls erforderlich, ein explizites Leerzeichen erzeugt. In einem solchen System wird das Flag "OverloadSelect" (auf das in den Blöcken 164 und 147 Bezug genommen wird) auf TRUE gesetzt. In Systemen mit einer eigenen Leerzeichentaste, die zum Erzeugen eines expliziten Leerzeichens vorgesehen ist, wird das Flag "OverloadSelect" auf FALSE gesetzt.
Fig. 3 ist ein Flußdiagramm einer Hauptroutine der Begriffsklärungssoftware, die eine Auswahlliste erzeugt, um dem Benutzer beim Eindeutig-Machen einer mehrdeutigen Tastenanschlagsfolge zu helfen. Bei einem Block 150 wartet das System auf den Empfang eines Tastenanschlags von der Tastatur 54. Beim Empfang eines Tastenanschlags führt das System eine für die Satzzeichentaste 63 erforderliche Vorverarbeitung aus, die in Fig. 5A dargestellt ist und nachfolgend im einzelnen diskutiert werden wird. In einem Entscheidungsblock 151 wird ein Test ausgeführt, um festzustellen, ob der empfangene Tastenanschlag eine Modus-Auswahl-Taste ist. Wenn ja, dann setzt das System im Block 172 ein Flag zur Anzeige des aktuellen Systemmodus. In einem Entscheidungsblock 173 wird ein Test durchgeführt, um festzustellen, ob sich der Systemmodus geändert hat. Wenn ja, dann werden im Block 171 die Tastenoberflächen, wie für den geltenden Systemmodus erforderlich, neu gezeichnet. Wenn der Systemmodus sich nicht geändert hat oder wenn er sich geändert hat und die Tastenoberflächen nachfolgend neu gezeichnet worden sind, kehrt die Hauptroutine zum Block 150 zurück und wartet auf einen weiteren Tastenanschlag.
Wenn andererseits im Block 151 festgestellt wird, daß der Tastenanschlag nicht eine Modus-Auswahl-Taste ist, dann wird im Entscheidungsblock 152 ein Test durchgeführt, um zu überprüfen, ob der empfangene Tastenanschlag die Auswahltaste ist. Wenn der Tastenanschlag nicht die Auswahltaste ist, dann wird im Entscheidungsblock 153 ein Test durchgeführt, um zu bestimmen, ob das System in einem Modus für explizite Buchstaben wie z. B. in einem expliziten numerischen Modus ist. Falls ja, dann wird im Entscheidungsblock 166 ein Test durchgeführt, durch den überprüft wird, ob irgendein vorläufig ausgewählter Gegenstand in der Auswahlliste vorhanden ist. Falls ja, dann wird in einem Block 167 der Gegenstand akzeptiert und als normaler Text ausgegeben. Wenn kein vorläufig akzeptierter Gegenstand in der Auswahlliste vorhanden ist oder wenn er vorhanden ist und bereits akzeptiert worden ist, dann wird im Block 168 der dem Tastenanschlag entsprechende explizite Buchstabe im Textbereich ausgegeben. Weiterhin wird in einem Entscheidungsblock 169 ein Test durchgeführt, um zu bestimmen, ob der Systemmodus wie im Fall des Symbolmodus automatisch geändert werden soll. Wenn ja, dann wird die Ausführung mit den Blöcken 170 und 171 fortgesetzt, wobei der Systemmodus in den zuvor aktiven Modus zurückgeschaltet wird und die Tastenoberflächen entsprechend gezeichnet werden. Die Ausführung kehrt dann zum Block 150 zurück.
Wenn im Block 153 kein Modus für explizite Buchstaben aktiv ist, wird in einem Block 154 der Tastenanschlag zu einer gespeicherten Tastenanschlagfolge hinzugefügt. Im Block 156 werden der Tastenanschlagsfolge entsprechende Objekte vom Vokabularmodul im System identifiziert. Die Vokabularmodule sind Bibliotheken von Objekten, die den Tastenanschlagsfolgen zugeordnet sind. Ein Objekt ist jedes Stück gespeicherter Daten, das auf der Grundlage der empfangenen Tastenanschlagsfolge abgerufen werden kann. Objekte innerhalb des Vokabularmoduls können beispielsweise Zahlen, Buchstaben, Worte, Wortstämme, Sätze oder Systemfunktion und Makros umfassen. Jedes dieser Objekte wird nachfolgend kurz in der Tabelle beschrieben:
Objekt Entsprechende Daten
Zahlen Eine Zahl, deren Ziffern einem einzelnen Tastenanschlag entsprechen, z. B. die Folge "42" mit zwei Ziffern.
Buchstaben Ein Buchstabe oder eine Folge von Buchstaben entspricht Paaren von Tastenanschlägen, z. B. der Folge "str" mit drei Buchstaben. Jedes Paar von Tastenanschlägen wird zum Eindeutig-Machen verwendet, indem das Verfahren zur Eingabe von einzelnen Buchstaben gemäß der Zwei-Anschläge- Spezifikation verwendet wird.
Wort Ein Wort entspricht einem einzelnen oder einer Vielzahl von Tastenanschlägen, z. B. das Wort "done" mit vier Buchstaben.
Stamm Eine Folge von Buchstaben, die einen gültigen Teil einer längeren Buchstabenfolge bildet, die ein Wort bildet, z. B. "albe" als Stamm des Wortes "albeit".
Satz Ein vom Benutzer oder vom System gebildeter Satz entspricht einem einzelnen oder einer Vielzahl von Tastenanschlägen, z. B. " To Whom it May Concern:"
Systemmakro Ein Wort und ein zugeordneter Code, der ein Systemfunktion oder eine vom Benutzer definierte Funktion beschreibt, z. B. "(clear)", um den aktuellen Textbereich zu löschen. Das Systemmakroobjekt ist im Vokabularmodul neben dem zu beschreibenden Wort mit ausführbarem Code verknüpft, der zum Ausführen der spezifizierten Funktion erforderlich ist.
Obwohl die bevorzugten Vokabularobjekte oben diskutiert worden sind, sei angemerkt, daß andere Objekte auch in Betracht gezogen werden können. Beispielsweise kann ein Grafikobjekt mit einem abgespeicherten Grafikbild verknüpft werden oder ein Sprachobjekt kann mit einem abgespeicherten Sprachsegment verknüpft werden. Denkbar ist auch ein Buchstabierobjekt, das die Buchstabenfolge eines im allgemeinen falsch geschriebenen Worts und von Tippfehlern mit der korrekten Schreibweise des Worts verknüpft. Beispielsweise werden Worte mit der Buchstabenfolge "ie" oder "ei" in der Wortliste erscheinen, selbst wenn die richtige Reihenfolge der Buchstaben aus Versehen vertauscht worden ist. Um die Verarbeitung zu vereinfachen, enthält jedes Vokabularmodul vorzugsweise ähnliche Objekte. Es sei jedoch angemerkt, daß verschiedene Objekte innerhalb eines Vokabularmoduls gemischt werden können.
Eine repräsentative Darstellung einer einzelnen Taste 540 ist in Fig. 6 gezeichnet. Die interne logische Darstellung der Tasten braucht bei der bevorzugten Ausführungsform nicht die physische Anordnung widerspiegeln. Das Beispiel 541 ist eine bevorzugte logische Beschreibung einer Taste, die mit einem französischen Vokabularmodul verknüpft ist. Im französischen Alphabet sind drei zusätzliche Symbole 642 ( ) erforderlich. Diese Symbole werden vorzugsweise gemäß der abnehmenden Gebrauchshäufigkeit in einem französischen Lexikon einem Index 543 zugeordnet. In einer verallgemeinerten Form stellt Fig. 7 eine bevorzugte Tabelle dar, die die Indices von logischen Symbolen zu Tastenindices, die zum Eindeutig-Machen von Tastendrücken in französischen Wörtern verwendet werden, in Beziehung setzt.
Ein repräsentatives Diagramm eines Vokabularmoduls 110 mit Wortobjekten ist in Fig. 10 gezeigt. Um die Objekte in einem Vokabularmodul auf der Grundlage von entsprechenden Tastenanschlagsfolgen zu organisieren, wird eine Baumstruktur verwendet. Wie in Fig. 10 gezeigt, stellt jeder Knoten N1, N2, . . ., N9 in dem Baum des Vokabularmoduls eine bestimmte Tastenanschlagsfolge dar. Die Knoten in dem Baum sind durch Pfade P1, P2, . . ., P9 verbunden. Da bei der bevorzugten Ausführungsform des Begriffsklärungssystems neun mehrdeutige Datentasten vorhanden sind, kann jeder Elternknoten in dem Vokabularmodulbaum mit neun Kinderknoten verknüpft sein. Über Pfade verknüpfte Knoten kennzeichnen gültige Tastenanschlagsfolgen, während das Fehlen eines Pfades von einem Knoten eine ungültige Tastenanschlagsfolge kennzeichnet, d. h. eine, die keinem abgespeicherten Wort entspricht.
Der Vokabularmodulbaum wird auf eine empfangene Tastenanschlagsfolge hin durchlaufen. Wenn z. B. ein Drücken der ersten Datentaste vom Wurzel-Knoten 111 dazu führt, das mit der ersten Taste verknüpfte Daten aus dem Wurzel-Knoten 111 geholt und ausgewertet werden, dann wird der Pfad P1 zum Knoten N1 durchlaufen. Wenn die neunte Datentaste nach dem Drücken der ersten Datentaste dazu führt, daß mit der neunten Datentaste verknüpfte Daten aus dem Knoten N1 geholt und ausgewertet werden, dann wird der Pfad P19 zum Knoten N19 durchlaufen. Wie nachfolgend noch im einzelnen beschrieben werden wird, ist jeder Knoten mit einer Anzahl von Objekten verknüpft, die der Tastenanschlagfolge entsprechen. Bei jedem Empfang eines Tastenanschlags und bei jeder Verarbeitung des entsprechende Knotens, wird eine Objektliste der der jeweiligen Tastenanschlagfolge entsprechenden Objekte erzeugt. Die Objektliste von jedem Vokabularmodul wird von der Hauptroutine des Begriffsklärungssystems zum Erzeugen einer Auswahlliste 76 verwendet.
Fig. 8A ist ein Blockdiagramm einer bevorzugten, jedem Datenknoten zugeordneten Datenstruktur 400. Die Datenstruktur enthält Informationen, die jeden Elternknoten mit den Kinderknoten in dem Vokabularmodulbaum verbindet. Die Datenstruktur enthält darüber hinaus Informationen (Befehle), um die Objekte zu identifizieren, die mit der vom Knoten dargestellten bestimmten Tastenanschlagsfolge verknüpft sind.
Das erste Feld in der Knotendatenstruktur 400 ist ein Bitfeld 402 für gültige Tasten, das die Zahl und Identität der mit dem Elternknoten verknüpften Kinderknoten angibt und ferner anzeigt, welche der neun möglichen Tasten mit Informationen (Befehlen) verknüpft sind, um die Objekte zu identifizieren, die mit einer bestimmten vom Knoten dargestellten Tastenanschlagsfolge verknüpft sind. Da neun Datentasten in der bevorzugten Ausführungsform vorhanden sind, können maximal neun Kinderknoten mit einem Elternknoten verknüpft sein und neun Bits für gültige Tasten sind daher in dem Bitfeld für gültige Tasten vorgesehen, um die Anwesenheit oder Abwesenheit von Kinderknoten anzuzeigen. Jedes Bit für gültige Tasten ist mit einem Zeigerfeld 404a, 404b, . . ., 404n verknüpft, das einen Zeiger zu der jeweiligen Datenstruktur des Kinderknotens im Vokabularmodul enthält. Da ein Kinderknoten nur dann vorhanden ist, wenn der mit dem Kinderknoten verknüpfte Tastenanschlag eine gültige Fortsetzung der mit dem Elternknoten verknüpften Tastenanschlagsfolge ist, variiert die Zahl von Zeigerfeldern in jedem Knoten. Beispielsweise kann das Bitfeld 402 für gültige Tasten anzeigen, daß lediglich sechs der möglichen neun Tastenanschläge zu einem gültigen Kinderknoten führen. Da nur sechs gültige Pfade vorhanden sind, sind nur sechs Zeigerfelder in der Datenstruktur des Elternknotens vorhanden. Das Bitfeld 402 für gültige Tasten wird dazu verwendet, die Identität der innerhalb der Knotendatenstruktur enthaltenen Zeigerfelder zu bestätigen. Wenn ein Tastenanschlag nicht zu einem gültigen Kinderknoten führt, wird das zugehörige Zeigerfeld aus der Knotendatenstruktur weggelassen, um den zum Abspeichern des Vokabularmoduls erforderlichen Speicherplatzes zu beschränken.
Mit jedem Knoten ist eine Anzahl von Objekten verknüpft, die der vom Knoten dargestellten Tastenanschlagsfolge entspricht. Jedes der Objekte wird durch einen Befehl in 406 in einem Paket beschrieben, das wie von dem Bitmuster in dem Bitfeld 402 für gültige Tasten in der Knotendatenstruktur angegeben, einer bestimmten gültigen Taste zugeordnet ist.
Jeder Befehl in jedem Paket 406 beschreibt eines der Objekte, die der von jedem Knoten dargestellten Tastenanschlagsfolge entsprechen. Die Beschreibung eines Objekts erfordert den Unterhalt von zwei Objektlisten. Fig. 11 stellt repräsentative Objektlisten dar, die durch einen Begriffe klärenden Softwareprozeß in dem Vokabularmodulbaum von einem Elternknoten und einem Kinderknoten dynamisch erstellt worden sind. Die Objektliste 430 ist eine Objektliste, die die Objekte 1 bis N&sub1; enthält, die mit einem Knoten für zwei Tastenanschläge verknüpft sind. Die Objektliste 440 ist eine Objektliste, die die Objekte 1 bis N&sub2; enthält, die mit einem Knoten für drei Tastenanschläge verknüpft sind. Jede Objektliste enthält eine Liste von allen Objekten, die mit dem jeweiligen Knoten verknüpft sind. Die Objektliste 430 ist mit einem Elternknoten verknüpft, der die Tastenanschlagsfolge ABC ABC von der Tastatur aus Fig. 1 darstellt. Die Objektliste 440 ist mit einem Kinderknoten verknüpft, der die Tastenanschlagsfolge ABC ABC TUF darstellt. Es sei angemerkt, daß die Größe der Objektliste variiert wird, um der tatsächlichen Zahl von der mit dem jeweiligen Knoten verknüpften Objekten Rechnung zu tragen.
Jedes mit einem Kinderknoten verknüpfte Objekt wird konstruiert, indem eine Buchstabenfolge einem für den Elternknoten konstruierten Objekt hinzugefügt wird. Das Befehlspaket 406 in Fig. 8A enthält daher einen Befehl 558 mit einem in Fig. 8B dargestellten Feld OBJECT-LIST-INDEX, das in einer Elternknotenobjektliste ein Objekt identifiziert, das zur Konstruktion des Kinderknotenobjekts verwendet wird. Beispielsweise wird in Fig. 11 das erste Objekt "ba" in der alten Objektliste 430 zur Konstruktion des zweiten Objekts "bat" in der neuen Objektliste 440 verwendet. Das der Identifikation des vorhergehenden Objekts dienende Feld OBJECT-LIST-INDEX 556 stellt daher eine Verknüpfung zu den Einträgen in der alten Objektliste zur Verfügung, um das zur Konstruktion des neuen Objekts verwendete alte Objekt zu identifizieren.
Der Befehl 558 kann auch ein Feld LOGICAL-SYMBOL-INDEX 556 enthalten, um für die Konstruktion des neuen Objekts das zu dem identifizierten Objekt hinzuzufügende Symbol anzugeben. Das Feld LOGICAL-SYMBOL-INDEX spezifiziert daher den Buchstaben der letzten Taste in der Tastenfolge des Knoten, der zur Konstruktion des neuen Objekts angehängt wird. Der Buchstabe wird mit Hilfe einer Tabelle, wie zum Beispiel der in Fig. 7 dargestellten, spezifiziert, wobei die Felder LOGICAL-SYMBOL-INDEX den logischen Symbolindices 552 in der ersten Reihe der Tabelle 550 entsprechen und wobei die Reihe, in der die spezifizierte Taste erscheint, durch den Tastenindex in der ersten Spalte der Tabelle angegeben wird. Das erste Objekt "CAT" in der neuen Objektliste 440 in Fig. 11 wird beispielsweise dadurch konstruiert, daß das zweite Objekt "CA" in der alten Objektliste 430 verwendet und ein zusätzlicher Tastenanschlag zur Spezifikation des "T" angehängt wird. In der logischen Symbolindextabelle in Fig. 7 ist "T" der erste logische Buchstäbe der TUV-Taste und daher wird das Feld LOGICAL-SYMBOL-INDEX des Befehls der das Objekt "CAT" erzeugt gleich 1 gesetzt, um den ersten Buchstabe n in der Tabelle anzugeben. Das auf diese Weise erfolgende Codieren der Objekte macht Gebrauch von der bekannten Zuordnung von Tastenfolgen zu jedem Knoten und der bekannten Zuordnung von Buchstaben zu Tasten, um die für jedes Vokabularmodul erforderliche Speichermenge wesentlich zu reduzieren.
Die Vokabular-Encodiertechnik gestattet auch einen Zugang zu dem Vokabularmodul ohne Suchen. Beim Empfang eines neuen gültigen Tastenanschlags führt das System die mit der Taste am aktuellen Knoten verknüpften Befehle aus, um eine neue Objektliste aus der alten zu konstruieren, und folgt dann einem einzelnen Zeiger zu dem passenden Kinderknoten. Anstatt jedes Objekt in dem Vokabularmodul abzuspeichern, wird ein neues Objekt dadurch gebildet, daß das Feld LOGICAL-SYMBOL-INDEX zur Ergänzung einer alten Interpretation verwendet wird. Auf diese Weise wird ein einer Vielzahl von Objekten gemeinsamer Wortstamm im Vokabularmodul lediglich einmal gespeichert und wird zum Erzeugen aller von ihm abgeleiteter Objekte verwendet. Die beschriebene Speichermethode setzt voraus, daß für die Konstruktion einer Objektliste des Kinderknotes eine Objektliste eines Elternknotens in einen Vokabularmodulbaum aufrechterhalten wird.
Die Einträge in der logischen Symbolindextabelle, wie zum Beispiel der in Fig. 7 dargestellten, brauchen nicht einzelne Schriftzeichen zu sein; beliebige Folgen können den Platz eines Eintrags einnehmen. Beispielsweise kann die ASCII- Zeichenfolge "tlike" dem zweiten Objekt "ca" der alten Objektliste hinzugefügt und das Wort "catlike" gebildet werden. Auf diese Weise entspricht die Länge einer eingegebenen Tastenanschlagsfolge nicht notwendigerweise unmittelbar der Länge der zugeordneten Objekte. Eine als Eintrag in die Symbolindextabelle abgespeicherte ASCII-Folge gestattete die Identifikation eines Vokabularobjekts durch eine beliebige Tastenfolge, d. h. ein Abspeichern an einer beliebigen Stelle innerhalb des Vokabularmodulbaums.
Die Möglichkeit, Objekte mit einer beliebigen Tastenanschlagsfolge abzuspeichern, wird dazu verwendet, die Systemverarbeitung von Abkürzungen und Kontraktionen zu beschleunigen. Die Abkürzungen und Kontraktionen können durch eine Tastenanschlagsfolge identifiziert werden, die dem rein alphabetischen Inhalt ohne Berücksichtigung der Satzzeichen entspricht. Im Ergebnis können Abkürzungen und Kontraktionen ohne die Eingabe von Satzzeichen auf einfache Weise eingegeben werden, was zu einer wesentlichen Einsparung bei den Tastenanschlägen führt. Beispielsweise kann der Benutzer die Tastenanschlagsfolge für "didn't" eingeben, ohne den Apostroph zwischen dem "n" und dem "t" einzutippen. Der Befehl in dem Vokabularmodul, der der Tastaturanschlagsfolge "didn't" entspricht, verweist auf eine ASCII-Folge mit einem Apostroph zwischen dem "n" und dem "t" als einzigem Symbol in der Tabelle. Das Begriffsklärungssystem wird daher automatisch dem Benutzer das korrekte Wort "didn't" anzeigen, ohne daß der Benutzer das Satzzeichen eintragen muß. Das Begriffsklärungssystem verwendet die gleiche Tabelle um fremdsprachige Wörter mit besonderen Buchstaben korrekt anzuzeigen (z. B. D, das als einzelner Tastenanschlag der TUV-Taste eingegeben werden kann). Die Verwendung von Großbuchstaben kann auf ähnliche Weise gehandhabt werden. Wörter die immer in Großbuchstaben geschrieben werden sollen, Wörter mit einem Großbuchstaben am Anfang oder in der Mitte können mit Tastenanschlagsfolgen verknüpft werden, in dem die Großbuchstaben anzeigenden Tastenanschläge fehlen, was dem Benutzer erspart, Großbuchstaben einzugeben. Es ist auch möglich, in jeden Befehl 558 ein Feld für den Objekttyp vorzusehen, um zusätzliche Informationen über das zu konstruierende Objekt anzugeben. Das Feld für den Objekttyp kann zur Spezifikation, ob das erzeugte Objekt ein Wort, ein Wortstamm oder ein anderes Objekt ist, Code enthalten. Das Feld für den Objekttyp gestattet daher das Mischen von verschiedenen Objekttypen in einem gegebenen Vokabularmodul. Darüber hinaus kann das Feld für den Objekttyp Informationen über die Wortart, Information über das Großschreiben des Objekts oder zu Konstruktion verschiedener Beugungen und Endungen erforderliche Informationen enthalten. Ein Begriffsklärungssystem mit eingeschränkter Tastatur, das ein Vokabularmodul mit Information zu den Wortarten benutzt, kann diese zusätzlichen Informationen zur Implementierung einer syntaktischen Analyse zur Verbesserung des Begriffsklärungsvorgangs verwenden. Das Feld für den Objekttyp kann auch eindeutigen Code zur Übertragung von Text in einer komprimierten Form enthalten. In diesem Fall wird anstelle der Übertragung der eingegebenen Tastenanschlagsfolge oder der zugehörigen eindeutig gemachten Buchstaben eine Übertragung des eindeutigen Codes an ein entferntes Terminal stattfinden.
Eines der Hauptmerkmale der bevorzugten Vokabularmodul-Baumstruktur ist, daß die mit jedem Knoten verknüpften Objekte in der Knotendatenstruktur 400 entsprechend ihrer Gebrauchshäufigkeit gespeichert sind. Das bedeutet, daß ein mit Hilfe des ersten Befehls im Paket 406 konstuiertes Objekt eine größere Gebrauchshäufigkeit als das mit Hilfe des zweiten Befehls (wenn vorhanden) in 406 konstruierten Objekt hat, welches eine höhere Gebrauchshäufigkeit als das mit Hilfe des dritten Befehls (wenn vorhanden) konstruierte Objekt hat. Auf diese Weise werden die Objekte in der Objektliste automatisch so angeordnet, daß sie nach abnehmender Gebrauchshäufigkeit sortiert sind. In diesem Zusammenhang bezieht sich der Begriff der Gebrauchshäufigkeit auf die Wahrscheinlichkeit, ein bestimmtes Wort innerhalb eines repräsentativen, hauptsächlichen Anwendungsfalls zu gebrauchen, was proportional zur Auftrittshäufigkeit in diesem hauptsächlichen Anwendungsfall ist. Im Fall von Wortstämmen wird die Gebrauchshäufigkeit durch Addition der Häufigkeiten aller Worte mit dem gleichen Wortstamm bestimmt.
Das Abspeichern der Gebrauchshäufigkeit oder weiterer Ranginformationen in jedem Knoten erspart beim Gebrauch des Systems die Bestimmung und das Sortieren nach dem Rang jedes Objekts. Dies hat wichtige Folgen für das Wortobjektvokabular, da die gespeicherten Objekte gemeinsame Stämme enthalten können, die einer großen Zahl von längeren Wörtern gemeinsam sind. Die dynamische Bestimmung des relativen Rangs dieser Stämme würde voraussetzen, daß der gesamte Baum der Kinderknoten durchlaufen wird und Information über jeden Stamm gesammelt wird, was ein tragbares Computergerät mit einer signifikanten zusätzlichen Rechenaufwand belasten würde. Die Bestimmung der Information im voraus und das Abspeichern in den Vokabulardaten reduziert daher den zusätzliche Rechenaufwand. Darüber hinaus ist kein zusätzlicher Speicherplatz für diese Information erforderlich, wenn die Gebrauchshäufigkeit oder der Rang implizit durch die Anordnung der Objekte 406 im Knoten dargestellt wird.
Obwohl die Objekte in der Knotendatenstruktur 400 entsprechend ihrer Gebrauchshäufigkeit abgespeichert werden, ist denkbar, daß auch ein Feld zur Gebrauchshäufigkeit mit jedem Befehl verknüpft werden kann. Das Feld für die Gebrauchshäufigkeit würde eine repräsentative Zahl enthalten, die der Gebrauchshäufigkeit des zugehörigen Objekts entspricht. Die Gebrauchshäufigkeit von verschiedenen Objekten würde durch einen Vergleich der Felder für die Gebrauchshäufigkeit jedes Objekts bestimmt. Der Vorteil der letzten Konstruktion, die jedem Objektpaket ein Feld zur Gebrauchshäufigkeit zuordnet ist, daß das Feld für die Gebrauchshäufigkeit durch das Begriffsklärungssystem verändert werden kann. Das System könnte beispielsweise ein Feld für die Gebrauchshäufigkeit ändern, um die Häufigkeit wiederzugeben, mit der ein Benutzer gewisse Objekte innerhalb des Vokabularmoduls während einer repräsentativen Texteingabe nutzt.
Zurück zu Fig. 3: im Block 156 werden die einer empfangenen Tastenanschlagsfolge entsprechenden Objekte in jedem Vokabularmodul identifiziert. Fig. 12 ist ein Flußdiagramm einer Subroutine 600 zum Analysieren der empfangenen Tastenanschlagsfolge und zur Identifizierung der entsprechenden Objekte in einem bestimmten Vokabularmodul. Die Subroutine 600 erzeugt eine Objektliste für eine bestimmte Tastenanschlagsfolge. Der Block 602 löscht die neue Objektliste. Der Block 604 initialisiert das Durchlaufen des Baums 110 am Wurzel-Knoten 111. Der Block 604 bekommt die erste gedrückte Taste. Die Blöcke 608 bis 612 bilden eine Schleife, um alle verfügbaren Tastenanschläge zu verarbeiten. Der Block 608 ruft die Subroutine 620 in Fig. 13 auf. Der Entscheidungsblock 610 bestimmt, ob alle verfügbaren Tastenanschläge verarbeitet worden sind. Wenn ein Tastenanschlag unverarbeitet geblieben ist, rückt der Block 612 zu dem nächsten verfügbaren vor. Wenn alle Tastenanschläge verarbeitet worden sind, gibt der Block 614 die komplette Objektliste zurück. Wenn die Hauptroutine die Routine 600 wiederholt mit neuen Tastenanschlagsfolgen aufruft, wobei zu jeder jeweils eine weitere Taste hinzugekommen ist und alle Tasten außer der letzten die gleichen wie bei dem letzten Aufruf sind, ist es denkbar, daß die Initialisierungsblöcke 602 und 604 übersprungen werden, wenn die Subroutine 620 unmittelbar zur ausschließlichen Verarbeitung der letzten Tastenanschläge aufgerufen wird.
Fig. 13 ist ein Flußdiagramm einer von der Subroutine 600 aufgerufenen Subroutine 620. In der in Fig. 3 dargestellten Hauptroutine wurde ein Tastenanschlag durch das System im Block 150 delektiert. Der Empfang eines neuen Tastenanschlags führt zu einem nach unten gerichteten Durchlaufen in dem Vokabularmodulbaum, wenn ein gültiger Pfad zu einem dem Tastenanschlag entsprechenden Kind existiert. Im Block 621 in Fig. 13 wird das Bitfeld für die gültigen Tasten der Knotendatenstruktur 400 überprüft, um festzustellen, ob dem empfangenen Tastenanschlag ein gültiger Befehl und ein Zeiger entspricht. In einem Entscheidungsblock 622 wird das Bitfeld für die gültigen Tasten überprüft, um festzustellen, ob ein aus Befehl 406 und einem Zeigerfeld, wie zum Beispiel 404a, bestehendes gültiges Paket 408 existiert, das dem eingegebenen Tastenanschlag entspricht. Falls kein gültiges Paket dem Tastenanschlag entspricht, wird im Block 624 die alte Objektliste zum Erzeugen der Auswahlliste zurückgegeben, da der empfangene Tastenanschlag Teil einer ungültigen Tastenanschlagfolge ist, die keinem Objekt innerhalb des Vokabularmoduls entspricht. Der Zweig der Subroutine 620, der die Blöcke 622 und 624 umfaßt, ignoriert daher ungültige Tastenanschlagsfolgen und gibt die am Elternknoten erzeugte Objektliste für eine mögliche Darstellung in der vom Begriffsklärungssystem erzeugten Auswahlliste zurück.
Wenn im Entscheidungsblock 622 ein dem empfangenen Tastenanschlag entsprechendes gültiges Paket existiert, fährt die Subroutine mit dem Block 626 fort, wo die neue Objektliste auf die alte Objektliste kopiert wird. Wie oben angemerkt, beginnt das Begriffklärungssystem zur Konstruktion einer neuen Objektliste mit einer Kopie der alten Objektliste. Im Block 626 wird die Objektliste des vorhergehenden Knotens daher abgespeichert, so daß sie zur Konstruktion der neuen Objektliste verwendet werden kann.
Der Block 628 holt den ersten mit einer bestimmten Taste verknüpften Befehl. Der Block 630 initialisiert den Zähler NEW-INDEX mit 1, so daß der erste Befehl den ersten Gegenstand in der neuen Objektliste erzeugt. Die Subroutine tritt dann in die Schleife mit den Blöcken 632 bis 642 ein, um die den gültigen Befehlen zugeordnete Objektliste zu erstellen. Im Block 632 wird das Feld OBJECT-LIST- INDEX 556 überprüft und das entsprechende Objekt von der alten Objektliste geladen. Im Block 634 wird das Feld LOGICAL-SYMBOL-INDEX 555 überprüft und das geeignete Symbol (das mit dem empfangenen Tastenanschlag durch eine logische Symbolindextabelle wie die in Fig. 7 dargestellte verknüpft ist) wird an das Ende des identifizierten Objekts angehängt. Es ist denkbar, daß eine ASCII Folge mit einer Länge größer 1 an das identifizierte Objekt in dem Block 634 angehängt wird, wenn der Eintrag in die Symboltabelle 550 bei der gegebenen Taste 551 und dem logischen Symbolindex 552 eine Buchstabenfolge enthält. Im Block 636 wird die Kombination von Objekt und Symbol als neues Objekt in der neuen Objektliste abgespeichert. In einem Block 638 wird ein Test durchgeführt um festzustellen, ob die Subroutine den letzten mit der bestimmten Taste an einen bestimmten Knoten verknüpften gültigen Befehl ausgeführt hat. Wenn der letzte gültige Befehl nicht ausgeführt worden ist, wird im Block 640 der nächste gültige Befehl geholt. Im Block 642 wird NEW-INDEX inkrementiert.
Wenn der Test im Entscheidungsblock 638 anzeigt, daß alle Objekte für den Knoten konstruiert worden sind, fährt die Subroutine mit dem Block 644 fort und folgt dem zugehörigen Zeiger zum Kindknoten. Im Block 646 wird die neue Objektliste zum Erzeugen der Auswahlliste an die Hauptroutine zurückgegeben. Es sei angemerkt, dass die Subroutine 600 zum Erzeugen der mit jedem Knoten verknüpften Objektliste bei jedem vom Benutzer empfangenen Tastenanschlag ausgeführt wird. Wenn der Benutzer eine neue Tastenanschlagfolge ausführt, wird kein "Suchvorgang" im Vokabularmodul ausgeführt, da jeder Tastenanschlag die Subroutine lediglich eine weitere Ebene innerhalb des Vokabularmodulbaums voranbringt. Da keine Suche für jeden Tastenanschlag ausgeführt wird, gibt das Vokabularmodul die mit jeden Knoten verknüpfte Objektlist mit einem minimalen Rechenaufwand zurück.
Es sei angemerkt, daß die Beziehung zwischen den Vokabularmodulobjekten und den Tastenanschlagsfolgen ein Detail der Implementierung des Vokabularmoduls ist. Wenn der mit der vorliegenden Eingabetastenfolge verknüpfte Knoten verarbeitet wird, können zusätzliche Kinderknoten durchlaufen werden, um Objektkandidaten zu identifizieren, die eine Tastenanschlagsfolge aufweisen, die mit der eingegebenen Tastenanschlagsfolge beginnt und die mit einer relativen Häufigkeit oberhalb eines bestimmten Schwellwerts auftreten. Dieser Schwellwert kann auf der Grundlage von Eigenschaften des vorliegenden Knotens dynamisch angepaßt werden, z. B. unter dem Gesichtspunkt, ob genug Objekte zum Auffüllen der Auswahlregion 70 auf der Anzeige erzeugt werden. Die Objekte werden identifiziert, indem der Vokabularmodulbaum entlang gültiger Pfade durchlaufen wird, bis die Objekte identifiziert sind. Derartige Objektkandidaten können zu dem Zeitpunkt identifiziert werden, zu dem die Datenbank aus der Eingabewortliste erzeugt wird, und die Knoten und die dem Fertigstellen eines Wortkandidatens entsprechenden Befehle können derart markiert werden, daß das System in der Lage ist, zu erkennen, wenn ein Durchlauf durch den Knoten dem Erzeugen eines Wortkandidaten entspricht. Die spezielle Markierung ist erforderlich, da derselbe Knoten und derselbe Befehl bei der Verarbeitung unterschiedlicher Eingabetastenfolgen durchlaufen werden kann, die nachdem die Baumstruktur mit Hilfe des unten beschrieben Kompressionsvorgangs transformiert worden ist, verschiedenen Worten entsprechen. Es sind lediglich eine ausreichende Menge an Informationen hinzuzufügen, um die Tastenfolge eines Wortkandidaten von anderen Tastenfolgen zu unterscheiden, wie beispielsweise die Tastenfolgenlänge oder spezifische Tastenwerte an bekannten Positionen in der Tastenfolge. Bei einer abgewandelten Ausführungsform werden Endknoten für Wortkandidaten auf besondere Weise derart markiert, daß sie nicht mit Knoten zusammengefaßt werden, die wie oben beschrieben für andere Worte benutzt werden. Die Begriffe klärende Software kann dann im Voraus innerhalb eines bestimmten Nachbarschaftsbereich in den absteigenden Ästen des aktuellen Knotens nach den Objektkandidaten suchen, die dann, wenn sie aufgefunden sind, in die Auswahlliste aufgenommen werden können, bevor alle den Objekten entsprechende Tastenanschläge eingegeben werden. Diese Objekte werden zusätzlich zu den Objekten, die unmittelbar mit der Eingabetastenanschlagfolge verknüpft sind, aufgeführt. Die Anzeige von mit längeren Tastenanschlagfolgen verknüpften Objekten in der Auswahlliste (nachfolgen "Vorschaumerkmal") gestattet dem Benutzer, die Objekte nach Wunsch sofort auszuwählen, ohne daß die fehlenden Tastenanschläge zur Spezifikation des Objekts ausgeführt werden müssen.
Zurück zu Fig. 3: die durch Nachschlagen der Tastenanschlagsfolge in den Vokabularmodulen aufgefundenen Objekte werden in den Blöcken 156 bis 158 priorisiert und dem Benutzer in der Auswahlliste 76 dargestellt. Um die in der Auswahlliste dargestellte Objektfolge zu bestimmen, werden Prioritäten zwischen den Vokabularmodulen und auch zwischen den zurückgegebenen Objekten jedes Vokabularmoduls eingerichtet.
Um die von den verschiedenen Vokabularmodulen identifizierten Objektlisten zu priorisieren, wird im Block 158 der Betriebsmodus des Begriffsklärungsystem für eingeschränkte Tastaturen überprüft. Wie oben erwähnt, werden im normalen Betriebszustand die Wortinterpretation in der Auswahlliste zuerst angezeigt. Der Objektliste von einem Wortvokabularmodul würde dann eine höhere Priorität als der Objektliste von einem anderen Vokabularmodul zugewiesen. Wenn das Begriffsklärungssystem umgekehrt in einem numerischen Betriebszustand ist, würde den numerischen Interpretationen eine höhere Priorität als den anderen Vokabularmodulen zugewiesen werden. Der Modus des Begriffsklärungssystem bestimmt daher die Priorität zwischen den Objektlisten der Vokabularmodule. Es ist denkbar, daß in bestimmten Betriebsmoden die Objektlisten von bestimmten Vokabularmodulen vollständig von der Auswahlliste entfernt werden.
Die von den Vokabularmodulen erzeugten Objektlisten können lediglich einen einzelnen Eintrag oder mehrfache Einträge enthalten. Im Block 160 wird deshalb die Priorität zwischen den Objekten eines einzelnen Vokabularmoduls bestimmt, wenn die Objektliste mehrfache Einträge enthält. Den Objekten, die mit einer bestimmten Tastenanschlagsfolge übereinstimmen und die in einem bestimmten Vokabularmodul nachgeschlagen werden, wird auch eine Priorität zugewiesen, die ihre relative Darstellung bezüglich der anderen Objekte bestimmt. Wie oben angemerkt, erfolgt die vorgegebene Ordnung der Darstellung vorzugsweise nach abnehmender Gebrauchshäufigkeit in einem repräsentativen hauptsächlichen Anwendungsfall. Die mit jeden Objekt verknüpften Prioritätsdaten werden daher dazu verwendet, die Objekte in der Auswahlliste zu ordnen. Da der Auswahllistenbereich 70 hinsichtlich der darstellbaren Einträge begrenzt ist, können Objekte, deren Gebrauchshäufigkeit unterhalb einer minimalen Gebrauchshäufigkeit liegt, aus einer anfänglichen Darstellung der Auswahlliste entfernt werden. Die entfernten Objekte können später der Auswahlliste hinzugefügt werden, wenn sich der Benutzer über das Ende der angezeigten Liste hinaus bewegt. Die Auswahlliste wird automatisch so verschoben, daß das jeweilige ausgewählte Objekt immer sichtbar ist. Der Benutzer kann auch dafür vorgesehene Verschiebe-Tasten (Scroll-Tasten) verwenden, um von Hand zusätzliche Objekte in das Gesichtsfeld zu bewegen, wobei in diesem Fall die aktuell ausgewählten Objekte das Gesichtsfeld verlassen. In einer abgewandelten Ausführungsform werden alle Objekte in der Auswahlliste auf Wunsch des Benutzers gleichzeitig in einer Klappliste ("Drop-Down"-Liste) angezeigt.
Viele der mit der Darstellung der in den Vokabularmodulen nachgeschlagenen Objekte verknüpften Eigenschaften sind durch den Benutzer mit Hilfe geeigneter Systemmenüs programmierbar. Beispielsweise kann der Benutzer die Ordnung von einzelnen Objekten oder Klassen von Objekten im Auswahllistenbereich spezifizieren. Der Benutzer kann auch das Prioritätsniveau einstellen, das die Priorität zwischen Vokabularmodulen und zwischen den von den Vokabularmodulen identifizierten Objekten bestimmt. Auf diese Weise kann die dem Benutzer im Auswahllistenbereich dargestellte Zahl von Einträgen auf ein Minimum beschränkt werden. Zusätzliche Einträge im Auswahllistenbereich können immer durch wiederholtes Drücken der Auswahltaste ins Blickfeld bewegt werden.
Nachdem die Prioritäten zwischen den Objekten bestimmt worden sind, wird im Block 165 eine Auswahlliste aus den identifizierten Objekten konstruiert und dem Benutzer präsentiert. Als vorgegebene Interpretation der mehrdeutigen vom Benutzer eingegebenen Tastenanschlagsfolge wird der erste Eintrag der Auswahlliste vorläufig am Einfügepunkt in der Textregion 66 eingefügt und hervorgehoben. Die Begriffe klärende Softwareroutine kehrt dann zum Block 150 zurück und wartet auf den nächsten Tastenanschlag.
Zum Entscheidungsblock 152 zurück: wenn der delektierte Tastenanschlag die Auswahltaste 60 ist, zweigt der Entscheidungsblock 152 über den "Ja"-Zweig zum Entscheidungsblock 163 ab, wo ein Test feststellt, ob die aktuelle Auswahlliste leer ist. Wenn ja, dann wird in einem Block 164, wenn das Flag OverloadSelect auf TRUE gesetzt ist, ein explizites Leerzeichen erzeugt und unmittelbar im Textbereich ausgegeben. Das Flag OverloadSelect ist ein Systemflag, das in Systemen auf TRUE gesetzt wird, die keine explizite Leerzeichentaste 64 aufweisen und in denen ein Leerzeichen bei der ersten Betätigung einer fortlaufenden Folge von Betätigungen der Auswahltaste oder, wenn die Auswahlliste leer ist, bei der Betätigung der Auswahltaste erzeugt wird. Nach dieser zu Beginn erfolgenden Verarbeitung der empfangenen Tastenanschläge, führt das System im Block 164B eine in Fig. 5B dargestellte und nachfolgend im Detail diskutierte Nachbearbeitung durch, die für die Satzzeichentaste 63 erforderlich ist. Die Ausführung kehrt dann zum Block 150 zurück. Wenn im Entscheidungsblock 163 die Auswahlliste nicht leer ist, wird der "Nein"-Zweig zum Block 174A eingeschlagen. Im Block 174A wird, wenn das Flag OverloadSelect auf TRUE gesetzt ist, ein Leerzeichen an das Ende jeder Texteinheit in der Auswahlliste und am Einfügepunkt angefügt. Im Block 174 wird der Kasten um den ersten Eintrag in der Auswahlliste (und am Einfügepunkt, wo der erste Eintrag vorläufig eingefügt wurde) in einen Kasten mit einer gestrichelten Linie geändert. In einem in Fig. 3 dargestellten Block 175 wartet das System auf die Detektion des nächsten vom Benutzer eingegebenen Tastenanschlags. Nach dem Empfang des Tastenanschlags führt das System eine in Fig. 5A dargestellte, für die Satzzeichentaste 63 erforderliche Vorverarbeitung durch, die nachfolgend im Detail diskutiert werden wird. In einem Entscheidungsblock 176 wird ein Test durchgeführt, um festzustellen, ob der nächste Tastenanschlag die Auswahltaste ist. Wenn der nächste Tastenanschlag die Auswahltaste ist, geht das System in einem Block 178 zu einem nächsten Eintrag in der Auswahlliste über und markiert diesen als aktuell ausgewählte Einheit. Nach dieser anfänglichen Verarbeitung des empfangenen Tastenanschlags führt das System im Block 178B eine in Fig. 5B dargestellte für die Satzzeichentaste 63 erforderliche Nachverarbeitung durch, die nachfolgend im Detail diskutiert werden wird. Im Block 179 wird der aktuell ausgewählte Eintrag vorläufig in der Auswahlliste und am Einfügepunkt in einem Kasten mit gestrichelten Linien um den Eintrag angezeigt. Die Routine kehrt dann zum Block 175 zurück, um den nächsten vom Benutzer eingegebenen Tastenanschlag zu delektieren. Es sei angemerkt, daß die von den Blöcken 175 bis 179 gebildete Schleife dem Benutzer ermöglicht, verschiedene Interpretationen der eingegebenen mehrdeutigen Tastenanschlagsfolge mit einer geringeren Gebrauchshäufigkeit durch mehrfaches Drücken der Auswahltaste auszuwählen.
Wenn der nächste Tastenanschlag nicht die Auswahltaste ist, geht die Routine vom Block 176 zum Block 180 über, wo der vorläufig angezeigte Eintrag als Interpretation der Tastenanschlagfolge ausgewählt und in die Formatierung für normalen Text im Textbereich umgewandelt wird. In einem Block 184 wird die alte Tastenanschlagfolge aus dem Systemspeicher gelöscht, da der Empfang eines mehrdeutigen Tastenanschlags nach der Auswahltaste dem System den Beginn einer neuen mehrdeutigen Tastenfolge anzeigt. Der neu empfangene Tastenanschlag wird dann dazu verwendet, eine neue Tastenanschlagfolge im Block 154 zu starten. Da die Wortinterpretation mit der größten Gebrauchshäufigkeit als vorgegebenene Auswahl präsentiert wird, gestattet die Hauptroutine der Begriffe klärenden Software dem Benutzer die kontinuierliche Eingabe von Text mit einer minimalen Anzahl von Fällen, in denen die zusätzliche Betätigung der Auswahltaste erforderlich ist.
Wie oben erwähnt werden im normalen Betriebszustand die Worten entsprechenden Einträge in der Auswahlliste 76 zuerst in der Liste präsentiert. Unter besonderen Umständen ist es wünschenswert, das andere Interpretationen von Tastenanschlagfolgen in der Liste zuerst präsentiert werden. In Systemen, bei denen nicht genügend Anzeigefläche vorhanden ist, um die Anzeige einer Auswahlliste im Wortsinn auf dem Anzeigeschirm zu unterstützen, wird z. B. die Menge der möglicherweise passenden Objekte aus der Datenbank intern von der Software gespeichert, und wird nur das vorgegebene Objekt oder das explizit ausgewählte Objekt (nach einem oder mehreren Betätigungen der Auswahltaste) am Einfügepunkt angezeigt.
In derartigen Systemen neigt das am Einfügepunkt angezeigte Objekt dazu, sich mit jedem zu der Eingabefolge hinzugefügten Tastenanschlag wesentlich zu verändern, da das der neuen Tastenanschlagfolge entsprechende, am häufigsten auftretende Wort nur wenig oder geringe Ähnlichkeit mit dem der vorhergehenden Eingabefolge entsprechenden häufigsten Wort aufweist. Das Ergebnis ist unter Umständen, daß das am Einfügepukt dargestellte Objekt dem Benutzer "unruhig" zu sein scheint, und die sich ständig ändernde Darstellung kann insbesondere für einen neuen oder nicht eingewöhnten Benutzer ablenkend sein. Um diese "Unruhe" am Einfügepunkt zu reduzieren, kann das System so konfiguriert werden, daß anstelle der Anzeige des häufigsten, der aktuellen Tastenfolge entsprechenden Wordobjekts ein Wort- oder Wortstammobjekt dargestellt wird, wenn dieses einem längeren Wort oder einer Vielzahl von Worten entspricht, deren Gesamthäufigkeit einen bestimmten Schwellenwert überschreitet. Das Ergebnis dieser "Stammbevorzugung" ist, daß die Änderungen an dem am Einfügepunkt dargestellten Wort häufig einfach im Anhängen eines zusätzlichen Buchstabens an das zuvor dargestellte Objekt bestehen. Beim Tippen des häufigen Worts "this" drückt der Benutzer beispielsweise auf die vier Tasten TUW, GHI, GHI und PQRS. Ohne die Stammbevorzugung wurde das System die folgende Reihe von Objekten (einer nach dem anderen) am Einfügepunkt anzeigen: "t", "vi", "ugh", "this". Wenn die Stammbevorzugung ausgeführt wird, zeigt das System "t", "th", "thi", "this" an. Das Ergebnis ist, daß ein neuer oder nicht eingewöhnter Benutzer eher darauf vertraut, daß das Begriffsklärungssystem seine Tastenanschläge korrekt interpretiert. Das Flußdiagramm in Fig. 4 zeigt wie das System das an einem bestimmten Knoten für eine bestimmte Tastenanschlagfolge anzuzeigende Objekt bestimmt.
Fig. 4 ist ein Flußdiagramm einer Routine des Softwareprogramms das eine Wortdatenbank in der Baumstruktur von Knoten erzeugt, in der jeder Knoten einer mehrdeutigen Tastenanschlagfolge entspricht. In jedem Knoten wird eine Zahl von Wortobjekten erzeugt, die den möglichen Worten oder Wortstämmen entsprechen, die von den Tastenanschlagsfolgen erzeugt werden. Im Block 190 wird ein Schwellenwert "MinFactor" gesetzt. Dieser Schwellenwert entspricht dem minimalen Faktor, um den die Gesamthäufigkeit eines Textobjekts die Häufigkeit des häufigsten Wortobjekts an einem Knoten übertreffen muß, um diesem Wortobjekt vorgezogen zu werden (d. h. um das vorgegebene Objekt zu werden, das in der Auswahlliste zuerst angezeigt wird). Die Gesamthäufigkeit eines Wortobjekts ist die Häufigkeit des Wort selbst plus die Summe der Häufigkeiten aller längeren Worte, deren Stamm das Wort ist (das heißt, von denen das Wort gleich den Anfangsbuchstaben des längeren Worts ist). Im Block 191 wird ein zweiter Schwellwert "MaxWordFreq" gesetzt, der der maximalen relativen Häufigkeit eines Worts entspricht, dem ein anderer Stamm vorgezogen wird. Im Block 192 werden alle Knoten im Baum durchlaufen und als unbearbeitet markiert. Im Block 193 stellt die Routine fest, ob alle Knoten des Baums bearbeitet worden sind. Wenn ja, dann bricht die Routine ab, anderenfalls holt das System im Block 194 den nächsten unbearbeiteten Knoten und bestimmt die Häufigkeit des häufigsten Wortobjekts (MostFreqWord), die Gesamthäufigkeit dieses Worts zusammen mit allen Worten von denen dieses Wort ein Stamm ist (MostFreqWordTot) und das Objekt, für das die Gesamthäufigkeit aller Worte, deren Stamm dieses ist, den höchsten Wert unter allen dem Knoten zugeordneten Objekten aufweist (MostFreqStemTot). Im Block 195 prüft das System, ob MostFreqStemTot den Wert MostFreqWordTot zumindest um einen Faktor MinFaktor übersteigt. Wenn nein, dann wird das mit dem Knoten verknüpfte vorgegebene Objekt unverändert gelassen und das System kehrt zum Block 198 zurück, wo der Knoten vor der Rückkehr zum Block 193 als bearbeitet gekennzeichnet wird. Wenn im Block 195 MostFreqWordTot mindestens um einen Faktor MinFactor übertroffen wird, dann prüft das System im Block 196, ob die Häufigkeit des mit dem Knoten verknüpften aktuellen vorgegebenen Objekts (MostFreqWord) den Maximalwert eines Wortes übersteigt, dem ein anderes Objekt vorgezogen werden kann (MaxWordFreq). Wenn ja, dann wird das mit dem Knoten verknüpfte vorgegebene Objekt unverändert gelassen und das System kehrt zum Block 198 zurück. Wenn nein, dann wird im Block 197 der Knoten derart modifiziert, daß vor der Rückkehr zum Block 198 das mit MostFreqStemTot verknüpfte Objekt als mit dem Knoten verknüpftes vorgegebenes Objekt bestimmt wird.
Der Test im Block 196 ist notwendig, um zu verhindern, daß sehr häufige Stämme üblichen Worten vorgezogen werden. Beispielsweise tritt der Stamm "fo" des Wortes "for" mit einer sehr hohen Häufigkeit auf, so daß bei vernünftigen Werten für MinFactor, (z. B. ein Wert von 1.5) der Test im Block 195 zufriedenstellend verläuft, selbst wenn das übliche Wort "do" auch im selben Knoten auftritt. Das Wort "do" tritt offensichtlich mit einer verhältnismäßigen hohen Häufigkeit auf, und es würde eine signifikante Verschlechterung der Effizienz des Begriffsklärungssystems bedeuten, wenn "do" nicht als vorgegebenes Objekt dieses Knoten auftreten würde.

II. Fortgeschrittene Systemmerkmale

1. Klärung von Satzzeichen

Fig. 1 zeigt eine bevorzugte Ausführungsform der vorliegenden Erfindung, bei der die linke obere Taste der Datentaste 56 (die "Satzzeichentaste") den Satzzeichen Punkt, Bindestrich und Apostroph zugeordnet ist. Diese Zeichen werden im allgemeinen in einer Anzahl von Sprachen, z. B. sowohl im Englischen als auch im Französischen, verwendet. Andere Zeichenmengen (z. B. die Zeichen Komma Bindestrich und Gedankenstrich) können der Taste zugewiesen werden und dadurch eindeutig gemacht werden, daß dieselben Prinzipien des Ansatzes wie diejenigen des Begriffsklärungsystems der vorliegend Erfindung benutzt werden. Das System verwendet den Kontext der Tastenanschläge in der Umgebung des Tastenanschlags einer Satzzeichentaste 63, um das beabsichtige Satzzeichen zu bestimmen. Das vorgegebene Verhalten der Satzzeichentaste 63 wird ferner modifiziert, um die in bestimmten Sprachen vorliegenden besonderen Fälle zu handhaben.
Die Flußdiagramme in den Fig. 5A und 5B zeigen, wie das System bestimmt, welches Zeichen bei einer bestimmten Betätigung der Satzzeichentaste zu erzeugen ist. Die unter Verwendung verschiedener, der Satzzeichentaste 63 zugeordneter Satzzeichen erzeugten Textobjekte werden der Auswahlliste hinzugefügt. Die vorgegebene Interpretation der Betätigung der Satzzeichentaste 63 wird durch die Auswahl des ersten Objekts in der Auswahlliste bestimmt. Andere Interpretationen können durch Betätigen der Auswahltaste ausgewählt werden oder indem die gewünschte Interpretation in der angezeigten Auswahlliste angetippt wird. Fig. 5A zeigt die Routine, die jeden vom System empfangenen Tastenanschlag vor der in Fig. 3 gezeigten normalen Systemverarbeitung verarbeitet, bei der das System den Tastenanschlag der aktuellen eingegeben Tastenanschlagfolge hinzufügt, die der neuen Eingabefolge entsprechenden Worte bestimmt und auf der Grundlage der neuen Folge eine aktualisierte Auswahlliste erzeugt. Die in Fig. 5A dargestellte Verarbeitung erfolgt in Blöcken 150A und 175A in Fig. 3. Fig. 5B zeigt die Routine, die dann die neu erzeugten Auswahllisten nachbearbeitet. Die in Fig. 5B dargestellte Verarbeitung erfolgt in den Blöcken 164B und 178B in Fig. 3. Es wird vorausgesetzt, daß alle Flags zur Zeit der Initialisierung des Systems zurückgesetzt worden sind.
Beim Start der Vorverarbeitung wird im Block 200 in Fig. 5A das Flag ClearPunctMode überprüft. Das Flag ClearPunctMode wird (im Block 262) gesetzt, um anzuzeigen, daß alle im Zusammenhang mit der Satzzeichentaste stehenden Flags und Puffer beim Beginn der Verarbeitung des nächsten Tastenanschlags zurückgesetzt werden sollen. Wenn im Block 200 herausgefunden wird, daß das Flag gesetzt ist, dann werden im Block 202 alle Flags und Puffer, die ausschließlich zu Verarbeitung der Satzzeichentaste 63 verwendet werden, gelöscht. Diese Flags und Puffer werden auch zum Zeitpunkt der Initialisierung des Systems gelöscht. Der Puffer curPunctWord wird dazu verwendet, diejenigen Textobjekte zu speichern, an die die Software für die Satzzeichentaste Satzzeichen anhängt, um Objekte zu erzeugen, die der Auswahlliste hinzugefügt werden. Das Flag pState speichert den aktuellen Status der Software für die Satzzeichentaste und unterscheidet zwischen verschiedenen möglichen Kontextfällen, in denen die Satzzeichentaste 63 betätigt wurde. Wenn im Block 204 die aktuelle vorverarbeitete Taste die Satzzeichentase 63 ist, dann wird im Block 206 das aktuelle vorgegebene (oder explizit ausgewählte) Objekt in den Puffer curPunctWord gespeichert und im Block 208 wird das Flag pState auf PUNCT_KEY gesetzt, was anzeigt, daß die Satzzeichentaste 63 die letzte empfangene Taste war. Der Block 212 stellt die normale Verarbeitung des Tastenanschlags dar, die wie in Fig. 3 dargestellt an Blöcken 151 oder 176 beginnt. Die Ausführung wird dann mit der in Fig. 5B dargestellten Nachverarbeitung fortgesetzt, die vom Übergang D ausgeht.
Wenn im Block 204 die aktuellen Taste nicht die Satzzeichentaste ist, dann wird im Block 220 das Flag pState nicht gesetzt, und im Block 222 werden alle ausschließlich für die Satzzeichentaste verwendeten Flags und Puffer gelöscht, und die normale Verarbeitung der Tastenanschläge wird im Block 212 fortgesetzt. Wenn im Block 220 das Falg pState auf einen Wert verschieden von Null gesetzt wird, dann prüft das System im Block 230, ob die aktuelle Taste eine der mehrdeutigen Datentasten 56 ist, und geht dann zum Block 232 über und testet, ob das System-Flag Apostrophe_S gesetzt ist. Das Flag Apostrophe_S wird nur bei Sprachen wie dem Englischen auf TRUE gesetzt, wo es üblich ist, einen von dem Buchstaben "s" gefolgten Apostroph an das Ende eines Worts anzuhängen (um eine Besitzanzeige oder eine Kontraktion mit dem Wort "is" zu bilden). Wenn das Flag Apostrophe_S auf TRUE gesetzt ist und wenn sich im Block 234 ergibt, daß das Flag pState auf PUNCT_KEY gesetzt ist (was zeigt, daß die vorhergehende Tastenbetätigung die Satzzeichentaste war) und wenn sich im Block 236 ergibt, daß die aktuelle Taste die mit dem Buchstaben "s" verknüpfte Datentaste ist (die Taste PQRS in Fig. 1), dann wird im Block 238 das Flag pState auf APOS_S gesetzt, was anzeigt, daß die Satzzeichentaste 63 empfangen wurde und das der Spezialfall eines von einem "s" gefolgten Apostrophs erkannt worden ist. Wenn einer der beiden Tests (Block 234 oder Block 236) fehlschlägt, dann wird im Block 237 das Flag pState auf PUNCT_RCVD gesetzt, was anzeigt, daß die Satzzeichentaste 63 empfangen wurde und daß die Verarbeitung der Satzzeichentaste ausgeführt werden soll, aber daß im Augenblick kein Spezialfall vorliegt (wie z. B. die Erkennung des von einem "s" gefolgten Apostrophs). Nachdem das Flag pState gesetzt ist, wird die Verarbeitung der Tatenanschläge in beiden Fällen am Block 212 fortgesetzt.
Wenn im Block 230 festgestellt wird, daß die aktuelle Taste keine mehrdeutige Datentaste ist, dann prüft das System im Block 250, ob die aktuelle Taste die Rücktaste ist. Wenn ja, dann werden alle die Satzzeichentaste betreffende Flags und Puffer in den Zustand vor dem gelöschten Tastenanschlag gebracht und danach wird die normale Verarbeitung des Tastenanschlags (der Rücktaste über den Übergang C) im Block 212 fortgesetzt. Wenn sich im Block 250 ergibt, daß die aktuelle Taste nicht die Rücktaste ist, dann wird im Block 260 ein Test ausgeführt, um festzustellen, ob die aktuelle Taste eine Taste MODE, die Auswahltaste oder die Umschalttaste ist (d. h. eine Taste, die nicht dazu führt, daß das aktuelle Wort "akzeptiert" und in den Textpuffer ausgegeben wird). Wenn ja, dann wird die normale Verarbeitung des Tastenanschlags (über den Übergang C) im Block 212 fortgesetzt. Im anderen Fall wird im Block 260 festgestellt, daß die Taste die Annahme des aktuellen Worts veranlaßt und im Block 262 wird das Flag pState gelöscht und das Flag ClearPunctMode wird gesetzt, so daß alle die Satzzeichentaste betreffende Flags und Puffer beim Empfang des nächsten Tastenanschlags im Block 212 gelöscht werden.
Wenn im Block 232 festgestellt wird das das Flag Apostrophe_S nicht gesetzt ist, dann stellt das System im Block 270 fest, ob das Flag Apostroph_Term gesetzt ist, und in dem Block 272, ob das Flag pState auf PUNCT_APOS gesetzt ist, was anzeigt, daß die Satzzeichentaste 63 empfangen wurde und das der Spezialfall erkannt wurde, bei dem ein mit einem Apostroph endendes Wort einer Auswahlliste hinzugefügt wird. Das Flag Apostroph_Term wird für Sprachen wie beispielsweise Französisch auf TRUE gesetzt, wo es üblich ist, verschiedene mit einem Apostroph endende Worte, (z. B. I', d' usw.) mit einem nachfolgenden Wort zu verknüpfen, ohne ein Leerzeichen zwischen den zwei Worten zu tippen. In derartigen Sprachen ist es sehr bequem, wenn das System automatisch ein implizites "Auswählen" erzeugt, damit der Benutzer sofort mit dem Tippen des folgenden Worts beginnen kann, ohne das explizit die Auswahltaste betätigen muß. Wenn die Tests sowohl im Block 270 und 272 positiv verlaufen, wird das aktuelle vorgegebene oder ausgewählte Wort akzeptiert und zum Textpuffer ausgegeben, als ob die Auswahltaste betätigt worden wäre. Daraufhin wird im Block 276 die aktuelle Tastenanschlagliste gelöscht und die Verarbeitung geht zum Block 262 über, wo das Flag pState gelöscht und das Plag CearPunctMode gesetzt wird. Wenn andererseits im Block 270 das System feststellt, daß das Flag Apostrophe Term nicht gesetzt ist oder im Block 272 feststellt, daß das Flag pState nicht auf PUNCT_APOS gesetzt ist, dann wird im Block 278 das Flag pState auf PUNCT_RCVD gesetzt und die normale Verarbeitung des Tastenanschlags wird (über den Übergang C) im Block 212 fortgesetzt.
Nach der normalen Verarbeitung eines Tastenanschlags, die durch Block 212 in Fig. 5A (und im Detail in Fig. 3) dargestellt ist, wird ausgehend vom Übergang D die in Fig. 5B dargestellte Nachbearbeitung ausgeführt. Im Block 300 ist, wenn das Flag pState nicht gesetzt ist, keine Nachbearbeitung erforderlich und die Subroutine endet einfach im Block 320. Die Blöcke 302, 304 und 306 überprüfen, ob das Flag pState auf PUNCT_KEY gesetzt ist und ob das aktuelle vorgegebene Wort mit einem Apostroph endet. Wenn alle drei Bedingungen erfüllt sind, wird im Block 308 das Flag pState auf PUNCT_APOS gesetzt; anderenfalls geht das System auf Block 310 über, ohne einen neuen Wert für pState zu setzten. Wenn im Block 310 das Flag pState auf PUNCT_APOS oder PUNCT_KEY gesetzt ist, dann wird in den Blöcken 312, 314 und 360 das im Puffer curPunctWord gespeicherte Textobjekt nach Hinzufügen jeweils eines Punkts, eines Gedankenstrichs oder eines Apostrophs der Auswahlliste hinzugefügt. Wenn der Test im Block 310 fehlschlägt und wenn im Block 330 festgestellt wird, daß das Flag pState auf APOS_S gesetzt ist, dann wird das im Puffer curPunctWord gespeicherte Textobjekt nach Hinzufügen eines Apostrophs und eines "s" der Auswahlliste hinzugefügt. Daraufhin wird in den Blöcken 334, 336, 338 und 340 das im Puffer curPunctWord gespeicherte Wort nach Anhängen eines Bindestrichs, dem jeweils ein der Taste PQRS zugeordneter Buchstabe folgt, der Auswahlliste hinzugefügt. Das Flag pState wird dann auf PUNCT_RCVD im Block 342 gesetzt.
Wenn im Block 343 das Flag pState nicht auf APOS_S gesetzt ist, dann überprüft das System im Block 352, ob die aktuelle Auswahlliste leer ist. Wenn nein, dann wurden ein oder mehrere Objekte in der Datenbank aufgefunden, die mit der aktuellen Tastenfolge im Tastenanschlagspuffer explizit übereinstimmen (was zumindest eine Betätigung der Satzzeichentaste einschließt). In diesem Fall kehrt die Subroutine einfach zum Block 364 zurück, ohne den Inhalt des Tastenanschlagspuffer zu verändern, so daß die Objekte aus der Datenbank buchstabiert werden können, wenn das die Absicht des Benutzers ist. Anderenfalls wird, sobald keine weiteren übereinstimmenden Objekte in der Datenbank vorhanden sind, im Block 356 das im Puffer curPunctWord gespeicherte Textobjekt nach Anhängen eines Bindestrichs als akzeptierter Text ausgegeben. Im Block 358 werden alle Tastenanschläge vom Beginn des Tastenanschlagspuffer bis einschließlich dem Tastenanschlag der Satzzeichentaste gelöscht. Daraufhin wird dem Block 360 die Datenbank abgefragt und eine aktualisierte Auswahlliste wird auf der Grundlage des modifizierten Tastenanschlagspuffer erzeugt. Schließlich werden im Block 362 alle Flags und Puffer für die Satzzeichentaste vor dem Ende der Subroutine gelöscht.

2. Maximierung der Leistung und gleichzeitiges Minimieren des Speicherbedarfs des Vokabularmoduls

Der Kombination der Tastenanschläge mit dem Softwareprozeß der Objektidentifikation der in Fig. 13 dargestellten Subroutine 620, die mit der in Fig. 10 dargestellten Baumdatenstruktur 110 arbeitet, sind einige neue Mittel inhärent, um ein größeres Objektvokabular unter gleichzeitigem geringerem Speicherbedarf für das Vokabularmodul abzurufen, ohne die Verarbeitungszeit der Subroutine 620 zu vergrößern.
Dadurch, daß die Symbole in jeder Reihe der logischen Symbolindextabelle 550 eines Vokabularmoduls gemäß ihrer Gebrauchshäufigkeit im Eingabelexikon angeordnet werden, können in der Mehrzahl der Befehle 558 aller Knoten 400 in der Baumstruktur 110 die Felder LOGICAL-SYMBOL-INDEX 555 gleich 1 gesetzt werden. Auf gleiche Weise können in einer Mehrzahl der Befehle 558 aller Knoten 400 in der Baumstruktur 110 die Felder OBJECT-LIST-INDEX 556 gleich 1 gesetzt werden, indem die Befehle 558 aller Pakete wie z. B. 406 in einem Knoten 400 so angeordnet werden, daß die Stamm- und Wortobjekte in der Objektliste 440 in absteigender Ordnung gemäß ihren Gebrauch in der Sprache erzeugt werden. Demnach sind viele Daten im Baum 110 redundant. Das systematische Identifizieren der Redundanzen und deren Elimination durch Neuausrichten der die Elternknoten mit den Kinderknoten verbindenden Pfaden und durch Löschen von Kinderknoten, auf die keine Verweise bestehen, führt zu einer in hohem Maßen gefalteten oder gewickelten Datenstruktur, die weit weniger Knoten, Befehle und Verbindungen als der ursprüngliche Baum enthält, aus der jedoch alle Objekte abgerufen werden können, die auch aus dem ursprünglichen Baum abrufbar sind. Außerdem werden verschiedene Fälle von Pfaden durch den ursprünglichen Baum, deren Befehle ähnliche Objekte in der Objektliste 440 erzeugen, im gefalteten Baum zu gemeinsamen Pfaden zusammengefaßt, die infolgedessen als generalisierte (im Gegensatz zu spezifischen) Regeln zur Konstruktion von Objekten funktionieren, was der reduzierten Struktur gestattet, weit mehr Objekte zu erzeugen, als ursprünglich zur Bildung des Baums 110 eines bestimmten Vokabularmoduls verwendet wurden. Ein ungefalteter Vokabularbaum, der aus einer Liste von 30.000 englischen Worten gebildet worden ist, kann beispielsweise über 78.000 Befehle in einer bevorzugten Ausführungsform enthalten. Nach dem Falten durch eine bevorzugte Ausführungsform des Faltprozesses kann der modifizierte Baum weniger als 29.000 Befehle enthalten, was eine kleinere Zahl als die Zahl der Wortobjekte ist, die die Struktur auf der Grundlage der mehrdeutigen Tastenanschlagsfolgen und des in dem Flußdiagramm in Fig. 12 dargestellten bevorzugten Abrufvorgangs abrufen kann. Dies ist ein bemerkenswertes und neues Ergebnis, da jeder Befehl als Antwort auf das Drücken einer Taste ein Objekt in der Objektliste 430 nur durch Anhängen eines einzelnen Symbols ändert. Dies ist eine Folge des gefalteten Baums und des Softwareabrufvorgangs, der wiederholt allgemeine Befehlsfolgen als allgemeine Regeln zur Konstruktion von Objekten benutzt.
Die in Fig. 9 dargestellten Knoten sind Beispiele. Der Knoten 560 verfügt über zwei gültige Tasten, was durch die "1" in dem Feld 572 für gültige Tasten mit dem Wert "010100000" angezeigt wird. In einer bevorzugten Ausführungsform zeigen die Positionen der "1" an, daß die zweite und vierte Taste gültige Pfade sind und über Pakete 566 und 568 von mit Kinderknoten verknüpften Befehlen und Zeigern verfügen. Das Paket 566 enthält drei Befehle "(1, 1, 0)","(1, 2, 0)" und "(2, 1, 1)", denen ein Pointer "P" folgt, der das Paket 560 mit dem Kinderknoten verbindet.
Wenn die Subroutine 600 eine Liste von Tastenanschlägen verarbeitet hat, die zum Knoten 560 führen, dann wird die Subroutine 620 aufgerufen um die Taste "2" zu verarbeiten, die in einer bevorzugten Ausführungsform die Taste ABC ist, und dann läuft Folgendes ab: Der Befehl 561 hängt das erste logische Symbol der Taste ABC (ein "a") an das alte Objekt mit dem Index "1" an, um das neue Objekt mit dem Index "1" zu erzeugen. Das dritte Feld von 561, "0", ist der Wert FALSE des STOP-FLAGS 557, was anzeigt, daß dies nicht der letzte Befehl des aktuellen Pakets ist, so daß der nächste Befehl 563 interpretiert wird. Der Befehl 563 hängt dann das erste logische Symbol der Taste ABC (ein "a") an das alte Objekt mit Index "2" an, um das neue Objekt mit Index "2" zu erstellen. Der Index des neuen Objekts ist "2", da die Indices der neu erstellten Objekte implizit der Reihenfolge der Befehle folgen; der zweite Befehl erstellt z. B. immer das zweite Objekt. Das dritte Feld des Befehls 563, "0", ist der Wert FALSE des STOP-FLAGS 557, so daß der nächste Befehl 567 interpretiert wird. Der Befehl 567 hängt dann das zweite logische Symbol der Taste ABC (ein "c") an das alte Objekt mit Index "1" an, um ein neues Objekt mit Index "3" zu erstellen. Das dritte Feld des Befehls 567, "1", ist der Wert TRUE des STOP-FLAGS 557, was anzeigt, daß dies der letzte Befehl des aktuellen Pakets ist, so daß die Ausführung der Subroutine 620 vom Block 638 auf den Block 644 übergeht.
Es ist möglich, ein oder mehrere Knoten mit verschiedenen Befehlspaketen 408 in einen einzelnen Knoten zusammenzufassen, der die gleiche Funktion wie die einzelnen getrennten Knoten aufweist, was bedeutet, daß bestimmte Knoten im Vokabularbaum 110 in einem neuartigen Sinn redundant sind. Im Rahmen dieser Erfindung wird das Wort "redundant" bezüglich zweier Knoten in dem Sinn gebraucht, daß einer der Knoten entfernt werden kann, indem der in einer bevorzugten Ausführungsform in den Fig. 14 bis 17 dargestellte Softwareprozeß ausgeführt wird.
Man vergleiche z. B. in Fig. 9 Knoten 560 mit Knoten 574. Die Befehlspakete 566 und 571 auf der Taste "2" stimmen exakt überein, aber der Befehl 570 auf der Taste "4" des Knotens 560 steht im Widerspruch mit dem Befehl 572 auf Taste "4" des Knoten 574, so daß keiner die Funktion des anderen übernehmen kann und die zwei Knoten nicht zu einem einzigen kombiniert werden können, der die Funktion von beiden hat. Man vergleiche nun den Knoten 560 mit dem Knoten 576. Die Befehlspakete 566 und 567, die mit der Taste Ziffer "2" in jeden Knoten verknüpft sind, stimmen exakt überein. Die Befehle 569 und 578 unterscheiden sich hinsichtlich der im Feld STOP-FLAG 557 gesetzten Werte, aber dieser Unterschied führt zu keinem Konflikt. Das wesentliche Ergebnis des Objektabrufvorgangs der Subroutine 620 in Fig. 14 ist die durch Ausführen der Befehlsmenge an einem bestimmten Knoten für eine bestimmte Taste erstellte neue Objektliste. Zusätzliche Objekte können an das Ende einer Objektliste angefügt werden, ohne das die korrekte Verarbeitung eines Kinderknotens leidet. Demnach werden keine Fehler gemacht, wenn bei der Bearbeitung des Kinderknotens 576 ein zusätzlicher Befehl nach 578 ausgeführt wird. Die wesentliche Funktion des Vorgangs würde nur dann gestört werden, wenn der falsche Befehl ausgeführt würde oder wenn zuwenig Befehle ausgeführt würden. In gleicher Weise führt das Vorhandensein einer gültigen Taste bei Taste "9" von Knoten 576 nicht zu einem Konflikt mit dem Vorhandensein mit einer gültigen Taste "9" in Knoten 560. Infolgedessen sind die Knoten 560 und 576 redundant und können in einen neuen Knoten 582 zusammengefaßt werden, der die gleiche Wirkung wir die beiden erzielt und als Elternknoten beider Kinder korrekt funktioniert. Es sei angemerkt, daß die Zeiger auch eine Rolle beim Bilden von Redundanz spielen. Beim letzten Tastenanschlag von Folgen im Baum, die mit Worten verknüpft sind, die nicht der Stamm von längeren Worten sind, weisen die Zeiger in den Paketen 408 für die gültigen Tasten in einer bevorzugten Ausführungsform einen speziellen Wert, nämlich NULL, auf, um anzuzeigen, daß keine weiteren Kinder vorhanden sind. Derartige Knoten werden "Endknoten" genannt. Für zwei Knoten mit Kinderknoten an beiden gemeinsamen gültigen Tasten müssen die jeweiligen Kinderknoten redundant sein, damit die Elternknoten redundant sind, und so weiter für die von den Kindern absteigenden Knoten, bis die Endknoten erreicht sind oder bis es keine weiteren absteigenden Äste für gültige Tastenfolgen gibt, die den zu vergleichenden Knoten gemeinsam sind.
Die Fig. 14 bis 17 zeigen Flußdiagramme bevorzugter Ausführungsformen von Softwareprozessen für die Kompression und das Falten eines zu dem in Fig. 10 gezeigten Baum 110 ähnlichen Baumes. Fig. 14 ist ein Flußdiagramm einer bevorzugten Ausführungsform eines Softwareprozesses, um ein komprimiertes Vokabularmodul zu erstellen. Im Block 652 wird ein Lexikon gescannt, um alle erforderlichen zusätzlichen mehrdeutigen Symbole, wie die in Fig. 6 für ein französisches Vokabularmodul dargestellten Symbole, neben den auf den physischen Tasten erscheinenden Symbolen zu identifizieren. In den Blöcken 654 bis 656 werden den Symbolen ihre logischen Indizes auf den jeweiligen Tasten gemäß einer absteigenden Ordnung der Gebrauchshäufigkeit im Eingabelexikon, wie in dem in Fig. 7 dargestellten Beispiel, zugewiesen. Wenn ein Lexikon von Objekten mit Häufigkeiten vorhanden ist, ist es für den Fachmann offensichtlich, wie der Block 658 ein Vokabularbaum in der Form 110 erstellt. Im Block 660 werden redundante Knoten identifiziert und zusammengefasst, um das Duplizieren von Daten zu minimieren und mit einzelnen Objekten verknüpfte, isolierte Befehlsfolgen werden in generalisierte Regeln umgewandelt, um mehrfache Objekte abzurufen. Dieser Prozeß ist in Fig. 15 im einzelnen dargestellt. Der Block 662 identifiziert alle verbleibenden NULL-Zeiger der Endknoten und ändert sie derart, daß sie zu den Knoten mit der größten Elternzahl zeigen, wodurch die Zahl der Regeln im Modul vergrößert wird. Es sei angemerkt, daß auch andere Regeln angewendet werden können, um den NULL-Zeigern Kinderknoten zuzuweisen und das diese Regeln dynamisch auf der Grundlage der mit den verarbeitenden Tastenanschlägen verknüpften Faktoren zum Abrufzeitpunkt der Objekte angewendet werden können. Im Block 664 werden die verbleibenden Fälle jedes einmaligen Befehls 558 und jedes einmaligen Zeigers 404a gezählt, so daß sie als einmalige Bitmuster enkodiert werden können, wobei kürzere Bitmuster den häufigeren Befehlen und Adressen zugewiesen werden, um Speicherplatz zu sparen. Bei einer bevorzugten Ausführungsform der vorliegenden Erfindung wird eine Huffmankodierung verwendet, um Bitmuster minimaler Länge den Befehlen und Adressen zuzuweisen. Es sei angemerkt, daß die Technik der Huffmankodierung als solche dem Fachmann bekannt ist und daher nicht im einzelnen diskutiert zu werden braucht. Darüber hinaus können Kinderknoten von mehrfachen Elternknoten in speziellen Ordnungen gespeichert werden, um ihre schnelle Beschaffung zu ermöglichen und um die zu ihrer Adressierung erforderliche Zahl von Bits zu minimieren. Schließlich werden die wie oben beschrieben erzeugten Daten im Block 666 in eine Datei geschrieben.
Im Zusammenhang mit der Auswahl von Befehlen, die dazu dienen, Objekte zu beschreiben, die während des Erstellens des Baums im Block 658 abgespeichert werden sollen, sei angemerkt, daß die Zeichenfolge, wenn die Objekte Wörter oder Wortstämme sind, zusätzliche Daten enthalten können, die vorteilhafterweise dazu verwendet werden können, die Redundanz in den Knoten des Baums 110 zu vergrößern. Nicht alle Buchstabenpaare in der englischen Sprache sind z. B. gleich häufig; z. B. ist "s" häufig mit "t" gepaart. Die Statistik der Buchstabenpaare oder Bigramme kann dazu verwendet werden, ausgehend von einem vorhergehenden Buchstaben, den wahrscheinlichsten nächsten Buchstaben vorherzusagen. Mit solchen Vorhersagen kann die logische Ordnung der mehrdeutigen Symbole in der logischen Symbolindextabelle 550 dynamisch geändert werden, um die Verwendung der ersten Position zu optimieren. Die Vorhersagen können zu Buchstabentripletts, Trigrammen und allgemein zu n- Grammen erweitert werden.
Fig. 15 ist ein Flußdiagramm einer bevorzugten Ausführungsform eines Softwarevorgangs, um den Baum 110 eines Vokabularmoduls zu falten. Block 670 ist vom Block 660 in dem Flußdiagramm der Fig. 14 aus zugänglich. Der Block 672 initialisiert den Prozeß derart, daß dieser mit dem ersten Knoten des Baum 110 aus Fig. 10 nach dem Wurzel-Knoten 111 beginnt. Der Block 674 ruft die Subroutine 690 auf, die in einer bevorzugten Ausführungsform im Flußdiagramm der Fig. 16 dargestellt ist, um einen Knoten, wenn vorhanden, zu finden, der bezüglich dem aktuellen Knoten maximal redundant ist. Wenn ein Zielknoten gefunden wurde, lenkt der Entscheidungblock 676 den Prozeß zum Block 678, wo der redundante (die redundanten) Knoten zusammengefaßt werden, um Datenduplikate aus dem Baum zu entfernen, indem mehrfache, individuelle Exemplare von Befehlen in gemeinsame Folgen zusammengefaßt werden, die allgemeine Regeln für die Zuordnung von Tastenanschlagsfolgen zu Objekten darstellen. Wenn der Entscheidungsblock 676 fehlschlägt, überprüft der Entscheidungsblock 680, ob der Prozeß abgeschlossen ist. Wenn es noch mehr Knoten zum Verarbeiten gibt, geht der Fluß zum Block 682 über, um einen weiteren Knoten zu identifizieren.
Fig. 16 ist ein Flußdiagramm einer bevorzugten Ausführungsform eines Softwarevorgangs, um in einem Baum 110 einen Knoten mit dem höchsten Grad an Redundanz bezüglich einem bestimmten Knoten zu finden. Der Block 690 ist vom Block 674 des Flußdiagramms der Fig. 15 aus zugänglich. Der Block 692 initialisiert einen Platzhalter MAX-SAVINGS für die gemessene Redundanz. Der Block 694 initialisiert den Prozeß derart, das dieser am Wurzel-Knoten 111 des Baums 110 aus Fig. 10 startet. Der Block 696 ruft die Subroutine 710 auf, die in dem Flußdiagramm einer bevorzugten Ausführungsform in Fig. 17 dargestellt ist, um die Redundanz eines bestimmten Knotens bezüglich eines aktuellen Knotens zu berechnen. Der Entscheidungsblock 698 überprüft, ob ein Redundanz größer als MAX-SAFINGS gemeldet wird. Wenn ja, dann merkt sich der Block 700 die Identität BEST-NODE des Knotens, der vorübergehend bezüglich des bestimmten Knotens als der am meisten redundante Knoten aufgefunden wurde, und merkt sich das gemeldete Redundanzmaß als MAX-SAFINGS. Der Entscheidungsblock 702 überprüft, ob alle Knoten bewertet worden sind. Wenn nein, dann wird die Verarbeitung mit Block 704 fortgesetzt, der vom aktuellen Knoten zum nächsten Knoten übergeht. Vom Block 704 kehrt der Fluß zum Block 696 zurück. Wenn das Ergebnis des Tests am Entscheidungsblock 702 lautet, daß der letzte Knoten bewertet worden ist, dann gibt Block 706 die Identität des am meisten redundanten Knoten, wenn vorhanden, bezüglich eines bestimmten Knotens dem Block 674 der Subroutine 670 aus Fig. 15 zurück.
Fig. 17 ist ein Flußdiagramm einer bevorzugten Ausführungsform eines Softwarevorgangs, um die numerische Redundanz zwischen zwei spezifischen Knoten zu berechnen. Der Block 710 ist vom Block 696 des Flußdiagramms der Subroutine 690 in Fig. 16 aus zugänglich. Der Block 712 initialisiert einen Zähler für Befehlsduplikate. Block 714 initialisiert KEY-INDEX mit dem Wert 1. Der Block 716 liest die mit dem KEY-INDEX verknüpften Befehlspakte 406 aus den ersten beiden als Parameter für die Subroutine spezifizierten Knoten 400 aus und legt sie in einer temporären Liste, LIST-A, ab. Wenn die Taste KEY-INDEX keine gültige Taste ist, werden keine Befehle ausgelesen. Der Block 718 liest die mit der Taste KEY-INDEX verknüpften Befehlspakete 406 aus dem zweiten der beiden als Parameter für die Subroutine spezifizierten Knoten 400 aus und legt sie in der temporären Liste LIST-B ab. Wenn die Taste KEY-INDEX keine gültige Taste ist, werden keine Befehle ausgelesen. Der Entscheidungsblock 720 bestimmt, ob entweder die Liste LIST-A oder die Liste LIST-B leer ist. Wenn nein, dann holt Block 722 einen sowohl in der Liste LIST-A als auch in der Liste LIST-B enthaltenen Befehl und reduziert nacheinander die Zahl der verbleibenden Befehle. Der Entscheidungsblock 724 überprüft, ob die Befehle hinsichtlich der Felder LOGICAL-SYMBOL-INDEX und OBJECT-LIST-INDEX die gleichen sind. Wenn nein, dann wird ein Fehlercode für keine Redundanz in einem Block 726 zum Block 666 der Subroutine 96 zurückgegeben. Wenn die Entscheidung des Blocks 724 ja lautet, dann inkrementiert der Block 728 den Zähler SAVED- INSTRUCTIONS. Damit geht die Kontrolle wieder an den Block 720 über. Wenn der Entscheidungsblock 720 auf TRUE prüft, dann geht die Kontrolle auf den Entscheidungsblock 730 über, der überprüft, ob die beiden Knoten bezüglich aller möglichen Tasten überprüft worden sind. Wenn nein, dann inkrementiert der Block 732 KEY-INDEX und die Kontrolle geht auf den Block 716 über. Wenn die Entscheidung am Block 730 positiv ist, geht die Kontrolle auf den Block 734 über, um KEY-INDEX auf 1 zurückzusetzen. Der Block 736 überprüft die mit der Taste KEY-INDEX der beiden Knoten verknüpften Zeiger. Der Entscheidungsblock 738 überprüft, ob einer der beiden Zeiger leer (NULL) ist, was für einen Zeiger in einem Endknoten oder bei einer ungültigen Taste der Fall sein würde. Wenn keiner der beiden Zeiger leer ist, geht die Kontrolle zum Block 740 über, der die Subroutine 710 rekursive nutzt, um zu überprüfen, ob die Kinderknoten, auf die die beiden nichtleeren Zeiger verweisen, redundant sind. Das Ergebnis des Blocks 740 wird im Entscheidungsblock 742 überprüft. Wenn das Ergebnis ist, daß die beiden Kinderknoten nicht redundant sind, dann wird ein Fehlerkode in einem Block 744 zurückgegeben. Im anderen Fall wird festgestellt, daß die beiden Kinder mit einem gewissen numerischen Wert redundant sind, der vom Block 746 akkumuliert wird. Der Entscheidungsblock 748 prüft, ob die mit der letzten Taste verknüpften Zeiger (Taste 9 in der bevorzugten Ausführungsform) überprüft worden sind. Wenn nein, dann inkrementiert der Block 752 KEY-INDEX und übergibt die Kontrolle an Block 736. Wenn der Test am Block 748 ergibt, daß alle Zeiger überprüft worden sind, dann wird ein akkumuliertes numerisches Maß für die Redundanz der beiden Knoten zurückgegeben, die ursprünglich beim Aufrufen der Subroutine im Block 710 identifiziert worden sind.
Es sei angemerkt, daß die Berechnung der numerischen Redundanzwerte gewichtet werden kann, um zusätzliche Faktoren wie z. B. die Zahl der an jeden Knoten vorhandenen Zweige und die Zahl von Eltern, die zu einem Kinderknoten zeigen, zu berücksichtigen. Ferner sei angemerkt, daß wenn zwei Knoten aufgrund der Anordnung von mit einer bestimmten Taste verknüpften Befehlen nicht redundant sind, daß dann die Ordnung der mit weniger häufigen Worten in dem Eingabelexikon verknüpften Befehlen erneut geordnet werden kann, ohne die mit häufigeren Objekten verknüpfte Priorität von Befehlen zu beeinflussen, wodurch die Redundanz des Baums erhöht wird.

3. Repräsentativer Systembetrieb

Die Fig. 18A bis 18K zeigen die Anzeige 53 des tragbaren Computers 52 während eines repräsentativen Gebrauchs des Begriffserklärungsystems für eingeschränkte Tastaturen. Nach dem Einschalten des tragbaren Computers sind der Textbereich 66 und der Auswahllistenbereich 70 leer. In Fig. 18A hat der Benutzer den Satz "This is a test" eingegeben. Das Vokabularmodul hat die wahrscheinlichste Interpretation der Folge der letzten vier Tastenanschläge TU V, DEF, PQRS, TUV als das Wort "Test" identifiziert und hat diese Interpretation vorläufig am Einfügepunkt 900 eingefügt und auch dieses Wort als vorgegebene Interpretation 901 als erstes in der Auswahlliste angeordnet. Dieser erste Eintrag in der Auswahlliste wurde mit einem Kasten mit durchgezogenen Linien umgeben (was anzeigt, daß dies das implizit ausgewählte Objekt ist) und dieses Objekt wurde auch vorläufig im Textbereich am Einfügepunkt 900 eingefügt und mit einem Kasten mit durchgezogenen Linien umgeben. Das Vokabularmodul hat ferner die Wortinterpretation "vest" und die Stamminterpretation "vert" identifiziert und diese Interpretationen in der Auswahlliste angeordnet. Die in den Fig. 5A und 5B gezeigte Verarbeitungssoftware für die Satzzeichentaste hat die Textobjekte "test" im Puffer curPunctword abgespeichert.
In Fig. 18B hat der Benutzer im folgenden die Satzzeichentaste . - ' gedrückt. Kein Objekt in der Datenbank stimmt mit der Tastenanschlagsfolge der vier Tasten TUV, DEF, PQRS, TUV einschließlich der nachfolgenden Satzzeichentaste 63 überein. Infolgedessen sind die einzigen in der Auswahlliste erscheinenden Textobjekte diejenigen, die von der Verarbeitungssoftware für die Satzzeichentaste hinzugefügt worden sind, nämlich aus curPunctWord "test" mit einem angehängten Punkt 911, Bindestrich 913 und Apostroph 914. Das sich ergebende vorgegebene Objekt der Auswahlliste ist "test." 911, das auch vorübergehend in dem Textbereich am Einfügepunkt 910 eingefügt wird.
In Fig. 18C hat der Benutzer im folgenden die Leerzeichentaste 922 gedrückt. Dadurch wurde ein explizites Leerzeichen erzeugt, das die aktuelle Tastenanschlagsfolge beendet hat und das System veranlaßt, den vorläufig eingefügten Test "test." zu akzeptieren. Außerdem wurde ein nachfolgendes Leerzeichen ausgegeben, nach dem der Systemcursor 920 erscheint. Der Tastenanschlagspuffer ist nun leer und infolgedessen ist auch die aktuelle Auswahlliste 921 leer. Dies liefert ein Beispiel für das vorgegebene Verhalten der Satzzeichentaste 63 - wenn diese vor dem Betätigen der Leerzeichen - (oder Auswahl-)Taste betätigt wird, wird das vorhergehende vorgegebene Textobjekt mit einem angehängten Punkt ausgegeben, wenn keine Übereinstimmung mit einem Objekt in der Datenbank mit einem entsprechenden Satzzeichen vorhanden ist.
Im Fall eines für die englische Sprache ausgelegten Systems (in dem das Flag Apostrophe_S auf TRUE gesetzt ist) zeigt Fig. 18D das auf Fig. 18B folgende Ergebnis, wenn der Benutzer die Taste PQRS 932 drückt. Dies stößt die in den Blöcken 332 bis 342 in Fig. 5B dargestellte Verarbeitung an und führt dazu, daß die Verarbeitungssoftware für das Satzzeichen die Objekte "test's", "test-s", "testr", "test-p" und "test-q" in dieser Reihenfolge der Auswahlliste hinzufügt. Infolgedessen ist das sich ergebende vorgegebene Objekt der Auswahlliste "test's" 931, das auch vorläufig im Textbereich im Einfügepunkt 930 eingefügt ist.
Die Fig. 18E zeigt das auf Fig. 18D folgende Ergebnis, wenn der Benutzer die Taste TUV 932 (mit der Absicht, das mit dem Bindestrich verbundene Wort "testrun" einzutippen) drückt. Dies stößt die in den Blöcken 332 bis 340 in Fig. 5B dargestellte Verarbeitung an und führt dazu, daß die Verarbeitungssoftware für die Satzzeichentaste die Ausgabe des Textobjekts "test-" als akzeptierter Text veranlaßt und dafür sorgt, daß der Tastenanschlagpuffer derart modifiziert wird, daß er lediglich die beiden letzten Tastenanschläge PQRS und TUV enthält. Eine Abfrage der Datenbank (im Block 360 in Fig. 5B) auf der Grundlage der beiden Tastenanschläge führt zu der in Fig. 18E dargestellten Auswahlliste. Das Textobjekt "st" ist am häufigsten und erscheint daher als vorgegebenes Objekt "st" 941 der Auswahlliste und wird auch vorläufig im Textbereich am Einfügepunkt 941 eingefügt.
Fig. 18F zeigt das Ergebnis, das auf Fig. 18E folgt, wenn der Benutzer die Taste MNO 952 drückt, um das Eintippen des mit Bindestrich verbundenen Wort "testrun" abzuschließen. Da bei der Verarbeitung des vorhergehenden Tastenanschlags alle Flags im Block 372 in Fig. 5B gelöscht worden sind, läuft keine spezielle Verarbeitung eines Satzzeichens ab. Infolgedessen verarbeitet das System einfach die aktuelle Tastenfolge PQRS, TUV, MNO, Eine Abfrage der Datenbank auf der Grundlage dieser drei Tastenanschläge führt zu der in Fig. 18F dargestellten Auswahlliste. Das Textobjekt "run" ist am häufigsten und erscheint daher als vorgegebenes Objekt "run" 951 der Auswahlliste und wird auch vorläufig im Textbereich am Einfügepunkt 950 eingefügt.
Die Fig. 186 bis 18K zeigen ein Beispiel für ein auf die französische Sprache ausgelegtes System (in dem das Flag Apostroph_Term auf TRUE gesetzt ist). In diesem Beispiel tippt der Benutzer das Textobjekt "c'est" ein, das im vorliegenden Fall aus dem Wort "c'" besteht, das mit dem Wort "est" verknüpft ist. Fig. 18 G zeigt das Ergebnis, wenn der Benutzer die Taste ABC 962 drückt. Die Auswahlliste zeigt die einzelnen Zeichenobjekte, die mit der Taste ABC in der französischen Sprache verknüpft sind, einschließlich der Schriftzeichen à, â und ç. Es läuft keine spezielle Verarbeitung einer Satzzeichentaste ab, da alle Satzzeichen betreffenden Flags zuvor gelöscht worden sind. Das System verarbeitet einfach die aus der einzelnen Taste ABC bestehende Folge. Eine Abfrage der Datenbank auf der Grundlage dieses Tastenanschlags ergibt die in Fig. 18 G dargestellte Auswahlliste. Das Textobjekt "à" ist am häufigsten und erscheint daher als vorgegebenes Objekt "à" 961 der Auswahlliste und wird auch vorläufig im Textbereich am Einfügepunkt 960 eingefügt.
In Fig. 18H hat der Benutzer im folgenden die Satzzeichentaste . - ' 63 gedrückt. Die Objekte "c'" und "a-" werden in der Datenbank gespeichert und der Auswahlliste in den Blöcken 156 bis 160 in Fig. 3 nach einer Abfrage der Datenbank hinzugefügt, so daß das sich ergebende vorgegebene Objekt der Auswahlliste "c'" 971 ist. Im folgenden verläuft jeder der Tests in den Blöcken 300 bis 306 in Fig. 5B erfolgreich und das Flag pState wird im Block 308 auf PUNCT_APOS gesetzt. Nach den Objekten "c'" 971 und "a-" 973 in der Auswahlliste fügt die Verarbeitungssoftware für Satzzeichen (in den Blöcken 312, 314 und 316 in Fig. 5B) die Objekte "à.", "à-" und "à'" hinzu, die aus dem curPunctWord "à" mit einem hinzugefügten Punkt 974, Bindestrich 975 und Apostroph 976 bestehen. Das sich ergebende vorgegebene Objekt der Auswahlliste ist "c'" 971, das auch vorläufig in dem Textbereich am Einfügepunkt 970 eingefügt wird.
In Fig. 181, hat der Benutzer im folgenden die Taste DEF 982 gedrückt. Da das Flag pState in Folge der Verarbeitung des vorhergehenden Tastenanschlags in Fig. 18H auf PUNCT-APOS gesetzt worden ist, führt die Verarbeitungssoftware für Satzzeichen die Blöcke 274, 276 und 262 in Fig. 5A aus. Das aktuelle vorgegebene Objekt der Auswahlliste "c'" wird als akzeptierter Text 983 ausgegeben, der aktuelle Tastenanschlagspuffer wird gelöscht, und das System verarbeitet die sich ergebende, aus der einzelnen Taste DEF bestehende Folge, nachdem der aktuelle Tastenanschlag DEF dem gelöschten Tastenanschlagspuffer hinzugefügt worden ist. Eine Abfrage der Datenbank auf der Grundlage dieses Tastenanschlags führt zu der in Fig. 181 dargestellten Auswahlliste. Das Textobjekt "d" ist am häufigsten und erscheint als vorgegebenes Objekt "d" 981 der Auswahlliste und wird auch vorläufig im Textbereich am Einfügepunkt 980 eingefügt.
Die Fig. 18J und 18K zeigen die Ergebnisse, die auf Fig. 181 folgen, wenn der Benutzer die Taste PQRS 992 (in Fig. 18J) und die Taste TUV 997 (in 18K) drückt, um das Tippen des Worts "est" abzuschließen. Es läuft keine besondere Verarbeitung eines Satzzeichens ab, da das Flag ClearPunctMode im Block 262 in Fig. 5A beim Verarbeiten des vorhergehenden Tastenanschlags gesetzt worden ist, so daß alle Puffer und Flags für eine Satzzeichentaste im Block 202 von Fig. 5A gelöscht worden sind. Infolgedessen verarbeitet das System einfach die aktuelle Tastenfolge DEF, PQRS, TUV. Eine Abfrage der Datenbank auf der Grundlage dieser drei Tastenanschläge führt zu der in Fig. 18K dargestellten Auswahlliste. Das Textobjekt "est" ist das häufigste und erscheint daher als vorgegebenes Objekt "est" 996 in der Auswahlliste und wird auch vorläufig im Textbereich am Einfügepunkt 995 eingefügt.
Die französische Sprache enthält eine Vielzahl von sehr häufig verwendeten Partikeln, Präpositionen und Pronomen wie z. B. le, ne, ce, de, me, se, je, que, tu und te die, wenn sie einem mit einem Vokal beginnenden Wort vorhergehen, ihren Vokal am Ende in einen Apostroph ändern und mit keinem Leerzeichen vor dem folgenden Wort getippt werden. Ohne das im vorgehenden Beispiel gezeigte, von der Satzzeichentaste 63 unterstützte Verhalten würde diese häufige Verknüpfung von Wortobjekten vom Benutzer eine zusätzliche Tastenbetätigung der Auswahltaste verlangen, um das erste Wortobjekt (c' in dem dargestellten Beispiel) vor dem Tippen des zweiten Objekts (est) abzuschließen. Die Fähigkeit der Satzzeichentaste 63, die automatische Verknüpfung von mit einem Apostroph endenden Worten zu unterstützen, erhöht die Effizienz und die natürliche Wahrnehmung des Systems für Sprachen wie z. B. Französisch.
Es sei angemerkt, daß die Tastatur 54 des Begriffsklärungssystems für eingeschränkte Tastaturen so eingerichtet werden kann, daß sie drei oder auch 20 Datentasten enthält und das die hier beschriebene Technik zur Begriffsklärung in gleicher Weise auf Tastaturen verschiedener Größe anwendbar ist. Darüber hinaus können die mit der Satzzeichentaste 63 verknüpften, spezifischen Zeichen geändert werden. Beispielsweise kann der Punkt für bestimmte Anwendungen durch ein Komma ersetzt werden. Darüber hinaus kann die spezifische Auswahl des jeweiligen Satzzeichens in verschiedenen zusammenhängenden Kontexten des Tastenanschlags geändert werden. Beispielsweise können zwei aufeinanderfolgende Betätigungen der Satzzeichentaste 63 dazu führen, daß ein langer Querstrich "-" erzeugt wird, wohingegen drei aufeinanderfolgende Betätigungen ein Auslassungszeichen ". . ." erzeugen.
Der Fachmann erkennt weiterhin, daß zusätzliche Vokabularmodule innerhalb des Computers vorgesehen sein können z. B. Vokabularmodule mit juristischen, medizinischen oder fremdsprachlichen Ausdrücken. Über ein Systemmenü kann der Benutzer das System so konfigurieren, daß die Worte aus zusätzlichen Vokabularen als erste oder letzte der möglichen Wörter in einer speziellen Einfärbung oder Hervorhebung erscheinen. Schließlich sei angemerkt, daß die Erfindung innerhalb des Schutzbereichs der angefügten Ansprüche auch auf andere Weise als hier speziell beschrieben ausgeführt werden kann.

Claims

1. Begriffsklärungssystem (50) zum Eindeutig-Machen von durch einen Benutzer eingegebenen Eingabesequenzen, wobei das Begriffsklärungssystem von dem Typ mit folgenden Merkmalen ist: (a) ein Benutzereingabegerät (52) mit mehreren Eingängen (54), wobei jede von mehreren sequentiellen Betätigungen ausgewählter Eingänge eine Interpretation aufweist, die mehrdeutig ist, weil zu jedem Eingang mehrere Zeichen gehören; (b) einen Speicher (104), der Daten enthält, welche für den Aufbau mehrerer Objekte verwendet werden, von denen jedem Objekt eine Eingabesequenz und eine relative Benutzungshäufigkeit zugeordnet sind, sämtliche Objekte innerhalb des Speichers in einer Baumstruktur (110) aus einer Mehrzahl von Knoten (400) gespeichert sind, wobei jedem Knoten eine Eingabesequenz und ein oder mehrere Objekte zugeordnet sind, wobei die Knoten durch mehrere Pfade (P1, P2, . . .) verbunden sind, von denen jeder einen Elternknoten, zu dem eine Basiseingabesequenz gehört, mit einem Kinderknoten verbindet, zu dem die Basiseingabesequenz des Elternknotens und eine zusätzliche Eingabe gehören; und wobei die zu einem Kinderknoten gehörigen Objekte auf den Objekten basieren, die zu dem entsprechenden Elternknoten gehören, mit dem der Kinderknoten verknüpft ist und die aufgebaut werden unter Verwendung eines in dem Speicher (104) vorab gespeicherten Codes (406), um zu dem entsprechenden Elterncode gehörige Objekte zu modifizieren, wobei der Code, der dazu dient, Objekte aufzubauen, die zu einem Kinderknoten gehören, indem zu dem entsprechenden Elternknoten gehörige Objekte modifiziert werden, umfaßt: eine Spezifikation eines numerischen Index' des zu dem entsprechenden Elternknoten gehörigen Objekts und eine Spezifikation eines numerischen Index' von einem der Zeichen, die zu der zusätzlichen Eingabe gehören, welche den Elternknoten mit dem Kinderknoten verbindet; (c) eine Anzeige (53) zur Darstellung der Systemausgabe für den Benutzer; und (d) einen Prozessor (100), der mit der Benutzereingabeeinrichtung (52), dem Speicher (104) und der Anzeige (53) gekoppelt ist, und der Prozessor (100): (i) aus dem einen oder mehreren Objekten in dem Speicher, zugehörig zu jeder generierten Eingabesequenz, wird mindestens ein Kandidatenobjekt mit der höchsten Benutzungshäufigkeit identifiziert, wobei das Kandidatenobjekt ein Wortobjekt ist, wenn mindestens ein Wortobjekt zu der erzeugten Eingabesequenz gehört, und ein Wortstammobjekt ist, wenn zu der erzeugten Eingabesequenz kein Wortobjekt gehört; und (ii) ein Ausgangssignal erzeugt, welches die Anzeige (53) veranlaßt, das mindestens eine identifizierte Kandidatenobjekt, das zu jeder erzeugten Eingabesequenz gehört, als Text-Interpretation der erzeugten Eingabesequenz anzuzeigen, wobei das Begriffsklärungssystem dadurch gekennzeichnet ist, daß: die Speicher-Baumstruktur (110) so ausgebildet ist, daß redundante Elternknoten (560, 576) eliminiert werden, wobei zwei Elternknoten des Baums dann redundant sind, wenn sämtliche zu einer gegebenen Eingabesequenz gehörigen Codes (566, 577), die in den beiden Elternknoten vorhanden sind, identisch sind insofern, als die Codes (558) innerhalb derselben Sequenz auftreten und denselben numerischen Objektindex (556) und denselben numerischen Zeichenindex (555) identifizieren, und außerdem für sämtliche Eingaben, für die Kinderknoten mit jedem der beiden Elternknoten (560, 576) verknüpft sind, auch die Kinderknoten (569, 578) in derselben rekursiven Weise redundant sind, wobei einer der redundanten Elternknoten (576) aus der Baumstruktur in dem Speicher weggelassen wird und der verbleibende redundante Elternknoten (560) durch jegliche Codes und Verknüpfungen zu Kinderknoten (578) bereichert wird, die nur in dem weggelassenen redundanten Elternknoten (576) vorhanden waren, und sämtliche Verknüpfungen von irgendeinem Elternknoten, von dem der weggelassene Elternknoten ein Kind ist, an den verbleibenden redundanten Elternknoten als Verknüpfungen neu geschrieben werden.

2. System nach Anspruch 1, bei dem ein oder mehrere Zeichen, die spezielle unterscheidende Marken (550) enthalten, zu demselben Eingang gehören, mit dem das entsprechende Zeichen ohne spezielle unterscheidende Marken gehört.

3. System nach Anspruch 2, bei dem ein oder mehrere Zeichen, die spezielle unterscheidende Marken (541) aufweisen, nicht auf dem Eingang (540) erscheinen, der zu dem entsprechenden Zeichen ohne die speziellen unterscheidenden Marken gehört.

4. System nach Anspruch 1, bei dem das mindestens eine identifizierte Kandidatenobjekt mit der höchsten Benutzungshäufigkeit, das als Text-Interpretation der erzeugten Eingabesequenz angezeigt wird, ein Wortstammobjekt ist, wenn die Benutzungshäufigkeit des Wortstammobjekts die höchste Benutzungshäufigkeit, die zu irgendeinem Wortobjekt gehört, das zu der erzeugten Eingabesequenz (190) gehört, um einen vorbestimmten Faktor übersteigt, wobei die höchste Benutzungshäufigkeit, die zu irgendeinem Wortobjekt gehört, das zu der erzeugten Eingabesequenz gehört, einen vorbestimmten Schwellenwert (191) nicht übersteigt.

5. System nach Anspruch 1, bei dem das mindestens eine Objekt mit der höchsten Benutzungshäufigkeit, welches vorläufig als Text-Interpretation der erzeugten Eingabesequenz angezeigt wird, für die Ausgabe als Text-Interpretation der erzeugten Eingabesequenz bei Eingang irgendeiner Eingabe bestätigt wird, die zu der eindeutigen Erzeugung von einem oder mehreren Zeichen führt, wobei das eine oder die mehreren eindeutigen Zeichen unmittelbar im Anschluß an die Ausgabe der bestätigten Text-Interpretation ausgegeben werden.

6. System nach Anspruch 1, bei dem der Code (556), der für den Aufbau von Objekten (440) dient, die zu einem Kindercode gehören, indem zu dem entsprechenden Elternknoten (430) gehörige Objekte modifiziert werden, eine Spezifikation (557) darüber enthält, ob der Code ein Endcode der Sequenz von Codes ist, die Objekte erzeugen, welche zu dem Kinderknoten gehören.

7. System nach Anspruch 1, bei dem die Anzahl und die Identität zusätzlicher Eingaben, welche den Kinderknoten entsprechen, die mit einem Elternknoten verknüpft sind, in dem Elternknoten durch ein Feld von Zulässigkeitsschlüsselbits (402) angegeben wird, welche Nummer und die Identität der Kinderknoten angibt.

8. System nach Anspruch 7, bei dem jeder Menge aus einem oder mehreren Codes (406), die zum Erzeugen der zu einem Kinderknoten gehörigen Objekte verwendet werden, unmittelbar ein Zeiger (404) auf den Kinderknoten folgt, wobei die eine oder mehreren Mengen aus einem oder mehreren Codes (406) und nachfolgendem Zeiger (404) sequentiell im Speicher innerhalb des Elternknotens in der gleichen Reihenfolge wie die Zulässigkeitsschlüsselbits (402) plaziert werden, die die Nummer und Identität der Kinderknoten angeben.

9. System nach Anspruch 1, bei dem die Sequenz von Codes (406), die zu einem Kinderknoten gehörige Objekte (556) erzeugen, in dem Speicher derart geordnet sind, daß die Objekte in einer Folge erzeugt werden, die bezüglich der Benutzungshäufigkeit der Objekte geordnet sind.

10. System nach Anspruch 1, bei dem die Indizes (555) der Zeichen, die zu jedem Eingang gehören, sequentiell den Zeichen in absteigender Reihenfolge der Häufigkeit ihres Auftretens in Wortobjekten innerhalb des Speichers zugeordnet werden.

11. System nach Anspruch 1, bei dem die Indizes (555) der zu jedem Eingang gehörigen Zeichen Indizes enthalten, die einer Kette aus mehreren Zeichen zugeordnet sind.

12. System nach Anspruch 1, bei dem der zum Aufbau von Objekten in Verbindung mit einem Kinderknoten durch Modifizieren von zu dem entsprechenden Elterncode gehörigen Objekten verwendete Code (406) außerdem eine Spezifikation eines Objekttyps enthält, der zu dem zu dem Kinderknoten gehörigen aufgebauten Objekt gehört.

13. System nach Anspruch 12, bei dem der spezifizierte Objekttyp Information über den Sprachteil des aufgebauten Objekts enthält.

14. System nach Anspruch 12, bei dem der spezifizierte Objekttyp Information über die Kapitalisierung des aufgebauten Objekts enthält.

15. System nach Anspruch 12, bei dem der spezifizierte Objekttyp Information über Beugungs-Endungen und -Endsilben enthält, die an dem aufgebauten Objekt geändert werden können.

16. System nach Anspruch 12, bei dem der spezifizierte Objekttyp einen Code enthält, der in einzigartiger Weise das aufgebaute Objekt unter den in dem Speicher befindlichen Objekten identifiziert.

17. System nach Anspruch 12, bei dem der spezifizierte Objekttyp Information über die Benutzungshäufigkeit des aufgebauten Objekts enthält.

18. System nach Anspruch 12, bei dem der spezifizierte Objekttyp Information darüber enthält, ob das aufgebaute Objekt ein vollständiges Wort ist.

19. System nach Anspruch 1, bei dem die Indizes (555) von zu jedem Eingang gehörigen Zeichen sequentiell den Zeichen in absteigender Reihenfolge der Häufigkeit des Auftretens der Zeichen zugeordnet werden, gefolgt von dem unmittelbar vorausgehenden Zeichen in dem Objekt, welches dem entsprechenden Elternknoten zugeordnet ist, an welchem das mit Index versehene Zeichen hängt, um ein zu dem Kinderknoten gehöriges Objekt zu bilden.

20. System nach Anspruch 1, bei dem ein oder mehrere Codes (406), die zu einem gegebenen Eingang gehören und in beiden der redundanten Elternknoten enthalten sind, als identisch definiert werden, wenn die Codes den gleichen numerischen Objektindex (556) und den gleichen numerischen Zeichenindex (555) spezifizieren, auch wenn die Codes (406) in einer unterschiedlichen Sequenz in den beiden redundanten Elternknoten auftreten.

21. System nach Anspruch 1, bei dem zwei Elternknoten des Baums (110) nur dann als redundant definiert werden, wenn sämtliche zu einem gegebenen Eingang gehörigen Codes (406) in beiden redundanten Elternknoten vorhanden sind und dahingehend identisch sind, daß die Codes in derselben Sequenz auftreten und den gleichen numerischen Objektindex (556) und den gleichen numerischen Zeichenindex (555) spezifizieren, und außerdem für sämtliche Eingänge, für die Kinderknoten mit jedem der beiden redundanten Elternknoten verknüpft sind, diese Kinderknoten ebenfalls in dem gleichen rekursiven Sinn redundant sind.

22. System nach Anspruch 21, bei dem ein oder mehrere Codes (406), die zu einem gegebenen Eingang gehören und in beiden der redundanten Elternknoten enthalten sind, als identisch definiert werden, wenn die Codes (406) den gleichen numerischen Objektindex (556) und den gleichen numerischen Zeichenindex (555) spezifizieren, auch wenn die Codes in einer unterschiedlichen Sequenz in den beiden redundanten Elternknoten auftreten.

23. System nach Anspruch 1, bei dem ein oder mehrere Codes (406), die zum Aufbauen von Objekten verwendet werden, die zu Kinderknoten gehören, indem zu dem entsprechenden Elternknoten gehörige Objekte modifiziert werden, außerdem eine Spezifizierung eines Objekttyps enthalten, der zu dem aufgebauten Objekt gehört, das zu dem Kinderknoten gehört, wobei zwei Knoten als identisch definiert sind, wenn sie den gleichen numerischen Objektindex (556) und den gleichen numerischen Zeichenindex (555) spezifizieren, und wenn höchstens einer der beiden Codes einen Objekttyp spezifiziert, wobei derjenige Code, der in dem verbleibenden redundanten Elterncode vorhanden ist, welcher durch irgendwelche Codes (406) und Verknüpfungen zu solchen Kinderknoten (404) ergänzt wurde, die nur in dem weggelassenen redundanten Elternknoten vorhanden waren, die Spezifikation des Objekttyps enthält.

24. System nach Anspruch 23, bei dem der spezifizierte Objekttyp Information enthält zum Unterscheiden der Eingabesequenz entsprechend dem aufgebauten Objekt von anderen Eingabesequenzen, die den Knoten benutzen.

25. Verfahren zum Eindeutig-Machen mehrdeutiger Eingabesequenzen, wobei das Verfahren beinhaltet: (a) Erzeugen einer Eingabesequenz aus einer Mehrzahl von Eingängen, denen jeweils mehrere Zeichen zugeordnet sind, wobei die erzeugte Eingabesequenz eine Text-Interpretation besitzt, die aufgrund der Tatsache, daß jedem Eingang mehrere Zeichen zugeordnet sind, mehrdeutig ist; (b) Speichern von Daten, die dazu verwendet werden, eine Mehrzahl von Objekten aufzubauen, zu jedem von denen eine Eingabesequenz und eine relative Benutzungshäufigkeit gehören, und wobei sämtliche Objekte in einer Baumstruktur (110) gespeichert werden, bestehend aus einer Mehrzahl von Knoten (400), denen jeweils eine Eingabesequenz und ein oder mehrere Objekte zugeordnet sind, wobei die mehreren Knoten durch mehrere Pfade (P1, P2, . . .) verbunden sind, die jeweils einen zu einer Basis-Eingabesequenz gehörigen Elternknoten mit einem Kinderknoten verknüpfen, zu dem die Basis- Eingabesequenz des Elternknotens und eine zusätzliche Eingabe gehören, wobei die zu einem Kinderknoten gehörigen Objekte auf den Objekten basieren, zu denen der entsprechende Elternknoten gehört, mit dem der Kinderknoten verknüpft ist, und wobei die zu einem Kinderknoten gehörigen Objekte aufgebaut werden unter Verwendung eines Codes (406), der in einem Speicher (104) vorab gespeichert ist, um Objekte, die zu dem entsprechenden Elternknoten gehören, zu modifizieren, und wobei der Code (556), der zum Aufbauen von Objekten verwendet wird, die zu einem Kinderknoten gehören, indem Objekte, die zu dem entsprechenden Elternknoten gehören, modifiziert werden, eine Spezifikation aus einem numerischen Index (555) des zu dem entsprechenden Elternknoten gehörigen Objekts und eine Spezifikation eines numerischen Index' (555) eines der Zeichen aufweist, denen eine zusätzliche Eingabe zugeordnet ist, welche den Elternknoten mit dem Kinderknoten verbindet; (c) aus einem oder mehreren Objekten, die zu jeder erzeugten Eingabesequenz gehören, wird mindestens ein Kandidatenobjekt mit der höchsten Benutzungshäufigkeit identifiziert, wobei das Kandidatenobjekt ein Wortobjekt ist, wenn mindestens ein Wortobjekt zu der erzeugten Eingabesequenz gehört, während das Kandidatenobjekt ein Wortstammobjekt ist, wenn kein Wortobjekt zu der erzeugten Eingabesequenz gehört; und (d) Anzeigen des mindestens einen identifizierten Kandidatenobjekts, das zu jeder erzeugten Eingabesequenz gehört, in Form einer Text-Interpretation der erzeugten Eingabesequenz, dadurch gekennzeichnet, daß der Schritt des Speicherns sämtlicher Objekte in einer Baumstruktur (110) das Eliminieren redundanter Elternknoten beinhaltet, wenn zwei Elternknoten (560, 576) des Baums (110) redundant sind, wenn sämtliche zu einem gegebenen Eingang gehörigen Codes (566, 577), die in beiden genannten Elternknoten (560, 576) vorhanden sind, dahingehend identisch sind, daß die Codes (566, 577) in der gleichen Sequenz auftreten und denselben numerischen Objektindex (556) und denselben numerischen Zeichenindex (555) spezifizieren, und weiterhin sämtliche Eingänge, für die Kinderknoten mit jedem der beiden Elternknoten (560, 576) verknüpft sind, die Kinderknoten ebenfalls in dem gleichen rekursiven Sinn redundant sind, wobei einer der redundanten Elternknoten (576), der aus der Baumstruktur (110) im Speicher (104) eliminiert wird und der verbleibende redundante Elternknoten (560) ergänzt wird durch jegliche Codes und Verknüpfungen zu Kinderknoten (578), die nur in dem weggelassenen redundanten Elternknoten vorhanden waren, wobei sämtliche Verknüpfungen von irgendeinem Elternknoten, von welchem der weggelassene Elternknoten ein Kind ist, als Verknüpfungen zu dem verbleibenden redundanten Elternknoten neu geschrieben werden.

26. Verfahren nach Anspruch 25, bei dem das mindestens eine identifizierte Kandidatenobjekt mit der höchsten Benutzungshäufigkeit, das als Text-Interpretation der erzeugten Eingabesequenz angezeigt wird, ein Wortstammobjekt ist, wenn die Benutzungshäufigkeit des Wortstammobjekts die höchste Benutzungshäufigkeit, die zu irgendeinem Wortobjekt gehört, dem die erzeugte Eingabesequenz (190) zugeordnet ist, um einen vorbestimmten Faktor übersteigt, und die höchste Benutzungshäufigkeit, die zu irgendeinem zu der erzeugten Eingabesequenz gehörigen Wortobjekt gehört, einen vorbestimmten Schwellenwert (191) nicht übersteigt.

27. Verfahren nach Anspruch 25, bei dem das mindestens eine Objekt mit der höchsten Benutzungshäufigkeit, welches vorläufig als Text-Interpretation der erzeugten Eingabesequenz bei Eingang irgendeiner Eingabe angezeigt wird, die zu der eindeutigen Erzeugung von einem oder mehreren Zeichen führt, wobei ein oder mehrere eindeutige Zeichen unmittelbar im Anschluß an die Ausgabe der bestätigten Text-Interpretation ausgegeben werden.

28. Verfahren nach Anspruch 25, bei dem der Code (556), der zum Aufbau von zu einem Kinderknoten gehörigen Objekten (440) durch Modifizieren von Objekten verwendet wird, die zu dem entsprechenden Elternknoten (430) gehören, außerdem eine Spezifikation (557) darüber beinhaltet, ob der Code ein endgültiger Code der Folge von Codes ist, die zu dem Kinderknoten gehörige Objekte erzeugen.

29. Verfahren nach Anspruch 25, bei dem die Nummer und die Identität zusätzlicher Eingänge, die den mit einem Elternknoten verknüpften Kinderknoten entsprechen, in dem Elternknoten angegeben werden durch ein Feld von Zulässigkeitsschlüsselbits (402), die die Nummer und die Identität der Kinderknoten angeben.

30. Verfahren nach Anspruch 29, bei dem jeder Menge aus einem oder mehreren Codes (406), die zum Erzeugen der zu einem Kinderknoten gehörigen Objekte verwendet werden, unmittelbar ein Zeiger (404) auf den Kinderknoten folgt, wobei die eine oder mehreren Mengen aus einem oder mehreren Codes (406) und nachfolgendem Zeiger (404) sequentiell im Speicher innerhalb des Elternknotens in der gleichen Reihenfolge wie die Zulässigkeitsschlüsselbits (402) plaziert werden, die die Nummer und Identität der Kinderknoten angeben.

31. Verfahren nach Anspruch 25, bei dem die Sequenz von Codes (406), die zu einem Kinderknoten gehörige Objekte (556) erzeugen, in dem Speicher derart geordnet sind, daß die Objekte in einer Folge erzeugt werden, die bezüglich der Benutzungshäufigkeit der Objekte geordnet sind.

32. Verfahren nach Anspruch 25, bei dem die Indizes (555) der Zeichen, die zu jedem Eingang gehören, sequentiell den Zeichen in absteigender Reihenfolge der Häufigkeit ihres Auftretens in Wortobjekten innerhalb des Speichers zugeordnet werden.

33. Verfahren nach Anspruch 25, bei dem bei dem die Indizes (555) der zu jedem Eingang gehörigen Zeichen Indizes enthalten, die einer Kette aus mehreren Zeichen zugeordnet sind.

34. Verfahren nach Anspruch 25, bei dem der zum Aufbau von Objekten in Verbindung mit einem Kinderknoten durch Modifizieren von zu dem entsprechenden Elterncode gehörigen Objekten verwendete Code (406) außerdem eine Spezifikation eines Objekttyps enthält, der zu dem zu dem Kinderknoten gehörigen aufgebauten Objekt gehört.

35. Verfahren nach Anspruch 34, bei dem der spezifizierte Objekttyp einen Code enthält, der eindeutig das aufgebaute Objekt unter den Objekten in dem Speicher identifiziert.

36. Verfahren nach Anspruch 34, bei dem der spezifizierte Objekttyp Information über die Benutzungshäufigkeit des aufgebauten Objekts enthält.

37. Verfahren nach Anspruch 34, bei dem der spezifizierte Objekttyp Information darüber enthält, ob das aufgebaute Objekt ein vervollständigtes Wort ist.

38. Verfahren nach Anspruch 25, bei dem die Indizes (555) von zu jedem Eingang gehörigen Zeichen sequentiell den Zeichen in absteigender Reihenfolge der Häufigkeit des Auftretens der Zeichen zugeordnet werden, gefolgt von dem unmittelbar vorausgehenden Zeichen in dem Objekt, welches dem entsprechenden Elternknoten zugeordnet ist, an welchem das mit Index versehene Zeichen hängt, um ein zu dem Kinderknoten gehöriges Objekt zu bilden.

39. Verfahren nach Anspruch 25, bei dem ein oder mehrere Codes (406), die zu einem gegebenen Eingang gehören und in beiden der redundanten Elternknoten enthalten sind, als identisch definiert werden, wenn die Codes den gleichen numerischen Objektindex (556) und den gleichen numerischen Zeichenindex (555) spezifizieren, auch wenn die Codes (406) in einer unterschiedlichen Sequenz in den beiden redundanten Elternknoten auftreten.

40. Verfahren nach Anspruch 25, bei dem zwei Elternknoten des Baums (110) nur dann als redundant definiert werden, wenn sämtliche zu einem gegebenen Eingang gehörigen Codes (406) in beiden redundanten Elternknoten vorhanden sind und dahingehend identisch sind, daß die Codes in derselben Sequenz auftreten und den gleichen numerischen Objektindex (556) und den gleichen numerischen Zeichenindex (555) spezifizieren, und außerdem für sämtliche Eingänge, für die Kinderknoten mit jedem der beiden redundanten Elternknoten verknüpft sind, diese Kinderknoten ebenfalls in dem gleichen rekursiven Sinn redundant sind.

41. Verfahren nach Anspruch 40, bei dem ein oder mehrere Codes (406), die zu einem gegebenen Eingang gehören und in beiden der redundanten Elternknoten enthalten sind, als identisch definiert werden, wenn die Codes (406) den gleichen numerischen Objektindex (556) und den gleichen numerischen Zeichenindex (555) spezifizieren, auch wenn die Codes in einer unterschiedlichen Sequenz in den beiden redundanten Elternknoten auftreten.

42. Verfahren nach Anspruch 25, bei dem ein oder mehrere Codes (406), die zum Aufbauen von Objekten verwendet werden, die zu Kinderknoten gehören, indem zu dem entsprechenden Elternknoten gehörige Objekte modifiziert werden, außerdem eine Spezifizierung eines Objekttyps enthalten, der zu dem aufgebauten Objekt gehört, das zu dem Kinderknoten gehört, wobei zwei Knoten als identisch definiert sind, wenn sie den gleichen numerischen Objektindex (556) und den gleichen numerischen Zeichenindex (555) spezifizieren, und wenn höchstens einer der beiden Codes (406) einen Objekttyp spezifiziert, wobei derjenige Code, der in dem verbleibenden redundanten Elterncode vor handen ist, welcher durch irgendwelche Codes und Verknüpfungen zu solchen Kinderknoten (404) ergänzt wurde, die nur in dem weggelassenen redundanten Elternknoten vorhanden waren, die Spezifikation des Objekttyps enthält.

43. Verfahren nach Anspruch 42, bei dem der spezifizierte Objekttyp Information enthält zum Unterscheiden der Eingabesequenz entsprechend dem aufgebauten Objekt von anderen Eingabesequenzen, die den Knoten benutzen.

44. Rechnerlesbares Medium mit durch einen Rechner ausführbaren Komponenten zum Eindeutig-Machen mehrdeutiger Eingabesequenzen, wobei die durch einen Rechner ausführbaren Komponenten umfassen: (a) eine Benutzereingabekomponente zum Verarbeiten einer Mehrzahl von Eingängen, wobei jeder der mehreren Eingänge zu einer Mehrzahl von Zeichen gehört, die erzeugte Eingabesequenz eine Text-Interpretation hat, die aufgrund der Tatsache mehrdeutig ist, daß die mehreren Zeichen zu einem Eingang gehören; (b) eine Speicherkomponente, die Daten enthält, welche dazu dienen, eine Mehrzahl von Objekten aufzubauen, von denen jedes zu einer Eingabesequenz und einer relativen Benutzungshäufigkeit gehört, und wobei sämtliche Objekte in eine Baumstruktur (110) gespeichert werden, umfassend eine Mehrzahl von Knoten (400), von denen jeder Knoten (400) zu einer Eingabesequenz und zu einem oder mehreren Objekten gehört, die Mehrzahl von Knoten (400) durch eine Mehrzahl von Pfaden (P1, P2, . . .) verbunden ist, von denen jeder einen zu einer Basis-Eingabesequenz gehörigen Elternknoten mit einem Kinderknoten verknüpft, der zu der Basis-Eingabesequenz des Elternknotens und zu einer zusätzlichen Eingabe gehört; wobei die zu einem Kinderknoten gehörigen Objekte auf den Objekten basieren, die zu dem entsprechenden Elternknoten gehören, mit dem der Kinderknoten verknüpft ist; zu einem Kinderknoten gehörige Objekte unter Verwendung eines vorab in einem Speicher (104) gespeicherten Codes (406) aufgebaut werden, um zu dem entsprechenden Elternknoten gehörige Objekte zu modifizieren; wobei der Code, der dazu dient, Objekte aufzu bauen, die zu einem Kinderknoten gehören, indem zu dem entsprechenden Elternknoten gehörige Objekte modifiziert werden, eine Spezifikation eines numerischen Index' des zu dem entsprechenden Elternknoten gehörigen Objekts und eine Spezifikation eines numerischen Index' von einem der Zeichen enthält, die zu der zusätzlichen Eingabe gehören, die den Elternknoten mit dem Kinderknoten verbindet; (c) eine Identifizierungskomponente zum Identifizieren aus einem oder mehreren Objekten, die zu jeder erzeugten Eingabesequenz gehören, mindestens eines Kandidatenobjekts mit der höchsten Benutzungshäufigkeit; und (d) eine Ausgabekomponente zum Anzeigen des mindestens einen identifizierten Kandidatenobjekts, der zu jeder erzeugten Eingabesequenz gehört, in Form einer Text-Interpretation der erzeugten Eingabesequenz, wobei das durch einen Rechner lesbare Medium dadurch gekennzeichnet ist, daß die Baumstruktur (110) so angeordnet ist, daß redundante Elternknoten (560, 576) eliminiert werden, wobei zwei Elternknoten des Baums (110) redundant sind, wenn sämtliche Codes, die zu einem gegebenen Eingang gehören, der in beiden der beiden Elternknoten vorhanden ist, dahingehend identisch sind, daß die Codes in der gleichen Sequenz auftreten und den gleichen numerischen Objektindex (556) sowie den gleichen numerischen Zeichenindex (555) spezifizieren, und außerdem für sämtliche Eingänge, für welche Kinderknoten mit jedem der beiden Elternknoten verknüpft sind, die Kinderknoten ebenfalls im gleichen rekursiven Sinn redundant sind, einer der redundanten Elternknoten aus der Baumstruktur in dem Speicher weggelassen wird (576), und der verbleibende redundante Elternknoten (560) ergänzt wird durch jegliche Codes und Verknüpfungen zu Kinderknoten (578), die nur in dem weggelassenen, redundanten Elternknoten (576) vorhanden waren, und sämtliche Verknüpfungen von irgendeinem Elternknoten aus, von denen der weggelassene Elterncode ein Kind ist, als Verknüpfungen zu dem verbleibenden, redundanten Elternknoten neu geschrieben werden.

45. Medium nach Anspruch 44, bei dem das mindestens eine identifizierte Kandidatenobjekt mit der höchsten Benutzungshäufigkeit, welches als Textinterpretation der erzeugten Eingabesequenz angezeigt wird, ein Wortstammobjekt ist, wenn die Benutzungshäufigkeit des Wortstammobjekts die höchste Benutzungshäufigkeit irgendeines Wortobjekts, das zu der erzeugten Eingabesequenz (190) gehört, um einen vorbestimmten Faktor übersteigt, und die höchste Benutzungshäufigkeit irgendeines Wortobjekts, das zu der erzeugten Eingabesequenz gehört, einen vorbestimmten Schwellenwert (191) nicht übersteigt.

46. Medium nach Anspruch 44, bei dem das mindestens eine Objekt mit der höchsten Benutzungshäufigkeit, welches vorläufig als Text-Interpretation der erzeugten Eingabesequenz angezeigt wird, für die Ausgabe als Text-Interpretation der erzeugten Eingabesequenz bei Eingang irgendeiner Eingabe bestätigt wird, die zu der eindeutigen Erzeugung von einem oder mehreren Zeichen führt, wobei das eine oder die mehreren eindeutigen Zeichen unmittelbar im Anschluß an die Ausgabe der bestätigten Text-Interpretation ausgegeben werden.

47. Medium nach Anspruch 44, bei dem der Code (556), der für den Aufbau von Objekten (440) dient, die zu einem Kindercode gehören, indem zu dem entsprechenden Elternknoten (430) gehörige Objekte modifiziert werden, eine Spezifikation (557) darüber enthält, ob der Code ein Endcode der Sequenz von Codes ist, die Objekte erzeugen, welche zu dem Kinderknoten gehören.

48. Medium nach Anspruch 44, bei dem die Anzahl und die Identität zusätzlicher Eingaben, welche den Kinderknoten entsprechen, die mit einem Elternknoten verknüpft sind, in dem Elternknoten durch ein Feld von Zulässigkeitsschlüsselbits (402) angegeben wird, welche Nummer und die Identität der Kinderknoten angibt.

49. Medium nach Anspruch 48, bei dem jeder Menge aus einem oder mehreren Codes (406), die zum Erzeugen der zu einem Kinderknoten gehörigen Objekte verwendet werden, unmittelbar ein Zeiger (404) auf den Kinderknoten folgt, wobei die eine oder mehreren Mengen aus einem oder mehreren Codes (406) und nachfolgendem Zeiger (404) sequentiell im Speicher innerhalb des Elternknotens in der gleichen Reihenfolge wie die Zulässigkeitsschlüsselbits plaziert werden, die die Nummer und Identität der Kinderknoten angeben.

50. Medium nach Anspruch 44, bei dem die Sequenz von Codes (406), die zu einem Kinderknoten gehörige Objekte erzeugen, in dem Speicher derart geordnet sind, daß die Objekte (556) in einer Folge erzeugt werden, die bezüglich der Benutzungshäufigkeit der Objekte geordnet sind.

51. Medium nach Anspruch 44, bei dem die Indizes (555) der Zeichen, die zu jedem Eingang gehören, sequentiell den Zeichen in absteigender Reihenfolge der Häufigkeit ihres Auftretens in Wortobjekten innerhalb des Speichers zugeordnet werden.

52. Medium nach Anspruch 44, bei dem die Indizes (555) der zu jedem Eingang gehörigen Zeichen Indizes enthalten, die einer Kette aus mehreren Zeichen zugeordnet sind.

53. Medium nach Anspruch 44, bei dem der zum Aufbau von Objekten in Verbindung mit einem Kinderknoten durch Modifizieren von zu dem entsprechenden Elterncode gehörigen Objekten verwendete Code (406) außerdem eine Spezifikation eines Objekttyps enthält, der zu dem zu dem Kinderknoten gehörigen aufgebauten Objekt gehört.

54. Medium nach Anspruch 53, bei dem der spezifizierte Objekttyp einen Code enthält, der eindeutig das aufgebaute Objekt unter den in dem Speicher befindlichen Objekten identifiziert.

55. Medium nach Anspruch 53, bei dem der spezifizierte Objekttyp Information enthält über die Benutzungshäufigkeit des aufgebauten Objekts.

56. Medium nach Anspruch 53, bei dem der spezifizierte Objekttyp Information darüber enthält, ob das aufgebaute Objekt ein vollständiges Wort ist.

57. Medium nach Anspruch 44, bei dem die Indizes (555) von zu jedem Eingang gehörigen Zeichen sequentiell den Zeichen in absteigender Reihenfolge der Häufigkeit des Auftretens der Zeichen zugeordnet werden, gefolgt von dem unmittelbar vorausgehenden Zeichen in dem Objekt, welches dem entsprechenden Elternknoten zugeordnet ist, an welchem das mit Index versehene Zeichen hängt, um ein zu dem Kinderknoten gehöriges Objekt zu bilden.

58. Medium nach Anspruch 44, bei dem ein oder mehrere Codes (406), die zu einem gegebenen Eingang gehören und in beiden der redundanten Elternknoten enthalten sind, als identisch definiert werden, wenn die Codes den gleichen numerischen Objektindex (556) und den gleichen numerischen Zeichenindex (555) spezifizieren, auch wenn die Codes (406) in einer unterschiedlichen Sequenz in den beiden redundanten Elternknoten auftreten.

59. Medium nach Anspruch 44, bei dem zwei Elternknoten des Baums (110) nur dann als redundant definiert werden, wenn sämtliche zu einem gegebenen Eingang gehörigen Codes (406) in beiden redundanten Elternknoten vorhanden sind und dahingehend identisch sind, daß die Codes in derselben Sequenz auftreten und den gleichen numerischen Objektindex (556) und den gleichen numerischen Zeichenindex (555) spezifizieren, und außerdem für sämtliche Eingänge, für die Kinderknoten mit jedem der beiden redundanten Elternknoten verknüpft sind, diese Kinderknoten ebenfalls in dem gleichen rekursiven Sinn redundant sind.

60. Medium nach Anspruch 59, bei dem ein oder mehrere Codes (406), die zu einem gegebenen Eingang gehören und in beiden der redundanten Elternknoten enthalten sind, als identisch definiert werden, wenn die Codes (406) den gleichen numerischen Objektindex (556) und den gleichen numerischen Zeichenindex (555) spezifizieren, auch wenn die Codes in einer unterschiedlichen Sequenz in den beiden redundanten Elternknoten auftreten.

61. Medium nach Anspruch 44, bei dem ein oder mehrere Codes (406), die zum Aufbauen von Objekten verwendet werden, die zu Kinderknoten gehören, indem zu dem entsprechenden Elternknoten gehörige Objekte modifiziert werden, außerdem eine Spezifizierung eines Objekttyps enthalten, der zu dem aufgebauten Objekt gehört, das zu dem Kinderknoten gehört, wobei zwei Knoten als identisch definiert sind, wenn sie den gleichen numerischen Objektindex (556) und den gleichen numerischen Zeichenindex (555) spezifizieren, und wenn höchstens einer der beiden Codes einen Objekttyp spezifiziert, wobei derjenige Code, der in dem verbleibenden redundanten Elterncode vorhanden ist, welcher durch irgendwelche Codes und Verknüpfungen zu solchen Kinderknoten ergänzt wurde, die nur in dem weggelassenen redundanten Elternknoten vorhanden waren, die Spezifikation des Objekttyps enthält.

62. Medium nach Anspruch 61, bei dem der spezifizierte Objekttyp Information enthält zum Unterscheiden der Eingabesequenz entsprechend dem aufgebauten Objekt von anderen Eingabesequenzen, die den Knoten benutzen.