パーティクルの出力セットにおいて、アイテムのセットの少なくとも一部分によって形成されるパーティクルのセットを変換するための方法であって、該アイテムのセットは、情報検索システムにおいて用いるのに適した単語のセットを表し、該方法は、前記パーティクルのセット内の各パーティクルについて、前記パーティクルのセット内のパーティクルの一部分の組合せを生成するステップと、前記パーティクルのセット内の前記パーティクルを、該パーティクルのセットの総最小編集距離MEDを最大にする組合せの前記一部分と置き換え、前記パーティクルの出力セットにおいて前記パーティクルのセットを変換する、置き換えるステップと、一意の単語ベースのセットをパーティクルベースのセットに変換するステップと、単語のセットを前記パーティクルベースのセットに基づく対応するアイテムのセットに変換するステップと、前記アイテムのセットをインデックス付けするステップであって、パーティクルベースのインデックスを生成する、インデックス付けするステップとを含み、該方法の前記ステップは、プロセッサによって実行される、パーティクルの出力セットにおいて、アイテムのセットの少なくとも一部分によって形成されるパーティクルのセットを変換するための方法。前記パーティクルのセットの前記総MEDを最大にする前記組合せを求めるステップをさらに含む請求項1に記載の方法。前記パーティクルのセット内の各パーティクルのMEDを求めるステップと、各パーティクルの前記MEDの和として前記パーティクルのセットの前記総MEDを求めるステップとをさらに含む請求項1に記載の方法。前記パーティクルと、前記パーティクルのセット内の全ての他のパーティクルとの間の編集距離を求めるステップと、前記パーティクルの前記MEDとして最も小さい編集距離を選択するステップとをさらに含む請求項3に記載の方法。前記置き換えるステップは、前記パーティクルのセットから前記パーティクルを取り除くステップと、前記組合せの前記一部分を前記パーティクルのセットに加えるステップと、前記パーティクルのセット内の各パーティクルのMEDを求めるステップと、前記パーティクルのセットの前記総MEDを求めるステップとをさらに含む請求項1に記載の方法。前記パーティクルのセットから前記組合せの前記一部分を取り除くステップをさらに含む請求項1に記載の方法。前記置き換えるステップは、前記パーティクルのセットから前記パーティクルを取り除くステップと、各組合せについて、該組合せの各部分のMEDと、前記パーティクルのセットの前記総MEDとを求めるステップであって、該総MEDは前記組合せの前記一部分の前記MEDを含む、求めるステップと、前記組合せの前記一部分を前記総MEDの最大値に対応する前記パーティクルのセットに加えるステップとをさらに含む請求項1に記載の方法。前記組合せは、前記パーティクルの接頭部および接尾部を含み、前記生成するステップは、接頭部および接尾部の全ての可能な組合せを生成するステップ、をさらに含む請求項1に記載の方法。前記単語のセット内の各単語について、パーティクルが一意になるような該パーティクルへの前記単語の全ての可能な分割を求めるステップと、前記パーティクルから前記アイテムのセットを形成するステップとをさらに含む請求項1に記載の方法。アイテムのセットと単語のセットとの間をインデックス付けするインデックスマップを用いて、前記アイテムのセットに基づいて前記パーティクルの出力セットをインデックス付けするステップをさらに含む請求項1に記載の方法。ユーザーからクエリを取得するステップと、前記パーティクルベースのインデックスを用いて前記アイテムのセットにアクセスするステップであって、前記クエリに最も一致する対応するアイテムを求める、アクセスするステップと、前記ユーザーに対し、結果リストとして前記対応するアイテムを出力するステップとをさらに含む請求項1に記載の方法。前記アイテムのセット内のアイテムは、前記単語のセット、該単語のセットから導出された音声ストリングのセット、前記単語のセットから導出されたパーティクルのセット、およびそれらの組合せのうちの少なくとも1つから選択される請求項1に記載の方法。単語のセットを表すパーティクルの出力セットを生成する方法であって、前記単語のセットからパーティクルのセットを求めるステップと、前記パーティクルのセット内のパーティクルの一部分の組合せを生成するステップと、前記パーティクルのセット内の前記パーティクルを、該パーティクルのセットの総最小編集距離MEDを最大にする組合せの前記一部分と置き換えるステップと、一意の単語ベースのセットをパーティクルベースのセットに変換するステップと、単語のセットを前記パーティクルベースのセットに基づく対応するアイテムのセットに変換するステップと、前記アイテムのセットをインデックス付けするステップであって、パーティクルベースのインデックスを生成する、インデックス付けするステップと、前記パーティクルのセット内の各パーティクルについて前記生成するステップと前記置き換えるステップとを反復して、前記パーティクルの出力セットを生成する、反復するステップとを含み、該方法の前記ステップは、プロセッサによって実行される、単語のセットを表すパーティクルの出力セットを生成する方法。前記求めるステップは、前記単語のセット内の各単語を複数のパーティクルに分割するステップと、前記パーティクルのセット内の全てのパーティクルが一意となるように、該パーティクルのセットに入れる前記パーティクルを選択するステップとをさらに含む請求項13に記載の方法。前記求めるステップは、前記単語のセット内の各単語の音声ストリングを求めるステップと、前記音声ストリングに基づいて前記パーティクルのセットを形成するステップとをさらに含む請求項13に記載の方法。前記パーティクルのセット内の各パーティクルのMEDを求めるステップと、各パーティクルの和として前記パーティクルのセットの前記総MEDを求めるステップとをさらに含む請求項13に記載の方法。前記パーティクルと、前記パーティクルのセット内の全ての他のパーティクルとの間の編集距離を求めるステップと、前記パーティクルの前記MEDとして最も小さい編集距離を選択するステップとをさらに含む請求項13に記載の方法。図1に示すように、本発明の実施の形態は、情報検索IRシステム100においてデータベースからアイテムを検索する方法を提供する。本方法のステップは、当該技術分野において既知のプロセッサにおいて動作する。プロセッサは、メモリおよびI/Oインタフェースを備える。IRシステムは、単語によって表されるアイテムリスト101を備える。単語ベースのリスト101から、パーティクルによって表されるアイテムリスト102を生成する110。単語ベースのリスト内のアイテムとパーティクルベースのリスト内のアイテムとの間の対応は、1対1、または単語の代替的な発音が可能であるときには1対多とすることができる。パーティクルは、音声認識の分野において既知である。本明細書において定義されるように、パーティクルは、連結された音素配列を表す。一連のパーティクルは、単語の音素配列を表す。Whittaker他著ParticlebasedlanguagemodellingInternationalConferenceonSpeechandLanguageProcessing2000を参照されたい。これまで、パーティクルは、自動音声認識ASRシステムにおいて単語を認識するためにしか用いられてこなかった。対照的に、本発明は、パーティクルを用いて情報検索IRを実行する。リスト102にインデクサー120を適用してパーティクルベースのインデックス121を作成する。アイテムを検索するために、ユーザー104からパーティクルベースのクエリ103が取得される。クエリは、ASRを用いてテキスト内の単語または発話から導出することができる。クエリ103を用いて、パーティクルベースのリスト102から構築されたインデックス121を調べる。クエリ103に応答する出力は、パーティクルベースのリスト102内の最も一致するアイテムに対応する、単語ベースのリスト101からのアイテムの結果リスト130である。パーティクルベースのリスト102を生成するために、前処理ステップにおいて、リスト101内の一意の単語のセット149を保持する。単語ベースのセット149を一意のパーティクルのセット151に変換する。パーティクルベースのセット151を取得した後、リスト101内のアイテムに関する単語を対応するパーティクルベースのアイテムに変換して、パーティクルベースのリスト102を生成する110ことができる。図2Aは、本発明の単語ベースのアイテムリスト101の詳細を示している。アイテムは、地理的関心地点であり、各ID201は、アイテム202を一意に識別する。図2Bは、単語211および対応する音素212を示している。幾つかの単語、例えばHOUSESは、代替的な発音を有し得る。図3は、単語301および対応するパーティクル302を示している。単語ベースのリスト内のアイテムが複数の発音を有する場合、全ての単語について、パーティクルへの全ての可能性のある分割のデカルト積が形成され、パーティクルベースのリスト内に列挙される。例えば、AASHIANIがAA_SH_IYAA_N_IYとしてまたはAA_SHY_AE_N_IHとしてパーティクルに分割することができ、RESTAURANTがR_E_S_T_R_AA_N_TとしてまたはR_E_S_T_ER_R_AA_N_Tとしてパーティクルに分割することができる場合、全ての可能性のある分割:AA_SH_IYAA_N_IYR_E_S_T_R_AA_N_T、AA_SH_IYAA_N_IYR_E_S_T_ER_R_AA_N_T、AA_SHY_AE_N_IHR_E_S_T_R_AA_N_T、およびAA_SHY_AE_N_IHR_E_S_T_ER_AA_N_Tが、パーティクルベースのインデックス内に列挙される。図4は、パーティクルベースのリスト102の詳細を示し、該リストは、アイテム402ごとに一意のID401を含む。図5は、ASRによって使用することができる発音辞書を示し、該発音辞書は、パーティクル501および対応する音素502を含む。本発明の言語モデルは、パーティクル、例えば、パーティクルnグラムに対する統計を含むnグラム言語モデルを含む。パーティクルの変換本発明の実施の形態は、情報検索IRシステムの動作のために、単語のセットを、可能な限り互いに異なるパーティクルを用いて表すことが有利であるという認識に基づいている。例えば、可能な限り互いに異なるパーティクルを有することによって、ASR中の正確な認識が可能になる。さらに、実施の形態は、パーティクル間の差を編集距離を用いて測定することができるという更なる認識に基づいている。したがって、実施の形態は、パーティクルの出力セットにおいて、アイテムのセット660を変換する。本発明の様々な実施の形態において、アイテムのセットは、IRシステムにおいて用いるのに適した単語のセットを表す。例えば、1つの実施の形態は、単語のセット内の各単語について、該単語の複数のパーティクルへの全ての可能な分割を求め、単語のセットから導出された一意のパーティクルからアイテムのセットを形成する。他の実施の形態では、アイテムのセット内のアイテムは、単語のセット、単語のセットから導出された音声ストリングのセット、単語のセットから導出されたパーティクルのセット、およびそれらの組合せのうちの少なくとも1つから選択される。図8は、パーティクルのセットの一例を示している。セット内の各パーティクルについて、最小編集距離MED810が求められる。MEDは、全ての他のパーティクルに対するそのパーティクルの最も小さい編集距離である。また、パーティクルのセットの総MED820が各パーティクルのMEDの和として求められる。図6は、パーティクルの出力セット615においてパーティクルのセット610を変換するための方法600のブロック図を示している。1つの実施の形態において、パーティクルのセットは、アイテムのセットの少なくとも一部分によって形成される。本方法のステップは、当該技術分野において既知のように、プロセッサ601によって実行される。変換モジュール602は、パーティクルのセット内のパーティクル620の一部分の組合せ635を生成する630。例えば、1つの実施の形態では、組合せは、2つの部分、すなわち、パーティクルの接頭部および接尾部のみを含む。加えて、組合せ635は、パーティクルの全ての可能な組合せである。代替の実施の形態では、組合せは、3つ以上の部分を含む。パーティクル620は、パーティクルのセット内で、該パーティクルのセットの総最小編集距離MEDを最大にする640組合せの一部分645と置き換えられる650。変換は、パーティクルのセット内の全てのパーティクルについて反復され、これによって、パーティクルの出力セットにおいてパーティクルのセットを変換する。図7は、パーティクル710を該パーティクルの接頭部および接尾部715と置き換える700一例を示している。パーティクルは、パーティクルのセットから取り除かれ720、組合せの一部分、すなわち、接頭部および接尾部がパーティクルのセットに加えられる730。次に、パーティクルのセット内の各パーティクルについてMEDが求められ740、MEDが合算され、パーティクルのセットの総MED755が求められる750。置き換えは、パーティクルの全ての組合せについて繰り返される。具体的には、組合せの一部分がパーティクルのセットから取り除かれ、パーティクルの別の組合せの一部分と置き換えられ、該別の組合せの一部分を用いてMEDおよび総MEDが求められる。最後に、総MEDの最大値に対応する組合せの一部分がパーティクルのセットに加えられる。1つの実施の形態は、パーティクルのセット内の一意のパーティクルのみを保持する。組合せの一部分がパーティクルのセット内のパーティクルと同一である例では、この部分は、セットに加えられない。変換中、パーティクルのセット、したがってパーティクルの出力セットは、単語のセットに従ってインデックス付けされる。例えば、1つの実施の形態は、アイテムのセットと単語のセットとの間でインデックスのインデックスマップを作成する。インデックスマップは、複数のパーティクルへの単語の分割を追跡する。変換中、インデックスマップは、パーティクルに置き換わるパーティクルの一部分をインデックス付けするツリーマップとなる。図9~図11は、図8に示すパーティクルのセット810からのパーティクルabcd830の変換の例を示している。パーティクルabcdの全ての可能な2つの部分の組合せは、図9に示すようにabcdと、図10に示すようにabcdと、図11に示すようにabcdとである。各組合せについて、変換モジュールは各パーティクルのMEDと、全体セットの総MED値とを求める。組合せの一部分abcdが総MEDを最大にするので、総MEDの値は7に等しく、その組合せの一部分がパーティクルabcdを置き換える。