(57)【要約】  言語モデルを圧縮する方法（３００、７０８）を提供する。ユーザ入力の要素から数値のリスト（３００）が生成される。リストの値のリストがソートされる（３０２）。リスト内で隣り合う２つの整数値間の差が計算される。計算された差はそれぞれＧｏｌｏｍｂ符号を使用して符号化される（３０６、７１２）。
2008547116.tif 000002
【特許請求の範囲】
【請求項１】
言語モデルを圧縮する方法であって、
ユーザ入力のｎ−ｇｒａｍから数値のリストを生成するステップと、
前記値のリストをソートするステップと、
前記リスト内で隣り合う値間の差を計算するステップと、
計算された差のそれぞれを、Ｇｏｌｏｍｂ符号を使用して符号化するステップと
を備えることを特徴とする方法。
【請求項２】
前記符号化するステップは、
前記リスト内で隣り合う値間の前記計算された差として期待される値の１／２にほぼ等しくなるような値Ｍを選択するステップと、
計算された差のそれぞれについて前記計算された差と前記値Ｍとの比率から商の値と剰余の値とを計算するステップと、
前記商の値と前記剰余の値とをメモリ内に格納するステップとを備えることを特徴とする請求項１に記載の方法。
【請求項３】
前記格納するステップは、
前記商の値をｕｎａｒｙ形式で格納するステップと、
前記剰余の値をバイナリ形式で格納するステップとを備えることを特徴とする請求項２に記載の方法。
【請求項４】
前記商の値は、最も近い整数値に切り捨てられた前記値Ｍに対する最初の差の比率を含むことを特徴とする請求項２に記載の方法。
【請求項５】
前記剰余の値は、最も近い整数値に切り捨てられた前記値Ｍに対する最初の差の比率の剰余を含むことを特徴とする請求項２に記載の方法。
【請求項６】
前記符号化された差をメモリ内に格納するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項７】
前記符号化された差は式
【数１】
2008547116.tif 000011
に従ってメモリ内のいくつかのビット数を占有することを特徴とする請求項６に記載の方法。
【請求項８】
記憶媒体上にコンピュータ可読の命令を格納するステップをさらに備えており、前記コンピュータ可読の命令は生成、ソート、計算、符号化のステップを定義すること
を特徴とする請求項１に記載の方法。
【請求項９】
ユーザ入力を処理するシステムであって、
ユーザ入力を受信するように構成されたユーザインターフェイスと、
情報を格納し、Ｇｏｌｏｍｂ圧縮された言語モデルを格納するように構成されたメモリと、
ユーザ入力を符号化し、前記Ｇｏｌｏｍｂ圧縮された言語モデルの要素を復号化するように構成されたＧｏｌｏｍｂ符号器／復号器と、
ユーザ入力を前記Ｇｏｌｏｍｂ圧縮された言語モデルの要素と比較して一致の候補を特定するように構成されたプロセッサとを備えることを特徴とするシステム。
【請求項１０】
前記プロセッサで使用され、前記一致の候補を特定するように構成された統計学的アルゴリズムのセットをさらに備えることを特徴とする請求項９に記載のシステム。
【請求項１１】
前記プロセッサは前記特定された一致の候補をユーザに対して表示する出力として前記ユーザインターフェイスに提供するように構成されることを特徴とする請求項９に記載のシステム。
【請求項１２】
前記プロセッサはユーザ入力に関連する数値を計算するように構成されることと、前記Ｇｏｌｏｍｂ符号器／復号器は前記計算された数値を符号化するように構成されることとを特徴とする請求項９に記載のシステム。
【請求項１３】
前記Ｇｏｌｏｍｂ符号器／復号器はハッシュ値のリスト内のハッシュ値間の差として期待される値に基づいて値Ｍを計算するように構成されており、前記Ｇｏｌｏｍｂ符号器／復号器は前記差の前記期待される値に対する比率に基づいて商と剰余を計算するように構成されることを特徴とする請求項９に記載のシステム。
【請求項１４】
ユーザ入力を復号化する方法であって、
受信されたユーザ入力を複数のｎ−ｇｒａｍに分割するステップと、
ハッシュ技術を使用して各ｎ−ｇｒａｍを符号化するステップと、
符号化された各ｎ−ｇｒａｍをＧｏｌｏｍｂ符号化された言語モデルと比較して一致の候補を特定するステップと、
各一致の候補が前記受信されたユーザ入力のＧｏｌｏｍｂ符号化された言語モデル内の要素への正しいマッピングである尤度を統計的に評価するステップを備えることを特徴とする方法。
【請求項１５】
前記比較するステップは、累計が符号化されたｎ−ｇｒａｍの値以上になるまで前記言語モデル内の符号化されたｎ−ｇｒａｍ間の差を合計するステップと、
前記受信されたユーザ入力を前記適切なｎ−ｇｒａｍの前記言語モデル内の値に関連付けるステップとを備えることを特徴とする請求項１４に記載の方法。
【請求項１６】
前記関連付けられた受信されたユーザ入力は前記一致の候補を含むことを特徴とする請求項１５に記載の方法。
【請求項１７】
前記複数のｎ−ｇｒａｍはｎ−ｇｒａｍのリストを備え、
前記符号化するステップは、
前記リスト内で隣り合うｎ−ｇｒａｍ間の差を計算するステップと、
前記計算された差のそれぞれについて前記リスト内で隣り合う値間の前記計算された差として期待される値の１／２にほぼ等しくなるような値Ｍを選択するステップと、
計算された差のそれぞれについて前記差と前記Ｍの値との比率から商の値と剰余の値とを計算するステップと、
各ｎ−ｇｒａｍについて前記ｕｎａｒｙ形式の商の値と前記バイナリ形式の剰余の値とを組み合わせて前記符号化されたｎ−ｇｒａｍを形成するステップとを備えること
を特徴とする請求項１４に記載の方法。
【請求項１８】
前記値のリストは数値を含むことを特徴とする請求項１７に記載の方法。
【請求項１９】
記憶媒体上にコンピュータ可読の命令を格納するステップをさらに備えており、前記コンピュータ可読の命令は分割、符号化、比較、評価のステップを定義すること
を特徴とする請求項１４に記載の方法。
【請求項２０】
請求項１４に記載の方法に従ってユーザ入力をＧｏｌｏｍｂ圧縮された言語モデルと比較することによって前記ユーザ入力を復号化するように構成されたことを特徴とする携帯用コンピューティングデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＧＯＬＯＭＢ符号を使用して言語モデルを圧縮する方法に関する。
【背景技術】
【０００２】
以下の説明は、一般的な背景情報を提供するものにすぎず、請求対象の範囲を指定するために使用するものではない。
【０００３】
言語モデルは、自然言語処理（Ｎａｔｕｒａｌ  Ｌａｎｇｕａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ）、スペルチェック（ｓｐｅｌｌ  ｃｈｅｃｋｉｎｇ）などのようにノイズの多いチャネルアプリケーションを含むさまざまなアプリケーションで使用されている。自然言語アプリケーションにおいて、音声認識装置（ｓｐｅｅｃｈ  ｒｅｃｏｇｎｉｚｅｒ）は一般に音響特徴量（ａｃｏｕｓｔｉｃ  ｅｖｉｄｅｎｃｅ）（チャネルモデル）とユーザが発する可能性のあることば（言語モデル）に関する予想を組み合わせることによって動作する。言語モデルの一般的な形の１つはｔｒｉ−ｇｒａｍと呼ばれている。
【０００４】
一般に、ｎ−ｇｒａｍはｎ個のトークン（ワード）で構成される部分列（ｓｕｂｓｅｑｕｅｎｃｅ）である。ｔｒｉ−ｇｒａｍは３つのトークン（ワード）で構成される部分列（ｓｕｂｓｅｑｕｅｎｃｅ）である。例えば、“ｔｏ  ｂｅ  ｏｒ  ｎｏｔ  ｔｏ  ｂｅ”という句からは、“＄  ＄  ｔｏ”、“＄  ｔｏ  ｂｅ”、“ｔｏ  ｂｅ  ｏｒ”、“ｂｅ  ｏｒ  ｎｏｔ”、“ｏｒ  ｎｏｔ  ｔｏ”、“ｎｏｔ  ｔｏ  ｂｅ”、“ｔｏ  ｂｅ  ＄”、“ｂｅ  ＄  ＄”の８つのｔｒｉ−ｇｒａｍを生成できる。ここで、入力文字列は“＄”で表す２つの特殊なトークンが埋め込まれている。こうしたｎ−ｇｒａｍに統計学を適用して、ユーザが特定の入力を意図する尤度を評価することができる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
かつては１０億ワードで構成されるテキストは大きいと考えられていたが、音声認識のトレーニングセットは日常的に１００億ワードのテキストでトレーニングしている。一般に、大規模な言語モデルは有効に機能する（つまりエントロピーが低い）が、多くの場合、特に携帯電話、携帯情報端末（ＰＤＡ）、電子プラナー（ｅｌｅｃｔｒｏｎｉｃ  ｐｌａｎｎｅｒｓ）などのモバイルデバイスの場合はメモリ容量が限定される。こうしたメモリの状況に対応する１つの技術として、言語モデルのトリミングがある。これは、使用頻度の低いワードや一般的でない変形を削除することによる。しかし、こうした用語の削除によって言語モデル全体の有効性が低下し、その結果、入力をトリミングされたモデル内のワードに一致できないことにより、意味論的な誤りがより多く発生する。
【課題を解決するための手段】
【０００６】
ここでは、後述の実施形態に関する説明の前に、いくつかの概念を簡略化した形で紹介する。以下に示す解決手段は、請求対象の重要な機能または必須の機能を特定するものではない。また、請求対象の範囲を指定するために使用するものでもない。
【０００７】
１つの実施形態では、言語モデルはＧｏｌｏｍｂ符号化技術を使用して圧縮される。言語モデルの要素から値のリストが生成される。整数値のリストがソートされ、要素ごとにリスト内の隣り合う整数値間の差が計算される。計算された差はそれぞれＧｏｌｏｍｂ符号を使用して符号化される。
【０００８】
別の実施形態では、ユーザ入力を処理するシステムは、ユーザインターフェイス、メモリ、Ｇｏｌｏｍｂ符号器／復号器、およびプロセッサを備えている。ユーザインターフェイスはユーザ入力を受信するように構成されている。メモリは、情報を記憶し、Ｇｏｌｏｍｂ圧縮された言語モデルを記憶するように構成されている。Ｇｏｌｏｍｂ符号器／復号器は、ユーザ入力を符号化し、Ｇｏｌｏｍｂ圧縮された言語モデルの要素を復号化するように構成されている。プロセッサは、符号化されたユーザ入力をＧｏｌｏｍｂ圧縮された言語モデルの要素と比較し、一致の候補を特定するように構成されている。
【０００９】
別の実施形態では、Ｇｏｌｏｍｂ符号化された言語モデルを使用してユーザ入力を復号化する方法が提供される。ユーザ入力は複数の要素に分割され、そのそれぞれはハッシュ技術を使用して符号化される。符号化された各要素は、Ｇｏｌｏｍｂ符号化された言語モデルの要素と比較され、一致の候補が特定される。一致の候補が統計学的に分析され、一致の候補がユーザ入力のＧｏｌｏｍｂ符号化された言語モデルへの正しいマッピングである尤度が評価される。
【発明を実施するための最良の形態】
【００１０】
言語モデルは、音声認識システム、コンテキスト依存のスペル訂正（ｃｏｎｔｅｘｔ  ｓｅｎｓｉｔｉｖｅ  ｓｐｅｌｌｉｎｇ  ｃｏｒｒｅｃｔｉｏｎ）システム、コンピュータにアジア文字を入力するために使用されるインターフェイスなどで利用されている。Ｇｏｌｏｍｂ圧縮技術は、インターネットのように世界規模のコンピュータネットワークの探査をするＵＲＬ（ｕｎｉｆｏｒｍ  ｒｅｓｏｕｒｃｅ  ｌｏｃａｔｏｒ）データなどのユーザ入力に適用できる。メモリは実際には、特に携帯電話、携帯情報端末（ＰＤＡ）などのモバイルプラットフォームの場合、限られていることが多いので、言語モデルの圧縮は非常に有効であり、Ｇｏｌｏｍｂ符号化技術は言語モデルの圧縮と結果の復号化の両方に利用できる。
【００１１】
図１は、言語モデル圧縮技術の実施形態を実装できる適切なコンピューティングシステム環境１００を例として示している。コンピューティングシステム環境１００は適切なコンピューティング環境の１つの例にすぎず、本発明の使用または機能の範囲に関するいかなる制限を示唆するものでもない。また、コンピューティング環境１００は、例示的なオペレーティング環境１００に示すコンポーネントの１つまたは組合せに関して、依存性も要件もないと解釈するものとする。
【００１２】
本発明の実施形態は、他のさまざまな汎用または専用のコンピューティングシステム環境または構成でも動作可能である。本発明の実施形態による使用に適した周知のコンピューティングシステム、環境、および／または構成の例には、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラム可能な家庭用電子機器、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、テレフォニー（ｔｅｌｅｐｈｏｎｙ）システム、前述の任意のシステムまたはデバイスを含む分散コンピューティング環境などが含まれるが、これらに限定はされない。
【００１３】
実施形態は、プログラムモジュールのようにコンピュータで実行可能な命令をコンピュータで実行する一般的なコンテキストで説明できる。一般に、プログラムモジュールには、特定のタスクを実行したり、特定の抽象データ型を実装したりするルーチン、プログラム、オブジェクト、コンポーネント、データ構造などがある。本発明は、通信ネットワークを介してリンクするリモート処理装置でタスクを実行する分散コンピューティング環境で実施するように設計されている。分散コンピューティング環境において、プログラムモジュールはメモリ記憶装置を含むローカルとリモートの両方のコンピュータ記憶媒体に格納される。
【００１４】
図１を参照すると、実施形態を実装する例示的なシステムには、コンピュータ１１０の形で汎用のコンピューティングデバイスが配置されている。コンピュータ１１０のコンポーネントには、処理装置１２０、システムメモリ１３０、及びシステムバス１２１（システムメモリを含むさまざまなシステムコンポーネントを処理装置１２０へ接続する）が含まれるが、それらに限定はされない。システムバス１２１は、さまざまなバスアーキテクチャの任意の１つを使用したメモリバスまたはメモリコントローラ、周辺バス、ローカルバスを含む各種バス構造のいずれでもよい。こうしたアーキテクチャには、例として、ＩＳＡ（Ｉｎｄｕｓｔｒｙ  Ｓｔａｎｄａｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＭＣＡ（Ｍｉｃｒｏ  Ｃｈａｎｎｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＥＩＳＡ（Ｅｎｈａｎｃｅｄ  ＩＳＡ）バス、ＶＥＳＡ（Ｖｉｄｅｏ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｓｔａｎｄａｒｄｓ  Ａｓｓｏｃｉａｔｉｏｎ）ローカルバス、ＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ）バス（メザニン（Ｍｅｚｚａｎｉｎｅ）バスとしても知られている）が含まれるが、これらに限定はされない。
【００１５】
コンピュータ１１０には、通常はさまざまなコンピュータ可読媒体が含まれる。コンピュータ可読媒体は、コンピュータ１１０からアクセスできる任意の使用可能な媒体でよい。また、揮発性と不揮発性の両方の媒体、および取り外し可能と不可能の両方の媒体が含まれる。例として、コンピュータ可読媒体にはコンピュータ記憶媒体および通信媒体を含めてもよいが、これらに限定はされない。コンピュータ記憶媒体には、コンピュータ可読の命令、データ構造、プログラムモジュール、またはその他のデータなどの情報を記憶する任意の方法または技術で実装された、揮発性と不揮発性の両方、および取り外し可能と不可能の両方の媒体が含まれる。コンピュータ記憶媒体には、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ：ｄｉｇｉｔａｌ  ｖｅｒｓａｔｉｌｅ  ｄｉｓｋ）または他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージまたは他の磁気記憶装置、または所望の情報の格納に使用でき、コンピュータ１１０からアクセスできる他の任意の媒体が含まれるが、これらに限定はされない。通信媒体は、通常、搬送波やその他の搬送メカニズムのような変調データ信号に含まれるコンピュータ可読の命令、データ構造、プログラムモジュール、またはその他のデータなどを具体化したものであり、任意の情報伝達媒体を含んでいる。「変調データ信号」という用語は、信号内の情報を符号化するように設定または変更された１つまたは複数の特性を持つ信号を意味する。通信媒体には、例として、有線ネットワーク、直接ワイヤ接続などの有線媒体と、音響、ＲＦ、赤外線および他の無線媒体が含まれるが、これらに限定はされない。上記の任意の組合せも、コンピュータ可読媒体の範囲内に含まれるものとする。
【００１６】
システムメモリ１３０には、読み取り専用メモリ（ＲＯＭ：ｒｅａｄ  ｏｎｌｙ  ｍｅｍｏｒｙ）１３１やランダムアクセスメモリ（ＲＡＭ：ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）１３２のように揮発性および／または不揮発性メモリという形をとるコンピュータ記憶媒体が含まれる。起動時などにコンピュータ１１０内の要素間の情報転送を支援する基本ルーチンを含む基本入出力システム１３３（ＢＩＯＳ：ｂａｓｉｃ  ｉｎｐｕｔ／ｏｕｔｐｕｔ  ｓｙｓｔｅｍ）は、通常はＲＯＭ  １３１に格納される。ＲＡＭ  １３２には、通常は処理装置１２０から直ちにアクセスできる、かつ／または処理装置１２０で現在操作しているデータおよび／またはプログラムモジュールが格納される。例として、図１にはオペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６、およびプログラムデータ１３７が示されているが、これらに限定はされない。
【００１７】
コンピュータ１１０には、その他の取り外し可能／不可能、揮発性／不揮発性のコンピュータ記憶媒体を含めてもよい。単に例として、図１は取り外し不可能な不揮発性の磁気媒体の読み出しまたは書き込みを行うハードディスクドライブ１４１、取り外し可能な不揮発性の磁気ディスク１５２の読み出しまたは書き込みを行う磁気ディスクドライブ１５１、ＣＤ  ＲＯＭや他の光媒体のような取り外し可能な不揮発性の光ディスク１５６の読み出しまたは書き込みを行う光ディスクドライブ１５５を示している。例示的なオペレーティング環境で使用できる上記以外の取り外し可能／不可能、揮発性／不揮発性のコンピュータ記憶媒体には、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭなどが含まれるが、それらに限定はされない。ハードディスクドライブ１４１は、通常はインターフェイス１４０などの取り外し不可能なメモリインターフェイスを介してシステムバス１２１に接続し、磁気ディスクドライブ１５１と光ディスクドライブ１５５は、通常はインターフェイス１５０などの取り外し可能なメモリインターフェイスを介してシステムバス１２１に接続する。
【００１８】
前述し図１に示したドライブとこれに対応するコンピュータ記憶媒体は、コンピュータ可読の命令、データ構造、プログラムモジュール、およびその他のコンピュータ１１０のデータを格納する。例えば、図１には、ハードディスクドライブ１４１は、オペレーティングシステム１４４、アプリケーションプログラム１４５、その他のプログラムモジュール１４６、およびプログラムデータ１４７を格納するものとして示されている。こうしたコンポーネントは、オペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６、およびプログラムデータ１３７と同じでもよいし、異なっていてもよいことに留意されたい。ここでは、オペレーティングシステム１４４、アプリケーションプログラム１４５、その他のプログラムモジュール１４６、およびプログラムデータ１４７には異なる番号を付けて、少なくとも別の複製であることを示している。
【００１９】
ユーザは、キーボード１６２、マイクロフォン１６３、ポインティングデバイス１６１（マウス、トラックボール、またはタッチパッドなど）などの入力装置を使用してコンピュータ１１０にコマンドや情報を入力できる。他の入力装置（図示せず）には、ジョイスティック、ゲームパッド、サテライトディッシュ、スキャナなどを含めてもよい。これらの入力装置および他の入力装置は、多くの場合にシステムバスに接続されたユーザ入力インターフェイス１６０を介して処理装置１２０に接続するが、パラレルポート、ゲームポート、ＵＳＢ（ｕｎｉｖｅｒｓａｌ  ｓｅｒｉａｌ  ｂｕｓ）のような他のインターフェイスやバス構造によって接続してもよい。モニタ１９１または他のタイプの表示装置も、ビデオインターフェイス１９０のようなインターフェイスを介してシステムバス１２１に接続される。さらに、コンピュータには出力周辺インターフェイス１９５を介してスピーカ１９７やプリンタ１９６など、モニタ以外の周辺出力装置を接続できる。
【００２０】
コンピュータ１１０は、リモートコンピュータ１８０のような１台または複数台のリモートコンピュータへの論理接続を使用してネットワーク環境で動作する。リモートコンピュータ１８０は、パーソナルコンピュータ、ハンドヘルドデバイス、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、または他の一般的なネットワークノードでもよく、通常はコンピュータ１１０に関連して上に説明した要素の多くのまたはすべてが含まれる。図１に示す論理接続には、ローカルエリアネットワーク（ＬＡＮ：ｌｏｃａｌ  ａｒｅａ  ｎｅｔｗｏｒｋ）１７１とワイドエリアネットワーク（ＷＡＮ：ｗｉｄｅ  ａｒｅａ  ｎｅｔｗｏｒｋ）１７３が含まれるが、他のネットワークを含めてもよい。このようなネットワーキング環境は、オフィス、企業規模のコンピュータネットワーク、イントラネット、およびインターネットではごく一般的である。
【００２１】
ＬＡＮネットワーキング環境で使用する場合、コンピュータ１１０はＬＡＮ１７１にネットワークインターフェイスまたはアダプタ１７０を介して接続する。ＷＡＮネットワーキング環境で使用する場合、コンピュータ１１０は一般にインターネットなどのＷＡＮ１７３を介して通信を確立するためのモデム１７２またはその他の手段を備えている。モデム１７２（内蔵または外付け）は、ユーザ入力インターフェイス１６０または他の適切なメカニズムを使用してシステムバス１２１に接続できる。ネットワーク環境では、コンピュータ１１０またはその一部に関連して図示したプログラムモジュールをリモートメモリ記憶装置に格納できる。例として、図１にリモートコンピュータ１８０に格納されたリモートアプリケーションプログラム１８５を示すが、これに限定はされない。図示されたネットワーク接続が例示的なものであり、コンピュータ間の通信リンクを確立する他の手段を使用してもよいことは言うまでもない。
【００２２】
図２は、例示的なコンピューティング環境であるモバイルデバイス２００を示すブロック図である。モバイルデバイス２００には、マイクロプロセッサ２０２、メモリ２０４、入力／出力（Ｉ／Ｏ）コンポーネント２０６、およびリモートコンピュータまたはその他のモバイルデバイスと通信するための通信インターフェイス２０８が含まれる。１つの実施形態において、前述のコンポーネントは適切なバス２１０を介して互いに通信するために接続される。
【００２３】
メモリ２０４は、バッテリバックアップモジュール（図示せず）を備えたランダムアクセスメモリ（ＲＡＭ）などの不揮発性の電子メモリとして実装されるので、モバイルデバイス２００への一般的な電力が遮断されても、メモリ２０４内に格納された情報は失われない。メモリ２０４の一部はプログラム実行のためのアドレス指定可能なメモリとして割り当てられるのが好ましい。また、メモリ２０４の別の一部は例えばディスクドライブ上のストレージをシミュレートするストレージとして使用されるのが好ましい。
【００２４】
メモリ２０４には、オペレーティングシステム２１２、アプリケーションプログラム２１４、およびオブジェクトストア２１６が含まれる。動作中に、オペレーティングシステム２１２はプロセッサ２０２によってシステムメモリ２０４から実行されるのが好ましい。１つの好ましい実施形態において、オペレーティングシステム２１２はＭｉｃｒｏｓｏｆｔ  Ｃｏｒｐｏｒａｔｉｏｎから市販されているＷＩＮＤＯＷＳ（登録商標）ＣＥオペレーティングシステムである。オペレーティングシステム２１２は、モバイルデバイス用に設計されているのが好ましい。また、公開されたアプリケーションプログラミングインターフェイスおよびメソッドのセットを使用してアプリケーション２１４で利用できるデータベース機能を実装する。オブジェクトストア２１６内のオブジェクトは、少なくとも部分的には公開されたアプリケーションプログラミングインターフェイスおよびメソッドの呼び出しに応答して、アプリケーション２１４とオペレーティングシステム２１２によって保守される。
【００２５】
通信インターフェイス２０８は、モバイルデバイス２００が情報を送信および受信できるようにするための多くのデバイスおよび技術を表す。こうしたデバイスのいくつかの例を挙げると、有線および無線のモデム、サテライトレシーバ、ブロードキャストチューナーがある。モバイルデバイス２００は、コンピュータに直接接続して、それを使用してデータを交換してもよい。このような場合に、通信インターフェイス２０８は赤外線トランシーバでもシリアルまたはパラレル通信接続でも、ストリーミング情報を送信できるあらゆるものでよい。
【００２６】
入力／出力コンポーネント２０６には、タッチスクリーン（ｔｏｕｃｈ−ｓｅｎｓｉｔｉｖｅ  ｓｃｒｅｅｎ）、ボタン、ローラー、マイクロフォンなどのさまざまな入力装置と、オーディオジェネレータ、振動装置、ディスプレイを含むさまざまな出力装置が含まれる。上記にリストアップされた装置は一例であり、モバイルデバイス２００上にすべてが存在する必要はない。さらに、本発明の範囲を逸脱しない限り、モバイルデバイス２００にはその他の入力／出力装置を接続または配置してもよい。
【００２７】
言語モデルの枝刈り（ｐｒｕｎｉｎｇ）はメモリの制限に対処する１つの有望な技術であるが、圧縮は元の言語モデルのより多くの部分をメモリ内に格納できるので、より有効な代替技術である。
【００２８】
図３は、コンピューティングデバイスで使用する言語モデルを圧縮するプロセスの１つの実施形態を示す簡素化された流れ図である。プロセッサは、次の式に従って要素（ワード、ＵＲＬ、ｎ−ｇｒａｍなど）を数値１〜Ｐにハッシュ変換する。
【００２９】
ＨＧ＝ＨＡＳＨ（要素）％Ｐ
ここで、Ｐは適切な素数である。１つの実施形態では、例えば数値は整数値でもよい。ここで使用される整数という用語は小数点以下の端数のない数値を指し、すべての自然数とその負数、およびゼロが含まれる。プロセッサは、言語モデル内のすべての要素について、入力の各要素を整数にハッシュ変換する（ステップ３００）。ハッシュ値（ＨＧ）がソートされる（ステップ３０２）。リスト内の隣り合うハッシュ値（ＨＧ）間の最初の差（ＸＧ）が計算される（ステップ３０４）。インターアライバル（ｉｎｔｅｒａｒｒｉｖａｌｓ）はＧｏｌｏｍｂ符号を使用して格納される（ステップ３０６）。ここで使用される「インターアライバル」という用語は、Ｇｏｌｏｍｂ符号化されたデータの差またはゼロを表す。例えば、Ｐｏｉｓｓｏｎプロセスのインターアライバルは指数分布に従う。
【００３０】
Ｐｏｉｓｓｏｎプロセスを使用すると、Ｎ個の要素を格納するのに必要なメモリのビット数は、次の式で計算できる。
【００３１】
【数１】
2008547116.tif 000003
【００３２】
ここで、Ｎは要素の数である。素数Ｐはメモリの使用と損失との調整（ｔｒａｄｅｏｆｆ）、例えば次の連続する値間に期待される平均の差にＮをかけた結果より大きい最小の素数などを表す。本方法は要素のサイズには無関係なので、ロングワード、ＵＲＬ、ｎ−ｇｒａｍが短い要素より多くのメモリを消費するわけではない（メモリの使用に関して）。
【００３３】
図４は、図３に示すプロセスに従って計算されたハッシュ値間の差をＧｏｌｏｍｂ符号化するプロセスを示す簡素化された流れ図である。この流れ図は効率的なＧｏｌｏｍｂ符号化方式の１つの例を表しているということを理解されたい。当業者は商と剰余を計算するその他の方法を定義でき、こうした方法では符号化のメモリ必要条件に関する特徴は若干異なる。値Ｋは次の式に従って選択される。
【００３４】
【数２】
2008547116.tif 000004
【００３５】
ここで、Ｎは入力シーケンス内の項目（要素やｎ−ｇｒａｍなど）の数、ＰはＮを超える適切な素数（Ｎに連続する値の間に望まれる平均の差をかけた結果を超える最小の素数など）、関数ｃｅｉｌ（切り上げ）はその引数を下回らない最小の整数を表す（ステップ４００）。値Ｍは次の式に従って選択される
Ｍ＝２Ｋ
（ステップ４０２）。商の値Ｘｑは、最初の差の値（ＸＧ）のそれぞれについて次の式に従って計算される。
【００３６】
【数３】
2008547116.tif 000005
【００３７】
ここで、関数ｆｌｏｏｒ（切り捨て）はその引数を超えない最大の整数を表す（ステップ４０４）。剰余の値Ｘｒは、最初の差の値ＸＧのそれぞれについて、次の式に従って計算される
Ｘｒ＝ＸＧ  ｍｏｄ  Ｍ
（ステップ４０６）。
【００３８】
商の値Ｘｑは、ｕｎａｒｙ形式（Ｘｑ個のゼロビットの後に１つの１ビット）で符号化される（ステップ４０８）。剰余の値Ｘｒは、バイナリ形式でＫビットに符号化される（ステップ４１０）。図４に示すＧｏｌｏｍｂ符号化技術により、言語モデルを格納するメモリ必要条件が緩和され、商の値にはＸｑ＋ｌビット、剰余の値にはｌｏｇ２Ｍビットが必要である。
【００３９】
適切な近似値としてソートされたハッシュ値は、Ｐｏｉｓｓｏｎプロセスによって作成されたと考えられる。Ｐｏｉｓｓｏｎプロセスではインターアライバルは指数分布に従う。一般に、確率は次のように表すことができる。
【００４０】
Ｐｒ（ｘ）＝λｅ−λｘ
ここで、
【００４１】
【数４】
2008547116.tif 000006
【００４２】
ここで、変数λはインターアライバルを表す。メモリ使用量は次のように計算できる。
【００４３】
【数５】
2008547116.tif 000007
【００４４】
メモリ使用量は次の式で定義される。
【００４５】
【数６】
2008547116.tif 000008
【００４６】
このように、メモリ使用量は要素のサイズには無関係である。これは、ハッシュとＧｏｌｏｍｂ符号化を併用することにより全体のメモリ使用量、例えば、言語モデル全体のメモリ使用量が削減されることを示す。
【００４７】
図５は、アルファ符号（ｕｎａｒｙ符号）を示すＨｕｆｆｍａｎツリーの簡素化されたブロック図である。この場合は、記号Ａの確率は０．５、記号Ｂの確率は０．２５、以下同様である。ｘの確率を次のように仮定する。
【００４８】
Ｐｒ（ｘ）＝（１−Ｂ）ＢＸ
ただし、Ｂ＝１／２である。図式５００には複数のノードが含まれており、ノードの子のそれぞれに割り当てられる確率はほぼ等しい。ルートノード５０２はルートワードまたは記号を表す。記号は“Ａ”またはそれ以外である。記号がＡの場合は、ルート５０２からノード５０６Ａへのパスに対応して値“１”が割り当てられる。本システムは、ここで次のビットまたはビットシーケンスを検索する。記号がＡでない場合は、システムがゼロを割り当て、次いで記号がＢかどうかを確認する。記号がＢの場合は、次にシステムが５０４Ｂから５０６Ｂへのパスに対応して値“１”を割り当てる。したがって、記号Ｂの結果の値は“０１”、記号Ａの結果の値は“１”である。一般に、図式５００はｚ−ｌ個のゼロの後に１つの１が続くｕｎａｒｙシーケンスを示している。
【００４９】
下の表１は、ルートワードを基準としたグラフ内の位置に基づく記号の確率を示している。
【００５０】
【表１】
2008547116.tif 000009
【００５１】
図６は、Ｇｏｌｏｍｂ符号化された最初の差を復号化するプロセスを示す簡素化された流れ図である。商Ｘｑの記号が値“１”が検出されるまで１度に１ビットずつ読み込まれる（ステップ６００）。剰余Ｘｒの記号がバイナリで読み込まれる（ｌｏｇ２Ｍビットが読み込まれる）（ステップ６０２）。最終的に、ＸｑとＸｒから最初の差Ｘが次のように計算される。
【００５２】
ＸＧ＝Ｍ＊Ｘｑ＋Ｘｒ
これで出力ＸＧが復号化される（ステップ６０４）。この場合に、変数Ｍは最初の差として期待される値を２で割り、正の方向で最も近い整数に切り上げた値にほぼ等しい２のべき乗を表す。
【００５３】
図７は、Ｇｏｌｏｍｂ符号化された言語モデルを使用するように構成されたシステム７００の１つの実施形態を示す簡素化されたブロック図である。システム７００は、ユーザインターフェイス７０４、メモリ７０６内に格納されたＧｏｌｏｍｂ圧縮された言語モデル７０８、プロセッサ７１０、Ｇｏｌｏｍｂ符号器／復号器７１２、および統計学的なアルゴリズムのセット７１４が含まれるソフトウェアアプリケーション７０２を備える。ユーザは、インターフェイス７０４を使用してシステム７００にデータを入力する。Ｇｏｌｏｍｂ符号器／復号器７１２はユーザ入力を符号化し、符号化された入力をプロセッサ７１０に渡す。プロセッサは、符号化された入力をＧｏｌｏｍｂ圧縮された言語モデル７０６に対して分析し、一致の候補のセットを生成する。プロセッサ７１０は、Ｇｏｌｏｍｂ圧縮された言語モデル７０６内の語に基づいて１つまたは複数の一致の候補を、統計学的なアルゴリズム７１４を使用して選択し、ユーザに表示する出力としてこの１つまたは複数の一致の候補をユーザインターフェイス７０４に渡す。
【００５４】
表２は、本発明の１つの実施形態によるいくつかのパラメータ設定をリストに示している。
【００５５】
【表２】
2008547116.tif 000010
【００５６】
表２は、ＵＲＬに関するＧｏｌｏｍｂ符号化されたハッシュ値の１つの実施形態に関するメモリ使用量を示している。メモリはＵＲＬの数（Ｎ）と差の平均（Ｐ／Ｎ）の両方に依存する。この表には、ＵＲＬあたり１４〜２９ビットに対応する差の平均に関する３つの設定が示されている。この種の圧縮により、大規模な言語モデルを携帯用のデバイスに組み込むことができる。
【００５７】
一般に、言語モデルはユーザが情報にアクセスするのを支援するのに使用できる。例えば、検索エンジンでは、Ｇｏｌｏｍｂ符号化技術を使用してユーザが指定した検索用語の代わりのスペルをテストできる。携帯用デバイス上のＷｅｂブラウザのコンテキストでは、Ｇｏｌｏｍｂ圧縮（符号化／復号化）技術を使用して代わりのＵＲＬの値をテストし、ＵＲＬの入力ミスを修正することができる。
【００５８】
図８は、Ｇｏｌｏｍｂ符号化された言語モデルに対してユーザ入力を復号化するプロセスの１つの実施形態を示す簡素化された流れ図である。ユーザ入力は、例えばデータストリーム、ファイル、入力デバイスから記号が１つずつ受信される（または読み込まれる）（ステップ８００）。ユーザ入力が複数のｎ−ｇｒａｍに分割される（ステップ８０２）。複数のｎ−ｇｒａｍのそれぞれは、ハッシュ技術を使用して符号化される（ステップ８０４）。符号化された各ｎ−ｇｒａｍは、Ｇｏｌｏｍｂ符号化された言語モデルと比較され、一致の候補が特定される（ステップ８０６）。一致の候補のそれぞれについて、その一致の候補が受信したユーザ入力のＧｏｌｏｍｂ符号化された言語モデル内の要素への正しいマッピングである尤度が統計学的に評価される（ステップ８０８）。任意の数の統計学的アルゴリズムを使用して、特定の一致が正しい確率を評価できるように適用される。一般に、各ｎ−ｇｒａｍは図４に関連して先に説明したようなＧｏｌｏｍｂ符号化技術を使用して符号化できる。
【００５９】
本発明について、特定の実施形態に関連して説明してきたが、本発明の趣旨と範囲を逸脱せずに、その形態および細部においてさまざまな変更が可能なことを、当業者は認識されたい。
【図面の簡単な説明】
【００６０】
【図１】実施形態を実施できる１つのコンピューティング環境を示すブロック図である。
【図２】実施形態を実施できる別のコンピューティング環境を示すブロック図である。
【図３】コンピューティングデバイスで使用する言語モデルを圧縮するプロセスの１つの実施形態を示す簡素化された流れ図である。
【図４】図３に示すプロセスに従って計算されたハッシュ値間の差をＧｏｌｏｍｂ符号化するプロセスを示す簡素化された流れ図である。
【図５】アルファ符号（ｕｎａｒｙ符号）を示すＨｕｆｆｍａｎツリーの簡素化されたブロック図である。
【図６】Ｇｏｌｏｍｂ符号化された最初の差を復号化するプロセスの１つの実施形態を示す簡素化された流れ図である。
【図７】Ｇｏｌｏｍｂ符号化技術で圧縮された言語モデルを使用するように構成されたシステムの１つの実施形態を示す簡素化されたブロック図である。
【図８】ユーザ入力をＧｏｌｏｍｂ符号化された言語モデルに対して復号化するプロセスの１つの実施形態を示す簡素化された流れ図である。
【図１】
2008547116.tif 000012
【図２】
2008547116.tif 000013
【図３】
2008547116.tif 000014
【図４】
2008547116.tif 000015
【図５】
2008547116.tif 000016
【図６】
2008547116.tif 000017
【図７】
2008547116.tif 000018
【図８】
2008547116.tif 000019
【手続補正書】
【提出日】平成20年10月2日(2008.10.2)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
言語モデルを圧縮する方法であって、
ユーザ入力のｎ−ｇｒａｍから数値のリストを生成するステップと、
前記値のリストをソートするステップと、
前記リスト内で隣り合う値間の差を計算するステップと、
計算された差のそれぞれを、Ｇｏｌｏｍｂ符号を使用して符号化するステップと
を備え、
前記符号化するステップは、
前記リスト内で隣り合う値間の前記計算された差として期待される値の１／２にほぼ等しくなるような値Ｍを選択するステップと、
計算された差のそれぞれについて前記計算された差と前記値Ｍとの比率から商の値と剰余の値とを計算するステップと、
前記商の値と前記剰余の値とをメモリ内に格納するステップとを備えること
を特徴とする方法。
【請求項２】
前記格納するステップは、
前記商の値をｕｎａｒｙ形式で格納するステップと、
前記剰余の値をバイナリ形式で格納するステップとを備えることを特徴とする請求項１に記載の方法。
【請求項３】
前記商の値は、最も近い整数値に切り捨てられた前記値Ｍに対する最初の差の比率を含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記剰余の値は、最も近い整数値に切り捨てられた前記値Ｍに対する最初の差の比率の剰余を含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記符号化された差をメモリ内に格納するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項６】
前記符号化された差は式
【数１】
2008547116.tif 000020
に従ってメモリ内のいくつかのビット数を占有し、
Ｎはｎ−ｇｒａｍの数であり、Ｐは言語モデルコンテントのメモリの使用と損失とのトレードオフ値であること
を特徴とする請求項５に記載の方法。
【請求項７】
記憶媒体上にコンピュータ可読の命令を格納するステップをさらに備えており、前記コンピュータ可読の命令は生成、ソート、計算、符号化のステップを定義すること
を特徴とする請求項１に記載の方法。
【請求項８】
ユーザ入力を処理するシステムであって、
ユーザ入力を受信するように構成されたユーザインターフェイスと、
情報を格納し、Ｇｏｌｏｍｂ圧縮された言語モデルを格納するように構成されたメモリと、
ユーザ入力を符号化し、前記Ｇｏｌｏｍｂ圧縮された言語モデルの要素を復号化するように構成されたＧｏｌｏｍｂ符号器／復号器と、
ユーザ入力を前記Ｇｏｌｏｍｂ圧縮された言語モデルの要素と比較して一致の候補を特定するように構成されたプロセッサと
を備え、
前記Ｇｏｌｏｍｂ符号器／復号器はハッシュ値のリスト内のハッシュ値間の差として期待される値に基づいて値Ｍを計算するように構成されており、前記Ｇｏｌｏｍｂ符号器／復号器は前記差の前記期待される値に対する比率に基づいて商と剰余を計算するように構成されること
を特徴とするシステム。
【請求項９】
前記プロセッサで使用され、前記一致の候補を特定するように構成された統計学的アルゴリズムのセットをさらに備えることを特徴とする請求項８に記載のシステム。
【請求項１０】
前記プロセッサは前記特定された一致の候補をユーザに対して表示する出力として前記ユーザインターフェイスに提供するように構成されることを特徴とする請求項８に記載のシステム。
【請求項１１】
前記プロセッサはユーザ入力に関連する数値を計算するように構成されることと、前記Ｇｏｌｏｍｂ符号器／復号器は前記計算された数値を符号化するように構成されることとを特徴とする請求項８に記載のシステム。
【請求項１２】
ユーザ入力を復号化する方法であって、
受信されたユーザ入力を複数のｎ−ｇｒａｍに分割するステップと、
ハッシュ技術を使用して各ｎ−ｇｒａｍをハッシュして各ｎ−ｇｒａｍのｎ−ｇｒａｍハッシュ値を取得するステップと、
前記ｎ−ｇｒａｍハッシュ値をＧｏｌｏｍｂ符号化して符号化ｎ−ｇｒａｍを取得するステップと、
符号化された各ｎ−ｇｒａｍをＧｏｌｏｍｂ符号化された言語モデルと比較して一致の候補を特定するステップと、
各一致の候補が前記受信されたユーザ入力のＧｏｌｏｍｂ符号化された言語モデル内の要素への正しいマッピングである尤度を統計的に評価するステップと
を備え、
前記符号化された各ｎ−ｇｒａｍをＧｏｌｏｍｂ符号化された言語モデルと比較するステップは、
累計が符号化されたｎ−ｇｒａｍの値以上になるまで前記言語モデル内の符号化されたｎ−ｇｒａｍ間の差を合計するステップと、
前記受信されたユーザ入力を適切なｎ−ｇｒａｍの前記言語モデル内の値に関連付けるステップとを備えること
を特徴とする方法。
【請求項１３】
前記関連付けられた受信されたユーザ入力は前記一致の候補を含むことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記複数のｎ−ｇｒａｍはｎ−ｇｒａｍのリストを備え、
前記Ｇｏｌｏｍｂ符号化するステップは、
前記リスト内で隣り合うｎ−ｇｒａｍのｎ−ｇｒａｍハッシュ値間の差を計算するステップと、
前記計算された差のそれぞれについて前記リスト内で隣り合うｎ−ｇｒａｍハッシュ値間の前記計算された差として期待される値の１／２にほぼ等しくなるような値Ｍを選択するステップと、
計算された差のそれぞれについて前記差と前記Ｍの値との比率から商の値と剰余の値とを計算するステップと、
各ｎ−ｇｒａｍについて前記ｕｎａｒｙ形式の商の値と前記バイナリ形式の剰余の値とを組み合わせて前記符号化されたｎ−ｇｒａｍを形成するステップとを備えること
を特徴とする請求項１２に記載の方法。
【請求項１５】
前記値のリストは数値を含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
記憶媒体上にコンピュータ可読の命令を格納するステップをさらに備えており、前記コンピュータ可読の命令は分割、符号化、比較、評価のステップを定義すること
を特徴とする請求項１２に記載の方法。
【請求項１７】
プロセッサ及びメモリを有し、請求項１２に記載の方法に従ってユーザ入力をＧｏｌｏｍｂ圧縮された言語モデルと比較することによって前記ユーザ入力を復号化するように構成されたことを特徴とする携帯用コンピューティングデバイス。
【国際調査報告】
2008547116.tif 000021
2008547116.tif 000022
2008547116.tif 000023