(57)【要約】  文字の前の選択に基づいて、低減キーキーパッドの押下された複数文字キーの所望の英数字を予測するための方法および装置。文字の前の選択に基づいて押下されたキーに関連付けられている予測を定義するルールツリーは、使用されると、すべての言語スタイルおよび語彙で容易に機能するように、動的に構築される。さらに、ルールツリーは、重み付けされて、所望の文字を予測する確率を向上させ、異なる言語スタイルまたは語彙を有する異なるユーザに迅速に適合させる。
2009532773.tif 000002
【特許請求の範囲】
【請求項１】
低減キーキーパッドの複数文字キーを押下することによって所望の単語の文字を予測する方法であって、
（１）前記所望の単語の第１の単語文字であるキー文字を有する第１のキーを選択し、
前記第１のキーの前記キー文字を一度に１つ予測されたシーケンスで表示し、前記キー文字が前記所望の単語の前記第１の単語文字であるとき、前記表示されたキー文字を前記第１の文字キーとして選択することによって、
前記所望の単語の前記第１の単語文字に対応する先頭文字ルールリストにアクセスするステップと、
（２）前記所望の単語の後続の単語文字を連続して予測し、表示するためのルールのマルチレベル階層ツリーを含むルールツリーを処理し、前記所望の後続の単語文字が表示されるとき、その選択を可能にするか、新しい所望の単語文字のマルチタップによって選択を可能にするステップと
を含む方法。
【請求項２】
前記ルールによって予測された前記後続の単語文字が前に選択された回数に基づいて、前記所望の単語の前記後続の単語文字の各ルールの予測を動的に重み付けするステップをさらに含む請求項１に記載の方法。
【請求項３】
各ルールを動的に重み付けする前記ステップが、選択された少なくとも１つのすぐ前の単語文字の後に、前記後続の単語文字が前に選択された回数に基づいて重み付けするステップを含む請求項２に記載の方法。
【請求項４】
前記ルールツリーに動的に重み付けする前記ステップが、前記同じく前に押下されたキーの後のその後の予測に関連付けられている前記予測に重み付けするためにカウンタを増分するステップを含む請求項３に記載の方法。
【請求項５】
前記前の予測が前記所望の文字を正しく予測した回数に基づいて、他の所望の文字のその後の予測の前記動的な重み付けを正規化するステップをさらに含む請求項２に記載の方法。
【請求項６】
前記ルールツリーから前記最低の重量を有する１つまたは複数のルールを削除するステップをさらに含む請求項２に記載の方法。
【請求項７】
各文字が選択された後、所望の単語の前記所望の文字のすべてが選択された後、または複数の所望の単語の前記所望の文字のすべてが選択された後、前記ルールツリーを更新するステップをさらに含む請求項１に記載の方法。
【請求項８】
前記第１のキーの前記キー文字を表示し、前記キー文字が前記所望の単語の前記第１の単語文字であるとき、前記表示されたキー文字を前記第１の文字キーとして選択する前記ステップが、前記第１の文字キーが選択される回数に基づいて前記選択に重み付けし、次いで、それに基づいて、前記その後の第１のキー文字の前記連続表示を予測するステップを含む請求項１に記載の方法。
【請求項９】
前記キーに関連付けられている前記キー文字すべてを一度に１つ表示する前記ステップが予測された順序で行われる請求項８に記載の方法。
【請求項１０】
前記予測された順序がアルファベット順を含む請求項８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データのキーパッド入力に関する。より詳細には、本発明は、複数の英数字が１つのキーに割り当てられたキーパッドを使用した英数字データの入力に関する。
【背景技術】
【０００２】
歴史的に、従来の「回転式」電話は、１〜９および０という番号が付けられた１０個の指穴を備える回転式ダイヤルを含んでおり、それによって、電話をかけるべき所望の電話番号の各数字を順次ダイヤルすることができた。トランジスタの時代では、１〜９および０とラベル付けされた１０個の数字キーを含むデュアルトーンマルチ周波数（ｄｕａｌ  ｔｏｎｅ，ｍｕｌｔｉｐｌｅ  ｆｒｅｑｕｅｎｃｙ：ＤＴＭＦ）キーパッドを備える電子電話が広く使われるようになり、従来の回転式電話に完全に取って代わった。
【０００３】
従来のＤＴＭＦキーパッドは、一般に、＊および＃とラベル付けされた、番号が付いていない２つの追加キーを含んでいた。番号付きのキーとの組合せで、従来のＤＴＭＦキーパッドのトポグラフィは、したがって、合計１２個のキーについて、０キーが＊キーと＃キーとの間の第４行に配置されている状態で、３×４のレイアウトを含んでいた。かなりの先見の明があり、ＤＴＭＦキーパッドの製造業者は、番号が付けられたキー（キー１を除く）に２６文字の英語のアルファベットも割り当て、ラベル付けして、ＤＴＭＦキーパッドで英数字データを入力できるようにした。普遍的ではないにしても、一般に、キー２には文字Ａ、Ｂ、およびＣがラベル付けされ、キー３にはＤ、Ｅ、Ｆ、キー４にはＧ、Ｈ、Ｉ、キー５にはＪ、Ｋ、Ｌ、キー６にはＭ、Ｎ、Ｏ、キー７にはＰ、Ｑ、Ｒ、Ｓ、キー８にはＴ、Ｕ、Ｖ、キー９にはＷ、Ｘ、Ｙ、Ｚがラベル付けされた。
【０００４】
アルファベット文字が割り当てられるキーを含むキーを複数回叩くことによって、所望のアルファベット文字の選択を可能にするために、様々な「マルチタップ（ｍｕｌｔｉｔａｐ）」技術が、適切な復号化回路と共に考案されている。最も普及しているマルチタップ技術は、キー上のアルファベット文字の位置に等しい回数、所望のアルファベット文字でラベル付けされたキーを押し、次いで、デフォルトのタイムアウト期間の間待つか、異なるキーを押すことを含む。例えば、文字Ｂが望まれる場合、キー２が２回押され、これは、文字Ｂがキー２の第２の位置に配置されているという事実によって表される。同様に、文字Ｃが望まれる場合、キー２が３回押され、これは、文字Ｃがキー２の第３の位置に配置されているという事実によって表される。マルチタップ技術および適切な復号化回路を教示する代表的な早期の特許には、米国特許第４，３０７，２６６号、第４，５３２，３７８号、および第４，６０８，４５７号などがある。
【０００５】
英数字ＤＴＭＦキーパッドの早期の実装によって、聴覚障害者は、従来の電話を使用して通信することができた。１９８０年代、英数字ＤＴＭＦキーパッドを備える電話は、英数字データの入力を必要とする双方向音声応答技術に欠かせなくなった。１９９０年代、英数字ＤＴＭＦキーパッドは、電話用小型メッセージサービス（ｔｅｌｅｐｈｏｎｙ  ｓｍａｌｌ  ｍｅｓｓａｇｉｎｇ  ｓｅｒｖｉｃｅｓ：ＳＭＳ）用の英数字データを入力するために広範に使用されるようになった。より最近では、従来の英数字ＤＴＭＦキーパッド、および１つまたは複数のキーに複数の英数字が割り当てられた他の低減キー（ｒｅｄｕｃｅｄ−ｋｅｙ）英数字キーパッドは、それだけに限定されないが、個人用デジタル補助装置やインスツルメンテーションなど、英数字データを入力するための他の多数の用途に、至る所で使用されていた。
【０００６】
残念ながら、上述したように、従来のマルチタップ技術では、単一の英数字を選択するために、それに関連付けられている複数文字（multicharacter）を「スクロール」するのに、複数回キーを押す必要がある。例えば、上述した従来のＤＴＭＦキーパッドでは、文字Ｂ、Ｅ、Ｈ、Ｋ、Ｎ、Ｑ、Ｕ、およびＸを選択するのに、それぞれのキー２〜９を２回押下する必要があり、文字Ｃ、Ｆ、Ｉ、Ｌ、Ｏ、Ｒ、Ｖ、およびＹを選択するのに３回押下する必要があり、文字ＳおよびＺを選択するのに、それぞれのキー７および９を４回押下する必要がある。実際に、複数の英数字が低減キー英数字キーパッドにおける特定のキーに割り当てられているときは必ず、関連の英数字をスクロールするのにそれぞれのキーをかなり押下する必要がある。
【０００７】
現在、それに関連付けられている特定の英数字をスクロールし、選択するための低減キー英数字キーパッドの複数文字キー（multicharacter keys）の押下数を最低限に抑えるための技術がいろいろ存在している。一般的なアプローチの１つは、辞書データベースを使用し、次いで、辞書内で最も一般的に使用される単語に一致する英数字の入力に基づいて、所望の英数字を予測することである。
【０００８】
例えば、Ｔｅｇｉｃ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ（ｈｔｔｐ：／／ｗｗｗ．ｔ９．ｃｏｍ）は、登録商標「Ｔ９」によって識別され、一連のキー入力を読み、こうしたキーに関連付けられている英数字に対応する言語固有の辞書から最も一般的に使用される単語を連続的に提示する辞書ベースのソフトウェアアプリケーションを提供する。例えば、英語辞書データベースは、単語「ｈｏｗ」を含み、それを、ＤＴＭＦキー入力シーケンス４−６−９に関連付けられている最も一般的に使用される単語として優先させることができる。次いで、キー入力シーケンス４−６−９を入力すると、ユーザによる選択のために、単語「ｈｏｗ」が表示され、提供される。「ｈｏｗ」は、対象の単語である場合、（６つのキー入力を必要とした上記のマルチタップ技術とは対照的に）３つのキー入力のみで選択されることになる。「ｈｏｗ」が対象の単語ではない場合、ユーザは、「次へ」キーとして指定されたキーを押下して、プログラムに、次によく使用される単語を表示するよう指示することができる。「次へ」キーを繰り返し押下しても所望の単語が表示されない場合、マルチタップ方法を使用して、所望の単語を手動で辞書に入力することができる。
【０００９】
Ｔ９は、実質的な商業的成功を達成したが、言語固有の辞書を格納するために、かなりのメモリを必要とする。さらに、辞書は、言語固有であるため、Ｔ９は、多言語の使用、またはしばしば頭文字、略語、科学用語などを使用する他のあまり一般的ではない実装には特に適していない。
【００１０】
そのＴ９ソフトウェアに関して、Ｔｅｇｉｃ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｉｎｃに委譲された代表的な特許。
米国特許                  名称
第６，３０７，５４９号    Reduced keyboard disambiguating system
第６，３０７，５４８号    Reduced keyboard disambiguating system
第６，２８６，０６４号    Reduced keyboard and method for simultaneous ambiguous and unambiguous text input
第６，０１１，５５４号    Reduced keyboard disambiguating system
第５，９５３，５４１号    Disambiguating system for disambiguating ambiguous input sequences by displaying objects associated with the generated input sequences in the order of decreasing frequency of use
第５，９４５，９２８号    Reduced keyboard disambiguating system for the Korean language
第５，８１８，４３７号    Reduced keyboard disambiguating computer
【００１１】
それに関連付けられている特定の英数字を選択するためにスクロールする低減キー英数字キーパッドのキーの押下数を最低限に抑える別の一般的な手法は、事前に定義されている言語的ルールに基づいて所望の英数字を予測する言語ベースアルゴリズムを使用することである。例えば、Ｅａｔｏｎｉ  Ｅｒｇｏｎｏｍｉｃｓ，Ｉｎｃは、他の文字の直前の入力に基づいて押下された複数文字キーの所望の文字を予測するいくつかの言語的ルールを含む登録商標「Ｌｅｔｔｅｒｗｉｓｅ」で売られるソフトウェアプログラムを提供する。言語的ルールの簡単な例は、直前に入力された文字が文字「ｑ」であるときはいつでも、複数文字（Ｔ、Ｕ、Ｖ）キー８を押下すると、文字「ｕ」を提供することである。というのは、文字「ｔ」または「ｖ」は言語的に適切ではないからである。使用された言語理論は、「Ｔｏｕｃｈ−ｔｙｐａｂｌｅ  ｄｅｖｉｃｅｓ  ｂａｓｅｄ  ｏｎ  ａｍｂｉｇｕｏｕｓ  ｃｏｄｅｓ  ａｎｄ  ｍｅｔｈｏｄｓ  ｔｏ  ｄｅｓｉｇｎ  ｓｕｃｈ  ｄｅｖｉｃｅｓ」という名称の米国特許第６，８８５，３１７号、および「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｉｍｐｒｏｖｅｄ  Ｍｕｌｔｉ−Ｔａｐ  Ｔｅｘｔ  Ｉｎｐｕｔ」という名称の米国特許第６，２１９，７３１号を含むＥａｔｏｎｉの特許に開示されている。
【００１２】
辞書ベースのＴ９同様、言語ベースのＬｅｔｔｅｒｗｉｓｅは言語固有である。Ｌｅｔｔｅｒｗｉｓｅは、あまり一般的ではない単語を使用する科学的な用途において好ましい場合がある。というのは、科学用語は、しばしば言語ベースであり、おそらくより少ないキー入力が必要になるからである。しかし、Ｔ９またはＬｅｔｔｅｒｗｉｓｅはいずれも、例えば軍事的な用途において、珍しい頭文字や略語を予測することができない。
【００１３】
前の文字（または単語）の入力に基づいて所望の文字（または単語）を予測するアルゴリズムを開示するさらに別の代表的な特許を、以下の米国特許において見つけることができる。
米国特許                  名称
第５，９５２，９４２号    Method and Device for Input of Text Messages from a Keypad
第５，９７４，１２１号    Alphanumeric Message Composing Method using Telephone Keypad
第６，０５２，４４３号    Alphanumeric Message Composing Method using Telephone Keypad
第６，０５４，９４１号    Apparatus and Method for Inputting Ideographic Characters
第６，１３７，８６７号    Alphanumeric Message Composing Method using Telephone Keypad
第５，８２８，９９１号    Sentence Reconstruction using Word Ambiguity Resolution
第５，９６０，３８５号    Sentence Reconstruction using Word Ambiguity Resolution
第５，０３１，２０６号    Method and Apparatus for Identifying Words Entered on DTMF Pushbuttons
第５，９０３，６３０号    Method and Apparatus for Specifying Alphanumeric Information with a Telephone Keypad
第６，１５０，９６２号    Predictive Data Entry Method for a Keyboard
第６，３４６，８９４号    Method and System for Intelligent Text Entry on a Numeric Keypad
第６，６４３，３７１号    Method and Apparatus for Alphanumeric Data Entry
第５，９１１，４８５号    Predictive Data Entry Method for a Keypad
第６，７９９，３０３号    Speed Typing Apparatus and Method
【発明の開示】
【発明が解決しようとする課題】
【００１４】
したがって、本発明の目的は、従来技術の方法の上述した欠点を克服する改良を提供するとともに、技術の進歩にかなり貢献する改良を提供することである。
【００１５】
本発明の別の目的は、１つまたは複数の英数字が各キーに割り当てられているキーパッドを使用した英数字データの入力のための装置および方法を提供することであり、押下されたキーに関連付けられている予測を定義するルールツリーが、文字の前の選択に基づいて構築されると共に、ルールツリーが予測を前に正しく定義した回数に基づいて重み付けされ、それによって所望の文字を予測する確率を向上させ、異なる言語スタイルまたは語彙を有する異なるユーザに迅速に適合できるようにする。
【００１６】
上記は、本発明の関連の目的の一部を概説している。これらの目的は、意図する本発明のより顕著な特徴および用途の一部の例示にすぎないと解釈されるものとする。他の多くの有益な結果は、開示された本発明を異なる方法で適用し、または開示の範囲内で本発明を変更することによって達成することができる。したがって、本発明の他の目的およびより完全な理解は、特許請求の範囲によって定義された本発明の範囲を添付の図面と共に併せ読むことに加えて、本発明の概要および好ましい実施形態の詳細な説明を参照にすることによって得られる。
【課題を解決するための手段】
【００１７】
本発明を要約する目的で、本発明は、押下される低減キーキーパッドの複数文字キーの所望の英数字を予測する方法および装置を含む。したがって、文字（以下、文字１、文字２、文字３など）から成る単語は、ＤＴＭＦ、および複数文字キーを有する他のキーパッドを使用して入力することができる。
【００１８】
より詳細には、文字１を選択するために特定のキーが押下されると、そのキーに関連付けられている文字のうちの１つに対応する先頭文字ルールリストがメモリから再度呼び出され、その文字が表示される。ユーザは、デフォルトの期間待つことによって、または異なるキーを選択することによって、こうした文字を選択することができ、そのキーのその文字に関連付けられている前に入力された英数字シーケンスのマルチレベル階層ツリーから成るその対応するルールツリーもメモリから再度呼び出される。表示された文字が所望の文字でない場合、ユーザが同じキーを押すこと（すなわちマルチタップ）によって要求を行った後、そのキーに関連付けられている別の文字が表示される。ユーザは、デフォルトの期間待つことによって、または異なるキーを選択することによって、こうした文字を選択することができ、同様にそのキーのその文字に関連付けられている前に入力された英数字シーケンスのマルチレベル階層ツリーから成るその対応するルールツリーもメモリから再度呼び出される。表示された文字が所望の文字ではない場合、所望の文字が選択されるまで（３文字が関連付けられているキーの場合、最大３回、４文字キーの場合、４回など）、ユーザの要求で、そのキーに関連付けられている他の文字が順次表示される。こうして文字１が選択される。
【００１９】
次いで、所望の文字２を選択するために次のキーが入力されると、ルールツリーは、直前に入力された文字１に基づいて文字２を予測するために再度構文解析される。同様に、所望の文字３を選択するために次のキーが入力されると、ルールツリーは、直前に入力された文字１および文字２に基づいて文字３を予測するために、さらに再度構文解析される。このプロセスは、前に構成された前の文字の数（すなわち、少なくとも１つ、好ましくは２つ、より好ましくは３つ）に基づいて、所望の単語のすべての文字が予測され、選択のために表示されるまで繰り返される。以前表示されなかった文字が選択されるときはいつでも、ルールツリーは、可能な選択としてそれを含むように変更される。したがって、ルールツリーは、より多くの文字が選択されるように、動的に構築される。さらに、前に選択された文字に基づいて表示された文字が選択される回数に対応する増分カウンタを使用して、その文字に重み付けし、それによって同じく前に選択された同じ文字に続くより少ないカウントの他の文字よりも、その文字を表示する。
【００２０】
単語が選択され、スペースが入力されると、この方法は、押下される次のキーに対応する先頭文字ルールリストに関連付けられているルールツリーをメモリから再度呼び出すことによって、それ自体を繰り返す。
【００２１】
重要なことに、ルールツリーは、ルールツリーを動的に「構築」するために、各使用時にメモリに格納される、前に入力された英数字シーケンスに基づき得る。したがって、ルールツリーは、実際の使用時に形成され、言語的ルールによって指示されたり、格納されている辞書によって示唆されたりしない。さらに、カウンタは、以前選択された文字に続く文字に重み付けするよう働く（すなわち、１つ、好ましくは２つ、より好ましくは３つの以前選択された文字）ため、所望の文字を予測する尤度は、頭文字、略語、科学用語などに等しく適用可能であり、異なる語彙、言語を使用する、または異なる書体を有する異なるユーザに迅速に適用可能である追加の目的に応える。
【００２２】
本発明の装置および方法は、１つまたは複数の文字が関連付けられている１つまたは複数のキーを有する任意のトポロジの任意のキーパッドと共に使用することができ、具体的には、ＤＴＭＦキーパッドとの使用に限定されない。さらに、本発明の装置および方法は、キーパッドの特定のキーに関連付けられている、日本語など、１つまたは複数の記号を含み得る言語を含めて、任意の言語と共に使用されてもよい。
【００２３】
例示の目的で、本発明による文字の予測の簡単な例は、以下の通りである。
【００２４】
単語「Ｍｉｓｓｉｓｓｉｐｐｉ」の前の入力の後、次のルールツリー（ボックスのそれぞれの上部は文字を表し、ボックスの下部は前に入力した２つの文字に続く文字の増分カウントを示す）および先頭文字ルールリストが構築されることになる。
【００２５】
【表１】
2009532773.tif 000003
【００２６】
システムはすでに単語Ｍｉｓｓｉｓｓｉｐｐｉを認識しており、上述したようにそのためのルールツリーを作成しているので、予測は、ユーザがＭｉｓｓｉｓｓｉｐｐｉの入力を試みる次の時に以下のように進む。
キーマッピングが以下のように与えられる：
キー１＝Ａ、Ｂ、Ｃ
キー２＝Ｄ、Ｅ、Ｆ
キー３＝Ｇ、Ｈ、Ｉ
キー４＝Ｊ、Ｋ、Ｌ
キー５＝Ｍ、Ｎ、Ｏ
キー６＝Ｐ、Ｑ、Ｒ
キー７＝Ｓ、Ｔ、Ｕ
キー８＝Ｖ、Ｗ、Ｘ
キー９＝Ｙ、Ｚ
５、３、７、７、３、７、７、３、６、６、および３のキーシーケンスは、前に入力された２文字それぞれに基づいて、以下を予測することになる。
【００２７】
【表２】
2009532773.tif 000004
【００２８】
それに対して、本発明の予測ルールのメリット無しに、ユーザが従来のマルチタップを使用して「Ｍｉｓｓｉｓｓｉｐｐｉ」を入力しようとすると、以下が起こることになる。
【００２９】
【表３】
2009532773.tif 000005
【００３０】
容易にわかるように、従来のマルチタップ技術を使用すると、文字選択の精度は、１１中７正しく、すなわち６３．６％であった。これに対して、本発明に従って単語「Ｍｉｓｓｉｓｓｉｐｐｉ」を事前入力してルールツリーを構築するために、精度は１００％であった。
【００３１】
以下の本発明の詳細な説明をよりよく理解でき、したがって技術への現在の貢献をより十分理解できるように、上記は、本発明のより適切で重要な特徴をかなり大まかに概説している。以下、本発明の特許請求の範囲の主題を形成する本発明の追加の特徴について説明する。本発明の同じ目的を実行するための他の回路およびアセンブリを変更したり、設計したりするための基礎として、概念および開示された特定の実施形態を容易に使用できることを当業者であれば理解されたい。また、こうした等価の回路およびアセンブリは、添付の特許請求の範囲に記載された本発明の意図および範囲から逸脱しないことも当業者であれば理解されたい。
【００３２】
本発明の性質および目的をより十分理解するために、以下の好ましい実施形態の詳細な説明を添付の図面と併せて参照されたい。
【００３３】
類似の参照文字は、いくつかの図面を通じて同じ部分を指す。
【発明を実施するための最良の形態】
【００３４】
図１は、曖昧なキーパッドＡ（１つまたは複数のキーに複数の文字が割り当てられているキーパッド）のキーの各押下が、不揮発性メモリＣおよびランダムアクセスメモリＤに動作可能に結合されている処理ユニットＢによって処理される本発明のテキスト予測機構１０のブロック図である。次いで予測は、グラフィカルユーザインターフェースＥによって表示される。
【００３５】
図２は、本発明の方法を実施するコンピュータプログラムの高レベルシステムフローを示すフロー図である。プログラムは、トリガイベント２を待つ待機状態１で開始し、トリガイベントは、各単語またはメッセージの末尾を含むことが好ましいが、あるいは、各キーの押下でもよく、または本発明が使用されるシステムに最も適したどんなものでもよい。
【００３６】
トリガイベント２が起こると、イベントカウンタ３は、システムがルールシステムにおいて行ったイベント／更新の回数を追跡するために、増分される。イベントカウンタ３は、ルールの更新が不揮発性メモリＣに保存されるときを決定するために使用される。しかし、不揮発性ストレージＣは、一般に遅いが、より速い不揮発性ストレージＣによって、更新をメモリに直接保存することができ、それによって、イベントカウンタ３の必要性がなくなる。
【００３７】
イベントカウンタ３を増分した後、４で動的に重み付けされる先頭文字ルールリストが更新され、次いで、５で動的に重み付けされるルールツリーが更新される。これらの更新４および５が終了した後、更新４および５の不揮発性メモリストレージＣへのコミット７を保証するために十分なトリガイベント２が行われたかどうかについての決定が６で行われる。コミット７を行う前に必要なトリガイベント２の回数は、アプリケーションに合わせることができることに留意されたい。例えば、ＣＰＵ時間が重要である場合、イベントカウンタ３は、多数のトリガイベント２が行われた後のみコミット７するようプリセットすることができる。これに対して、システムが大きい平均「アップタイム」を有していない場合、より少ないトリガイベント数によって、７でルール４および５をコミットすべきである。上記のいずれの場合も当てはまる場合、最初の２、３のコミット７は、ほんのわずかのトリガイベント２の後に起こり、システムが起動したままであるとき、コミット７は、ＣＰＵサイクルの保護を助けるために、累進的に大きい数のトリガイベント２で起こるようにしてもよい。
【００３８】
十分なトリガイベント２が実際に起こった場合、ルール４および５は、７で不揮発性ストレージＣにコミットされ、その後、イベントカウンタは、８でリセットされ、次いで、プロセスフローは、再度待機状態１に入る。十分なトリガイベントが起こらなかった場合、プロセスフローは、７でルール４および５を不揮発性メモリストレージＣにコミットすることなく、直接待機状態１に進む。
【００３９】
図３は、図２のルール４および５を７で不揮発性メモリストレージＣにコミットする機能を詳細に説明するフロー図である。第１のステップは、７１で先頭文字ルールリスト４の正確なコピーを行うことである。とりわけ、サイズを圧縮する必要はない。というのは、リストは、２６バイトのサイズ（英語のアルファベットの２６文字に基づく）にすぎないからである。しかし、各文字は、１バイトのストレージ空き容量を必要とするため、より大きいアルファベットは、比例してより大きいストレージ空き容量を必要とすることになり、したがって圧縮が望ましくなる場合があることに留意されたい。
【００４０】
ルールツリー５を格納する第１のステップは、ルール４および５を格納すべきではないカットオフ（ｃｕｔｏｆｆ）７２を決定することである。カットオフ７２は、ルールツリーが格納されるたびに再計算されることが好ましく、したがって、カウンタ７２を、ルールツリー５がなり得る任意の状態に適合させることができる。例えば、不揮発性ストレージＣが限定されている場合、格納前のルールツリーの切り捨てが好ましい。より詳細には、カットオフ７２は、ルールの現在の値と比較される。値がカットオフ７２未満である場合、ルールは格納されず、その子供も格納されない。というのは、子供は常に親より小さい値を有しているからである。
【００４１】
カットオフ７２が決定されると、ルールツリー５内の第１ノードまたはルートノード７３から始まり、ルートノードの値がカットオフ７２より大きいかどうかを決定するために、ルートノードの値とカットオフとの比較７４が行われる。ルートノードの値が大きい場合、ルールの値は、不揮発性ストレージＣに適合するように、７５で正規化される。
【００４２】
正規化７５は、その最上位ビットが切り捨てられることなくツリーで見つけられた最大ルール値が完全には不揮発性ストレージＣに適合しないときのみ行われるのが好ましい。ルールの値が７５で正規化され得る最大値は、どれだけの空き容量を使用できるかに応じて構成可能である。例えば、好ましい実施形態の一実装形態において、すべての値は、最大５１２または９ビットに正規化された。この最大値は、ルールを比較することができる粒度を制限する（８ビットと１０ビットのアナログ−デジタル変換器の間の差に似ている）。２５６や１２８などより小さい最大値が使用される場合、正規化プロセス７５のために、より多くのルールが同じカウントを有し得ることになる。好ましい実施形態のテストを介して、不揮発性ストレージＣに格納されるべきツリーからのルールの合計数の１〜２倍である最大値を有することが好ましいように思われる。
【００４３】
最大値の別の側面は、システムの適合性である。最大値がより大きい場合、新しいルールが前の主要なルールに潜在的に打ち勝つことができるようになる前に、より多くの回数発生しなければならないことを意味する。これによって、電源スイッチを切ってまたすぐに入れることなく、システムが長い間稼働することができる場合、さほど問題ではなくなる。しかし、頻繁に電源スイッチを切ってまたすぐに入れることが見込まれる場合、および最大値が過度に増大する場合、潜在的に「良い」ルールが「登りつめ」、切り捨てられないようになるために十分な時間がない可能性がある。逆に、最大値が低下しすぎると、新しいルールは、前の主要なルールにあまりにも速く打ち勝つことができ、潜在的に、システムのパフォーマンスの変動が起こる。
【００４４】
ルールは、７５で正規化されると、７６で不揮発性ストレージＣ内にあるツリーに挿入される。これは、簡単なツリートラバースおよび新しい場所へのデータのコピーを必要とする。７６でルールがコピーされると、格納の必要がある任意のルールが残っているかどうかを決定するために、７７でチェックが行われる。そうである場合、およびより多くのルールがある場合、７８で深さ優先方法で次のルールが選択される。このルールに関して、７４でその値がカットオフより大きいかどうかを決定するためにチェックが行われる。カットオフ未満である場合、７９で、その値およびその全子供は無視される。格納の必要があるすべてのルールが格納されるまで、ループが続行する。
【００４５】
図４は、図３におけるカットオフ７２を決定する機能のフロー図である。カットオフ重量計算（ｃｕｔ−ｏｆｆ  ｗｅｉｇｈｔ  ｃａｌｃｕｌａｔｉｏｎ）７２は、ルールツリー自体に加えて、２つの追加の入力を必要とする。第１に、７２１のツリー内に現在あるルールの実数、および７２２の不揮発性ストレージに格納することができるルールの最大数を決定する必要がある。次のステップは、ルールツリーをトラバースし、７２３でルールの重量のそれぞれを一時的に正規化することである。正規化計算７２３は、ルールを不揮発性ストレージＣにコミットするときに使用されるのと同じであることが好ましい。しかし、ルールが正規化されたので、７２４で各重量レベルでどれだけのルールが存在するかを決定し、それによってルールの重量のヒストグラムを生成するために、ツリー全体がトラバースされなければならない。いつ十分なルールが存在しているかを知り、次いで７２５で一時カウンタをゼロに初期化するための計算の調和に、簡単なカウントが使用される。
【００４６】
７２６で最大重量（好ましい実施形態の実装形態では５１２）で開始し、この重量のルールの出現回数が、７２７で、７２５でゼロに初期化された一時カウンタ、ＴＣＮＴに追加される。７２８で、ＴＣＮＴにおける値が格納できるルールの最大数ほど大きくない場合、プロセスは、７２９でシステムにおいて次に低い重量に流れ、７２７でそのカウントが再度一時カウンタに追加される。７２８で、ＴＣＮＴにおける値が依然として、格納できるルールの最大数ほど大きくない場合、プロセスは、７２９でシステムにおいて次に低い重量に再度流れる。７２８で格納できる最大値が超えると、カットオフ重量は、７２１０で現在のものより１重量上に設定される。これによって、存在する余地より多くのルールを不揮発性ストレージに書き込むことができないことが確実になるが、これは、おそらく未使用のストレージ空き容量があるだろうということも意味する。というのは、次に低い重量のルールの一部は、おそらく適合するからである。これらの他のルールが含まれる場合、起動時にルールのわずかに大きいデータベースがあるため、パワーサイクルを越えてパフォーマンスを向上させることは概念上可能である。しかし、好ましい実施形態による実験に基づけば、使用可能なスペース空き容量のすべてが使用されることを保証するときでさえ、もしあるとしても、非常にわずかの向上しかない。感知できるほどのパフォーマンスの向上がないのは、格納される最終ルールが、あまり一般的ではなく、したがって、システムの予測機能にそれほど追加がないためのようである。７２１０でカットオフ重量が決定されると、７２１１で、カットオフ重量を使用することができるように戻される。
【００４７】
図５は、キーの押下がシステムを通過するときの本発明の方法の操作を高レベルに示すフロー図である。システムは、待機状態で起動し、５１で、他の何よりも前にユーザからのキー押しが起こるまで待つことが好ましい。５２でキー押しが受信されると、５３で、更新イベントが起こったかどうかを決定するためにチェックが行われる。好ましい実施形態では、更新イベントは、メッセージが保存または送信されることを意図することを示すキー押しである。しかし、別の実施形態において、更新イベントは、システムの要件に応じて任意の他のタイプのイベントとすることができる。好ましい実施形態において、イベントが起こった場合、５４で先頭文字ルールリスト、および５５でルールツリーが更新され、その後、５５で待機状態への戻りが起こる。別の実施形態において、更新の後、別のやり方でキー押しを処理し続けることも依然として可能である。イベントが起こらなかった場合、５６で、これが反復キー押し（ｒｅｐｅａｔｅｄ  ｋｅｙｐｒｅｓｓ）（言い換えれば、ユーザが同じキーを連続して２回以上押した）であるかどうかを決定するためにチェックが行われる。反復キー押しである場合、５７で、次に最適な予測が確認される。これが起こる２つの主な理由がある。第１は、最初に予測された文字は正しくなかったということであり、ある割合で起こり得る。もう一方の理由は、ユーザが単に間違ってそのボタンをもう一度押したということである。キー押しが反復キーではなかった場合、５８で、次の文字についての第１の予測が確認される。
【００４８】
予測は、ステップ５７または５８のいずれかから来て、何が予測されたかをユーザが見ることができるように、５９で、一時的に表示バッファに挿入される。次いでユーザは、予測が正しいかどうかを決定する。ユーザは、現在の予測を望む場合、５１０で予測を永続的にし、これによって、５１１でカーソルが次の位置にシフトされる。とりわけ、カーソルは、異なるキー押しにより、またはタイムアウトから、自動的に進む通常の機能を有し得る（いずれの場合でも、本実装形態は、予測システムの機能に関係しない）。カーソルが進んだ後、プロセスフローは、ユーザが別のキーを押してシステムが再度開始するまで、待機状態に戻る。
【００４９】
図６は、図５の５８における第１文字の予測の機能を詳細に説明するフロー図である。５８で第１の予測を行うと、システムは、５８１の押されたキー、およびある場合、５８２のシステムに入力されている前の文字を渡す。第１に、５８３で任意の前の文字が渡されたかどうかを決定するためにチェックが行われる。前の文字が提供されなかった場合、プロセスは、それが新しい単語の先頭であることがわかり、５８５で、先頭文字ルールリストにおける予測が探索される。しかし、前の文字が少なくとも１つある場合、５８４で、予測を探索するためにルールツリーが使用される。探索５８４および５８５は、０から「キー当たりマッピングされる最大文字」までを含む可変サイズのリストを戻す。文字が戻されない場合、前の文字および押されたキーに関係するルールが現在存在していないことを意味し、または、ある単語の第１の文字の場合、押されたまさにそのキーに関係するルールが存在しないことを意味する。複数の文字を戻す理由は、システムが、あるキーにマッピングされるすべての文字を、その状況に最良の順に順序付けなければならないからである。
【００５０】
例えばあるキーに「Ａ」、「Ｂ」、「Ｃ」がマッピングされていると仮定すると、これら３つの文字に６通りの可能な順序がある。Ａ、Ｂ、Ｃが最もありそうな順序である場合もあれば、Ｃ、Ａ、Ｂが最適な順序である場合もある。ルールツリーは、存在するルールに基づいて決定できるものをすべて決定する。必要なルールがないために、ルールツリーが第１文字についての予測を行うことしかできない場合もあれば、ルールツリーが必要とするルールを有している場合、すべての３文字を順序付けることができる場合もある。
【００５１】
ルールツリーによって予測が行われると、５８６で、そのキーにマッピングされたすべての文字が予測に含まれるかどうかを決定するためにチェックが行われる。すべての文字を予測できなかった場合、残りは、６７でアルファベット順に書き込まれる。好ましい実施形態において、より知的な順序付けが試行されたが、パフォーマンスの向上がそれほど得られなかった（＜０．５％）ため、こうしたより知的な順序付けが必要とする追加の複雑さをなくすことがより価値があると確信されることに留意されたい。
【００５２】
システムは、ユーザがキー押しで大文字、小文字、または数字を入力したいかどうかの推測を助けるための追加の発見的方法を含む。したがって、システムは、５８８で、所望の文字ケースまたは数字に達するのに必要なキー押しの回数を低減するように、予測を順序付ける。発見的方法は、単に、入力された最後の文字のケースを追跡するだけであり、または、最後の文字が数字であった場合、システムは、ユーザがケースを切り替えるまでこのケースを維持し、この時点で、新しいケースを覚える。
【００５３】
例えば、前の文字が大文字であった場合、予測の順序付けは、大文字、数字、小文字となり得る。前の文字が小文字であった場合、順序付けは、小文字、数字、大文字となり得る。前の文字が数字であった場合、順序付けは、数字、大文字、小文字となり得る。
【００５４】
予測は、完了すると（好ましい実施形態では、７文字、大文字、数字、および小文字）、５８９で、その後のＧｅｔＮｅｘｔＰｒｅｄｉｃｔｉｏｎステップへの呼び出しが処理の遅延なしに非常に効率的であるように格納される。５８１０で、格納された予測リスト内の現在の予測の位置は、第１の予測が戻されることを示すために、ゼロに初期化されることが好ましい。最後に、５８１１で単一文字の予測が戻される。
【００５５】
図７は、図６における次に最適な予測５７を探索する機能を詳細に説明するフロー図である。第１のステップは、５７１で予測リストにおける位置を示すカウンタを増分することである。予測リストは、キー押しが表すことができる大文字および小文字および数字を含む。予測が「折り返す」ため、５７２で、リストの末尾に到着したかどうかを決定するためにチェックが行われる。ｙｅｓである場合、５７３で、フローがリストを折り返すように、位置カウンタがゼロに戻される。次のステップは、５７４で現在のカウンタ値に基づいて予測を取り出すことであり、５７５で最後にその値を戻す。
【００５６】
図８は、図６の５８５における先頭文字ルールリストにおいて予測を探索する機能を詳細に説明するフロー図である。第１の文字を探索することは、５８５１で、押されたキーである単一の入力で開始する。第１文字ルールを検索することは、５８５２でキー押しに関連するすべてのルールが見つけられるまで行われる。好ましい実施形態において、所与のキーにマッピングされる文字ごとに１つ、最大３つのルールを見つけることができる。次に、５８５３で、その重量に基づいて見つけられたルールは、ソートされる。最後に、５８５４および５８５５で、ソートされた予測および見つけられたルールの数が戻される。
【００５７】
図９は、図６の５８４における予測を行うためにルールを探索する機能を詳細に説明するフロー図である。ルールツリー探索６４は、押されたキーである２つの入力、および５８４１および５８４２のすでに入力されている単語の前の文字で開始する。探索は、５８４３で、ルールツリーのルートノードで開始する。ルールツリーの各ノードは、実際には、子ノードを有する機能をそれぞれ有するルールのリストとすることができるため、ツリーの分岐因子は、かなり大きい可能性がある（すなわち、予測アルファベットにおける文字の数と同じぐらい大きい）ことに留意されたい。
【００５８】
現在の（第１）ノード上のリストを移動すると、５８５４で、与えられた前の文字の第１文字が見つけられる。例えば、文字列「ｔｈｅｉ」が渡されると、探される文字は、「ｔ」である。次のステップは、５８４５で、文字が実際に見つけられたかどうかをチェックすることである。文字が見つけられない場合、５８４１３で、前の文字列が左に１場所シフトされて、新しい第１の文字を提供する。例えば、「ｔｈｅｉ」の最初の文字列は、シフト後「ｈｅｉ」のようである。続行前に、依然として処理すべき前の文字があるかどうかを決定するためにチェックが行われる。この例では、５８４１４で、まだ３文字が残されている。新しい前の文字列に関して、５８４４および５８４５で、現在のノードにおいて、第１文字（例えば「ｈ」）が再度探される。今回ルールが見つかった（例えば「ｈ」について）場合、子ノードを有しているかどうかを決定するためにチェックが行われる。言い換えれば、５８４６で、このルールから通じるツリーに「別のレベルがあるか？」である。もしもない場合には、次のレベルのルールを見つけることはできない（例えば、「ｅ」についてルールを見つけることはできない、「ｉ」について第３レベルのルールを見つけることはできないなど）。これは、ツリーにまだルールが追加されていないため、システムが文字のこの組合せをまだ見たことがないことを意味する。また、別のレベルがない場合、これは、したがってより短い前の文字列を使用する必要があることを意味する。現在の例では、これは、前の文字列が、現在「ｅｉ」のようであることを意味することになる。しかし、第１レベルの第１文字（「ｈ」ルールなど）から遠ざかるツリーにおいて別のレベルがある場合。次に、５８４７で、処理すべき任意の別の前の文字が存在するかどうかが決定される。本例では、存在するため、５８４８で、現在のレベルポインタがツリーにおける次のレベル（すなわち、「ｈ」ルールの子ノード）に移動される。
【００５９】
ツリーにおける次のレベルで、現在のレベルで次の前の文字（「ｅ」など）についての検索が行われる。次の前の文字が存在しているかどうかをチェックするプロセスが繰り返される。見つけられない場合、この深さ優先検索パスは、再度行き止まりであり、前の文字列が１つだけ短縮され、再度検索が行われることを意味する。一方、現在のレベルで（「ｅ」など）見つけられた場合、（「ｅ」など）ルールから遠ざかるツリーにおいて、さらに別のレベルがあるかどうかを決定するためにチェックが行われる。そうである場合、前の文字列における次の文字（「ｉ」など）についての検索が再度行われる。すべての前の文字列と同じプロセスが、この文字列に適用される。
【００６０】
文字（「ｉ」など）についてのルールが見つけられると仮定して、プロセスは、ステップ５８４５に戻る。現在の例において、文字「ｉ」は、元の前の文字列「ｔｈｅｉ」における最後の文字であったことを思い出すと、次のステップは、５８５６で、「ｉ」から遠ざかるツリーにさらに別のレベルがあるかどうかを再度決定することである。ない場合、前の文字列は、再度短縮される。しかし、別のレベルがある場合、前の文字列において別の文字列があるかどうかを決定するために、チェックが再度行われる。現在の例では、それ以上ないため、５８４１０で、所与のキー押し入力に基づいてどの文字が予測されるかを確認するために、次のレベルが検査される。
【００６１】
例えば、ユーザが単語「ｔｈｅｉｒ」を入力しようとしており、文字「ｐ、ｑ、ｒ」がキー６にマッピングされていると仮定する。そのキー押しおよびアルファベットのキーマッピングに基づいて、ツリーにおける次のレベルで、文字「ｐ、ｑ、ｒ」のルールが探される。さらに、次の（ルール，値）対、（ｒ，１０）、（ｐ，３）、および（ｑ，６）が見つけられたと仮定する。こうした場合、「ｒ」のルールは、見つけられた「最強」ルールであるため、予測された第１文字であることになる。最強ルールは、最大数の前の文字を使用して見つけられ、それと同じノードで見つけられたすべてのルールの最大値を有するルールと定義することができる。複数のルールが存在する場合、５８４１１で、最大値が一番になる状態でソートされることが好ましい。
【００６２】
ルールのいくつかが存在している場合、５８４１２で、そのすべてが探索されたかどうかを決定するためのチェックが行われるべきである。これは、システムのキーマッピングに応じて、各キーがキー当たり最大２、３、４、またはそれ以上の文字を有することができることを意味し得る。最も情報を得た上での予測を可能にするために、すべてのルールが見つけられることが好ましい。これまでに、最大の、この場合３つのルールのうちの１つのみが見つけられているため、プロセスフローは、５８４１３で折り返して、まだ残りがあると仮定して、探される前の文字数を再度低減する。前の文字が残っている場合、入力としてより少ない文字に関して見つけられたすべてのルールは、常に、最初の時に見つけられたものに対する２次予測であり得る。言い換えれば、それらは、有する値に関係なく、予測リストの一番前の位置を決して引き継ぐことができないようにソートされる。前の文字がなくなる、またはこのキー押しについての最大数の予測が見つけられると、５８４１５で予測および見つけられた予測数が戻される。
【００６３】
図１０は、５８７７ですべての文字を予測できない場合、文字をアルファベット順に書き込む機能を詳細に説明するフロー図である。より詳細には、予測ツリーが完全な予測を提供できない場合、予測の空のスロットは、押されたキーにマッピングされる残りの文字で書き込まれる。これを行うために、５８７１および５８７２の押されたキーおよび予測された文字数である２つの入力が提供される。例えば、各キーにマッピングされた最大３文字が存在し、これらの文字のうちの１つのみを予測することができた場合、残りの２文字が書き込まれる必要がある。
【００６４】
上記の好ましい実施形態のテストを介して、性能の向上の大部分が予測リストにおける第１文字のより正確な予測から得られていると決定された。また、残りの予測を書き込む「知的な」方法が使用されたとき、システムのパフォーマンスは、非常にわずかの割合だけしか向上しなかったことも決定された。この向上は、ユーザが気付かないほど向上された予測パフォーマンスが小さく、「知的な」書き込み操作を行うのに必要なオーバーヘッドを克服するように思われなかった。そのことを考慮に入れて、残りのすべての文字は、好ましくは、アルファベット順であると「予測」されると考えられ、５８７３で、それに応じて書き込まれる。予測リストがいっぱいになると、プロセスフローは、５８７４で、リストを使用することができるように戻す。
【００６５】
図１１は、５４で先頭文字ルールリストが更新される機能を詳細に説明するフロー図である。より詳細には、先頭文字ルールリストの更新は、５４１で少なくとも１つの文字を含む文字列の入力のみを必要とするプロセスである。システムは、フォーマットされていない任意の文字列を処理することができる。言い換えれば、予測に使用されない文字は、任意の問題なしに文字列内に存在することができる。好ましい実施形態において、システムが予測で使用されていない文字に遭遇すると、それを余白および単語の切れ目と解釈する。
【００６６】
５４２で文字列における第１文字から開始して、５４３でそれが有効な予測アルファベット文字であるかどうかを決定するために、チェックが行われる。そうである場合、５４６で先頭文字ルールリストにおけるその文字の重量／値が増分される。次のステップは、その単語の第１文字を見つけるために、次の単語の先頭を見つけることである。現在の単語が終了するのがいつか、または次が始まるのがどこかがわかっていないため、これは、一度に１文字行われる。そのため、まず、プロセスフローは、５４７で次の文字に移動し、５４８でそれが有効な予測アルファベット文字であるかどうかを決定するために、チェックが行われる。そうである場合、５４９で、文字列に任意の文字が残されているかどうかを決定するために、チェックが行われる。ない場合、プロセスは終了するが、少なくとも１つ存在している場合、プロセスは、引き続き、その後の各文字に移動して、それらが有効な予測アルファベット文字であるかどうかをチェックする。有効ではないものが見つかった場合、ステップ５４４で、より多くの文字についてのチェックが行われる。依然として文字が残っている場合、５４５において、ラインにおける次の文字が確認される。この新しい文字が有効な予測文字でない場合、サイクルは、次の有効な文字が見つかるまで、文字を通じて続く。これは、単語の間に存在し得る任意の余白を進むために使用される方法である。次の有効な文字を見つけると、その値は、ルールリストにおいて再度更新され、プロセスは、次の単語の第１文字を見つけるために再度開始される。これは、元の入力文字列に文字が残らなくなるまで続行される。
【００６７】
図１２は、ルールツリーが更新される機能を詳細に説明するフロー図である。ルールツリーの更新は、５５１で少なくとも１つの文字を含む文字列の入力のみを必要とするプロセスである。システムは、フォーマットされていない任意の文字列を処理することができる。言い換えれば、予測に使用されない文字は、任意の問題なしに文字列内に存在することができる。好ましい実施形態において、システムが予測で使用されていない文字に遭遇すると、それを余白および単語の切れ目と解釈する。
【００６８】
５５２で文字列における第１文字から開始して、５５３で第１の有効な予測アルファベット文字についての線形検索が行われる。有効な文字が見つかるとすぐに、５５４で前の文字リストに追加される。例えば、渡された文字列が「ハロー、これはテストです」であるとする。前の文字リストは、現在、「Ｈ」のようである。予測システムは、予測を行うために使用されるべき前の文字の最大数を限定する機能を有する。好ましい実施形態の実装形態において、システムのパラメータの残りを考えると、３つの前の文字が最もよく働いたことがわかったが、簡潔にするために、この例では、２つの前の文字のみを使用する。
【００６９】
５５５で、前の文字リストがその最大より大きい長さを有するかどうかを決定するために、チェックが行われる。この例の場合、まだ制限に到達していないため、プロセスは、５５７でルールツリーのルートノードで開始し、次いで、５５８で第１の前の文字「Ｈ」を見つけることができるかを調べるために、検索を行う。予測システムは、大文字と小文字を区別しないことが好ましいため、すべては、まるで小文字であるかのように処理されることに留意されたい。次に、５５９で、現在のノードにおいて対応するルールが見つけられたかどうかを決定するために、チェックが行われ、この場合、各ノードは、文字値対またはルールのリンクされたリストとすることができる。例えば、文字「Ｈ」が見つけられなかったと仮定すると、「Ｈ」が新しい単語における第１文字であったという事実を追跡するために、新しいルールが作成されることになる。これは、ルールのこのノードのリストの末尾に新しいルールを追加することによって行われる。ルールを追加した後、５５１２で、その値、カウンタ、または重量は、１に等しくなるように設定される。これは、ルールが単一回のみ起こったことを示す。この値は、予測を行うときに他のルールと比較するために、後でも使用される。
【００７０】
ルールが追加されると、５５１３で、次の文字が予測アルファベット内にあるかどうかを決定するために、チェックが行われる。そうでない場合、５５１４で、前の文字リストが消去され、これは、現在の単語が終了したことを意味する。前の文字リストを消去した後、５５１５で予測アルファベットから別の文字が見つかるまで、入力文字列に再度線形検索が行われる。この時点から、この例での文字「Ｈ」と同じサイクルが続行される。次の有効な文字についての検索が行われる例に戻ると仮定すると、見つけられる次の文字は、「ｅ」である。これは、有効であるため、５５４で前の文字リストに追加され、それによって、「Ｈｅ」が生成される。５５５で、それほど多くの前の文字が検査されないことを確実にするためにチェックが行われ、次いで、５５７および５５８で、ツリーにちょうど追加された「Ｈ」ルールを見つけるために、プロセスがルートツリーレベルで再度開始する。５５９で文字が見つけられると、５５１０で使用すべき前の文字がさらにあるかどうかを決定するために、チェックが行われる。この例では、「ｅ」があるため、プロセスは、５５１１で次のツリーレベルに進む。
【００７１】
「Ｈ」ルールの子ポインタをたどることによって、次のツリーノードに到達する。ここでは、５５８で、「ｅ」について、現在のノードにおいて検索が行われる。５５９でルールが存在しないことを決定した後、「ｅ」についての新しいルールが現在のノードのルールリストに追加され、それを１の値に設定する。ルールが追加された後、次の文字を取得するプロセスが続行し、ステップ５５１３および５５１４に至る。
【００７２】
この時点で、前の文字リストは、「Ｈｅｌ」のようである。ステップ５５５で、最大深さが２であると仮定されると、プロセスはステップ５５６に進み、前の単語リストの第１文字が削除され、それによって、「ｅｌ」の結果として生じたリストを提供する。ルールノードでルール「ｅ」、および「ｅ」ルールの子ノードで「ｌ」ルールを見つけるために、同じプロセスが繰り返される。これらのルールの両方がすでに存在すると仮定する。したがって、このプロセスは、ステップ５５１０に進み、見つけるべき前の文字がさらに存在するかどうかを決定するために、チェックが行われる。現在の例において、「ｌ」が最後の前の文字であるため、プロセスは、ステップ５５１６に進み、「ｌ」ルールの値は、１だけ増分される。
【００７３】
次のステップは、５５１７で、前の文字リストにおける第１の文字をマスクオフする（すなわち、削除するのではなく、ただ無視する）ことである。視覚化のために、「＊」は、マスクされた前の文字を表すと仮定し、これによって、あたかもリスト「ｌ」であるかのようにシステムが処理する「＊ｌ」の新しい前の文字リストがもたらされる。次のステップは、５５１８で前の文字リストに残されているマスクされていない文字が存在するかどうかをチェックすることである。現在の例で、文字「ｌ」が依然としてマスクされていないので、プロセスフローは、ステップ５５７に移動し、５５７および５５８で、現在第１の前の文字となったものについて、ルートノードで再度検索が行われる。ルートノードにおいて「ｌ」についてのルールが存在すると仮定すると、それは、５５９、５５１０、５５１６で増分される。次のステップは、第１文字をマスクオフすることである。現在のものの前のサイクルは、「＊ｌ」を提供するためにマスクされた文字列「ｅｌ」を有していたことを思い出すと、今回、「ｌ」は、第１文字であり、したがって、５５１７で、文字列「＊＊」がもたらされる。５５１８で、任意のマスクされていない文字があるかどうかを決定するために、チェックが行われる。
【００７４】
前の文字リストが完全にマスクされているため、プロセスフローは、ステップ５５１９に移動して、すべての文字をマスクオフし、それによって、文字列を「＊＊」から「ｅｌ」に変更し直す。ループに戻って開始し、次の文字が探されて、結果として「ｅｌｌ」をもたらす別の「ｌ」を見つけ、これは、ツリーの深さ制限のために「ｌｌ」に低減される。適切な更新が行われ、次いで、次に新しい文字列「ｏ」は、「ｌｌｏ」をもたらし、これは、ツリーの深さ制限のために、「ｌｏ」に低減される。最後に、これらが更新された後、５５１３で次の文字列がチェックされ、＜スペース＞文字が見つけられる。これは、有効な予測アルファベット文字ではないため、プロセスフローは、ステップ５５１４に進んで、前の文字リストの全内容を削除する。これは、現在の単語の末尾が見つけられ、システムが次の新しい単語を処理する用意ができるために行われる。ステップ５５１５で、次の有効な予測アルファベット文字が見つかるまで、それについての検索が続行する。これによって、システムは、各単語を分離し得る任意の数の無効なまたは余白の文字を扱うことができる。
【００７５】
この全プロセスは、元の入力文字列内のすべての文字が処理されるまで続行する。
【図面の簡単な説明】
【００７６】
【図１】曖昧なキーパッド（１つまたは複数のキーに複数の文字が割り当てられているキーパッド）のキーの各押下が、不揮発性メモリおよびランダムアクセスメモリに動作可能に結合されている処理ユニットによって処理される本発明の装置を示すブロック図である。
【図２】本発明の方法を実施するコンピュータプログラムの高レベルシステムフローを示すフロー図である。
【図３】ルールをメモリストレージにコミットする機能を詳細に説明するフロー図である。
【図４】カットオフ重量計算を決定する機能のフロー図である。
【図５】キーの押下がシステムを通過するときの本発明の方法の操作を高レベルに示すフロー図である。
【図６】第１文字の予測の機能を詳細に説明するフロー図である。
【図７】次に最適な予測を探索する機能を詳細に説明するフロー図である。
【図８】先頭文字ルールリストにおいて予測を探索する機能を詳細に説明するフロー図である。
【図９】ルールツリーにおいて予測またはルールを探索する機能を詳細に説明するフロー図である。
【図１０】すべての文字のうちの１つまたは複数を予測できない場合、任意の残りの文字をアルファベット順に書き込む機能を詳細に説明するフロー図である。
【図１１】トリガイベントが起こらない場合、先頭文字ルールリストが更新される機能を詳細に示すフロー図である。
【図１２】トリガイベントが起こらない場合、ルールツリーを更新するステップのフロー図である。
【図１】
2009532773.tif 000006
【図２】
2009532773.tif 000007
【図３】
2009532773.tif 000008
【図４】
2009532773.tif 000009
【図５】
2009532773.tif 000010
【図６】
2009532773.tif 000011
【図７】
2009532773.tif 000012
【図８】
2009532773.tif 000013
【図９】
2009532773.tif 000014
【図１０】
2009532773.tif 000015
【図１１】
2009532773.tif 000016
【図１２】
2009532773.tif 000017
【手続補正書】
【提出日】平成20年11月10日(2008.11.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
低減キーキーパッドの複数文字キーを押下することによって所望の単語の文字を予測する方法であって、
（１）前記複数文字キーのユーザ選択の組に応答して、前記複数文字キーを使用してその後識別される単語の後続の単語文字を連続して予測し、表示するためのルールのマルチレベル階層ツリーを自動的に動的に構築するステップと、
（２）前記複数文字キーの第１のキーの選択に応答して、所望の単語の第１の単語文字に対応する先頭文字ルールリストにアクセスするステップであって、
前記アクセスするステップに続いて、前記第１のキーで識別された前記キー文字の組を一度に１つ予測されたシーケンスで表示し、前記キー文字が前記所望の単語の前記第１の単語文字であるとき、前記表示されたキー文字を前記第１の文字キーとして選択するステップと、
（３）前記複数文字キーの第２のキーの選択に応答して、前記所望の単語の前記後続の単語文字を連続して予測し、表示するためのルールの前記マルチレベル階層ツリーを含む動的に構築されたルールツリーを処理し、前記所望の後続の単語文字が表示されるとき、その選択を可能にするか、新しい所望の単語文字のマルチタップによって選択を可能にするステップと
を含む方法。
【請求項２】
前記ルールによって予測された前記後続の単語文字が前に選択された回数に基づいて、前記所望の単語の前記後続の単語文字の各ルールの予測を動的に重み付けするステップをさらに含む請求項１に記載の方法。
【請求項３】
各ルールを動的に重み付けする前記ステップが、選択された少なくとも１つのすぐ前の単語文字の後に、前記後続の単語文字が前に選択された回数に基づいて重み付けするステップを含む請求項２に記載の方法。
【請求項４】
前記動的に構成されたルールツリーに動的に重み付けする前記ステップが、前記同じく前に押下されたキーの後のその後の予測に関連付けられている前記予測に重み付けするためにカウンタを増分するステップを含む請求項３に記載の方法。
【請求項５】
前記前の予測が前記所望の文字を正しく予測した回数に基づいて、他の所望の文字のその後の予測の前記動的な重み付けを正規化するステップをさらに含む請求項２に記載の方法。
【請求項６】
前記動的に構成されたルールツリーから前記最低の重量を有する１つまたは複数のルールを削除するステップをさらに含む請求項２に記載の方法。
【請求項７】
各文字が選択された後、所望の単語の前記所望の文字のすべてが選択された後、または複数の所望の単語の前記所望の文字のすべてが選択された後、前記動的に構成されたルールツリーを更新するステップをさらに含む請求項１に記載の方法。
【請求項８】
前記第１のキーの前記キー文字を表示し、前記キー文字が前記所望の単語の前記第１の単語文字であるとき、前記表示されたキー文字を前記第１の文字キーとして選択する前記ステップが、前記第１の文字キーが選択される回数に基づいて前記選択に重み付けし、次いで、それに基づいて、前記その後の第１のキー文字の前記連続表示を予測するステップを含む請求項１に記載の方法。
【請求項９】
前記キーに関連付けられている前記キー文字すべてを一度に１つ表示する前記ステップが予測された順序で行われる請求項８に記載の方法。
【請求項１０】
前記予測された順序がアルファベット順を含む請求項８に記載の方法。
【国際調査報告】
2009532773.tif 000018