(57)【要約】簡潔言語学データを生成かつ使用するシステムおよび方法が提供される。コーパス中に出現するワードの頻度が算出される。これらワード中の特有の文字の各々が、文字インデックスにマップされ、そしてこれらワード中の文字が文字インデックスで置き換えられる。文字のシークエンスが置換インデックスにマップされ、そしてこれらワード中の文字のシークエンスがこの置換インデックスで置換される。これらワードは、共通プレフィックスによってグループ分けされ、そして各プレフィックスが、このプレフィックスで開始するワードのグループの情報を位置決めするためにマップされる。【特許請求の範囲】
【請求項１】
簡潔言語学データを生成するシステムであって：
コーパス；および
言語学データアナライザを備え、
ここで、該言語学データアナライザが、該コーパス中に出現するワードの頻度を算出し、該ワード中の各特有の文字を文字インデックス中にマップし、該ワード中の各特有の文字を、該文字がマップされる文字インデックスで置き換え、該ワード中に出現する文字のシークエンスを置換インデックスにマップし、各ワード中の各文字のシークエンスを該文字のシークエンスがマップされる置換インデックスで置き換え、該ワードを、各グループが共通プレフィックスで開始するワードを含むグループに整列し、そして各プレフィックスを、該プレフィックスで開始するワードのグループのための位置情報にマップし；そして
ここで、該簡潔言語学データが、該特有文字、該文字インデックス、該置換インデックス、該位置情報、該ワードのグループおよび該ワードの頻度を含む、システム。
【請求項２】
さらに、ユーザーインターフェースを備え：
該ユーザーインターフェースが：
テキスト入力デバイス；および
テキスト出力デバイス；および
テキスト入力論理ユニットを備え、
ここで、該テキスト入力論理ユニットが、該テキスト入力デバイスからのテキストプレフィックスを受け、該プレフィックスで開始する簡潔言語学データからの複数の推定ワードを検索し、そして該推定ワードを、該テキスト出力デバイスを用いて表示する、請求項１に記載のデバイス。
【請求項３】
前記テキスト入力デバイスがキーボードである、請求項２に記載のシステム。
【請求項４】
前記キーボードが縮小キーボードである、請求項３に記載のシステム。
【請求項５】
前記ユーザーインターフェースおよび前記テキスト入力論理ユニットがモバイル通信デバイス上で履行される、請求項２に記載のシステム。
【請求項６】
複数のワードのための簡潔言語学データ構造であって、
ここで、該ワードがグループに組織化され、各グループが共通プレフィックスを有するワードを含み、該簡潔言語学データ構造が：
該ワード中の各特有の文字から構成されるアルファベット；
該アルファベット中の各文字を文字インデックスにマップするための文字マッピングテーブル；
該ワードからの文字のシークエンスを置換インデックスにマップするための置換テーブル；
該ワードを記憶するための複数のワード定義テーブルであって、各ワード定義テーブルが該グループの１つに含まれるワードの各々を記憶するワード定義テーブル；および
該ワード定義テーブルを位置決めするためのオフセットテーブルを備え、
ここで、該共通プレフィックスの各々について、該オフセットテーブルが該共通プレフィックスで開始するワード定義テーブルの位置を含み、
ここで、該ワード定義テーブル中ワードの各々が、該ワード中の各文字を該文字が該文字マッピングテーブルによりマップされる該文字インデックスで置換されることにより、かつ該ワード中に出現する該置換テーブルからの文字の各シークエンスを、文字の該シークエンスがマップされる該置換インデックスで該置換テーブルによって置換することによりコード化され；そして
ここで、各ワード定義テーブル中のワードに対する該共通プレフィックスが除去されている、簡潔言語学データ構造。
【請求項７】
前記ワードと関連する複数の頻度をさらに備え、ここで、前記ワード定義テーブルが該頻度を記憶する、請求項６に記載の簡潔言語学データ構造。
【請求項８】
前記頻度が、それらが所定の範囲内にあるように規格化され、そしてここで、ワードの各グループについて、最大頻度を有するグループのワードの頻度が完全な正確さで記憶され、そして該グループ中の残りのワードの頻度が最大頻度のパーセントとして記憶される、請求項７に記載の簡潔言語学データ構造。
【請求項９】
請求項７に記載の簡潔言語学データ構造であって、
ここで、前記ワード定義テーブルの少なくとも１つが：
該ワード定義テーブルによって記憶されるワードを記憶するための複数のローカルワード定義テーブルであって、各ローカルワード定義テーブルが、該ワード定義テーブル中のワードに対する共通プレフィックスより長い共通プレフィックスを有するワード定義テーブルによって記憶されるワードを記憶する、ワード定義テーブル；
該ワード定義テーブルの各々を位置決めするためのローカルオフセットテーブル；
該ローカルワード定義テーブル中のワード中の各文字をローカル文字インデックスにマップするためのローカル文字マッピングテーブル；
該ワード定義テーブル中に含まれるグループ中のワードの最も高い頻度と関連するワードのローカルワード定義テーブル中の位置を記憶するためのホットワードテーブル；および
該ワード定義テーブル中に含まれるグループ中のワードの最も高い頻度と関連するワードを記憶するための例外テーブルを備え、
ここで、該ローカルワード定義テーブル中のワードの各々が、該ワード中の文字を該文字が該ローカル文字マッピングテーブルによってマップされるローカル文字インデックスで置換されることにより、かつ該ワード中に出現する該置換テーブルからの文字の各シークエンスを、該文字のシークエンスが該置換テーブルによってマップされる置換インデックスで置換することによりコード化され、そして
ここで、該ローカルワード定義テーブル中のワードの共通プレフィックスが除去されている、簡潔言語学データ構造。
【請求項１０】
名前テーブルをさらに備え、該名前テーブルが前記ワードを識別するための名前を備える、請求項６に記載の簡潔言語学データ構造。
【請求項１１】
前記ワードのサフィックスを記憶するための屈折テーブルをさらに備え、前記ワード定義テーブル中に記憶されるワードが、該屈折テーブル中に記憶されたサフィックスに言及する、請求項６に記載の簡潔言語学データ構造。
【請求項１２】
前記置換テーブル中に含められる文字のシークエンスが異なる長さを有し、ここで、該長さの各々について、該置換テーブルが、該長さの文字のシークエンスを置換インデックスにマップするサブテーブルを含み、そしてここで、該サブテーブルが、該サブテーブルに含まれるシークエンスの該長さに従う昇順で組織化されている、請求項６に記載の簡潔言語学データ構造。
【請求項１３】
前記オフセットテーブルが、アルファベットからの２つの文字の各組み合わせを、オフセットテーブル中のインデックスにマップし、該オフセットテーブル中のインデックスが、該アルファベット中の文字の数で乗じられる、該組み合わせ中の第１の文字の該アルファベット中の位置、および該組み合わせ中の第２の文字の該アルファベット中の位置の合計に等しい、請求項６に記載の簡潔言語学データ構造。
【請求項１４】
前記ワード中の文字が、最も重要なビットを有するビットのシークエンスにより表され、前記ワード定義テーブル中のワードの各々における最後の文字における最も重要なビットがセットされ、そして前記ワード中の各文字の値が該最も重要なビット以外のビットのビット値を基に決定される、請求項６に記載の簡潔言語学データ構造。
【請求項１５】
さらに：
新規ワードを記憶するための新規ワードテーブルであって、前記ワード定義テーブルに含まれない文字マッピングテーブルおよび置換テーブル、該新規ワードと関連する複数の頻度、該新規ワードの開始のためのインデックス、および該新規ワードのアルファベットでソートされた順序を特定する記憶インデックスを用いてコード化される、新規ワードテーブル；および
該ワード定義テーブル中に記憶されるワードを記憶するためのアップデートされた頻度テーブルであって、該文字マッピングテーブルおよび置換テーブル、該ワード定義テーブル中に記憶されたワードと関連するアップデートされた頻度、該アップデートされた頻度テーブル中のワードの開始のためのインデックス、および該アップデートされた頻度テーブル中のワードのアルファベットによりソートされた順序を特定する記憶インデックスを用いてコード化される、アップデートされた頻度テーブルをさらに含む、請求項７に記載の簡潔言語学データ構造。
【請求項１６】
前記文字マッピングテーブル、前記置換テーブル、前記ワード定義テーブル、および前記オフセットテーブルが、コンピューター読み出し可能なファイル中に含まれる、請求項６に記載の簡潔言語学データ構造。
【請求項１７】
前記コンピューター読み出し可能なファイルが、ヘッダーをさらに備え、該ヘッダーが、フォーマット、バージョンおよび優先情報を備える、請求項１６に記載の簡潔言語学データ構造。
【請求項１８】
インデックステーブルをさらに備え、該インデックステーブルが、前記コンピューター読み出し可能なファイル中のテーブルを位置決めするための該コンピューター読み出し可能なファイル中へのインデックスを含む、請求項１６に記載の簡潔言語学データ構造。
【請求項１９】
前記コンピューター読み出し可能なファイルが、コンピューター読み出し可能な媒体中で具現化される、請求項１６に記載の簡潔言語学データ構造。
【請求項２０】
簡潔言語学データを生成する方法であって：
コーパス中で最も頻繁に生じる複数ワードを含むワードリストを生成する工程；
該ワードリスト中のワードをアルファベットでソートする工程；
該ワード中の文字を文字インデックスにマップする文字マッピングテーブルを生成する工程；
該ワードリスト中のワードをグループに分離する工程であって、各グループにおけるワードが共通プレフィックスを有する工程；
該ワード中の文字シークエンスを置換インデックスにマップする置換テーブルを生成する工程；
該ワード中の文字を、該文字が該文字マッピングテーブルによってマップされる文字インデックスで置換することにより、および該ワード中の文字シークエンスを、該文字シークエンスが該置換テーブルによってマップされる置換インデックスで置換することにより、該ワードをバイトシークエンスにコード化する工程；
ワード定義テーブルを生成し、そして該ワード定義テーブル中にコード化されたワードを記憶する工程；
コード化されたワードのグループを位置決めするためのオフセットテーブルを生成する工程；および
該文字マッピングテーブル、該置換テーブル、該ワード定義テーブル、および該オフセットテーブルをソートする工程を包含する、方法。
【請求項２１】
前記ソートする工程が、前記文字マッピングテーブル、前記置換テーブル、前記ワード定義テーブル、および前記オフセットテーブルをコンピューター読み出し可能なファイルに書くことを包含する、請求項２０に記載の方法。
【請求項２２】
前記ワードリストを生成する工程が：
前記コーパスを複数のフィルターにかけられたワードにフィルターにかけること；
該フィルターにかけられたワードに関連する絶対頻度を算出すること；および
該コーパス中で最も頻繁に生じるフィルターにかけられたワード、および該ワードリスト中の最も頻繁に生じるフィルターにかけられたワードに関連する絶対頻度を記憶することを包含し；そして
該方法が、さらに：
該ワードリスト中に記憶された絶対頻度に規格化関数を適用することにより、複数の相対頻度を生成する工程；
該ワードのグループと関連する頻度セットを生成する工程；および
前記ワードテーブル中に該頻度セットを記憶する工程を包含し、
ここで、各グループについて、該関連する頻度セットが、該グループ中に最大相対頻度を、そして、該最大頻度と関連しないグループ中の各ワードについて、該ワードと関連する相対頻度に対応する最大相対頻度のパーセントを含む、請求項２０に記載の方法。
【請求項２３】
前記フィルターにかけられたワードに関連する絶対頻度を算出する工程が：
最も頻繁に生じるフィルターにかけられたワード、および該最も頻繁に生じるワードと関連する絶対頻度を記憶するためのワードツリーを生成することであって、より高い絶対頻度と関連するワードが該ワードツリーの内部ノード中に記憶され、そしてより低い絶対頻度と関連するワードが該ワードツリーのリーフノード中に記憶されること；
該フィルターにかけられたワードを該ワードツリーに付加することであって、各フィルターにかけられたワードについて該付加することが：
該フィルターにかけられたワードが該ワードツリー中にあるか否かを決定すること；
該フィルターにかけられたワードが該ワードツリーにない場合、該フィルターにかけられたワードおよびその関連する絶対頻度を該ワードツリーに付加すること；
該フィルターにかけられたワードが該ワードツリーにある場合、該フィルターにかけられたワードに関連する絶対頻度を増分すること；
該ワードツリー中のノードの数が所定の限度を超えるか否かを決定すること；および
該ワードツリー中のノードの数が該所定の限度を超える場合、該ワードツリーを収縮することを包含し、ここで、該収縮することが、最も低い絶対頻度と関連するワードを含むリーフノードを削除することを包含する、請求項２２に記載の方法。
【請求項２４】
前記コーパスをフィルターにかける工程が：
複数のコンピューターファイルを読むことであって、各ファイルが該ファイルのタイプを示す拡張子を有する、こと；
該ファイル中に含まれるテキストに規則式を適用し、該テキスト中の無効または所望されない文字を置換すること；
各ファイルについてフィルターを得ることであって、該フィルターが該式によって示されるタイプに対応する、こと；および
該コーパスの一部ではないファイルからテキストを除くために該ファイルを適用することを包含する、請求項２２に記載の方法。
【請求項２５】
さらに：
学習ワードリストに予測ワードのリストからユーザーによって選択されたワードを付加する工程であって、該予測のリストが、前記ワード定義テーブルおよび該学習ワードリストから検索されたワードを含む、工程；
該予測ワードのリスト中のワードの最大頻度と関連するワードを得る工程；
該最大頻度と関連するワードが該ワード定義テーブルから得られたか否かを決定する工程；
該最大頻度と関連するワードが該ワード定義テーブルから得られた場合、選択されたワードを、該最大頻度プラス１に等しい頻度に関連付ける工程；
該最大頻度と関連するワードが該ワード定義テーブルから得られなかった場合、選択されたワードを、該最大頻度に等しい頻度に関連付ける工程；および
該最大頻度と関連するワードが該ワード定義テーブルから得られなかった場合、該学習ワードリストから該最大頻度を割り当てたワードを削除する工程を包含する、請求項２２に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連する出願への相互参照）
本出願は、２００２年７月３日に出願された米国仮出願番号第６０／３９３,９０３号からの優先権を主張している。この仮出願の図面を含む全体の開示は、本明細書によって参考として本出願中に援用される。
【０００２】
（背景）
（発明の分野）
本発明は、一般に、言語学データに、そして詳細には、テキスト処理およびテキスト入力のための言語学データの記憶および使用に関する。
【背景技術】
【０００３】
（技術の状態の説明）
モバイルデバイスおよび異なるタイプの埋め込みシステムの発展する使用は、これらデバイスの開発者および製造業者が、なお良好に機能する最小のメモリー使用法を必要とする製品を作ることに挑戦させる。これら製品の鍵となる要素は、ユーザーインターフェースであり、これは、代表的には、ユーザーがこの製品によって処理されるテキストに入ることを可能にする。
【０００４】
言語学データの１つの適用は、ユーザーによって入力されるワードの最初の文字に基づくワード完了を予測することによりテキスト入力を容易にすることである。言語学データから検索される予測のセットが与えられると、ユーザーは、予測の１つを選択し得、そしてそれ故、ワード中の残りの文字を入力する必要はない。
【０００５】
ユーザー入力の予測は、モバイルデバイス中に含められるとき特に有用である。なぜなら、このようなデバイスは、代表的には、サイズが拘束されるキーボードを含む入力デバイスを有するからである。入力予測は、このようなデバイスに対してワードを入力するために必要なキーストロークの数を最小にする。
【０００６】
入力予測はまた、テキストが縮小キーボードを用いて入力されるとき有用である。縮小キーボードは、入力され得る文字より少ないキーを有し、それ故、キーストロークの組み合わせは多義性である。入力予測のために言語学データを用いるシステムは、ユーザーがこのような多義性を容易に解決することを可能にする。言語学データはまた、縮小キーボードを用いて入力されている個々のキーストロークを明確にするために用いられ得る。
【０００７】
テキスト入力および処理のために用いられる言語学データの記憶のための現存する解決法は、ハッシュテーブル、ツリー、言語学データベースまたは平易ワードリストに依存する。これら言語学データフォーマットによってカバーされるワードの数は、記憶されたワードに制限される。
【０００８】
現存するテキスト入力予測システムで用いられている言語学データは、代表的には、コーパスとして知られ、テキストまたはスピーチのいずれかである、言語の集団から派生する。コーパスは、言語の特徴を確立するための言語の分析、特定の状況における言語の使用に関するヒトの挙動の分析、システムを特定の言語学環境にその挙動を適合させるために訓練すること、言語に関する理論を経験的に確証すること、または言語処理技法または適用のために試験セットを提供しそれが実際にどのように働くのかを確立することのような使用を有している。数億のワードの国のコーパスがあり、そしてまた、特定の目的のために構築されているコーパスがある。目的特異的なコーパスの例は、話された命令を認識するボイス作動制御システムのシミュレーションに対して車ドライバーが話すことを記録ことから構成されるものがある。国のコーパスの例は、英語の言語である。
【発明の開示】
【課題を解決するための手段】
【０００９】
（要約）
簡潔言語学データを生成するためのシステムが提供される。このシステムは、コーパスおよび言語学データアナライザを備える。この言語学データアナライザは、コーパス中に出現するワードの頻度を算出する。この言語学データアナライザはまた、ワード中に特有の各文字を文字インデックスにマップし、そしてこのワード中の各文字を、この文字がマップされる文字インデックスで置換する。この言語学データアナライザはまた、これらワード中に出現する文字のシークエンスを置換インデックスにマップし、そして各ワード中の文字の各シークエンスをこれら文字のシークエンスがマップされる置換インデックスで置換する。言語学データアナライザはまた、これらワードを、各グループが共通のプレフックスで開始するワードを含むグループに整列し、そして各プレフィックスを、このプレフィックスで開始するワードのグループに対する位置情報にマップする。上記簡潔言語学データは、特有文字、文字インデックス、置換インデックス、位置情報、ワードのグループおよびワードの頻度を含む、システム。
【００１０】
複数のワードのための簡潔言語学データ構造もまた提供される。これらワードはグループに組織化され、各グループが共通プレフィックスを有するワードを含む。該簡潔言語学このデータ構造は、該ワード中の各特有の文字から構成されるアルファベット、該アルファベット中の各文字を文字インデックスにマップするための文字マッピングテーブル、該ワードからの文字のシークエンスを置換インデックスにマップするための置換テーブル、および該ワードを記憶するための複数のワード定義テーブルから構成される。各ワード定義テーブルは、該グループの１つに含まれるワードの各々を記憶する。この簡潔言語学データ構造は、該ワード定義テーブルを位置決めするためのオフセットテーブルをさらに備える。上記共通プレフィックスの各々について、このオフセットテーブルは、上記共通プレフィックスで開始するワード定義テーブルの位置を含む。上記ワード定義テーブル中ワードの各々は、該ワード中の各文字を該文字が該文字マッピングテーブルによりマップされる該文字インデックスで置換されることにより、かつ該ワード中に出現する該置換テーブルからの文字の各シークエンスを、文字の該シークエンスがマップされる該置換インデックスで該置換テーブルによって置換することによりコード化される。各ワード定義テーブル中のワードに対する該共通プレフィックスは除去され。
【００１１】
簡潔言語学データを生成する方法もまた提供される。この方法は、コーパス中で最も頻繁に生じる複数ワードを含むワードリストを生成する工程で始まる。この方法では、該ワードリスト中のワードをアルファベットでソートする工程が続く。この方法では、該ワード中の文字を、上記文字マッピングテーブル中に含まれる関連する文字インデックスで置換することにより上記ワードリスト中のワードをコード化するための文字マッピングテーブルを生成する工程が続く。この方法では、該ワードリスト中のワードをグループに分離する工程が続き、ここで、各グループにおけるワードが共通プレフィックスを有している。この方法では、上記ワードを、上記グループ中のワード中の文字シークエンスを置換テーブルによって文字シークエンスにマップされる置換インデックスで置換することにより、上記グループにコード化するための置換テーブルを生成する工程が続く。この方法では、上記文字マッピングテーブルおよび置換テーブルを用いて、上記グループ中の上記ワードをバイトシークエンスにコード化する工程が続く。この方法では、ワード定義テーブルを生成する工程、およびこのワード定義テーブル中にコード化されたワードを記憶する工程が続く。この方法では、コード化されたワードのグループを位置決めするためのオフセットテーブルを生成する工程が続く。この方法は、上記文字マッピングテーブル、上記置換テーブル、上記ワード定義テーブル、および上記オフセットテーブルをソートする工程で終了する。
【発明を実施するための最良の形態】
【００１２】
（詳細な説明）
統計学的文字置換でワードプレフィックス（接頭語）を索引することに基づく、簡潔言語学データを生成および用いるシステムおよび方法が提供される。このシステムが言語学データを記憶する方法は、最小のメモリー使用法を必要とし、そして特定されたプレフックスおよびそれらの関連する頻度で始まるワードへの非常に迅速なアクセスを提供する。
【００１３】
図１は、言語学データがテキスト入力予測のための用いられるシステムのブロック図である。このシステムは、言語学データ１００、テキスト入力論理ユニット１０２、およびユーザーインターフェース１０３を含む。このシステムは、テキスト入力を必要とする任意の計算デバイス上で履行され得るが、モバイル通信デバイスのような、遅いＣＰＵおよび顕著なＲＡＭおよびＲＯＭ制限をもつ埋め込みデバイスに特に適している。
【００１４】
ユーザーインターフェース１０３は、ユーザーがこのシステムにテキストを入力することを可能にするテキスト入力デバイス１０４を含む。このテキスト入力デバイス１０４は、テキスト入力を可能にする、ＱＷＥＲＴＹ、ＡＺＥＲＴＹまたはＤｖｏｒａｋキーボード、または縮小キーボードのような任意のデバイスである。このユーザーインターフェース１０３はまた、テキストをユーザーに表示するテキスト出力デバイス１０６を含む。テキスト出力デバイス１０６は、モバイルデバイスまたはコンピューターのスクリーン上に提示されるグラフィックコンポーネントであり得る。
【００１５】
言語学データ１００は、統計学的文字置換でワードプレフックスを索引することに基づき、そして以下により詳細に記載される。
【００１６】
テキスト入力論理ユニット１０２は、例えば、モバイルデバイス中に含まれているコンピュータープロセッサによって実行されるコンピューター指示によって履行され得る。
【００１７】
このテキスト入力論理ユニット１０２は、テキスト入力デバイス１０４を用いてユーザーにより入力されたテキストを受ける。このテキスト入力論理ユニット１０２は、次いで、テキスト出力デバイス１０６を用いてユーザーに、ユーザーが入力を開始したワードの予測を提示する。これらの予測は、ユーザーによってテキストとして入力されるプレフィックスで開始する最も可能性の高い全体ワードであり、そして言語学データ１００からのテキスト入力論理ユニット１０２によって検索される。次いで、ユーザーは、テキスト入力デバイス１０４を用いて予測の１つを選択し得る。
【００１８】
このテキスト入力デバイス１０４が縮小キーボードである場合、テキスト入力論理ユニット１０２はまた、縮小キーボードから受ける個々のキーストロークを明確にし、ユーザーに、言語学データ１００中のワードに基づく最も可能性の高い文字を提示する。
【００１９】
図２は、簡潔言語学データを生成するシステムのブロック図である。言語学データアナライザ２０２は、以下に詳細に説明される言語学データ２０４を、英語またはフランス語のような国の言語のコーパス２００を分析することにより生成する。この言語学データアナライザ２０２は、コーパス２００中に出現するワードの頻度を算出し、ワード中の各特有の文字を文字インデックスにマップし、ワード中の文字をこれら文字がマップされる文字インデックスで置換し、ワード中に出現する文字のシークエンスを置換インデックスにマップし、ワード中の文字のシークエンスを、文字のシークエンスがマップされる置換インデックスで置換し、これらワードを、各グループが共通プレフィックスで開始するワードを含むグループに整列し、そして各プレフィックスを、このプレフィックスで開始するワードのグループに位置情報をマップする。
【００２０】
上記言語学データアナライザ２０２によりコーパス２００の分析は、コーパス２００中に出現する特有のワードの絶対頻度の算出を含む。この頻度の算出およびワードリストの作製のための方法は、図３および図４に説明される。一旦、ワードリストがコーパス２００から得られると、このワードリストを用いて言語学データ２０４を生成する。この言語学データ２０４は、この特有文字、文字インデックス、置換インデックス、位置情報、これらワードのグループおよびこれらワードの頻度を含む。言語学データ２０４を生成する方法は図５に説明される。言語学データアナライザ２０２によって生成される言語学データ２０４は、図６に示される。
【００２１】
コーパス２００中に見出されるワードの特定のグループの絶対頻度は、代替的に、このグループを異なるファイルに分離すること、およびこのファイルにカスタム重みを割り当てることにより改変され得る。このグループは、場所の名前または医療用語のようなドメイン特異的であるワードから構成され得、そして、ユーザー選択に基づき、得られるワードリスト中に含まれなければならない。結果として、ワードのこのグループに対する頻度の絶対値は、このグループに割り当てられた重みを用いて改変され得、その結果、ワードのこのグループは、それらがそうでなければ有するであろうと異なる頻度を有する。
【００２２】
図３は、ソースファイルをフィルターにかける方法を示すフローチャートである。ソースファイルは、コーパスを備えるテキストを含む。このフィルターにかける方法は、コーパス中のワードの頻度を算出するで最初の工程である。
【００２３】
この方法は、コンテンツのソースファイルを読み取る工程３００で始まる。ソースファイルが読まれた後、この方法では、プロパティファイル中に記憶され得るユーザー選択に従って、ファイルからテキストの置換を実施する工程３０２が続く。このユーザー選択は、無効または所望されない文字を置換するために、テキストに適用される規則式を特定する。例えば、ユーザーは、ワードリスト中に含まれる通り名（ｓｔｒｅｅｔ  ｎａｍｅ）を欲しないかも知れないか、またはイタリアのユーザーは、非英字が続く「ｅ」を
【００２４】
【数１】
2005531857.tif 000002
で置換することを欲するかも知れず、またはユーザーは、最後の文章が著者名のみを含むことが期待されるとき、テキストの最後の文章をスキップすることを欲するかも知れない。
【００２５】
この方法では、次に、ソースファイルのファイル拡張子により示されるタイプに対応するフィルターを得る工程３０４が続く。例えば、ファイル拡張子が「．ｘｍｌ」であれば、このファイルは、ｅＸｔｅｎｓｉｖｅ  Ｍａｒｋｕｐ  Ｌａｎｇａｕａｇｅ（ＸＭＬ）ドキュメントを含むと推定され、そこでＸＭＬフィルターが得られる。同様に、ファイル拡張子が「．ｈｔｍｌ」である場合、そのときは、Ｈｙｐｅｒ  Ｔｅｘｔ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ（ＨＴＭＬ）フィルターが得られ、そしてファイル拡張子が「．ｔｘｔ」である場合、そのときは、テキストフィルターが得られる。その他のファイル拡張子もまた、さらなるフィルターにマップされ得る。
【００２６】
工程３０４で得られたフィルターは、次いで、コーパスの一部ではなく、むしろフォーマット定義の一部であるワードを取り除くために工程３０６で適用される。例えば、ＸＭＬフィルターは、ファイルから読まれたテキストからマークアップタグを除去する。
【００２７】
この方法では、工程３０６から得られるデータからワード０抽出する工程３０８、および工程３１０でフィルターにかけられたワードファイルにこの抽出されたワードを書き込むことが続く。
【００２８】
工程３１２で、フィルターにかけるより多くのソースファイルがあることが決定される場合、そのときは、この方法は、工程３００で継続される。そうでなければ、この方法は、工程３１４で終了する。この方法が終了するとき、コーパスを備えるすべてのソースファイルはフィルターにかけられている。
【００２９】
図４は、ワード頻度算出の方法を示すフローチャートである。この方法は、図３に示される方法によって生成されたフィルターにかけられたワードファイルを利用する。このフィルターにかけられたワードファイルからのワードは、ワードツリー中にロードされる。このワードツリーは、最小のメモリーを用いて特有のワードおよびそれらの頻度を記憶するために効率的な構造である。このツリーは、フィルターにかけられたワードファイル中に頻繁に生じるワードが、ツリーの内部ノード中に位置決めされ、そしてより少ない頻度で生じるワードがツリーの葉に位置決めされるように組織化されている。このツリーの各ノードは、特有のワードおよびこのワードの絶対頻度を含む。ワードは、このツリーがバランスのとれたままであることを確実にする様式で、ツリーかに付加またはそれから削除される。
【００３０】
この方法は、フィルターにかけられたワードのファイルを読む工程４００で開始する。この方法では、このフィルターにかけられたワードのファイルからワードを読み取る工程４０２、および、このワードがワードツリー中に既に存在しない場合、それをワードツリーに付加することが続く。このツリー中のワードと関連する頻度は増分される。
【００３１】
この方法では工程４０４が続き、ツリー中のノードの数が、プロパティファイル中で特定され得る予備定義された限度を超えるか否かが決定され、次いで、この方法では工程４０８が続く。そうでなければ、この方法では工程４０６が続く。
【００３２】
工程４０６では、ワードツリーが、それがもはやサイズ限度を超えないように収縮される。このツリーは、葉ノード中に位置決めされている最も少ない頻度で用いられるワードをツリーから削除することにより収縮される。次いで、この方法では、工程４０８が続く。
【００３３】
工程４０８は、上記フィルターにかけられたワードのファイル中にフィルターにかけられた任意のワードからあるか否かを決定する。それが存在する場合、そのときは、この方法では、工程４０２が続く。フィルターにかけられたワードが残っていない場合、そのときは、この方法では、工程４１０が続く。
【００３４】
工程４１０は、処理するための任意の残存するフィルターにかけられたワードファイルが存在するか否かを決定する。存在する場合、そのとき、この方法では、工程４００が続く。そうでなければ、この方法では、工程４１２が続く。
【００３５】
工程４１２では、ワードツリーに付加されたワードおよびそれらの頻度を記憶するワードリストが出力ファイルに書き込まれる。
【００３６】
図４に示される方法は、非常に大きなコーポラでさえ、単一のコンピューターによって処理されることを可能にする。得られるワードリストは、コーパス中の最も頻繁に生じるワードの予備定義された限度数まで、およびこのワードに関連する絶対頻度を含む。
【００３７】
図５は、簡潔言語学データを生成する方法を示すフローチャートである。この方法は、簡潔言語学データを生成するためのワード頻度情報を含むワードリストを使用し、そしてワードプレフィックスを索引すること、および統計学的文字置換を含む。
【００３８】
この方法は、工程５００で開始し、ここで、ワードリストが、図４に示される方法のようなワード頻度算出の方法により生成された出力ファイルから読み取られる。ワードリスト中のワードは、次いで、アルファベット順で記憶される。
【００３９】
この方法では、ワードリスト中の絶対頻度を規格化する工程５０１が続く。各絶対頻度は、相対頻度によって置換される。絶対頻度は、ユーザーによって特定され得る関数を適用することにより相対頻度にマップされる。可能な関数は、放物線、ガウシアン、双曲線または線形分布を含む。
【００４０】
この方法では、文字マッピングテーブルを生成する工程５０２が続く。この文字マッピングテーブルは、この方法の次の工程でワードをコード化するために用いられる。コード化が実施されるとき、当初のワード中の文字は、文字マッピングテーブル中のこれら文字の文字インデックスで置換される。アルファベット言語のアルファベットのサイズは、２５６よりかなり少ないので、単一バイトが、ユニコード文字データを記憶するために十分である。例えば、ユニコード文字０×３６００は、文字マッピングテーブル中のインデックス１０で位置決めされる場合、１０として表現され得る。この文字マッピングテーブル中の文字の位置は、重要ではなく、そしてこれら文字が所定のワードリスト中に出現する順序に基づく。
【００４１】
この方法では、これらワードリスト中のワードをグループに分割する工程５０４が続く。各グループ中のワードは、所定長さの共通プレフィックスを有し、そして頻度によりソートされる。ワードは、最初、２文字長さであるプレフィックスによりグループ分けされる。同じ２文字プレフィックスで開始するワードが２５６を超えて存在する場合、そのときは、さらなる分離がより長いプレフィックスで実施される。例えば、ワードリストが、プレフィックス「ｃｏ」で５２０ワードを含む場合、そのときは、このグループは、プレフィックス「ｃｏｍ」、「ｃｏｎ」などを用いてグループに分割される。
【００４２】
この方法では、ワードの各グループに対する頻度セットを生成する工程５０６が続く。頻度情報を記憶するために必要なスペースの量を低減するために、各グループ中のワードの最大頻度のみが完全な正確さで保持される。その他の各ワードの頻度は、そのグループ内の最大頻度のワードのパーセントとして保持される。この技法は、正確さのある程度の損失を引き起こすが、テキスト入力予測の目的には受容可能であり、そして頻度情報のためのより小さな記憶要求を生じる。
【００４３】
この方法では工程５０８が続く。ワードリスト中にワードを記憶するために必要なデータの量を低減するために、これらワード中で最も頻繁に生じる文字シークエンスが置換インデックスで置換される。ｎ数の文字のシークエンスであるｎグラムの置換は、多くの文字が単一文字により表現されることを可能にする。この情報は、置換テーブル中に記憶される。この置換テーブルは、各ｎグラムが置換インデックスにマップされるように索引が付けられる。次いで、これらワードは、各ｎグラムを、あるワード中にｎグラムが出現する毎に置換テーブル中のその置換インデックスで置換することにより簡潔にされ得る。
【００４４】
この方法では、ワードグループを、上記のような文字マッピングテーブルおよび置換テーブルを用いて、バイトシークエンスにコード化する工程５１０が続く。ワードをグループに収集するために用いたプレフィックスは、これらワード自身から除かれる。その結果、各ワードは、そのプレフィックスが与えられると、当初のワードを見出すために必要なすべてのデータを含むバイトシークエンスによって表現される。
【００４５】
この方法では、ワード定義テーブルを生成する工程５１１が続く。このワード定義テーブルは、工程５０６で算出された頻度セットおよび５１０で生成されたコード化ワードを記憶する。
【００４６】
この方法では、オフセットテーブルを生成する工程５１２が続く。このオフセットテーブルは、ワードのグループを表現するバイトシークエンスを含む。このテーブルは、特定のワードグループを表現するバイトシークエンスの開始の識別を可能にする。このオフセットテーブルは、共通のプレフィックスで開始する特定のグループのためのコード化ワードを含むバイト配列を位置決めするために用いられる。
【００４７】
この方法は、工程５１４で終わる。この工程では、上記方法から得られる言語学データが、作製されたテーブル中に記憶されている。これらデータテーブルは、文字マッピングデータ、置換テーブル、オフセットテーブルおよびワード定義テーブルを含み、出力ファイル中に記憶される。
【００４８】
簡潔言語学データを生成する方法の間に集められた統計学的データは、必要に応じて、工程５１４で記憶され得る。この統計学的データは、置換テーブル中に記憶されたｎグラムが言語学データ中のワード中に出現する頻度、言語学データ中のワードの数、ワードリストおよびワードリストが生成されたコーパス、および言語学データ中のワードの数、ワードリストおよびコーパス間の比率を含む。
【００４９】
図６は、簡潔言語学データのフォーマットのブロック図である。このデータフォーマットの主要な目的は、データを生成および解釈するために必要なメモリーの使用およびコンピューター指令の数を最小にしながら、この言語学データの解釈の単純さを保存することである。フォーマット中の言語学データは、言語学データアナライザ２０２（図２）によって生成され、そして図５によって示される方法の出力である。
【００５０】
このフォーマットは、言語学データがワード頻度情報ありまたはなしで記憶されることを可能にする。この言語学データが頻度情報を含むとき、以下に説明される学習能力が履行され得、そしてこのデータは、縮小キーボードで入れられた入力を予測するために用いられ得る。頻度情報が含められないとき、そのときは、３文字長より少ないワードは含められない。なぜなら、それらは、ユーザー入力を予測するために有用ではないからである。
【００５１】
このフォーマットは、多数のテーブルが続くヘッダー６０２を含むコンピューターファイルの構造を定義する。
【００５２】
ヘッダー６０２は、ファイルのフォーマットを識別する数であるマジックナンバーを含むシグネチャーを含む。ヘッダー６０２はまた、ファイル中に含まれた言語学データのバージョンおよび優先度を特定する情報を含む。優先度情報は、言語学データを含む複数ファイルがテキスト入力論理ユニットにより用いられるとき、言語学データに相対的重要性を割り当てるために用いられる。ヘッダー６０２はまた、ファイルが頻度情報を含むか否かを示す。
【００５３】
ヘッダー６０２には、インデックステーブル６０４が続く。このインデックステーブル６０４は、以下に定義される残りのテーブルへのファイル中のインデックスを含み、そしてまた、付加されるべきさらなるテーブルを許容する。テーブルは、インデックステーブル６０４中のテーブルのエントリーで見出されるインデックス情報を用いて位置決めされる。
【００５４】
インデックステーブル６０４には、名前テーブル６０６が続く。この名前テーブル６０６は、上記ワードリストを識別する名前を含む。
【００５５】
この名前テーブル６０６には、文字マッピングテーブル６０８が続く。
【００５６】
この文字マッピングテーブル６０８は、このワードリストのために用いられるアルファベットを含み、そして文字インデックスにアルファベット中の各文字をマップする。このアルファベットは、ワードリスト中のワードで用いられる各特有の文字からなる。
【００５７】
この文字マッピングテーブル６０８には、置換テーブル６１０が続く。この置換テーブル６１０は、２グラム（ｂｉ−ｇｒａｍ）置換テーブルを含み、３グラム、４グラムなどのような定義されるより高いオーダーのｎグラムの各グループのためのテーブルが続く。各ｎグラムは、置換テーブル６１０により置換インデックスにマップされる。
【００５８】
置換テーブル６１０には、オフセットテーブル６１２が続く。このテーブルは、以下に説明されるように、位置決めされるべきワード定義テーブル中のワードの共通プレフィックスに基づき、ワード定義を位置決めするために用いられる。アルファベット中の２文字の各組み合わせについて、このテーブルは、文字のその組み合わせで開始するワードを含むワード定義テーブルのファイル中のオフセットを含む。空のグループについては、このオフセットは、次の空でないオフセットに等しい。各オフセットはまた、以下に説明されるように、ファイル中のオフセットに位置するワード定義テーブルが単純であるか、または複合であるかを特定する。
【００５９】
２文字シークエンスが与えられると、このオフセットは、式：（（アルファベット中の最初の文字の位置＊アルファベット中の文字の数）＋アルファベット中の第２番目の文字の位置）によって定義されるオフセットテーブル中のインデックスに位置決めされる。例えば、アルファベットが英語である場合、そのときは、アルファベットの数は２６であり、そこで、オフセットテーブル中の「ａｂ」のインデックスは、（（０＊２６）＋１）であり、これは１に等しい。これ故、オフセットテーブル６１２のサイズは、アルファベットの長さに基づく。
【００６０】
屈折テーブルは、示されていないが、必要に応じて、言語学データ中に含まれ得る。この屈折テーブルは、ワード定義において用いられ得るワードサフックスを記憶する。屈折分析の方法は、図９に示される。
【００６１】
言語学データはまた、ワード定義テーブル６１４を含む。ワード定義テーブルは、単一のワードグループからのワードおよびこれらワードに関連する頻度を記憶し、そして単純または複合のいずれかであり得る。単純テーブルは、２文字プレフィックスのみによりグループ分けされるワードを定義するために用いられる。複合テーブルは、より長い長さのプレフィックスによりグループ分けされるワードを定義するために用いられる。
【００６２】
定義テーブル６１４中のワードは、文字マッピングテーブル６０８および置換テーブル６１０を用いてコード化される。ワード中の文字は、文字マッピングテーブル６０８からの対応する文字インデックスで置換され、そして置換テーブル６１０中にあるｎグラムは、ワード中で置換テーブル６１０中のそれらの対応する置換インデックスで置換される。オフセットテーブル６１２は、アルファベット中の各２グラムプレフィックスを、そのプレフィックスで開始するワードを定義するファイル中の位置に特有にマップするので、これらプレフィックスは、保持される必要はなく、そしてそれ故、これらのワード定義から除去される。
【００６３】
大文字ワードは、必要に応じて、付加的な特別の文字でマークされ得る。この特別の文字は、文字マッピングテーブル６０８中に記憶され、アルファベットを、ワードリスト中のワードの言語中で用いられない付加的な文字で拡張する。
【００６４】
単純ワード定義テーブルは、グループのコード化ワード、およびこれらワードに関連する頻度を含む。これら頻度は、これら頻度を、それらの値が所定の範囲内にあるように変換する規格化関数を適用することにより規格化される。グループ中のワードの最大頻度ののみが、完全な正確さでテーブル中に記憶される。すべてのその他の頻度は、この最大頻度のパーセントとして記憶される。コード化されたワードは、頻度によって記憶される。しかし、以下に説明されるように、学習機能が適用される場合、そのときは、初期ソーティングはもはや有効ではなく、そしてコード化されたワードは、再ソートされる必要があり得る。
【００６５】
当業者によって認識されるように、文字は、ビットのシークエンスによりコンピューターシステム中で表現され得る。ワード定義テーブル６１４中のワードは、最も重要なビットセットをもつ文字によって分離される。文字がその最も重要なビットセットを有する場合、そのときは、それは、ワード中の最後の文字である。次に、この文字は、その最も重要なビットがこの文字の値を決定する目的のためにセットされないように処理され、その結果、この最も重要なビットは、文字の値に影響しない。
【００６６】
図７は、複合ワード定義テーブルのブロック図である。この複合ワード定義テーブルは、ローカルワード定義テーブル７０８を含み、その各々が上記に記載のような単純または複合ワード定義テーブルである点で帰納的である。
【００６７】
このローカルワード定義ファイル７０８は、より高いオーダーのｎグラムプレフィックスによってグループ分けされるワードを定義する。このローカルワード定義テーブル７０８の各々は、共通プレフィックスを有するワード定義テーブルにより記憶されるワードを記憶し、ここで、このローカルワード定義テーブル７０８の各々におけるワードに対するこの共通プレフィックスは、ワード定義テーブル中のワードに対する共通プレフィックスより長い。ローカルワード定義テーブル７０８中のワードの共通プレフィックスは、除去される。
【００６８】
例えば、ワードグループがプレフィックス「ｃｏ」で開始されるワードを含み、そしてそのプレフィックスで開始する２５６以上のワードがある場合、そのときは、「ｃｏ」プレフィックスワードに対する複合ワード定義テーブルは、「ｃｏｍ」、「ｃｏｎ」などで開始するワードを定義するローカルワード定義テーブル７０８を含む。「ｃｏｍ」プレフィックスのワードに対するテーブルは、「ｃｏｍｍ」および「ｃｏｍｐ」で開始するワードのためのローカルワード定義テーブル７０８をさらに含む複合ワード定義テーブルであり得、その一方、「ｃｏｎ」プレフィックスのワードに対するテーブルは、「ｃｏｎ」で開始するワードのみを含む定義テーブルであり得る。
【００６９】
ローカルワード定義テーブル７０８を含むことに加え、各ワード定義テーブルは、ローカルオフセットテーブル７０６を含み、これは、ローカルワード定義テーブル７０８の各々を位置決めするために用いられる。各オフセットはまた、オフセットによって言及されるテーブルが複合または単純ワード定義テーブルであるか否かを示す。
【００７０】
各複合ワード定義テーブルはまた、ローカル文字マッピングテーブル７０４を含む。このテーブルは、それは、ローカルワード定義テーブル７０８中にあるワード中の文字のみが含まれることを除き、文字マッピングテーブル６０８（図６）と機能的には同一である。このローカル文字マッピングテーブル７０４は、ローカルワード定義テーブル７０８中のワード中の各文字を、ローカル文字インデックスにマップする。単純ローカルワード定義テーブル中のワードは、ワード中の文字を、ローカル文字インデックスで置換することによりコード化される。
【００７１】
複合ワード定義テーブルはまた、ホットワードテーブル７００および例外テーブル７０２を含む。ホットワードは、複合ワード定義テーブル中に含まれるグループ中の最も高い頻度に関連するワードである。このホットワードテーブル７００は、単純ワード定義テーブルであるローカルワード定義テーブル７０８中に位置決めされるホットワードのインデックスを含む。例外テーブル７０２は、複合ワード定義テーブルであるローカルワード定義テーブル７０８中に位置決めされるホットワードを記憶する。ホットワードは、ローカルワード定義テーブル７０８のサーチを実施する代わりに、このホットワードテーブル７００および例外テーブル７０２を用いて迅速に検索され得、ホットワードを見出す。
【００７２】
上記に記載の言語学データのフォーマットは、最小量のメモリーを用いて、非常に迅速にワード予測の決定を可能にする。ユーザーが、ＱＷＥＲＴＹのような、特有のキーまたはキー組み合わせに文字をマップするテキスト入力デバイスを用いてワードプレフィックスを入力するとき、テキスト入力論理ユニットは、最も高い頻度を有するプレフィックスで開始する言語学データ中のワードを検索し、そしてユーザーに予測を提示する。ユーザーが、縮小キーボードを用いてワードをタイプすることを開始するとき、ワードプレフィックスはあいまいである。なぜなら、縮小キーボード上の各キーは、複数の文字にマップされるからである。この場合、テキスト入力論理ユニットは、ユーザーにより入力されたプレフィックスに対応する文字の任意の組み合わせで開始する言語学データから予測を検索する。
【００７３】
上記フォーマットはまた、個々のユーザーのテキスト入力習性に一致するために、ワードの頻度の容易な改変を可能にする。ワード予測代替物が提示されるとき、彼または彼女が行う入力選択によって確認されるユーザーの習性は、テキスト入力論理ユニットによって学習され、そして以下に説明されるようなテーブル中に記憶される。
【００７４】
学習能力は、ワードについての頻度情報の改変、および言語学データへのワードの付加を含む。両方の操作は、ワードおよび対応する頻度情報を学習ワードリストに付加する類似のプロセスを基にする。この学習ワードリストは、頻度改変のためのテーブルおよび新規ワードの付加のためのテーブルを含む。
【００７５】
図８は、頻度改変の方法を示すフローチャートである。この方法は、任意の学習データか集められる前に，上記のようにコンパイルされた言語学データである、基礎言語学データが、一般に、正確な頻度情報を有するという仮定の下に進行する。従って、この方法は、頻度情報の限られた改変を許容する。
【００７６】
この方法は、ユーザー選択ワード８００を学習ワードリストに付加する工程８０２で開始する。ユーザー選択ワード８００は、ユーザーによって、ユーザーにより入力されたワードプレフィックスで開始する提供された予測ワードのリストから選択されるワードである。ユーザーは、テキスト入力デバイスを用いて予測を選択する。選択されたワードは、学習ワードリストに付加される。
【００７７】
この方法では、ユーザーに提示された予測リスト中のワードの最大頻度をもつワードを得る工程８０４が続く。予測リスト中のワードおよびそれらの対応する頻度は、ベース言語学データ中のワード定義テーブルから、または学習ワードリストから得られたものであり得る。工程８０６で、最大頻度をもつワードが、ワード定義テーブルから得られたことが決定される場合、そのときは、この方法では、工程８０８が続き、そしてユーザー選択されたワード８００は、最大頻度プラス１に等しい頻度を割り当てられる。
【００７８】
工程８０６で、最大頻度をもつワードが、ワード定義テーブルから得られず、むしろ、学習ワードリストから得られたことが決定される場合、そのときは、この方法では、工程８１０が続き、そしてユーザー選択されたワード８００には、最大頻度に等しい頻度が割り当てられる。次いで、この方法は、学習ワードリストから工程８０４で得られた最大頻度をもつワードを削除する工程８１２で終了する。
【００７９】
以下の段落は、図８に示される方法の例である。各例は、ユーザーが３文字プレフィックスを入力すると仮定する。
【００８０】
「ｂｅｇ」の３文字プレフィックス、そして、予測が、３０２４の頻度を有する「ｂｅｇａｎ」、２９５０の頻度を有する「ｂｅｇｉｎ」、２８８０の頻度を有する「ｂｅｇｉｎｉｎｇ」、および２０００の頻度を有する「ｂｅｇｉｎｓ」であり、すべてのワードがベース言語学データ中のワード定義テーブルから得られるとすると、ユーザーがワード「ｂｅｇｉｎ」を選択する場合、そのときは、ワード「ｂｅｇｉｎ」が、頻度３０２５で学習ワードリストに添加される。
【００８１】
同じ３文字プレフィックス「ｂｅｇ」、そして、予測が、３０２５の頻度を有する「ｂｅｇｉｎ」、３０２４の頻度を有する「ｂｅｇａｎ」、２８８０の頻度を有する「ｂｅｇｉｎｎｉｎｇ」、および２０００の頻度を有する「ｂｅｇｉｎｓ」であり、ここで「ｂｅｇｉｎ」が学習ワードリストから得られるとすると、ユーザーが「ｂｅｇａｎ」を選択する場合、そのときは、ワード「ｂｅｇａｎ」が、学習ワードリストに頻度３０２５で付加され、そしてワード「ｂｅｇｉｎ」が学習ワードリストから削除される。
【００８２】
以下は、図８の方法の例であり、ここでは、３文字プレフィックスが縮小キーボードを用いて入力される。この縮小キーボードは、「ａ」、「ｂ」または「ｃ」を入力するためのキー、「ｎ」または「ｏ」を入力するためのキー、および「ｗ」、「ｘ」、または「ｙ」を入力するためのキーを含む。この例では、ユーザーが、「ａ／ｂ／ｃ」キー、次いで、「ｎ／ｏ」キー、そして最後に「ｗ／ｘ／ｙ」キーを押すことによって３文字プレフィックスを入力すると仮定される。３０２４の頻度を有する「ａｎｙ」、２９５０の頻度を有する「ｂｏｙ」、２８８０の頻度を有する「ｂｏｘ」、２０００の頻度を有する「ｂｏｗ」、１８９０の頻度を有する「ｃｏｗ」、および１００２の頻度を有する「ｃｏｘ」が与えられ、ここで、すべてのワードがベース言語学データ中のワード定義テーブルから得られる場合、ユーザーが「ｂｏｙ」を選択すると、そのときは、ワード「ｂｏｙ」が、ワード学習リストに頻度３０２５で付加される。
【００８３】
学習ワードリストは、アップデートされた頻度をもつワードを含むアップデートされた頻度テーブル、および新規ワードを含む新規ワードテーブルを含む。これらテーブルの両方は、ベース言語学データ中のように、ベース言語学データによって用いられるようなのと同じ文字マッピング６０８（図６）および置換テーブル６１０（図６）を用いてコード化されるワードを含む。各学習ワードリストテーブルはまた、テーブル中のワードの開始のためのインデックス、テーブル中のワードに関連する頻度情報、そしてアルファベット順にソートされたワードの順序を特定するソートインデックスを含む。各テーブルはまた、テーブルが、アップデートされた頻度または新規ワードを含むか否かを示すフラッグを含む。この学習ワードリストテーブルは、次々に、最初に出現するアップデートされた頻度テーブルとともに連続的に追従する。
【００８４】
学習ワードリストテーブルが、最大定義長さに到達する場合、そのときは、テーブル中の新規なエントリーのための余地を作製するために、最も古いワードがテーブルから削除される。
【００８５】
学習ワードリストテーブルにワードを付加すること、およびそれからワードを削除することは、アップデートされたテーブルを表現するバイトシークエンスを生成すること、そして同時に、出力ストリーム中にこのバイトシークエンスを書き込むことにより実施される。アップデートが終了した後、このアップデートされたデータは、再読み込みされる。出力ストリーム中への書き込みのプロセスは、ワードが学習ワードリストに付加または削除される毎に生じる。
【００８６】
学習ワードリストテーブルの１つにワードを付加または削除するために、文字マッピングテーブル６０８（図６）中のアルファベットは、それが、付加されるべきワード中に出現する文字を含まない場合にアップデートされる。次いで、付加されるべきワードは、文字マッピングテーブル６０８（図６）および置換テーブル（図６）を用いてコード化され、そして新規ワードテーブルの先頭中に挿入される。最後に、学習ワードリストテーブルの頻度およびソートインデックスがアップデートされる。
【００８７】
図９は、屈折分析の方法を示すフローチャートである。簡潔言語学データを生成するシステムおよび方法は、代わりに、屈折分析の方法を含み得、そこでは、最小の特定された頻度より高い頻度を有するワードのリストおよび屈折テーブルの両方が生成される。この屈折テーブルは、統計学的サフィックス分析を基に生成され、そしてコーパスの言語中にワード生成のための言語学規則をカプセル化する。この屈折テーブルは、屈折テーブル中に記憶された基礎ワード形態を用いて１より多いワードを生成することを可能にし、ワードリストが簡潔なままでありながら、より多くのワードが言語学データによって変換されることを確実にする。屈折テーブルは、必要に応じて、図６に示される言語学データフォーマット中に含められ得る。
【００８８】
この方法は、ワードの絶対頻度を基に、ワードリスト中で最も頻繁に起こるワードの構成された数を見出す工程９００で開始する。
【００８９】
この方法では、頻繁に生じるワードのサフィックスを見出す工程９０１が続く。このサフィックスを見出す工程は、６文字長であるサフィックスで開始し、そして２文字長であるサフィックスで終わる減少する長さのサフィックスの反復サーチに基づく。これらのサフィックスは、所定の言語の文法中に存在する相等物に常に一致するわけではなく、むしろ、このサフィックスを見出すことは、ワードリスト中のサフィックスの出現の数に基づく。
【００９０】
この方法では、先の工程で見出されたサフィックスで屈折テーブルをアップデートする工程９０２が続く。この最初の時の工程９０２が実施され、屈折テーブルは、それがアップデートされる前に生成される。
【００９１】
工程９０３では、言語学データのサイズが構成された最大サイズより小さい場合、そのときは、この方法は、工程９０１に続く。そうでなければ、この方法は、屈折テーブル中に含まれるサフィックスなくして、ワードリスト中にワードのリストを生成する工程９０４で終了する。
【００９２】
サフィックスなしの屈折テーブルおよびワードのリストは、次いで、図５を参照して上記で説明したようにコード化され得る。屈折分析の方法が用いられるとき、図６に示されるような得られる簡潔言語学データはまた、屈折テーブルを含む。ワード定義テーブル６１４（図６）中のワードは、そのときは、屈折テーブル中に含まれるサフィックスを含まず、むしろ、屈折テーブル中のサフィックスへの参照を含む。記憶された各サフィックスに対する屈折テーブルを用いることにより節約されたスペースは、サフィックスの長さにより乗じられるサフィックスの出現の数である。
【００９３】
上記の説明は、本発明の１つの例に関する。多くの改変が、当業者に明らかであり、そしてこのような改変は、本出願の範囲内にある。
【００９４】
例えば、大部分の例で用いられる言語は、英語であるが、提供されるシステムおよび方法は、任意のアルファベット言語について簡潔言語学データを生成する。
【００９５】
さらに、簡潔言語学データを生成および用いるシステムおよび方法は、ソフトウェア、ファームウェア、またはハードウェアとして、またはそれらの組み合わせとして、パーソナルコンピューター、セルラーテレホン、２方向ページャー、任意の種類の装着型コンピューター、プリンター、セットトップボックスおよびテキスト入力および表示を可能にする任意のその他のデバイス上で履行され得る。
【００９６】
また、図３、４、５、８および９に示される方法は、示されるものより少ないか、多いか、または異なる工程を含み得る。例えば、これら方法は、これら方法の最終および中間結果を記憶するためにコンピューターファイルを用いることを記載しているが、これらの結果はまた、ＲＡＭまたはＦｌａｓｈメモリーモジュールのようなコンピューターメモリー中に記憶され得る。
【図面の簡単な説明】
【００９７】
【図１】図１は、言語学データがテキスト入力予測のために用いられるシステムのブロック図である。
【図２】図２は、簡潔言語学データを生成するシステムのブロック図である。
【図３】図３は、ソースファイルをフィルターにかける方法を示すフローチャートである。
【図４】図４は、ワード頻度算出の方法を示すフローチャートである。
【図５】図５は、簡潔言語学データを生成する方法を示すフローチャートである。
【図６】図６は、簡潔言語学データのフォーマットのブロック図である。
【図７】図７は、複合ワード定義テーブルのブロック図である。
【図８】図８は、頻度改変の方法を示すフローチャートである。
【図９】図９は、屈折分析の方法を示すフローチャートである。
【図１】
2005531857.tif 000003
【図２】
2005531857.tif 000004
【図３】
2005531857.tif 000005
【図４】
2005531857.tif 000006
【図５】
2005531857.tif 000007
【図６】
2005531857.tif 000008
【図７】
2005531857.tif 000009
【図８】
2005531857.tif 000010
【図９】
2005531857.tif 000011