"明細書に記載の発明。従って、中国語、日本語および韓国語のような非ローマ語におけるスペルエラーの効果的、効率的および正確な検出および修正をするためのコンピュータシステムおよび方法が必要とされている。規則に基づいた分類子および隠れマルコフモデルを使用して、中国語、日本語および韓国語のような非ローマ語に基づいた言語に対するスペルミスを処理および修正するシステムおよび方法が開示されている。具体的には、前記システムおよび方法は変換規則、隠れマルコフモデルおよび混乱させるような文字の類似行列を使用する。中国語スペルチェックアプリケーションでは、一対の混乱させるような文字間の前記類似は、前記文字が同じ発音を有する、および/または簡体字または繁体字中国語でのいくつかの入力キーストロークを共有する場合は、正の数であってもよい。それ以外の場合では、値は零である。一つの実施では、前記類似はブール値、例えば、1は一対の混乱させるような文字、また0は一対の混乱させない文字、を有していてもよい。前記システムと方法はとりわけ、例えば、ツールバーまたはデスクバーに実装される、クライアントサイトで、ウェブに基づく検索エンジンおよびダウンロード可能性のあるアプリケーションに適用できるが、その他の様々なアプリケーションに適用できる。本発明は、プロセス、器具、システム、装置、方法、またはプログラム命令が光回線または電子通信回線上で送信されるコンピュータ可読の記憶媒体またはコンピュータネットワークのようなコンピュータ可読の媒体を含み、多数の手段で実行できることが理解されるべきである。用語コンピュータとは一般に、携帯情報端末PDA、携帯電話およびネットワークスイッチのような計算能力を持ついかなる装置をもいう。本発明の独創的な実施形態がいくつか以下に説明されている。前記方法は一般に、中国語のような第一言語での入力エントリーを第一言語とは異なるピンインのような中間表現での少なくとも一つの中間エントリーに変換すること、前記中間エントリーを前記第一言語での入力の少なくとも一つの可能性のある代替のスペルに変換すること、および前記入力エントリーと前記入力エントリーに対する全ての可能性のある代替のスペル間での一致がそれぞれ特定されたまたはされない場合、前記入力エントリーが正確な入力エントリーかまたは疑わしい入力エントリーであることを決定することを含む。本発明においては、ピンインとは、注音符号ボポモフォ、すなわち注釈音声の表記法を含む、簡体字または繁体字中国語のための全ての音声表記法をいう。前記第一言語での混乱させるような文字の対の間の類似は、中間表現での共通のトークン信号に従い定義できる。前記疑わしい入力エントリーは、例えば、変換規則生成器により生成される変換規則に基づいて、変換規則に基づいた分類子を使用して分類されてもよい。決定ツリーおよびニューラルネットワーク分類子などのその他の様々な分類子は同様に採用されてもよい。前記変換は、クエリーログ中のユーザークエリーのような複数の入力エントリーを変換することを含んでもよい。前記方法はさらに、例えば、変換規則に基づく分類子により、スペル修正変換規則のような一組の規則に基づいて正確にスペルされたエントリーまたは誤ってスペルされたエントリーとして前記疑わしいエントリーを分類することを含んでもよい。ユーザーの投票、例えば、クエリーログおよび/またはウェブページは、前記変換規則を生成するために好ましくは使用される。前記方法は前記疑わしい入力エントリーおよび前記可能性のある代替のスペルを使用する変換規則生成器を使用して、前記スペル修正変換規則を生成および訓練することも含んでもよい。前記方法はさらに、前記第一言語でユーザー入力を受信すること、前記規則の何れかが前記ユーザー入力に適合することを決定すること、少なくとも一つの規則が前記ユーザー入力に適合することを決定した後に、前記ユーザー入力に対応する前記第一言語での少なくとも一つの代替のスペルを生成すること、前記ユーザー入力についての可能性と前記ユーザー入力の少なくとも一つの代替のスペルについての可能性を比較することと、前記ユーザー入力よりも高い可能性を有する前記ユーザー入力の少なくとも一つの代替のスペルを伴うスペル修正提案およびスペル修正をすることを含んでもよい。システムは一般に、第一言語での入力を前記入力エントリーの少なくとも一つの中間表現前記中間表現は前記第一言語と異なるに、変換するように構成された第一変換器、および前記可能性のある代替のスペルを前記入力エントリーと比較することにより一致を特定し、一致が全ての可能性のある代替のスペルから特定されない場合、前記入力エントリーは疑わしい入力エントリーであると決定、また一致が特定された場合、前記入力エントリーは正確な入力エントリーであると決定し、前記中間表現を前記第一言語での入力の少なくとも一つの可能性のある代替のスペルに変換するように構成された第二変換器を含む。コンピュータシステムと協働して用いるコンピュータプログラム製品であって、前記コンピュータプログラム製品はコンピュータプロセッサ上で実行可能性のある命令を記憶するコンピュータ可読の記憶媒体を有し、前記命令は一般に、第一言語での入力エントリーを受信すること、前記入力エントリーを前記入力エントリーの少なくとも一つの中間表現に変換すること、前記中間表現は前記第一言語と異なるが、前記中間表現を前記第一言語での少なくとも一つの可能性のある代替のスペルに変換すること、少なくとも一つの可能性のある代替のスペルを前記入力エントリーと比較することにより一致を特定すること、また一致が全ての可能性のある代替のスペルから特定されない場合、前記入力エントリーは疑わしい入力エントリーであると決定し、また一致が特定された場合、前記入力エントリーは正確な入力エントリーであると決定することを含む。前記システムおよび方法をインプリメントするアプリケーションは、文書に入力するテキストにスペル修正を行なうために、または検索エンジンのようなリモートサーバーとインターフェースをとるために、検索エンジンのようなサーバーサイト上でインプリメントされてもよく、または、例えば、ダウンロードされた、ユーザーのコンピュータのようなクライアントサイト上でインプリメントされてもよい。前記クライアントサイトのアプリケーションは任意で、例えば、XがZの先に来るまたは後に来る場合を除きXおよびYを絶対に置換しないなど、特定のスペル修正を許可しないことを指示することにより、前記ユーザーが前記アプリケーションをカスタマイズすることを可能にするユーザーが編集できる停止規則パターンテーブルを含んでもよい。本発明のこれらおよびその他の特徴および長所は、以下の詳細な説明および本発明における例示的な実施形態を介して説明する添付の図でさらに詳しく提示される。例えば、本発明は以下の項目を提供する。項目1第一言語における入力エントリーを受信することと、前記入力エントリーを、前記第一言語とは異なる中間表現における少なくとも一つの中間エントリーに変換することと、前記中間エントリーを、前記第一言語における前記入力エントリーの少なくとも一つの可能性のある代替形式に変換することと、一致を特定するために、前記入力エントリーを前記入力エントリーの少なくとも一つの可能性のある代替形式と比較することと、前記比較することに基づいて、前記入力エントリーが疑わしい入力エントリーであることを決定することとを包含する、方法。項目2前記中間エントリーは、前記第一言語における前記入力エントリーの複数の可能性のある代替形式へ変換され、前記比較することは、前記入力エントリーを前記第一言語における前記入力エントリーのそれぞれの可能性のある代替物と比較することを含み、前記決定することは、一致が前記可能性のある全ての代替形式から特定されない場合、前記入力エントリーは疑わしい入力エントリーであると決定し、一致が特定された場合、前記入力エントリーは正確な入力エントリーであると決定することを含む、項目1に記載の方法。項目3前記第一言語は非ローマ語に基づいた言語である、項目1に記載の方法。項目4前記第一言語は中国語であり、前記中間表現はピンインである、項目1に記載の方法。項目5前記入力エントリーはクエリーログ内のユーザークエリーである、項目1に記載の方法。項目6前記受信することは、複数の入力エントリーを受信することを含む、項目1に記載の方法。項目7一組の規則に基づいて、正確にスペルされたエントリーと不正確にスペルされたエントリーとのうちの一つとして、前記疑わしいエントリーを分類することをさらに含む、項目1に記載の方法。項目8前記分類することは、変換規則に基づく分類子により実行される、項目7に記載の方法。項目9前記規則はスペル修正変換規則であり、前記疑わしい入力エントリーと前記少なくとも一つの可能性のある代替形式とを使用する変換規則生成器を使用して、前記スペル修正変換規則を生成および訓練することをさらに備える、項目7に記載の方法。項目10前記スペル修正変換規則を生成および訓練することは、疑わしい入力エントリーのデータベースを使用して自動的に実行される、項目9に記載の方法。項目11前記分類することは、自動監視と手動監視とのうちの少なくとも一つにより実行される、項目7に記載の方法。項目12前記第一言語においてユーザー入力を受信することと、前記規則の何れかが前記ユーザー入力に適用されるか否かを決定することと、少なくとも一つの規則が前記ユーザー入力に適用されることを決定した後に、前記ユーザー入力に対応する、前記第一言語における少なくとも一つの代替形式を生成することと、前記ユーザー入力の可能性と、前記ユーザー入力の少なくとも一つの代替形式の可能性とを比較することと、前記ユーザー入力よりも高い可能性を有する前記ユーザー入力の少なくとも一つの代替形式を用いて、スペル修正提案とスペル修正とのうちの少なくとも一つを行なうこととをさらに含む、項目7に記載の方法。項目13ユーザー入力と代替のスペルとの特定の規定された組み合わせに対して、スペル修正提案またはスペル修正を行なうことを許可しない停止規則パターンのユーザー編集可能なテーブルを維持することをさらに含む、項目12に記載の方法。項目14第一言語における入力を、前記第一言語とは異なる中間表現における少なくとも一つの中間エントリーに変換するように構成された第一変換器と、前記中間エントリーを、前記第一言語における入力の少なくとも一つの可能性のある代替のスペルに変換するように構成された第二変換器と、前記入力エントリーを、一致を特定するために少なくとも一つの可能性のある代替のスペルと比較するように構成された比較器であって、前記比較に基づいて前記入力エントリーが疑わしい入力エントリーであるかどうかを決定するようさらに構成されている、比較器とを備える、システム。項目15前記第二変換器は、前記中間エントリーを前記第一言語における前記入力エントリーの複数の可能性のある代替形式へ変換するように構成されており、前記比較器は、前記入力エントリーを前記第一言語における前記入力エントリーの前記少なくとも一つの可能性のある代替物のそれぞれと比較するように構成されており、また、一致が全ての前記可能性のある代替形式から特定されない場合、前記入力エントリーは疑わしい入力エントリーであると決定し、一致が特定された場合、前記入力エントリーは正確な入力エントリーであと決定するように構成されている、項目14に記載のシステム。項目16前記第一言語は非ローマ語に基づいた言語である、項目14に記載のシステム。項目17前記第一言語は中国語であり、前記中間表現はピンインである、項目14に記載のシステム。項目18前記入力エントリーはクエリーログ内のユーザークエリーである、項目14に記載のシステム。項目19一組の規則に基づいて、正確にスペルされたエントリーと不正確にスペルされたエントリーとのうちの一つとして、前記疑わしいエントリーを分類するように構成された分類子をさらに備える、項目14に記載のシステム。項目20前記分類子は変換規則に基づく分類子である、項目19に記載のシステム。項目21前記分類子の前記規則はスペル修正変換規則であり、前記分類子は、前記第一言語における前記入力の前記疑わしい入力エントリーと、前記少なくとも一つの可能性のある代替のスペルとを使用する前記スペル修正変換規則を生成する変換規則生成器をさらに含む、項目19に記載のシステム。項目22前記変換規則生成器は、疑わしい入力エントリーのデータベースを使用して、前記変換規則を自動的に生成する、項目21に記載のシステム。項目23前記分類子は自動監視と手動監視とのうちの少なくとも一つを実行する、項目19に記載のシステム。項目24前記規則の何れかがユーザー入力に適用されるかどうか決定するように構成された検出器と、少なくとも一つの規則が前記ユーザー入力に適用されることを決定した後に、前記第一言語における前記ユーザー入力の少なくとも一つの代替のスペルを生成するように構成された生成器と、前記ユーザー入力の可能性と、前記ユーザー入力の少なくとも一つの代替のスペルの可能性とを比較するように構成された比較器と、前記ユーザー入力よりも高い可能性を有する前記ユーザー入力のうちの少なくとも一つの代替のスペルを用いて、スペル修正提案とスペル修正とのうちの少なくとも一つを行なうように構成された修正器とをさらに備える、項目19に記載のシステム。項目25ユーザー入力と代替のスペルとの特定の規定された組み合わせに対して、前記修正器がスペル修正提案またはスペル修正を行なうことを許可しないカスタマイズ可能な停止規則パターンテーブルをさらに備える、項目24に記載のシステム。項目26コンピュータシステムと協働して用いるコンピュータプログラム製品であって、前記コンピュータプログラム製品は、コンピュータプロセッサ上で実行可能な命令を記憶するコンピュータ可読記憶媒体を備え、前記命令は、第一言語において入力エントリーを受信することと、前記入力エントリーを、前記第一言語とは異なる中間表現における少なくとも一つの中間エントリーに変換することと、前記中間エントリーを、前記第一言語における前記入力エントリーの少なくとも一つの可能性のある代替形式に変換することと、前記入力エントリーを、一致を特定するために前記入力エントリーの少なくとも一つの可能性のある代替形式と比較することと、前記比較することに基づいて前記入力エントリーが疑わしい入力エントリーであることを決定することとを包含する、コンピュータプログラム製品。項目27前記中間エントリーは、前記第一言語における前記入力エントリーの複数の可能性のある代替形式へ変換され、前記比較することは、前記入力エントリーを、前記第一言語における前記入力エントリーのそれぞれの可能性のある代替物と比較することを含み、前記決定することは、一致が全ての前記可能性のある代替形式から特定されない場合、前記入力エントリーは疑わしい入力エントリーであると決定し、一致が特定された場合、前記入力エントリーは正確な入力エントリーであると決定することを含む、項目26に記載のコンピュータプログラム製品。項目28前記第一言語は非ローマ語に基づいた言語である、項目26に記載のコンピュータプログラム製品。項目29前記第一言語は中国語であり、前記中間表現はピンインである、項目26に記載のコンピュータプログラム製品。項目30前記入力エントリーはクエリーログ内のユーザークエリーである、項目26に記載のコンピュータプログラム製品。項目31前記受信することは複数の入力エントリーを受信することを含む、項目26に記載のコンピュータプログラム製品。項目32前記コンピュータプログラム製品は、ツールバー内のクライアントサイトにインプリメンとされる、項目26に記載のコンピュータプログラム製品。項目33前記命令は、一組の規則に基づいて、正確にスペルされたものと、不正確にスペルされたものとのうちの一つとして、前記疑わしいエントリーを分類することをさらに含む、項目26に記載のコンピュータプログラム製品。項目34前記分類することは変換規則に基づいた分類である、項目33に記載のコンピュータプログラム製品。項目35前記規則はスペル修正変換規則であり、前記命令は、前記疑わしい入力エントリーと前記少なくとも一つの可能性のある代替形式とを使用する変換規則生成器を用いて、前記スペル修正変換規則を生成および訓練することをさらに含む、項目33に記載のコンピュータプログラム製品。項目36前記スペル修正変換規則は、疑わしい入力エントリーのデータベースを使用して自動的に生成される、項目35に記載のコンピュータプログラム製品。項目37前記分類することは、自動監視と手動監視とのうちの少なくとも一つで実行される、項目33に記載のコンピュータプログラム製品。項目38前記命令は、前記第一言語においてユーザー入力を受信することと、前記規則の何れかが前記ユーザー入力に適用されることかどうか決定することと、少なくとも一つの規則が前記ユーザー入力に適用されると決定した後に、前記ユーザー入力に対応する前記第一言語における少なくとも一つの代替形式を生成することと、前記ユーザー入力の可能性と前記ユーザー入力の少なくとも一つの代替形式の可能性とを比較することと、前記ユーザー入力よりも高い可能性を有する前記ユーザー入力の少なくとも一つの代替形式を使用して、スペル修正提案とスペル修正とのうちの少なくとも一つを行なうこととをさらに含む、項目33に記載のコンピュータプログラム製品。項目39前記命令は、ユーザー入力と代替形式との特定の規定された組み合わせに対して、スペル修正提案またはスペル修正を行なうことを許可しない停止規則パターンのユーザーが編集可能なテーブルを維持することをさらに含む、項目38に記載のコンピュータプログラム製品。規則に基づいた分類子および隠れマルコフモデルを使用して、中国語、日本語および韓国語のような非ローマ語に基づいた単語に対するスペルミスを処理および修正するシステムおよび方法が開示されている。明確にするだけの目的で、ここで提示されている例は中国語のスペルエラー検出および修正、より具体的には、簡体字中国語のスペルエラー検出および修正に適用可能である。しかしながら、スペルエラー検出および修正のための前記システムおよび方法は同様に、繁体字中国語、日本語、韓国語、タイ語などのような他の非ローマ語に基づく言語に適用可能であり得る。以下の説明は、当業者であれば誰でも本発明を作りまた使用することが出来るように示されている。具体的な実施形態およびアプリケーションの説明は、実例としてのみ提供される。様々な改良は当業者にとって容易に明白となる。本明細書で定義される一般的な原理は、本発明の精神および範囲を逸脱することなく、その他の実施形態およびアプリケーションに適用され得る。従って、本発明は、本明細書で開示されている原理および特徴と一致する多数の代替物、改良および相当物を網羅する最も幅広い範囲を与えるものである。明確にする目的で、本発明に関連して当該技術分野において知られている技術上の資材に関する詳細は、本発明を不必要に分かりにくくしないために、詳細には説明されていない。本明細書で説明されているシステムおよび方法は、一般に、入力エントリーから生成されるスペル修正変換規則を使用して、非ローマ語の言語でのスペルエラーを処理および修正することに関連している。本明細書では、スペルという用語は、前後関係で不適切に使用される有効な文字または単語と同様に、語彙の文字または単語以外であることどちらも指す。さらに、入力の代替のスペルまたは代替形式という用語は、本明細書において、入力が単一文字または単語、一連または一固まりの文字および/または単語、句、文などであろうとなかろうと、前記入力とは異なるが同じ言語である代替の組の文字または/および単語を指すために使用される。疑わしい入力エントリーは入力エントリーから識別され、また可能性のある代替のスペルは、図1で示される疑わしい入力エントリー検出器によって生成される。入力の時に疑わしい入力エントリー検出器から出る疑わしい入力エントリーおよび可能性のある代替のスペルを使用して、スペル修正変換規則はその後生成および訓練されtrain、疑わしいエントリーは、図2に示すように変換規則生成器および分類子によって、正確であるか、または不正確であるとして分類されている。前記システムおよび方法は変換規則、隠れマルコフモデルおよび混乱させるような文字の類似行列を使用する。中国語のアプリケーションでは、一対の混乱させるような文字間の類似度は、文字が同じ発音を有する、および/または簡体字または繁体字中国語でのいくつかの入力キーストロークを共有する場合は、正の数であり得る。それ以外の場合、値は零である。一つのインプリメンテーションでは、類似度はブール値例えば、1は一対の混乱させるような文字、また0は一対の混乱させない文字を有し得る。訓練された一組のスペル修正変換規則を使用して、スペルエラーを識別し、提案されたスペル修正を生成するプロセスを図4のフローチャートに示す。従って、変換規則を訓練するための一組の入力を使用して、最もよく起こるスペルエラーおよび修正は、スペルチェックおよび修正システムの効率および効果を高めるために決定および処理され得る。図1は、疑わしいオリジナルの入力を識別するために、また疑わしいオリジナルの入力に対する可能性のある代替のスペルを決定するために、例えば、簡体字中国語のピンインのような中間形式への、または中間形式からの、順方向および逆方向の変換を実行するための例示的な疑わしい入力エントリー検出器100のブロック図である。図1に示される疑わしい入力エントリー検出器100は、ピンインが簡体字中国語ではよく使われる入力方法であるという都合のよい事実を使用する。しかしながら、ローマ語に基づくまたは非ローマ語に基づくその他のどのような中間形式もインプリメントおよび利用され得る。同様に、疑わしい入力エントリー検出器100は、様々なその他の非ローマ語に基づく言語とともに使用するために適合され得る。図1に示すように、単語ピンイン変換器104は、中国語文字でのそれぞれのオリジナルのエントリー102を、オリジナルのエントリー102に対応する一つ以上の発音またはピンイン106に変換する。ピンイン単語変換器108は、その後ピンイン106を中国語の文字での可能性のあるスペル110に変換する。第一言語でのテキストを中間表現に変換、そしてその後第一言語に戻すためのその他の適切な変換器104、106が採用され得る。ピンインはただ単に中国語または簡体字中国語のための都合のよい中間表現に過ぎない。比較器112は、オリジナルの入力102と、可能性のあるスペル110を、第一言語で、および一致することを決定するために比較する。オリジナルのエントリー102がピンイン単語変換108により出力される、可能性のあるスペル110のうちの一つに一致する場合、オリジナルのエントリー102は正確にスペルされた114と一致すると見なされる。しかしながら、オリジナルのエントリー102がピンイン単語変換108により出力される、どの可能性のあるスペル110に一致しない場合、オリジナルのエントリー102は疑わしいエントリー116すなわち不正確であり得るものとなる。ピンインは簡体字中国語の文字を入力するために主に使用される音声入力方法である。本明細書で参照される場合、ピンインは一般に、中国語の文字に関連する音の表現の有無を問わず、中国語の文字の音声表現を指す。とりわけ、ピンインは、注音符号ボポモフォ、すなわち注釈音の表記法を含む、簡体字または繁体字中国語のための全ての音声表記法を指す。ピンインはローマ字を使用し、複数の音節単語の形で挙げられる語彙を有する。中国語は多数の同形異義語および同音異義語を有するために、それぞれのオリジナルのエントリー102は単語ピンイン104により複数のピンイン106に変換され得、同様に、それぞれのピンイン106はピンイン変換器108により中国語の文字110での複数の可能性のあるスペルに変換され得る。とりわけ、数万ある中国語の文字漢字を表現するトーンを含み異なる音声音節ピンインにより表現されるようには約1,300のみ、またトーンを含まない音声音節は約400のみしかないので、一つの音声音節トーンを含む、含まないを問わずは多くの異なる漢字に対応し得る。例えば、マンダリンでのyiの発音は100を超える漢字に対応し得る。従って、それぞれのオリジナルのエントリー102をピンイン106に変換し、その後中国語の文字110に戻すという、単語ピンイン変換器104およびピンイン単語変換器108によりインプリメントされるプロセスは、同形異義語および/または同音意義語である単語が中国語では大部分を占めることを考慮に入れれば重要なことであり得る。本明細書で説明されるシステムおよび方法は、変換規則、隠れマルコフモデルおよび混乱させるような文字の類似行列を使用する。中国語のアプリケーションでは、一対の混乱させるような文字間の類似度は、文字が同じ発音を有する、同様の入力キーストロークを共有する、および/または同様にスペルされる、すなわち視覚的に同様である場合は、正の数であり得る。それ以外の場合では、値は零である。一つのインプリメンテーションでは、類似度はブール値例えば、1は一対の混乱させるような文字、また0は一対の混乱させない文字を有し得る。第一言語での混乱させるような文字の対間の類似度は、中間表現での共通のトークン信号に従って定義され得る。中国語の単語をピンインに変換、またピンインを中国語の単語に変換する様々な適切なメカニズムがインプリメントされ得る。例えば、様々なデコーダはピンインを漢字中国語の文字に翻訳するのに適している。一実施形態では、隠れマルコフモデルを使用するビタビデコーダがインプリメントされ得る。隠れマルコフモデルのための訓練は、例えば、経験によるカウントをまとめることにより、または予想をコンピュータで計算し、また反復最大化プロセスを実行することにより達成され得る。ビタビアルゴリズムは、マルコフコミュニケーションチャネルの出力観察に従ってソース入力を復号するために有用および効率的なアルゴリズムである。ビタビアルゴリズムは、音声認識、光学式文字認識、機械翻訳、スピーチタグ、構文解析およびスペルチェックのような自然言語の処理のための様々なアプリケーションにうまくインプリメントされている。しかしながら、マルコフ仮定の代わりに、その他の様々な仮定が復号アルゴリズムをインプリメントするのになさ得ることは理解されるべきである。さらに、ビタビアルゴリズムは単に、デコーダによりインプリメンとされ得る一つの適切な復号アルゴリズムおよび有限状態機械のようなその他の様々な適切な復号アルゴリズムにすぎず、ベイジアンネットワーク、決定平面アルゴリズム高次元ビタビアルゴリズムまたはBahl-Cocke-Jelinek-RavivBCJRアルゴリズム2パス順方向/逆方向ビタビアルゴリズムがインプリメントされ得る。疑わしい入力エントリー検出器100により検出される疑わしいエントリーはほぼ全てのスペルエラーを含む。しかしながら、疑わしいエントリーは一般に、比較的高い誤警報/偽陽性率、すなわち、不正確なクエリーの数に対して不正確であると表示される正確なクエリーの数の比率をも含む。以下でより詳細に説明されるように、疑わしいエントリー検出器100により決定される疑わしいクエリー116は、その後正確または不正確であると分類され得る。分類子は変換規則に基づく分類子、好ましくは、決定ツリー分類子、ニューラルネットワーク分類子および同等のものであってもよい。正確として分類されたエントリーに対しては、提案はなされない。不正確として分類されたエントリーに対しては、それぞれの可能性のある代替のスペルの可能性によるが、提案がなされてもよい。図2は、疑わしいエントリー検出器100により処理されるときに、一組のオリジナルの入力102からスペル修正変換規則を生成するための例示的なシステムおよび方法120のブロック図である。とりわけ、一組のオリジナルのエントリー102は、ウェブの検索エンジンのためのクエリーログのようなユーザー入力エントリーおよび/または、例えばインターネット上で入手可能な文書のようなものから得られるエントリーを含んでもよい。ユーザー入力エントリーの場合は、一組のオリジナルの入力102は、例えば過去三週間または二ヶ月からユーザークエリーの集合を含んでもよい。文書の例は、新聞、本、雑誌、ウェブページまたは同等のもののようなウェブコンテンツおよび様々な公表物を含んでもよい。一組のオリジナルの入力102は、文書例えばインターネット上で入手可能な簡体字および/または繁体字中国語で書かれた文書の一式、集合または保存場所から引き出されてもよい。本明細書で説明される例示的なシステムおよび方法はとりわけ、ウェブ検索エンジンの文脈内および組織データを含んでいるデータベースのための検索エンジンに適用できることに留意されたい。しかしながら、前記システムおよび方法は、特に非ローマ語でのエントリーに対してのスペルエラー検出および修正のためのその他の様々なアプリケーションに適合および採用されてもよいことは理解されるべきである。例えば、前記システムおよび方法は、スペルエラーを検出および修正するCJKテキスト入力アプリケーション、例えば、文書処理アプリケーションに適合されてもよい。変換規則生成器および分類子120は、訓練データ、例えば人により注釈がつけられた不正確なスペルからの信頼度に従い、訓練の期間中、変換規則を自動的に引き出し学習しまた順位付けをする、EricBrillにより導入された、変換に基づく学習アルゴリズムをインプリメントする。これらの変換規則は注釈器/投票器124により使用される。変換規則は、変換規則が言語的知識よりもむしろ統計に基づいている言語学に使用されるという点で、文法規則と異なることに留意されたい。従って、例えば、ほとんどのエントリーが同様の不正確な方法で特定の単語を不正確にスペルした場合、前記不正確なスペルは正確として分類される。変換規則に基づく方法についての追加情報は、その全容が参考により本明細書に援用される、2004年1月27日にEricBrillに発行された、LinguisticDisambiguationSystemandMethodUsingString-BasedPatternTrainingtoLearntoResolveAmbiguitySitesと表題のついた米国特許第6,684201号に示されている。従って、変換規則生成器120は自動的に、すなわち、ユーザーの投票を利用し監視されずに、規則を生成する。言い換えれば、文字のパターンの正確さは、データベースでの大多数の投票例えば人により注釈がつけられたデータよりもクエリーログに従い決定される。それぞれの変換規則は、より高い信頼度の規則がより低い信頼度の規則よりも遅い時点で適用されるように、信頼度と関連している。一例として、第一の変換規則は、BがXより先に来る場合、XとYを置換することを特定してもよい。より高い信頼度のある第二の変換規則は、EがYの後に来る場合、YとXを置換することを特定してもよい。従って、第一の変換規則は、BYEを生成するためにエントリーBXEに最初に適用される。第二の変換規則はその後、エントリーをBXEに戻すために結果として生じるエントリーBYEに適用される。明確であるように、変換規則が適用される順番は結果に影響を与え得る。置換される文字および置換文字はエントリーのどの要素であってもよく、必ずしも単語である必要はないことも留意されたい。同様に、条件はどのような文脈、発話の一部であるタグまたは文法上の非末端ラベル例えば、名詞句のNPに基づいてもよい。変換規則に基づく分類子が好ましいとはいえ、単純ベイズ分類子、決定ツリー分類子、ニューラルネットワーク分類子またはその他の様々で適切などの分類子も同様に、疑わしいエントリー116を分類するためにインプリメントされてもよいことにさらに留意されたい。図2に戻り、示すように、疑わしいエントリー検出器100により出力されるそれぞれの疑わしいエントリー116およびそれに対応する可能性のある代替のスペル110は、スペル修正変換規則生成器120の注釈器124により受信される。注釈器124は最初の変換規則126に最初に、また引き出されまた順位付けをされた変換規則130に最終的に基づくエントリー128を分類する。学習段階では監督されても、すなわち人員による、および/または監督されなくてもよい。一つのインプリメンテーションでは、最初の組の手作業により作成された2、3の一般的な変換規則は、何らかの人間による監視付き、またはユーザーの投票を利用して人間による監視なしで、小さな組の疑わしいエントリーに自動的に注釈を付けるために利用される。最初の学習段階の後では、追加の変換規則は生成され、好ましくは、同様にいくつかの人による監視付きで、また追加の疑わしいエントリーは注釈を付けられる。例えば、比較的少ない規則を伴うかなりの量のユーザー情報を管理する結果として生じる規則は、非常に信頼性があると見なされてもよく、また、従って高い信頼度に相当するとしてもよい。より高い信頼を有する規則は概して、より低い信頼を有するものよりも対象範囲が狭いので、高い信頼を有する規則および比較的より低い信頼を有する規則と両方が使用されることに留意されたい。例えば、比較的小さな割合のユーザー情報を占める比較的多数の残った疑わしいエントリーは費用効果の目的から人による監視なしで自動的に生成されてもよい。そのような規則を自動的に生成する一つの実例となるプロセス150を図3のフローチャートに示す。とりわけ、ループ152でのそれぞれの疑わしいクエリーQに対して、またループ154でのそれぞれの対応する代替のスペルQ’に対して、Qおよび代替スペルQ’の比較は、場合により不適切なQの中の文字およびそれらの代用C’を決定するためにブロック156でされる。ブロック158では、幅2N1の窓は、Cに先行するN個の文字および後続するN個の文字を伴い開かれる。文脈の適切などの長さも、例えば、2N1はインプリメントされてもよく、また問題になっている文字の前および後の文脈の長さは同等であってもよいが必ずそうであるという必要はない。C_{-N}、...、C、...、C_{N}からの全ての部分列Cの前、C、Cの後の頻度FCの前、C、Cの後は、規則が有効であること、すなわち、規則が疑わしいエントリーの中で適度に多くの割合のスペルエラーを対象範囲にすることが出来るかどうかを確実にするためにカウントされる。文字列S=xs1,xs2,...、xsjは、1≦sl<s2...<sj<kの場合、文字列X=x1,x2,...xkの部分列である。次に、ブロック160では、CおよびC’の置換により対応頻度が決定される。決定ブロック162はその後、規則に信頼性があるかどうか、例えば、クエリーログおよびウェブページ、つまりユーザーの投票を利用して、判断する。規則は信頼性があると決定された場合、変換規則、すなわち、Cの前、Cの後である場合のCの代用C’を引き出す。とりわけ、Tlが最小有意閾値およびT2が最小信頼閾値である時、FCの前、C、Cの後>T1およびFCの前、C’、Cの後/FCの前、C、Cの後>T2の場合、規則は信頼性があると見なされる。上で述べたように、変換規則生成器によりインプリメントされるプロセス150は自動的に、すなわち、監督なしで、データベースでの多数の投票、例えば、人により注釈がつけられたデータよりもクエリーログに従い決定される文字パターンの正確性のようなユーザーの投票を利用して規則を生成する。最も頻度の高い変換規則はエラーパターンの非常に大きな割合を管理するので、規則の集まりの大きさは好ましくは、疑わしいエントリーの数とともに急速に増加しない。それぞれの規則の最低限の発生は、変換規則の集まりの大きさを限定するために設定されてもよい。本明細書で説明されるシステムおよび方法をインプリメントするアプリケーションは、テキスト入力用のスペル修正をワープロ文書へ提供するために、または検索エンジンのようなリモートサーバーとインターフェースするために、検索エンジン上のようなサーバーサイトでインプリメントされてもよく、またはエンドユーザーのコンピュータのようなクライアントサイトで、例えばダウンロードしてインプリメントされもよい。クライアントサイトアプリケーションは、例えば、ツールバー内にインプリメントされてもよく、またオプションとして、XがZの先に来るまたは後に来る場合を除きXおよびYを絶対に置換しないなど、特定のスペル修正を許可しないことを指示することにより、ユーザーがアプリケーションをカスタマイズすることを可能にするユーザーが編集できる停止規則パターンテーブルを含んでもよい。例えば、買うおよび売るなどいくつかの中国語の文字は、同じ発音マイしかし、異なるトーンを有し、また言語でのほとんど同じ構文的役割を有するが完全に異なる意味を有する。多くの自動的なスペル規則生成プログラムは、買うを売る、または逆もまた同様に不正確に変更する傾向がある。エンドユーザーは、スペル修正アプリケーションにXとYの置換が起こらないようにするために、停止規則パターンテーブルの中に、停止規則X、Yを指示してもよい。図4は、もしあれば、スペル修正提案を決定するためにエントリーを処理する変換規則を利用するプロセス200を示すフローチャートである。決定ブロック202は、いかなるスペル修正規則もユーザー入力に適用できることを決定する。決定ブロック202を実行するために、スペル修正変換規則のハッシュテーブルは、いかなる変換規則もユーザー入力に適用できることを決定するために検査されてもよい。例えば、既定の中国語のユーザー入力ABCDEに対して、変換規則が文字CをC’に置換することを指示する場合、Cの前に来る文字がABである場合、ひいてはこの特定の規則はユーザー入力に適用できる。どの規則もユーザー入力に適用できない場合は、スペル修正提案はユーザー入力に対してなされない。あるいは、ユーザー入力に適用できるそれぞれのスペル修正変換規則に対して、適用できるスペル修正変換規則に対応するユーザー入力に対する代替のスペルはブロック204で生成される。上記の例では、代替のスペルABC’DEは、適用できるスペル修正変換規則に対応するユーザー入力ABCEDに対して生成される。決定ブロック206では、それぞれの代替のスペルの可能性は決定され、またユーザー入力の可能性と比較される。一つの実施形態では、決定ブロック206は、可能性を計算するために隠れマルコフモデルおよびビタビデコーダを利用してもよい。現在の例では、ABCEDおよびABC’DEの相対的な出力の可能性は決定されまた比較されている。代替のスペルはユーザー入力よりもより高い可能性有し、従って、PABC’DEP変換規則>PABCDEであって、P変換規則が成功した修正の数および修正の総数の比率として定義され得る場合、有効な修正と見なされる。PABCDEは区分内でのあいまい性を考慮に入れることに注目されたい。例えば、ABCDEがAB―CDEとABC―DEの二つの可能性のある区分を有する場合、確率性はベイズ確率の積の合計となる。PABCDE=P入力-終了|CDEPCDE|ABPAB|入力-始まりP入力-終了|DEPDE|ABCPABC|入力-開始上記の方程式は、全体の履歴よりもむしろ前に来る単語により現在の単語を決定するマルコフ仮定を適用することによる最初のベイズ確率から得られるベイズ確率であることに留意されたい。PABC’DEの決定は同様にされてもよい。既定の代替のスペルが、決定ブロック206で決定されるようにユーザー入力よりも可能性は高くない場合、特定のスペル修正提案はされない。しかしながら、既定の代替のスペルが、決定ブロック206で決定されるようにユーザー入力よりも可能性は高い場合、ユーザーの入力に対する対応の代替のスペルは提案され、および/またはブロック208で自動的にスペルがなされる。本明細書で説明されるようにスペル修正のシステムおよび方法は、特に非ローマ語に基づく言語での使用にたいへん適切で、またスペルエラーの検出および代替のスペル提案および修正の生成の両方に非常に効果的となることが出来る。さらに、スペル修正のためのシステムと方法はとりわけ、様々なユーザー入力またはクエリーのスペル修正を実行するときに、ウェブ検索エンジンの文脈内および組織データを含んでいるデータベースに対する検索エンジンにも適用できる。本発明の例示的な実施形態を本明細書に説明し示したが、それらは単に説明に役立つものにすぎず、また改良を本発明の精神および範囲を逸脱することなくこれらの実施形態に施すことができることが理解される。従って、本発明の範囲は、本発明の実施形態として本具体的な実施形態の説明に明示的に含まれる各請求項と共に、修正され得る添付の請求項に関してのみ定義されることが意図されている。"