(57)【要約】  データ圧縮及びキーワード認識が提供され得る。第１のパスはテキスト文字列を移動し、用語を生成し、生成された用語の各々に対してハッシュ値を計算し得る。各ハッシュ値に対して、ハッシュバケットが作成され得る。そのハッシュバケットにおいて、関連付けられた出現回数が保持され得る。ハッシュバケットは出現回数によってソートされ得るし、いくつかのトップバケットが維持され得る。一度、それらトップバケットは知られると、第２のパスはテキスト文字列を移動し、用語を生成し、各用語に対してハッシュ値を計算し得る。用語のハッシュ値が維持されたバケットの１つのハッシュ値に一致する場合、用語が頻出用語であると考慮され得る。その結果、用語は対応する頻出回数と伴に辞書に追加され得る。そして、辞書は、頻出しないもののハッシュ衝突に起因して出現し得る用語を削除するように照合され得る。
2011501837.tif 000002
【特許請求の範囲】
【請求項１】
テキストを認識する方法であって、
テキスト文字列（１０５）において使用される複数の生成された用語（３０５）を生成するステップと、
前記複数の生成された用語（３０５）から複数のハッシュ値を計算するステップと、
前記複数のハッシュ値にそれぞれ対応する複数のハッシュバケット（３１０）を作成するステップと、
前記複数のハッシュバケット（３１０）にそれぞれ対応する複数の出現回数値を保持するステップであって、前記複数の出現回数値の各々は、前記複数の生成された用語（３０５）のうち全てが、前記複数の出現回数値の各ハッシュバケットにそれぞれ対応するハッシュ値を有する前記テキスト文字列（１０５）に出現する回数をそれぞれ示すステップと、
第１の所定値未満の各出現回数値を有する前記複数のハッシュバケット（３１０）のうち全てを破棄するステップと、
辞書用語を辞書（１２０）に追加するステップであって、前記辞書用語は、前記残存する複数のハッシュバケット（３１０）にそれぞれ対応する前記複数のハッシュ値のうちいずれにも対応するそれぞれのハッシュ値を有する前記複数の生成された用語（３０５）のうち全てを含み、前記辞書（１２０）は、前記辞書用語の各々が前記テキスト文字列（１０５）に出現した回数をそれぞれが示す複数の頻出回数値を含むステップとを備えることを特徴とする方法。
【請求項２】
前記辞書用語を順位付けするステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項３】
評価関数を使用して前記辞書用語を順位付けするステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項４】
データ圧縮のために構成された評価関数を使用して前記辞書用語を順位付けするステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項５】
データ圧縮のために構成された評価関数を使用して前記辞書用語を順位付けするステップをさらに備え、
前記辞書用語は、前記辞書用語の各々にそれぞれ対応する複数のそれぞれのインデックスに基づいて順位付けされ、前記複数のインデックスの各々は、それぞれの辞書用語の各々の長さを乗じたそれぞれの辞書用語の各々の前記頻出回数値をそれぞれ含むことを特徴とする請求項１に記載の方法。
【請求項６】
キーワード認識のために構成された評価関数を使用して前記辞書用語を順位付けするステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項７】
キーワード認識のために構成された評価関数を使用して前記辞書用語を順位付けするステップをさらに備え、
前記辞書用語は前記辞書用語それぞれの頻度回数値に基づいて順位付けされることを特徴とする請求項１に記載の方法。
【請求項８】
前記辞書（１２０）を使用して、前記生成された用語（３０５）のうちどの用語を前記テキスト文字列（１０５）において圧縮すべきかを決定するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項９】
前記辞書（１２０）を使用して、前記生成された用語（３０５）のうちどの用語をキーワードとして特徴付けるかを決定するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項１０】
前記辞書（１２０）から、第２の所定値未満の対応頻出回数値を有する辞書用語を削除するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項１１】
前記テキスト文字列（１０５）において使用される前記複数の生成された用語（３０５）を生成する前記ステップは、前記テキスト文字列（１０５）において使用される前記複数の生成された用語（３０５）を生成するステップを含み、
前記複数の生成された用語（３０５）の各々は個々の文字列を含むことを特徴とする請求項１に記載の方法。
【請求項１２】
前記テキスト文字列（１０５）において使用される前記複数の生成された用語（３０５）を生成する前記ステップは、前記テキスト文字列（１０５）において使用される複数の生成された用語（３０５）を生成するステップを含み、
前記複数の生成された用語（３０５）のうち少なくとも一部はサブ文字列を含むことを特徴とする請求項１に記載の方法。
【請求項１３】
前記複数の生成された用語（３０５）から前記複数のハッシュ値を計算する前記ステップは、完全ハッシュアルゴリズムに基づいて前記複数のハッシュ値を計算するステップを含むことを特徴とする請求項１に記載の方法。
【請求項１４】
一連の命令が実行されるとテキストを認識する方法を実行する前記一連の命令を記憶するコンピュータ可読媒体であって、
前記一連の命令によって実行される前記方法は、
テキスト文字列（１０５）における複数の生成された用語（３０５）に対応する複数のハッシュ値にそれぞれ対応する複数のハッシュバケット（３１０）を作成するステップであって、前記複数の生成された用語（３０５）の少なくとも一部はサブ文字列を含むステップと、
前記複数のハッシュバケット（３１０）にそれぞれ対応する複数の出現回数値を保持するステップであって、前記複数の出現回数値の各々は、前記複数の生成された用語（３０５）のうち全てが、前記複数の出現回数値の各ハッシュバケットにそれぞれ対応するハッシュ値を有する前記テキスト文字列（１０５）に出現する回数をそれぞれ示すステップと、
第１の所定値未満の各出現回数値を有する前記複数のハッシュバケット（３１０）のうち全てを破棄するステップと、
辞書用語を辞書（１２０）に追加するステップであって、前記辞書用語は、前記残存する複数のハッシュバケット（３１０）にそれぞれ対応する前記複数のハッシュ値のうちいずれにも対応するそれぞれのハッシュ値を有する前記複数の生成された用語（３０５）のうち全てを含み、前記辞書（１２０）は、前記辞書用語の各々が前記テキスト文字列（１０５）に出現した回数をそれぞれが示す複数の頻出回数値を含むステップと、
データ圧縮のために構成された評価関数を使用して前記辞書用語を順位付けするステップであって、前記辞書用語は、前記辞書用語の各々にそれぞれ対応する複数のそれぞれのインデックスに基づいて順位付けされ、前記複数のインデックスの各々は、それぞれの辞書用語の各々の長さを乗じたそれぞれの辞書用語の各々の前記頻出回数値をそれぞれ含むステップとを備えることを特徴とするコンピュータ可読媒体。
【請求項１５】
前記方法は、前記辞書（１２０）を使用して、前記生成された用語（３０５）のうちどの用語を前記テキスト文字列（１０５）において圧縮すべきかを決定するステップをさらに備えることを特徴とする請求項１４に記載のコンピュータ可読媒体。
【請求項１６】
前記方法は、前記辞書（１２０）から第２の所定値未満の対応頻出回数値を有する辞書用語を削除するステップをさらに備えることを特徴とする請求項１４に記載のコンピュータ可読媒体。
【請求項１７】
前記方法は、完全ハッシュアルゴリズムに基づいて前記複数のハッシュ値を計算するステップをさらに備えることを特徴とする請求項１４に記載のコンピュータ可読媒体。
【請求項１８】
記憶装置と、
前記記憶装置と接続された処理ユニットとを備えるテキストを認識するシステムであって、
前記処理ユニットは、
テキスト文字列（１０５）における複数の生成された用語（３０５）に対応する複数のハッシュ値にそれぞれ対応する複数のハッシュバケット（３１０）を作成するステップであって、前記複数の生成された用語（３０５）の各々は個々の文字列を含むステップと、
前記複数のハッシュバケット（３１０）にそれぞれ対応する複数の出現回数値を保持するステップであって、前記複数の出現回数値の各々は、前記複数の生成された用語（３０５）のうち全てが、前記複数の出現回数値の各ハッシュバケットにそれぞれ対応するハッシュ値を有する前記テキスト文字列（１０５）に出現する回数をそれぞれ示すステップと、
第１の所定値未満の各出現回数値を有する前記複数のハッシュバケット（３１０）のうち全てを破棄するステップと、
辞書用語を辞書（１２０）に追加するステップであって、前記辞書用語は、前記残存する複数のハッシュバケット（３１０）にそれぞれ対応する前記複数のハッシュ値のうちいずれにも対応するそれぞれのハッシュ値を有する前記複数の生成された用語（３０５）のうち全てを含み、前記辞書（１２０）は、前記辞書用語の各々が前記テキスト文字列（１０５）に出現した回数をそれぞれが示す複数の頻出回数値を含むステップと、
キーワード認識のために構成された評価関数を使用して前記辞書用語を順位付けするステップであって、前記辞書用語は、前記辞書用語のそれぞれの頻出回数値に基づいて順位付けされるステップとを実行するように動作することを特徴とするシステム。
【請求項１９】
前記処理ユニットは、第２の所定値未満の対応頻出回数値を有する辞書用語を前記辞書（１２０）から削除するステップをさらに実行するように動作することを特徴とする請求項１８に記載のシステム。
【請求項２０】
前記処理ユニットは、完全なハッシュアルゴリズムに基づいて前記複数のハッシュ値を計算するステップをさらに実行することを特徴とする請求項１８に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
情報理論において、データの圧縮又はソースコーディングは情報をエンコードする処理であり、その処理は、エンコードされていない表示が特定のエンコード方式の使用を介して使用するよりも少数のビットを使用する。
【背景技術】
【０００２】
例えば、「圧縮」という単語が「ｃｏｍｐ」としてエンコードされる慣習を受け入れる場合、テキストは少数のビットでエンコードされるであろう。多くのコンピュータユーザに知られた圧縮に関する１つの従来例として、「ＺＩＰ」ファイル形式がある。かかる形式は圧縮を提供するとともに、アーカイバとして作用し、多くのファイルを単一の出力ファイルに記憶する。
【０００３】
あらゆる通信と同様に、情報の送信側と受信側の双方がエンコード方式を理解しているときに、圧縮されたデータの通信が機能する。例えば、受信側が、英語を表す文字として解釈されることが意図されていることを理解する場合のみ、テキストは意味をなす。同様に、デコード方法が受信側に知られている場合、圧縮されたデータは理解され得る。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
圧縮は有益である。なぜならば、圧縮は、メモリ又は伝送帯等の高価な資源の消費の低減に寄与するからである。弱点としては、圧縮されたデータは解凍されて表示されなければならない（又は聞かれなければならない）。この付加的な解凍処理はいくつかのアプリケーションに不利益であり得る。例えば、映像の圧縮技術は、映像が解凍されつつ表示されるべく十分な速度で解凍されるように高価なハードウェアを必要とする（映像を見る前に映像全体を解凍するオプションは不便であり得るし、解凍された映像に対して記憶スペースを必要とする）。したがって、データ圧縮技術は様々な因子の間においてトレードオフを伴い、かかる因子は、メモリ、圧縮度、（非可逆的な圧縮技術を使用する場合には）導入されたひずみ量、及びデータを圧縮し且つ解凍するのに必要なコンピュータリソースを含む。
【課題を解決するための手段】
【０００５】
本概要は、発明の詳細な説明においてさらに後述する単純化した形態で概念の選択を導くために与えられている。この発明の概要は、特許請求の範囲に記載された発明の重要な特徴若しくは本質的な特徴を特定することを目的とはしていない。また、本概要は、特許請求の範囲に記載された発明の範囲を限定する目的で用いられるべきではない。
【０００６】
データ圧縮及びキーワード認識が提供され得る。第１のパスはテキスト文字列を移動し、用語を生成し、生成された用語の各々に対してハッシュ値を計算し得る。各ハッシュ値に対して、ハッシュバケットが作成され得る。そのハッシュバケットにおいて、関連付けられた出現回数が保持され得る。ハッシュバケットは出現回数によってソートされ得るし、いくつかの上位バケットが維持され得る。一度、それら上位バケットが知られると、第２のパスはテキスト文字列を移動し、用語を生成し、各用語に対してハッシュ値を計算し得る。用語のハッシュ値が維持されたバケットの１つのハッシュ値に一致する場合、その用語は頻出用語であると認められ得る。その結果、用語は対応する頻出回数と伴に辞書に追加され得る。そして、辞書は、頻出しないもののハッシュ衝突に起因して出現し得る用語を削除するように照合され得る。
【０００７】
上記概説及び以下の詳細な説明により、実施例が説明されるに過ぎない。従って、上記概説及び以下の詳細な説明は限定的に考慮されるべきではない。さらに、本明細書に説明された実施例に加えて、特徴又は変形が提供され得る。例えば、実施形態は、詳細な説明で記述された種々の組み合わせ及び下位の組み合わせに誘導され得る。
【図面の簡単な説明】
【０００８】
【図１】動作環境のブロック図である。
【図２】テキストを認識する方法のフロー図である。
【図３】第１のパスのブロック図である。
【図４】第２のパスのブロック図である。
【図５】アルゴリズムを示す図である。
【図６】コンピューティングデバイスを含むシステムのブロック図である。
【発明を実施するための形態】
【０００９】
添付図面は、本開示の一部に組み込まれ且つ本開示の一部を構成し、本発明の様々な実施形態を図示している。
【００１０】
以下の詳細な説明は添付図面を参照する。可能な限り、同一の参照番号が、図面及び以下の説明文において使用され、同一又は類似の要素に対して付されている。本発明の実施形態が説明され得るものの、修正、適応、及び他の実装が可能である。例えば、置換、付加、又は修正が図面に示された要素に対してなされ得るし、本明細書に記載された方法は、開示された方法を置換し、方法の順序を変更し、さらなるステージを付加することによって、変更され得る。従って、以下の詳細な説明は本発明を限定しない。むしろ、本発明の適切な範囲は添付した特許請求の範囲によって画定される。
【００１１】
本発明の実施形態によれば、ツー・パスハッシュベースのアルゴリズムは、ドキュメント（例えば、テキスト文字列）において頻出する用語を見つけ出すのに使用され得る。さらに、メモリの質対メモリ対ランタイムが制御され得る。本発明の実施形態は、例えば、上位頻出１００のキーワードを見出し得る。その場合、メモリを３ＫＢ未満に維持しつつ、１．５秒で、１％のエラーミス指数、１．６８ｍｅｇのドキュメントにおいて、キーワードの回数と共に見出され得る。
【００１２】
以下で説明するアルゴリズムは、例えば、テキスト文字列における頻出キーワードを見つけ出し得る。以下のテキストを含む文字列について考える。「Ｉ  ｗｅｎｔ  ｔｏ  ｔｈｅ  ｍａｒｋｅｔ  ｂｕｔ  ｔｈｅ  ｍａｒｋｅｔ  ｗａｓ  ｃｌｏｓｅｄ．」。本発明の実施形態は、「ｍａｒｋｅｔ」及び「ｔｈｅ」がキーワードとして適した頻出用語であり得ると見つけ出し得る。しかしながら、本発明の実施形態は、圧縮する目的のためにも使用され得る。以下のテキストを含む文字列を考える。「ａｂｒａｃａｄａｂｒａ、ａｂｒａｓｉｖｅ  ｂｒａｔｓ！」。本発明の実施形態は、「ｂｒａ」が圧縮する価値があり得る頻出用語であると見つけ出し得る。とにかく、本発明の実施形態の目的は、頻出反復用語を見つけ出すことであり得る。別の目的は、ドキュメントの概要を生成すること、重要な用語について強調表示すること、ドキュメントのデータを圧縮すること、及び文法的な過度の反復を見出すこと等であり得る。言い換えると、本発明の実施形態は、テキスト文字列において頻出用語を見出し得るし、頻出用語は、キーワードであるか又は文字列内のサブ文字列であってもよい。さらに、本発明の実施形態は、頻出用語の各々がテキスト文字列に何回現れているかを判断し得るし、メモリ使用量、実行ランタイム、及び結果の品質を制御し得る。
【００１３】
従来の圧縮アルゴリズムは圧縮及び記憶を目的として設計されている。したがって、従来のシステムは、索引を高価なものとし、或いは完全に解凍しなければ索引を不可能なものとし得る。本発明の実施形態によれば、上述のツー・パスハッシュベースのアルゴリズムは、迅速な索引を可能になし且つ軽量な圧縮を実行し得る。例えば以下のシナリオを考慮する。我々は、以下の長大なアカウントリスト／連絡リストを有し得る。
‐Ｊｏｈｎ  Ｄｏｅ
‐Ｊｏｈｎ  Ｗａｙｎｅ
‐Ｗａｙｎｅ  Ｓｍｉｔｈ
‐．．．
ユーザがいくつかのテキストをタイプするとき（これを入力と称する）、我々は上記アカウント／連絡を高速に特定し且つそれらを強調表示し得る。
【００１４】
ＺＩＰは、リストを圧縮するのに使用され得る。リストは非常に効率的に圧縮され得るものの、迅速な索引を実行する手法が全くあり得ない。ＺＩＰ圧縮が適応できるので、我々は、入力を圧縮し且つ圧縮されたリスト内で一致するバイトを検索しようとは望まなくてもよい。入力と比較するためにリストを解凍することも、全体的に逆効果となり得る。
【００１５】
前述のツー・パスハッシュベースのアルゴリズムが最も頻出する２つのシンボルを見出すように実行される場合（例えば、また、圧縮するべき「最良の」２つのシンボルを見出すために文字列の長さ及びエンコーディングのコストに重み付けする。）我々は軽量圧縮の後に以下のコンパクトなリストで終了し得る。  
−＄１＝Ｊｏｈｎ
−＄２＝Ｗａｙｎｅ
−＄１  Ｄｏｅ
−＄１  ＄２
−＄２  Ｓｍｉｔｈ
−．．．
【００１６】
我々は、いくつのシンボルがエンコードされるのかを制御し得るので、我々は、入力におけるそれらシンボルを置換し且つ比較し得る。
【００１７】
以下に、ＸＭＬを用いた別の例を示す。例えば、我々は、以下を含む多大なＸＭＬドキュメントを有し得る。  
＜Ｇｒｅｅｔｉｎｇｓ＞
＜Ｗｏｒｄ  ｉｄ＝”Ｗｅｌｃｏｍｅ”＞Ｅｎｇｌｉｓｈ＜／Ｗｏｒｄ＞
＜Ｗｏｒｄ  ｉｄ＝”Ｂｏｎｊｏｕｒ”＞Ｆｒｅｎｃｈ＜／Ｗｏｒｄ＞
＜Ｗｏｒｄ  ｉｄ＝”Ｄａｎｋｅ”＞Ｇｅｒｍａｎ＜／Ｗｏｒｄ＞
．．．
＜／Ｇｒｅｅｔｉｎｇｓ＞
我々は、ＸＭＬドキュメントを保持するべく、より少ないメモリを使用したいと欲し得るものの、XPath = Greetings/Word[@id="Welcome"]という索引に対するＸＰａｔｈクエリを使用できることも望み得る。
【００１８】
我々は、ＺＩＰを使用して、ＸＭＬドキュメントを圧縮し得る。ＸＰａｔｈは単に動作し得ない（なぜならば、我々はもはやＸＭＬドキュメントではなく、バイトを圧縮しているからである。）。我々は、前述のツー・パスハッシュベースのアルゴリズムを起動して、最も頻出する２つのシンボルを見出す場合（例えば、圧縮するべき「最良の」２つのシンボルを見出すために特定のＸＭＬノード若しくは属性をエンコードすることを避けことが使用され得る）、我々は軽量圧縮の後に以下のコンパクトなＸＭＬドキュメントで終了し得る。  
＄１＝Ｇｒｅｅｔｉｎｇｓ
＄２＝Ｗｏｒｄ
<$1>
＜＄２  ｉｄ＝”Ｗｅｌｃｏｍｅ”＞Ｅｎｇｌｉｓｈ＜＄２＞
＜＄２  ｉｄ＝”Ｂｏｎｊｏｕｒ”＞Ｆｒｅｎｃｈ＜＄２＞
＜＄２  ｉｄ＝”Ｄａｎｋｅ”＞Ｇｅｒｍａｎ＜＄２＞
．．．
<$1>
我々は、XPath = $1/$2[@id="Welcome"]というＸＰａｔｈクエリの実行を継続し得る。
【００１９】
図１は、本発明の実施形態に係る認識システム１００を示している。図１に示されているように、テキスト文字列１０５は第１のパス１１０及び第２のパス１１５によって操作されて、辞書１２０が生成され得る。例えば、第１のパス１１０は、テキスト文字列１０５を移動し、用語を生成し、生成された用語の各々に対してハッシュ値を計算し得る。各ハッシュ値に対して、ハッシュバケットが作成され得る。そのハッシュバケットにおいて、関連付けられた出現回数が保持され得る。ハッシュバケットは出現回数によってソートされ得るし、いくつかの上位バケットが維持され得る。一度、それら上位バケットが知られると、第２のパス１１５は、テキスト文字列１０５を再度移動し、用語を生成し、用語の各々に対してハッシュ値を再び計算し得る。用語のハッシュ値が維持されたバケットの１つのハッシュ値と一致する場合、用語が頻出用語である可能性が高いであろう。その結果、用語は対応する頻出回数と共に辞書１２０に追加され得る。そして、辞書１２０は、頻出しないもののハッシュ衝突に起因して出現し得る用語を削除するように照合され得る。次に、辞書１２０内の用語が、順位付けされ、不要なものは削除され、且つフィルターにかけられ得る。上述したツー・パス処理を実行するアルゴリズム５００の一例が図５に示されている。
【００２０】
図２は、テキストを認識する本発明の実施形態に係る方法２００に含まれる一般的なステージを詳しく説明するフロー図である。方法２００は、図６を参照して以下にさらに詳細に説明するように、コンピューティングデバイス６００を使用して実行され得る。方法２００のステージを実行する方法が以下に詳細に説明される。方法２００は、開始ブロック２０５で開始し、ステージ２１０に進み得る。ステージ２１０において、コンピューティングデバイス６００はテキスト文字列１０５において使用される複数の生成された用語を生成し得る。例えば、第１のパス１１０は「Ｉ  ｗｅｎｔ  ｔｏ  ｔｈｅ  ｍａｒｋｅｔ  ｂｕｔ  ｔｈｅ  ｍａｒｋｅｔ  ｗａｓ  ｃｌｏｓｅｄ．」を含むテキスト文字列１０５を分析し得る。図３に示すように、この分析は、「Ｉ」、「ｗｅｎｔ」、「ｔｏ」、「ｔｈｅ」、「ｍａｒｋｅｔ」、「ｂｕｔ」、「ｔｈｅ」、「ｍａｒｋｅｔ」、「ｗａｓ」、及び「ｃｌｏｓｅｄ」という複数の生成された用語３０５を生成し得る。
【００２１】
本発明の実施形態によれば、例えば、接頭部／接尾部の用語はデータを圧縮する目的のために生成され得る。例えば、「ａｂｒａ」という用語から、「ａｂｒａ」、「ｂｒａ」、「ｒａ」、「ａｂｒ」等の接頭部／接尾部用語が生成されるであろう。しかしながら、テキスト文字列１０５において頻出キーワードを見出すことが目的である場合、接頭部／接尾部を生成する必要はないであろうし、むしろ、テキスト文字列１０５から個々の文字列が生成され得る。
【００２２】
コンピューティングデバイス６００がテキスト文字列１０５において使用される複数の生成された用語３０５を生成するステージ２１０から、方法２００はステージ２２０に進み得る。ステージ２２０において、コンピューティングデバイス６００は、複数の生成された用語３０５から複数のハッシュ値を計算し得る。ハッシュ文字列アルゴリズムが、以下に示すようにハッシュを生成するのに使用され得る。
【００２３】
2011501837.tif 000003
【００２４】
完全ハッシュ関数は「衝突」を避けるのに使用され得る。衝突は、２つの異なった用語が同一のハッシュ値を有することとなり得る場合に生ずる。一連のＳの完全ハッシュ関数は、Ｓにおける異なるキー（要素）を異なる数にマップし得るハッシュ関数である。Ｓにおける要素の数の倍数のある一定のサイズの範囲内にある値を用いた完全ハッシュ関数は、効率的な索引動作に使用され得る。これは、完全ハッシュ関数の値に応じてハッシュテーブルにキーをセットすることによって使用され得る。
【００２５】
一定の時間で評価され得る特定の一連のＳに対する完全ハッシュ関数であって、狭い範囲の値を用いた完全ハッシュ関数は、Ｓのサイズに比例した多数の動作におけるランダムアルゴリズムによって見出され得る。完全ハッシュ関数の記述に関する最小サイズはその関数の値の範囲に依存し得る。すなわち、範囲が小となればなる程、より大なるスペースが必要とされる。ハッシュテーブルを用いた使用に好適である全ての完全ハッシュ関数は、Ｓのサイズに比例した少なくとも多数ビットを必要とし得る。多くのインプリメンテーションがｎｌｏｇ（ｎ）に比例するビット数を必要とし得る。ここで、ｎはＳのサイズである。これは、完全ハッシュ関数を記憶するためのスペースはセットを記憶するためのスペースと同程度であることを意味し得る。
【００２６】
完全ハッシュ関数を使用することは、頻繁にアップデートされない多数のセットがあり、多数の索引がそれに対してある状況において最善であり得る。アップデートの実行に対する効果的解決は、動的完全なハッシュとして知られているものの、これら方法は、実行するのに比較的複雑である。動的なアップデートをも可能にする完全ハッシュに対する単純な代替は、カッコウ・ハッシングであり得る。
【００２７】
その上、最小完全ハッシュが使用され得る。最小完全ハッシュ関数は、通常[0..n-1]又は[1..n]のｎ個のキーをｎ個の連続して整数にマップする完全ハッシュ関数であり得る。これを表現するより正式な形式は以下の通りである。ｊ及びｋをある一連のＫの要素とする。Ｆは最小完全ハッシュ関数であり、Ｆ（ｊ）＝Ｆ（ｋ）であることは、ｊ＝ｋであること及びＦがａ．．．ａ＋｜Ｋ｜−１となるような整数が存在することを意味している。あらゆるキーｊ及びｋに対して、ｊ＜ｋがＦ（ｊ）＜Ｆ（ｋ）を意味するならば、最小完全ハッシュ関数は順序を変えない関数である。耐えるのではなく、グラフ理論／確率に基づいた異なるアルゴリズムは、完全ハッシング関数を生成するのに使用され得る（例えば、ＣＨＭ最小完全ハッシュアルゴリズム）。しかしながら、これは第１の初期パスを必要とし（例えば、図５に示したアルゴリズム５００においてラベルされたパス０）、そのランタイムは入力サイズとともに直線的に増大し得る。
【００２８】
コンピューティングデバイス６００がステージ２２０において複数の生成された用語から複数のハッシュ値を計算すると、方法２００は、ステージ２３０に継続する。ステージ２３０において、コンピューティングデバイス６００は複数のハッシュ値にそれぞれ対応する複数のハッシュバケットを作成し得る。例えば、第１のパス１１０は複数のハッシュバケット３１０を作成し得る。図３に示すように、複数のハッシュバケット３１０は第１のバケット、第２のバケット、第３のバケット、第４のバケット、第５のバケット、及び第６のバケットを含み得る。
【００２９】
コンピューティングデバイス６００はステージ２３０において複数のハッシュバケット３１０を作成すると、方法２００はステージ２４０に進み得る。ステージ２４０において、コンピューティングデバイス６００は、複数のハッシュバケット３１０にそれぞれ対応する複数の出現回数値を保持し得る。複数の出現回数値の各々は、複数の生成された用語（例えば、複数の生成された用語３０５）のうち全てがテキスト文字列１０５に出現する回数をそれぞれ示しており、そのテキスト文字列１０５は、複数の出現回数値のそれぞれのハッシュバケットにそれぞれ対応するハッシュ値を有する。例えば、図３に示すように、第１のパス１１０は、テキスト文字列１０５をスキャンし、生成された用語３０５のハッシュを計算し得る。生成された用語３０５における「ｍａｒｋｅｔ」の２つの例が第３のバケットにハッシュされ、第３のバケットに対する出現回数が２となる。その上、生成された用語３０５における“ｔｈｅ”の２つの例が第１のバケットにハッシュされ得る。しかしながら、「ｗｅｎｔ」も衝突に帰属して第１のバケットにハッシュされ、第１のバケットに対する出現回数が３となる。どのような場合においても、複数の生成された用語において同じ用語のより多くの例を見出すことによって、特定のハッシュバケットのカウントが増強され得る。
【００３０】
コンピューティングデバイス６００が複数の出現回数値を保持するステージ２４０から、方法２００はステージ２５０に進み得る。ステージ２５０において、コンピューティングデバイス６００は、第１の所定値未満の各出現回数値を有する複数のハッシュバケットのうち全てを破棄し得る。例えば、第１の所定値は「３」を含み得る。その結果、図３の例において、第２のバケット、第３のバケット、第４のバケット、第５のバケット、及び第６のバケットはすべて破棄され得る。なぜならば、これらハッシュバケットの各々の出現回数は３未満であるからである。結果として図４の例に示したようになる。図４の例は、１つだけ維持されたハッシュバケットを示しているものの、上位Ｎのハッシュバケット又は所定閾値（例えば、第１の所定値）よりも大なる回数を有するハッシュバケットの全てが維持され得る。言い換えると、上位の出現回数値を有する上位Ｎのバケットが維持され得るが、例えば出現回数値がＸより大であるバケットは維持され得ない。
【００３１】
コンピューティングデバイス６００はステージ２５０において複数のハッシュバケットのうち全てを破棄すると、方法２００はステージ２６０に継続し得る。ステージ２６０において、コンピューティングデバイス６００は辞書用語を辞書１２０に追加し得る。辞書用語は複数の作成された用語のうち全てを含み得る。その複数の生成された用語は、残存する複数のハッシュバケットにそれぞれ対応する複数のハッシュ値のうちいずれにも対応するハッシュ値をそれぞれ有する。また、辞書１２０は複数の頻出回数値を含み得る。その複数の頻出回数値は、辞書用語の各々がテキスト文字列１０４に出現した回数をそれぞれ示している。例えば、図４に示されているように、第２のパス１１５は、テキスト文字列１０５を再スキャンし得るし、生成された用語のハッシュを計算し得る。ハッシュが維持されたバケット（例えば、第１のバケット）のものと一致する場合、用語は対応する頻出回数値と共に辞書１２０に追加され得る。さもなければ、用語は破棄され得る。図４に示されているように、辞書１２０は、用語「ｔｈｅ」（頻出回数値＝２）及び「ｗｅｎｔ」（頻出回数値＝１）を含み得る。テキスト文字列１０５が、より大である場合、第２のパス１１５は「ｔｈｅ」に対してより高い頻出回数値を生成し、「ｗｅｎｔ」に対してより低い頻出回数値を生成し得る
【００３２】
本発明の実施形態によれば、第２のパス１１５は衝突に起因するノイズを除去し、辞書１２０において用語を順位付けし得る。例えば、「ｗｅｎｔ」は「ｔｈｅ」と同じバケットにハッシュされた。しかしながら、第２のパス１１５の間に取得された最終的な回数は、「ｗｅｎｔ」がそんなに頻出せず、辞書１２０から削除され得ることを明らかにし得る。従って、衝突は修正され得る。
【００３３】
その上、辞書用語は、目的（例えば、データ圧縮、キーワード検出等）に依存する評価関数を使用して順位付けされ得る。例えば、目的がデータ圧縮である場合、順位付けは、この情報（すなわち、頻出辞書用語を圧縮する「利益」）をコード化するコストを差し引いた頻出回数値を乗じた文字列の長さに基づいて頻出辞書用語に対して割り当てられ得る。別の実施例では、目的がテキスト文字列のキーワードを見出すことである場合、順位付けは、それら重要度に基づいて頻出辞書用語に割り当てられ得る。例えば、英語で頻出する「ｔｈｅ」という用語はノイズとして取り扱われるので、高い順位付けはされ得ない。従って、目的に応じて、順位付けの処理が異なり得る。一度、コンピューティングデバイス６００がステージ２６０において辞書に辞書用語を追加すると、方法２００はステージ２７０で終了し得る。
【００３４】
本発明に係る実施形態はテキストを認識するためのシステムを含み得る。システムは記憶装置と、当該記憶装置と接続された処理ユニットを含み得る。処理ユニットは、テキスト文字列において使用される複数の生成された用語を生成し、複数の生成された用語から複数のハッシュ値を計算し、複数のハッシュ値にそれぞれ対応する複数のハッシュバケットを生成するように動作し得る。さらに、処理ユニットは、複数のハッシュバケットにそれぞれ対応する複数の出現カウント値を保持するように動作し得る。複数の出現回数値の各々は、複数の生成された用語のうち全てがテキスト文字列に出現する回数をそれぞれ示す。そのテキスト文字列は、複数の出現回数値の各ハッシュバケットにそれぞれ対応するハッシュ値を有する。その上、処理ユニットは、第１の所定値未満の各出現回数値を有する複数のハッシュバケットのうち全てを破棄するように動作し得る。その上、処理ユニットは、辞書用語を辞書に追加するように動作し得る。その辞書用語は、残存する複数のハッシュバケットにそれぞれ対応する複数のハッシュ値のうちいずれにも対応するそれぞれのハッシュ値を有する複数の生成された用語のうち全てを含み得る。辞書は複数の頻出回数値を含み得る。その複数の頻出回数値は、辞書用語の各々がテキスト文字列に出現した回数をそれぞれが示す。
【００３５】
本発明に係る別の実施形態はテキストを認識するシステムを含み得る。システムは記憶装置と、当該記憶装置と接続された処理ユニットを含み得る。処理ユニットは、複数のハッシュ値にそれぞれ対応する複数のハッシュバケットを作成するように動作し得る。その複数のハッシュ値はテキスト文字列において複数の生成された用語に対応する。複数の生成された用語の少なくとも一部は個々の副文字列を含む。さらに、処理ユニットは、複数のハッシュバケットにそれぞれ対応する複数の出現カウント値を保持するように動作し得る。複数の出現回数値の各々は、複数の出現回数値の各ハッシュバケットにそれぞれ対応する複数の生成された用語のうち全てがテキスト文字列に出現する回数をそれぞれ示す。その上、処理ユニットは、第１の所定値未満の出現カウント値のそれぞれを有する複数のハッシュバケットのうち全てを破棄するように動作し得る。また、処理ユニットは、辞書用語を辞書に追加するように動作し得る。辞書用語は、残存する複数のハッシュバケットにそれぞれ対応する複数のハッシュ値のうちいずれにも対応するそれぞれのハッシュ値を有する複数の生成された用語のうち全てを含み得る。辞書は複数の頻出回数値を含み得る。その複数の頻出回数値は、辞書用語の各々がテキスト文字列に出現した回数をそれぞれが示す。その上、処理ユニットは、データを圧縮するために構成された評価関数を使用して辞書用語を順位付けするように動作し得る。辞書用語は、辞書用語の各々にそれぞれ対応する複数のそれぞれのインデックスに基づいて順位付けされ得る。複数のインデックスの各々は、それぞれの辞書用語の各々の長さを乗じたそれぞれの辞書用語の各々の頻出回数値をそれぞれ含む。
【００３６】
本発明に係るさらに別の実施形態はテキストを認識するシステムを含み得る。システムは記憶装置と、当該記憶装置と接続された処理ユニットを含み得る。処理ユニットは、複数のハッシュ値にそれぞれ対応する複数のハッシュバケットを作成するように動作し得る。その複数のハッシュ値はテキスト文字列において複数の生成された用語に対応する。複数の生成された用語の各々は個々の文字列を含む。さらに、処理ユニットは、複数のハッシュバケットにそれぞれ対応する複数の出現カウント値を保持するように動作し得る。複数の出現回数値の各々は、複数の生成された用語のうち全てが複数の出現回数値の各ハッシュバケットにそれぞれ対応するハッシュ値を有するテキスト文字列に出現する回数をそれぞれ示す。また、処理ユニットは、第１の所定値未満の出現カウント値のそれぞれを有する複数のハッシュバケットのうち全てを破棄し、辞書用語を辞書に追加するように動作し得る。辞書用語は、残存する複数のハッシュバケットにそれぞれ対応する複数のハッシュ値のうちいずれにも対応するそれぞれのハッシュ値を有する複数の生成された用語のうち全てを含み得る。辞書は複数の頻出回数値を含み得る。その複数の頻出回数値は、辞書用語の各々がテキスト文字列に出現した回数をそれぞれが示す。その上、処理ユニットは、キーワードを認識するために構成された評価関数を使用して辞書用語を順位付けする
ように動作し得る。辞書用語は、辞書用語それぞれの頻出回数値に基づいて順位付けされる。
【００３７】
図６は、コンピューティングデバイス６００を含むシステムのブロック図である。本発明の実施形態によれば、前述の記憶装置及び処理ユニットは、図６のコンピューティングデバイス６００等のコンピューティングデバイスにおいて実装され得る。ハードウェア、ソフトウェア、又はファームウェアのいかなる好適な組合せも、記憶装置及び処理ユニットを実装するのに使用され得る。例えば、記憶装置及び処理ユニットは、コンピューティングデバイス６００と組み合わせて、コンピューティングデバイス６００又は他の全てのコンピューティングデバイス６１８とともに実装され得る。前述のシステム、デバイス、及びプロセッサは、一例であり、他のシステム、デバイス、及びプロセッサが、本発明の実施形態に係る前述の記憶装置及び処理ユニットを含み得る。その上、コンピューティングデバイス４００は、上述したように、システム１００の動作環境を含み得る。システム１００は、他の環境下で動作し得るし、コンピューティングデバイス６００に制限されない。
【００３８】
図６を参照すると、本発明の実施形態に係るシステムはコンピューティングデバイス６００等のコンピューティングデバイスを含み得る。基本構成においては、コンピューティングデバイス６００は少なくとも１つの処理ユニット６０２とシステムメモリ６０４を含み得る。コンピューティングデバイスの構成及び態様に依存して、システムメモリ６０４は、揮発性メモリ（例えば、ランダム・アクセス・メモリ（ＲＡＭ））、不揮発性メモリ（例えば、リードオンリーメモリ（ＲＯＭ））、フラッシュメモリ、又はいかなる組み合わせを含み得るが、これらに限定されない。システムメモリ６０４はオペレーティングシステム６０５，１つ以上のプログラミングモジュール６０６を含み得るし、プログラムデータ６０７を含み得る。オペレーティングシステム６０５は、例えば、制御コンピューティングデバイス６００の動作に適合し得る。一実施形態では、プログラミングモジュール６０６は例えば認識アプリケーション６２０を含み得る。その上、本発明の実施形態は、グラフィックライブラリ、他のオペレーティングシステム、又は他のあらゆるアプリケーションプログラムと連動して実行され、且つ特定のアプリケーション又は特定のシステムに限定されない。この基本構成は破線６０８内のそれら要素によって図６に図示されている。
【００３９】
コンピューティングデバイス６００は、さらなる特徴又は機能を有し得る。例えば、コンピューティングデバイス６００は、例えば、磁気ディスク、光ディスク、又はテープ等の（脱着可能及び／又は固定）付加的データ記憶デバイスをも含み得る。かかる付加的記憶装置は、脱着可能な記憶装置６０９及び固定記憶装置６１０によって、図６に図示されている。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、若しくは他のデータ等の情報を記憶する全ての方法若しくは技術において実装された揮発性の若しくは不揮発性の脱着可能媒体及び固定媒体を含み得る。システムメモリ６０４，脱着可能な記憶装置６０９，及び固定記憶装置６１０はすべてコンピュータ記憶媒体の一例（すなわち、記憶装置）である。コンピュータ記憶媒体は、以下のものを含み得るが、これらに限定されない。すなわち、ＲＡＭ、ＲＯＭ、電気的に消去可能な読出し専用メモリ（ＥＥＰＲＯＭ）、フラッシュメモリ若しくは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）若しくは他の光学記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置若しくは他の磁気記憶装置、又は情報を記憶するのに使用され且つコンピューティングデバイス６００によってアクセスされ得る他のいかなる媒体である。かかるコンピュータ記憶媒体の全てが、デバイス６００の一部であり得る。また、コンピューティングデバイス６００は、キーボード、マウス、ペン、音声入力装置、タッチ入力装置等の入力装置（群）６１２を有し得る。また、ディスプレイ、スピーカ、プリンタ等の出力装置（群）６１４が含まれ得る。前述のデバイスは一例であり、他のデバイスが使用され得る。
【００４０】
また、コンピューティングデバイス６００は通信接続６１６を含み得る。その通信接続６１６によって、デバイス６００は、分散コンピュータ環境内のネットワーク、例えば、イントラネット若しくはインターネット上の他のコンピューティングデバイス６１８と通信することが可能となる。通信接続６１６は通信媒体の１つの例である。通信媒体は、コンピュータの読取可能な指示、データ構造、プログラムモジュール又は伝送波若しくは他の転送機構等の変調されたデータ信号における他のデータによって典型的に具現化され得るし、いかなる情報配信媒体をも含む。「変調されたデータ信号」とい用語は、信号内の情報をエンコードするような手法で設定され又は変更された特性のうち１つ以上を有する信号を意味している。限定ではなく、例として、通信媒体は、有線ネットワーク若しくは直接有線接続等の有線媒体と、音声無線媒体、ラジオ周波数（ＲＦ）無線媒体、赤外線無線媒体、若しくは他の無線媒体等の無線媒体とを含み得る。本明細書に使用されているコンピュータ読取可能媒体という用語は、記憶媒体と通信媒体の両方を含み得る。
【００４１】
上述したように、オペレーティングシステム６０５を含む多数のプログラムモジュール及びデータファイルが、システムメモリ６０４内に記憶され得る。処理ユニット６０２上で実行中に、プログラミングモジュール６０６（例えば、認識アプリケーション６２０）が、上述したように、例えば１つ以上の方法２００のステージを含むプロセスを実行し得る。上述したプロセスは一例であり、処理ユニット６０２は他のプロセスを実行し得る。使用され得る本発明の実施形態に係る他のプログラミングモジュールは、電子メールアプリケーション及び連絡アプリケーション、文書処理アプリケーション、表計算アプリケーション、データベースアプリケーション、スライドプレゼンテーションアプリケーション、並びにドローイングアプリケーションプログラム若しくはコンピュータ支援アプリケーションプログラム等を含み得る。
【００４２】
一般に、本発明の実施形態によれば、プログラムモジュールは、ルーチン、プログラム、要素、データ構造、及び特定のタスクを実行し又は特定の抽象型データを実装し得る他のタイプの構造を含み得る。その上、本発明の実施形態は、他のコンピュータシステム構成によって実施され得る。その他のコンピュータシステム構成は携帯デバイス、マルチプロセッサシステム、マイクロプロセッサベースの家庭用電化製品若しくはプログラム可能な家庭用電化製品、ミニコンピュータ、メインフレームコンピュータ等を含む。本発明の実施形態は分散コンピュータ環境においても実行され得る。分散コンピュータ環境において、タスクは通信ネットワークを介してリンクされた遠隔処理デバイスによって実行される。分散コンピュータ環境においては、プログラムモジュールはローカル記憶デバイス及びリモートメモリ記憶デバイスの両方に設けられ得る。
【００４３】
その上、本発明の実施形態は、離散的電子的要素と、論理ゲートを含むパッケージ化電子チップス若しくは集積化電子チップスと、マイクロプロセッサを利用する回路とを含む電気回路内で実施され、或いは電子的要素若しくはマイクロプロセッサを含むシングルチップ上において実施され得る。また、本発明の実施形態は、例えば、ＡＮＤ、ＯＲ及びＮＯＴ等の論理演算を実行できる他の技術を使用して実施され得る。その他の技術は、機械技術、光学技術、流体技術、量子的技術を含み得るもののこれらに限定されない。さらに、本発明の実施形態は汎用コンピュータ内又はいかなる他の回路若しくはシステムにおいても実行され得る。
【００４４】
発明の実施形態は、例えば、コンピュータプロセス（方法）、コンピュータシステムとして、又は、コンピュータプログラム製品若しくはコンピュータ読取可能媒体等の製品として実装され得る。コンピュータプログラムプロダクトは、コンピュータシステムによって読み込み可能なコンピュータ記憶媒体であり、且つコンピュータプロセスを実行する命令に関するコンピュータプログラムをコード化するコンピュータ記憶媒体であり得る。また、コンピュータプログラムプロダクトはコンピュータシステムによって読み込み可能なキャリヤー上で伝播される信号であり得るし、コンピュータプロセスを実行する命令に関するコンピュータプログラムをコード化し得る。従って、本発明はハードウェア内及び／又は（ファームウェア、常駐ソフトウェア、マイクロコード等を含む）ソフトウェア内で具現化され得る。言い換えると、本発明の実施形態はコンピュータ使用可能記憶媒体若しくはコンピュータ可読記憶媒体上のコンピュータプログラム・プロダクトの形態を取り得る。そのコンピュータ使用可能記憶媒体若しくはコンピュータ可読記憶媒体は、命令実行システムによる使用のための媒体若しくは命令実行システムに接続して使用するための媒体において具現化されたコンピュータ使用可能プログラムコード又はコンピュータ可読プログラムコードを有する。コンピュータ使用可能媒体若しくはコンピュータ可読媒体は、デバイス命令実行システム、装置、若しくはデバイスとの接続されることによって若しくは接続して、使用のためのプログラムを含み、記憶し、通信し、伝播し、又は移送することができる媒体であり得る。
【００４５】
コンピュータ使用可能媒体若しくはコンピュータ可読媒体は、電子的な、磁気的な、光学的な、電磁的な、赤外線の、半導体のシステム、装置、デバイス、又は伝搬媒体であり得るがこれらに限定されない。より特定のコンピュータ可読媒体の例（非完全なりスト）として、コンピュータ可読媒体は以下を含み得る。すなわち、１つ以上のワイヤを有する電気接続、携帯用フロッピーディスク、ランダム・アクセス・メモリ（ＲＡＭ）、リードオンリーメモリ（ＲＯＭ）、消去可能であり且つプログラム可能な読取り専用記憶装置（ＥＰＲＯＭ又はフラッシュメモリ）、光ファイバ、及び携帯用コンパクト読取り専用メモリ（ＣＤ‐ＲＯＭ）である。尚、コンピュータ使用可能媒体若しくはコンピュータ可読媒体は、紙又は別の適切な媒体でもあり得る。その紙又は別の適切な媒体において、プログラムは、例えば、紙の光学スキャン若しくは他の媒体を介して電子的に取り込まれて、コンパイルされ、解読され又は必要であれば適切な方法によって処理され、且つコンピュータメモリに記憶され得る。
【００４６】
本発明の実施形態は、例えば、本発明に係る方法、システム、及びコンピュータプログラム・プロダクトを示すブロック図及び／又は動作説明図を参照して、上記に説明されている。ブロックにおいて記された機能／動作は、いかなるフロー図において示されるように、順序が異なっても生じ得る。例えば、連続して示された２つのブロックは、実際、実質的に同時に実行され、或いはかかるブロックは関連する機能／動作に依存して逆順で時には実行され得る。
【００４７】
本発明の特定の実施形態について説明してきたが、他の実施形態も存在し得る。その上、本発明の実施形態は、メモリ及び他の記憶媒体に関連づけられているものとして、説明されてきたが、データは、ハードディスク、フロッピィディスク、若しくはＣＤ−ＲＯＭのような二次記憶装置等の他の形態のコンピュータ可読媒体、インターネットからの伝送波、又は他の形態のＲＡＭ若しくはＲＯＭに記憶され得るし、或いは読み込まれ得る。さらに、開示された方法のステージは、本発明から出発せずに、ステージの順序を変更したり且つ／又はステージを挿入したり若しくは削除することを含むいかなる手法においても変更され得る。
【００４８】
コードにおける著作権を含む全ての権利が出願人の財産に付与され且つ出願人の財産である。出願人は、本明細書に含まれるコードにおけるすべての権利を保持し且つ留保する、他のどんな目的のためにも与えられた特許の再生品だけに関して素材を再生させないように、許可を与える。
【００４９】
明細書は複数例を含むものの、本発明の範囲は以下に示す特許請求の範囲によって示されている。その上、本発明が構造的特徴及び／又は方法の動作に対して特有の言語によって説明されてきたものの、特許請求の範囲は、上述した特定の特徴又は動作に限定されない。むしろ、上述した特有の特徴又は動作は本発明の実施形態の例示として開示されている。
【図１】
2011501837.tif 000004
【図２】
2011501837.tif 000005
【図３】
2011501837.tif 000006
【図４】
2011501837.tif 000007
【図５】
2011501837.tif 000008
【図６】
2011501837.tif 000009
【国際調査報告】
2011501837.tif 000010
2011501837.tif 000011