JP4805267B2 - トークンスペースレポジトリと共に使用される多段クエリ処理システム及び方法 - Google Patents

Description

関連出願
本出願は、「可変長データを符号化する及び復号するシステム及び方法（Ｓｙｓｔｅｍ ａｎｄ Ｍｅｔｈｏｄ Ｆｏｒ Ｅｎｃｏｄｉｎｇ Ａｎｄ Ｄｅｃｏｄｉｎｇ Ｖａｒｉａｂｌｅ−Ｌｅｎｇｔｈ Ｄａｔａ）」と題された、米国特許出願第１０／９１７，７４５号明細書（２００４年８月１３日出願）、及び「トークンスペースレポジトリと共に使用されるドキュメント圧縮システム及び方法（Ｄｏｃｕｍｅｎｔ Ｃｏｍｐｒｅｓｓｉｏｎ Ｓｙｓｔｅｍ ａｎｄ Ｍｅｔｈｏｄ Ｆｏｒ Ｕｓｅ Ｗｉｔｈ Ｔｏｋｅｎｓｐａｃｅ Ｒｅｐｏｓｉｔｏｒｙ）」と題された、米国特許出願第１０／９１７，７３９号明細書（２００４年８月１３日出願）に関する。これらの出願は、その全体が参照により本明細書に援用されている。

技術分野
開示されている実施形態は、一般に、データ処理システム及び方法、詳細には、関連付けられたインデックスを有するドキュメントコレクション（以下、「トークンスペースレポジトリ」とも呼ぶ）と共に使用される多段クエリ処理システム及び方法に関する。

背景
情報検索システム（たとえば、サーチエンジン）は、ドキュメントコーパス（たとえば、ワールドワイドウェブ）から生成されたドキュメントのインデックスにクエリを突き合わせる。代表的な逆インデックスは、それぞれのドキュメント内のワードを、ドキュメント内のそれらの場所に対するポインタと共に、含む。ドキュメント処理システムは、自動又は手動プロセスを使用して、ドキュメントコーパスから検索された、ドキュメント、ページ、又はサイトのコンテンツを処理することにより、逆引きインデックスを準備する。ドキュメント処理システムはまた、ドキュメントのコンテンツ又はコンテンツの一部分を、クエリプロセッサがクエリに応答する場合に使用するためにレポジトリ内に格納することがある。

クエリ結果がそのクエリに関連していることを確実にするために、より高度なクエリサーチ及びスコアリング技術が常に必要とされている。スコアリング技術によっては、たとえば、ドキュメント内で見つかったクエリ用語又はキーワードのコンテキストを判断するために、候補ドキュメントの部分的な再構築が必要である。しかし残念ながら、このような高度な技術を導入した場合に、追加処理及びそれに伴うオーバーヘッドによりサーチ性能が低下する恐れがある。

発明の概要
開示されている実施形態は、トークンスペースレポジトリと共に使用される多段クエリ処理システム及び方法を含む。多段クエリ処理システム及び方法により、多層マッピングスキームによって容易になった増分ドキュメントの再構築（incremental document reconstruction）による「スニペット（snippet）」の生成を含む、多段クエリスコアリングが使用可能となる。多段クエリ処理システムの１つ以上の段階で、１セットの関連性スコアが、順序付きリストとしてユーザに提示するための１サブセットのドキュメントを選択するのに使用される。その１セットの関連性スコアは、多段クエリ処理システムの前の段階で判断された１セット以上の関連性スコアから、一部導き出され得る。いくつかの実施形態においては、多段クエリ処理システムは、ユーザクエリで２つ以上のパスを実行することと、順序付きリスト内のドキュメントの関連性を向上させるために、それぞれのパスからの情報を使用して、その後のパスで使用するユーザクエリを拡張することとが可能である。

図全体を通じて、対応する部品には同様の参照符号が付されている。

実施形態の説明
システム概説
図１は、情報検索システム１００の実施形態を示すブロック図である。情報検索システム１００は、ドキュメント処理システム１０２とクエリ処理システム１０４とを含む。情報検索システム１００は、クエリに応答して情報を検索することが可能な、任意のシステムであり得る。これは、インターネット（たとえば、ワールドワイドウェブを介する）又はイントラネットなどの１つ以上のネットワークで、又は（たとえば、ファイル、電子メール、アプリケーションなどの）ユーザのコンピュータで局所的に、明示的な又は非明示的なドキュメントのサーチを遂行するための１つ以上のコンピュータシステムを含むが、これらに限定されるものではない。用語「ドキュメント」とは、ドキュメント、ウェブページ、Ｅメール、特定用途向けドキュメント及びデータ構造、インスタントメッセージング（ＩＭ）メッセージ、オーディオファイル、ビデオファイル、及び１つ以上のコンピュータシステムに常駐する他の任意のデータ又はアプリケーションを意味することに留意されたい。

ドキュメント処理システム
ドキュメント処理システム１０２は、一般に、１つ以上のドキュメントレポジトリ１０６と、レキシコンジェネレータ（lexicon generator）１０８と、符号化／復号化システム１１０と、トークンスペースレポジトリ１１２とを含む。符号化／復号化システム１１０は、１つ以上のドキュメントレポジトリ１０６からドキュメントを検索し、そのドキュメントを構文解析（parse）してトークンを得て、レキシコンジェネレータ１０８からのマッピングを使用して、そのトークンを圧縮形式に符号化し、次いで、その符号化されたトークンをトークンスペースレポジトリ１１２内に格納する。

「トークン」は、ドキュメント内で通常見られる、任意のオブジェクトであり得る。これは、用語、成句、区切り、ＨＴＭＬタグなどを含むが、これらに限定されるものではない。１セットのドキュメントは、構文解析された後、トークンシーケンスとして表される。さらに、トークンシーケンス内のそれぞれのトークンが、トークン位置を有し、これは、１セットのドキュメント内のトークンの位置をも表す。たとえば、１セットのドキュメント内の第１のトークンには０の位置が割り当てられ、１セットのドキュメント内の第２のトークンには１の位置が割り当てられるなどのように続いていく。

いくつかの実装形態においては、ドキュメントを復号するのに使用されるコンピュータとは完全に異なるセットのコンピュータが、ドキュメントを符号化するのに使用されることに留意されたい。たとえば、ウェブクローリングシステムが、ドキュメントを符号化するドキュメント処理システム１０２を含み、クエリ処理システム１０４が、符号化されたドキュメントの選択された部分を復号することがある。このような実装形態においては、ドキュメント処理システム１０２によって構築（build）されたドキュメント逆インデックス及びトークンスペースレポジトリ１１２、又はそのコピーが、クエリ処理システム１０４によって使用される。

レキシコンジェネレータ１０８は、ドキュメントを構文解析することにより、１セットのドキュメントを符号化するのに使用されるマッピングを生成する。レキシコンジェネレータ１０８によって作成された第１のマッピングは、本明細書においては、グローバルレキシコンと呼ばれる。これは、セットドキュメント内のすべての互いに異なるトークン（本明細書においては、ユニークトークンと呼ばれる）を識別し、グローバルトークン識別子をそれぞれのユニークトークンに割り当てる。レキシコンジェネレータ１０８によって作成された第２のマッピングは、実際には、マッピングのシーケンスであり、そのそれぞれが、本明細書においては、ミニレキシコンと呼ばれる。それぞれの各ミニレキシコンは、１セットのドキュメント内の位置の各範囲を符号化し、復号するためにのみ使用される。グローバルレキシコン及びミニレキシコンの生成及び使用について、以下により詳細に説明する。

クエリ処理システム
クエリ処理システム１０４は、符号化／復号化システム１１０に結合された１つ以上のクエリプロセッサ１１４と、トークンスペース逆インデックス１１６とを含む。トークンスペース逆インデックス１１６は、１セットのドキュメント内のすべてのＧＴｏｋｅｎＩＤを、ドキュメント内のそれらの位置にマッピングする。概念的には、逆インデックス１１６は、それぞれのＧＴｏｋｅｎＩＤのためのトークン位置のリストを含む。効率化のために、それぞれのＧＴｏｋｅｎＩＤのためのトークン位置のリストは、逆インデックスによって占有されるスペースの量を減少させるよう符号化される。

いくつかの実施形態においては、１つ以上のクエリプロセッサ１１４は、クエリを構文解析して、１つ以上のクエリプロセッサ１１４によりクエリ表現（たとえば、ブーリアンツリー表現）に変換される多くのクエリ用語を得る。クエリ用語は、図４について詳しく記載するように、トークン位置を検索するために、トークンスペース逆インデックス１１６に索引を付けるのに使用される。いくつかの実施形態においては、トークン位置は、図５について記載するように、多段クエリ処理システムにおいて、クエリに関連するドキュメントをスコアリングするのに使用される。クエリプロセッサ１１４は、クエリ用語に応答して、１つ以上の通信モード（たとえば、ディスプレイデバイス、オーディオなど）を介してユーザに提示される、ドキュメントの順序付きリストを生成する。

レキシコンジェネレータ
図２は、図１のレキシコンジェネレータ１０８の実施形態を示す概念ブロック図である。レキシコンジェネレータ１０８は、グローバルレキシコンビルダ２０２とミニレキシコンビルダ２０４とを含む。

グローバルレキシコンビルダ
グローバルレキシコンビルダ２０２は、ドキュメントレポジトリ１０６からドキュメントを検索し、ユニークなグローバルトークン識別子（ＧＴｏｋｅｎＩＤ）をドキュメント内に含まれているそれぞれのユニークトークンに割り当てることによりグローバルレキシコン２０６を生成する。いくつかの実施形態においては、ドキュメントレポジトリ１０６は、（時にパーティションと呼ばれる）多くの部分に論理的に又は物理的に分けられ、それぞれのパーティションについて、別個のグローバルレキシコン２０６が生成される。一実施形態においては、数十億のドキュメントの１セットが数千のパーティションに分割され、そのそれぞれが処理されて、グローバルレキシコン２０６を生成する。代表的なグローバルレキシコン２０６が、数百万のユニークトークンを含み得る。

いくつかの実施形態においては、符号化されるべき１セットのドキュメント（たとえば、１つのパーティション内のドキュメント）が、１つ以上の基準に従ってソートされ、その後、そのドキュメントが構文解析されてトークンが得られ、そのトークンが処理される。ドキュメントをこのようにソートすることにより、トークン化されたドキュメントの効率的な符号化が容易となり得る。何故なら、同様のセットのワードを使用するドキュメントが、その１セットのドキュメント内の互いの近くに位置決めされるからである。この結果、それぞれのミニレキシコン（以下に記載する）が、平均して、１セットのドキュメントの、通常より大きい部分をカバーする。より具体的には、ドキュメントを符号化することにより、より少ないスペースしか占有されなくなる。一実施形態においては、１セットのドキュメントは、まず言語によってソートされ、次いで、それぞれの言語のドキュメントが、ＵＲＬのホスト名部分のフィールドを逆順に用いてＵＲＬによってソートされる。たとえば、言語によってソートされた後、すべてのフランス語のドキュメントはグループ化され、次いで、そのフランス語のドキュメントは、ＵＲＬによってソートされる。ＵＲＬによってソートする場合、それぞれのＵＲＬは、最初、ｈ１．ｈ２．．．ｈｙ．ｈｚ／ｎｌ／ｎ２．．．のパターンを有する。ここで、ｈ１．ｈ２．．．ｈｙ．ｈｚは、ＵＲＬのホスト名部分を有し、／ｎ１／ｎ２は、ＵＲＬの残りの部分を表す。ＵＲＬは、ＵＲＬによってソートされる前に、パターンｈｚ．ｈｙ．．．ｈ２．ｈ１／ｎ１／ｎ２．．．に再マッピングされる。たとえば、ＵＲＬ「ｗｗｗ．ｇｏｏｇｌｅ．ｃｏｍ／ａｂｏｕｔ．ｈｔｍｌ」は、「ｃｏｍ．ｇｏｏｇｌｅ．ｗｗｗ／ａｂｏｕｔ．ｈｔｍｌ」に再マッピングされる。ＵＲＬによってソートされる前に、ＵＲＬのホスト名フィールドを逆順にすることにより、ドキュメントは、互いに近い論理に従ってソートされる。したがって、（特定の言語のための１群のドキュメント内の）同様のタイプのドキュメントがグループ化され、それぞれのドキュメントタイプの１群のドキュメント内では、それぞれのウェブサイトのドキュメントがグループ化され、それぞれのウェブサイトのドキュメント内では、ウェブサイトの様々なブランチのためのドキュメントがグループ化されるなどのように続いていく。

いくつかの実施形態においては、ドキュメントは、１つ以上のクラスタ化技術を使用して順序付けられる。ドキュメント内に含まれている用語、ワード、又は成句が、ドキュメントを様々な概念に関係するクラスタに編成するのに使用され得る。たとえば、ドキュメントについての一般的な情報（たとえば、識別されたドキュメントに埋め込まれた或いは関連付けられたメタデータ）、識別されたドキュメントからサンプリングされたコンテンツ、及び／又はドキュメントについてのカテゴリ情報が、ドキュメントを順序付けるのに使用され得る。

いくつかの実施形態においては、ドキュメントを構文解析している間、グローバルレキシコンビルダ２０２は、１セットのドキュメント内のそれぞれのユニークトークンの発生数などの、それぞれの識別されたユニークトークンについての情報（図２に図示せず）、及び、（あれば）そのユニークトークンに関連付けられた言語を格納する。ユニークトークンに関連付けられた言語は、そのトークンが見つかったドキュメントに関連付けられた言語に基づいて判断されることがある。特定のトークンがより多くの言語に関連付けられたドキュメント内で見つかった場合には、そのトークンに関連付けられた言語は、任意の好適な方法を使用して判断されることがある。１つの好適な方法は、ユニークトークンを識別するために１セットのドキュメントを構文解析する場合に使用される、統計的な方法である。それぞれのトークンが、最初、見つかった第１のドキュメントの言語に割り当てられ、次いで、そのトークンに割り当てられた現在の言語以外の言語のドキュメント内で発生するトークンのそれぞれのその後の発生について、そのトークンは、０と１との間でランダムに（又は擬似ランダムに）選択された数が１／Ｎ未満である場合にのみ、他の言語に再び割り当てられる（ここで、Ｎは、トークンの現在の発生カウント数である）。他の実施形態においては、任意の同様の、或いは好適な言語割当てメカニズムが、言語をそれぞれのユニークトークンに関連付けるのに使用され得る。いくつかの実施形態においては、言語は、区切り記号を表すユニークトークンに関連付けられない。さらに別の実施形態においては、言語があらゆるユニークトークンに関連付けられるが、Ｎ（たとえば、２５６）個の最も頻繁に発生するトークンを処理する場合には、言語の関連付けは無視される。この結果、区切りトークンに関連付けられた言語は、効果的に無視される。

いくつかの実施形態においては、ユニークトークンのリスト、及び関連付けられた頻度及び言語情報は、ユニークトークンの発生頻度に基づいてソートされる。次いで、エントリは、任意に、１セットのドキュメントの、スペース効率の良い符号化を容易にするようさらにソートされ得る。たとえば、一実施形態においては、すべてのユニークトークンが、まず発生頻度によってソートされる。次いで、この結果生じたユニークトークンのソートリストが、バンドに分割される。たとえば、トップバンドであるバンド０は、トップの２５５又は２５６のトークン（即ち、最高頻度のカウント数のトークン）を有することがある。第２のバンドであるバンド１は、バンド０内のトークンを除く、トップ２^１４（即ち、６５,５３６）のトークンを有することがある。第３のバンドであるバンド２は、ユニークトークンのソートリスト内の次の２^１４（即ち、６５,５３６）のトークンを有することがある。勿論、他の実施形態においては、それぞれのバンド内のトークンの数が異なることがある。次に、それぞれのバンド内のトークンが、第２のセットの基準に従ってソートされる。たとえば、一実施形態においては、第１のバンド内のトークンは、アルファベット順に、つまり数値又はアルファベット値によってソートされる。他のバンドのそれぞれは、まず言語によって、次いでアルファベット順にソートされる。この結果、バンド０以外のそれぞれのバンド内のソートされたトークンは、言語によってグループ化され、それぞれの言語グループ内では、トークンがアルファベット順にソートされる。他の実施形態においては、バンドのそれぞれにおいてユニークトークンをソートするために、他のソート基準が使用されることがある。

ソートプロセスでは、それぞれがリスト内の各位置を有する、ユニークトークンのソートリストを作成する。次いで、それぞれのソートされたユニークトークンに、ユニークなグローバルトークン識別子（以下、「ＧＴｏｋｅｎＩＤ」とも呼ぶ）が割り当てられる。ＧＴｏｋｅｎＩＤは、ドキュメント処理システム１０２を実装するのに使用されるプラットフォームに応じて、任意の好適なデータタイプ及び幅を含み得る（たとえば、３２ビットの符号のない整数）。いくつかの実施形態においては、ＧＴｏｋｅｎＩＤは、ソートされたユニークトークンに増加順に割り当てられるので、高頻度のトークンには小さい値のＧＴｏｋｅｎＩＤが割り当てられ、低頻度のトークンには大きい値のＧＴｏｋｅｎＩＤが割り当てられる。より具体的には、一実施形態においては、トークンのソートリスト内のそれぞれのトークンには、そのユニークトークンのソートリスト内の数値位置に等しい３２ビットのグローバルトークン識別子が割り当てられる。したがって、リスト内の第１のトークンには、０（即ち、１６進法では００００００００）に等しいＧＴｏｋｅｎＩＤが割り当てられ、リスト内の第２のトークンには、１に等しいＧＴｏｋｅｎＩＤが割り当てられるなどのように続いていく。この結果生じた、ＧＴｏｋｅｎＩＤのユニークトークン値への１セットのマッピングは、本明細書においては、グローバルレキシコン２０６と呼ばれる。いくつかの実施形態においては、グローバルレキシコン２０６は、実際には２つのマッピング構造を有し、その１つはＧＴｏｋｅｎＩＤをトークンにマッピングし、別のものはトークンをＧＴｏｋｅｎＩＤにマッピングする。トークンのＧＴｏｋｅｎＩＤへのマッピングは、符号化プロセス中に使用され、ＧＴｏｋｅｎＩＤのトークンへのマッピングは、ドキュメントの一部分を復号する場合に使用される。

以下に詳しく説明するように、頻度に基づいてユニークトークンを順序付けることは、ミニレキシコン２０８を格納するのに必要なスペースの量を減少するのに役立つ。このことは、ユニークトークンのバンドが発生頻度以外の基準に基づいてソートされる実施形態にも当てはまる。何故なら、より低いＧＴｏｋｅｎＩＤに割り当てられたバンド内のトークンは、より高いＧＴｏｋｅｎＩＤに割り当てられたバンド内のトークンより高い発生頻度を有するからである。

いくつかの実施形態においては、ＨＴＭＬタグ及び区切りなどの平均的なトークンより頻繁に発生する「特別な」トークンに、グローバルレキシコン２０６内のＧＴｏｋｅｎＩＤの接頭部２０５の部分（prefix 205 portion）を占有するＧＴｏｋｅｎＩＤが割り当てられる（たとえば、ＧＴｏｋｅｎＩＤ_０−ＧＴｏｋｅｎＩＤ_Ｎ−１）。他のすべてのＧＴｏｋｅｎＩＤが、接頭部２０５に割振られた最後の特別なＧＴｏｋｅｎＩＤによってオフセットされ得る。

上記の説明においては、ＧＴｏｋｅｎＩＤは、３２ビットの符号のない整数値などの、固定長値として記載されている。しかし、これらの同じＧＴｏｋｅｎＩＤは、可変長識別子として考えることもできる。何故なら、ＧＴｏｋｅｎＩＤが格納されるよう符号化された場合には、ゼロに等しい最上位のバイト（又はビット）が、符号化中に切り捨てられる又はマスクされることがあるからである。たとえば、いくつかの実施形態においては、２^８未満の値を有するすべてのＧＴｏｋｅｎＩＤは１バイト値として符号化され、２^１６未満の値を有するすべてのＧＴｏｋｅｎＩＤは２バイト値として符号化され、２^２４未満の値を有するすべてのＧＴｏｋｅｎＩＤは３バイト値として符号化される。このようにして、１セットのドキュメント内で最高の発生頻度を有するトークンが、より低い発生頻度を有するトークンより短い長さのＧＴｏｋｅｎＩＤによって表される。

以下に記載する実施形態においては、トークンスペースレポジトリには、可変長ＧＴｏｋｅｎＩＤではなく、固定長ＬＴｏｋｅｎＩＤが存在する（is populated）。しかし、トークンスペースレポジトリ内のＬＴｏｋｅｎＩＤを再び元のトークン（勿論、これも可変長である）にマッピングする場合、多数の「ミニレキシコン」を格納する必要があり、ミニレキシコンのコンテンツは、ＧＴｏｋｅｎＩＤを有する。ミニレキシコンを効率的に格納するために、それぞれのミニレキシコン内のＧＴｏｋｅｎＩＤが可変長値として扱われることがある。代替形態として、それぞれのミニレキシコン内のＧＴｏｋｅｎＩＤが、まずデルタ符号化されるリストとして扱われ、次いで、この結果生じたデルタ値が、可変長符号化スキームを使用して符号化される。

ミニレキシコンビルダ
グローバルレキシコン２０６が生成された後、１セットのミニレキシコン２０８が、符号化／復号化システム１１０によって使用されるミニレキシコンビルダ２０４によって生成される。ミニレキシコン２０８内のそれぞれのエントリが、ＧＴｏｋｅｎＩＤとこれに対応するローカルトークン識別子（ＬＴｏｋｅｎＩＤ）とを含む。それぞれのエントリのためのＬＴｏｋｅｎＩＤは、ミニレキシコン２０８内のエントリの位置によって暗黙に定義されるので、明示的に格納される必要がない。それぞれの各ミニレキシコン２０８は、トークン化されたドキュメント内の、互いに異なる各特有の範囲のトークン位置を符号化し、復号するためにのみ使用されるので、同じセットのＬＴｏｋｅｎＩＤをそれぞれのミニレキシコン２０８によって使用することが可能となる。たとえば、ミニレキシコンビルダ２０４がドキュメントを通じて構文解析する時に出会う最初のＰ個のユニークトークンのために、Ｐ（たとえば、２５６）エントリを有する第１のミニレキシコン２０８（たとえば、ミニレキシコンＡ）が生成される。最初のＰ個のユニークトークンに出会うと、第１のミニレキシコン２０８が有効であるトークン位置の範囲のための、開始トークン位置、Ｓｔａｒｔ＿Ｐｏｓ_Ａを含む、「有効範囲マップ（valid range map）」２１０の第１のエントリが作られる。第１のミニレキシコン２０８内のＰ個のＬＴｏｋｅｎＩＤのそれぞれが、ユニークなＧＴｏｋｅｎＩＤに割り当てられる。ＬＴｏｋｅｎＩＤのすべてがＧＴｏｋｅｎＩＤに割り当てられた場合には、第２のミニレキシコン２０８（たとえば、ミニレキシコンＢ）が、ミニレキシコンビルダ２０４が出会う次のＰ個のユニークトークンのために生成され、第２のミニレキシコン２０８が有効である位置の範囲の、開始トークン位置、Ｓｔａｒｔ＿Ｐｏｓ_Ｂを含む、有効範囲マップ２１０の第２のエントリが作られる。したがって、Ｓｔａｒｔ＿Ｐｏｓ_ＢからＳｔａｒｔ＿Ｐｏｓ_Ｃ−１までの範囲内に入るトークン化されたドキュメント内の位置を有するトークンが、図２に示されているように、ミニレキシコンＢを使用して復号され得る。

具体例を示すために、一実施形態においては、それぞれのミニレキシコン内のＬＴｏｋｅｎＩＤは、０〜２５５の値を有し、それぞれが８ビットの符号のない整数で表され、ＧＴｏｋｅｎＩＤは、３２ビットの符号のない整数である。第１のミニレキシコンが、トークン位置０から開始して、予め定義された数Ｐ（たとえば、２５６）の互いに異なるトークンが識別されるまで、１セットのドキュメントを走査することによって生成される。Ｐ個の互いに異なるトークンのためのＧＴｏｋｅｎＩＤは、リストに集められる（assembled in a list）。いくつかの実施形態においては、リスト内のＧＴｏｋｅｎＩＤは、リストのトップに最小のＧＴｏｋｅｎＩＤがくるように、数値によってソートされる。次いで、ＬＴｏｋｅｎＩＤは、リスト内のＧＴｏｋｅｎＩＤの位置に従って、リスト内のＧＴｏｋｅｎＩＤに割り当てられる。たとえば、リスト内の第１のＧＴｏｋｅｎＩＤには、０のＬＴｏｋｅｎＩＤが割り当てられ、リスト内の次のＧＴｏｋｅｎＩＤには、１のＬＴｏｋｅｎＩＤが割り当てられるなど、と続いていく。この結果生じた、ＬＴｏｋｅｎＩＤのＧＴｏｋｅｎＩＤへのマッピングは、ミニレキシコン２０８と呼ばれる。Ｓｔａｒｔ＿Ｐｏｓ_ＡからＳｔａｒｔ＿Ｐｏｓ_Ｂへのトークン位置の範囲は、ミニレキシコンに関連付けられる。第２のミニレキシコンが、第１のミニレキシコンに関連付けられた最後の位置の直後の位置Ｓｔａｒｔ＿Ｐｏｓ_Ｂから開始して、１セットのドキュメントを走査することによって生成される。走査は、予め定義された数Ｐの互いに異なるトークンが識別されるまで継続する。この時点で、第２のミニレキシコンが、上述したのと同じプロセスを使用して生成される。ミニレキシコンビルダ２０４は、引き続き、ドキュメント内のすべてのトークンがミニレキシコン２０８にマッピングされるまで、１セットのドキュメント内のトークン位置の次の範囲のために、ミニレキシコン２０８のシーケンスを生成する。

代替実施形態においては、それぞれのミニレキシコン２０８内の最初のＦ個のＬＴｏｋｅｎＩＤは、１セットのドキュメント内の、Ｆ個の最も普及しているトークンのために予約される。これらのＦ個のＬＴｏｋｅｎＩＤについて、ＬＴｏｋｅｎＩＤは、常にＧＴｏｋｅｎＩＤに等しい。この割当てスキームにより、ドキュメントの速い復号化が容易となる。（Ｆ−１）以下の値を有する（トークンスペースレポジトリ内の）ＬＴｏｋｅｎＩＤが復号される時はいつでも、ＬＴｏｋｅｎＩＤをこれに対応するＧＴｏｋｅｎＩＤにマッピングする必要なく、グローバルレキシコンに従って直接トークンにマッピングすることができる。

同じセットのＬＴｏｋｅｎＩＤ（たとえば、０〜２５５）が、それぞれのミニレキシコン２０８内で使用される。ドキュメントの圧縮を容易にするために、ＬＴｏｋｅｎＩＤは、ＧＴｏｋｅｎＩＤ（たとえば、４バイト）より小さい幅（たとえば、１バイト）を有する。これらの幅の差（たとえば、３バイト）は、トークン化されたドキュメントをトークンスペースレポジトリ１１２内に格納するのに使用される、トークン毎のバイト数の減少を表している。それぞれのＬＴｏｋｅｎＩＤが１バイトを占有する実施形態においては、１０億のトークンを有する１セットのドキュメントは、他のサポーティングデータ構造（supporting data structures）（本文書において、後に記載する）によって占有されるスペースを無視すれば、トークンスペースレポジトリ１１２内の１０億バイト（１ＧＢ）を占有する。

ミニレキシコン２０８を生成するプロセスが完了した場合には、トークン化されたドキュメント内のあらゆるトークンが、そのトークン化されたドキュメント内のその位置に基づいてミニレキシコン２０８に関連付けられる。トークンが１つ以上の位置範囲内に発生した場合、トークン化されたドキュメント内のそれぞれのユニークトークンが１つ以上のミニレキシコン２０８に関連付けられることがあることに留意されたい。一実施形態においては、平均的なドキュメントは約１１００のトークンを有し、平均的なミニレキシコン２０８は、約１０００のトークンにまたがる。

それぞれのミニレキシコン２０８が生成された後、１セットのドキュメントのこれに対応する部分のトークンが、符号化／復号化システム１１０によりＬＴｏｋｅｎＩＤにマッピングされ、その後の検索のためにトークンスペースレポジトリ１１２に格納される。このマッピングにより、ドキュメントレポジトリ１０６内のあらゆるトークンが、トークンスペースレポジトリ１１２内の固定長（たとえば、１バイト）のＬＴｏｋｅｎＩＤにマッピングされる。したがって、復号化／復元中に、トークンスペースレポジトリ１１２内の１つのトークン位置から別のトークン位置にジャンプすることができ、テーブル又はこれに相当するデータ構造をスキップする必要がない。そのようなスキップは、復号化プロセスの速度を下げる恐れがある。

いくつかの実施形態においては、ミニレキシコン２０８は、圧縮形式に符号化され、ドキュメントの再構築が必要となるまで、格納される。一実施形態においては、それぞれのミニレキシコン２０８内のＧＴｏｋｅｎＩＤのソートリストはデルタ符号化され、次いで、この結果生じたデルタ値のリストが、圧縮形式に、好ましくはミニレキシコンの速くかつ効率的な復号化及び再構築を容易にする形式に符号化される。好適なデータ構造及び符号化／復号化方法が、「可変長データを符号化する及び復号するシステム及び方法（Ｓｙｓｔｅｍ ａｎｄ Ｍｅｔｈｏｄ Ｆｏｒ Ｅｎｃｏｄｉｎｇ Ａｎｄ Ｄｅｃｏｄｉｎｇ Ｖａｒｉａｂｌｅ−Ｌｅｎｇｔｈ Ｄａｔａ）」と題された、同時係属中の米国特許出願第１０／９１７,７４５号明細書（２００４年８月１３日出願）に記載されている。

特定のドキュメントを復元するために、そのドキュメントのためのトークン位置の範囲に関連付けられたミニレキシコン２０８が復元され、ミニレキシコン２０８のエントリから構築された翻訳テーブル又はマッピングが得られる。このマッピングは、ＬＴｏｋｅｎＩＤをこれに対応するＧＴｏｋｅｎＩＤに翻訳する。したがって、トークンスペースレポジトリ１１２内のトークン化されたドキュメントを復号することが、そのドキュメント用のトークンスペースレポジトリ１１２内に格納されている固定長ＬＴｏｋｅｎＩＤを読み取り、そしてＬＴｏｋｅｎＩＤをこれに対応するＧＴｏｋｅｎＩＤに翻訳するためにドキュメント内のそれぞれのトークン位置のためのミニレキシコンにアクセスすることによって、達成される。次いで、ＧＴｏｋｅｎＩＤは、グローバルレキシコン２０６を使用して、これに対応するトークン（たとえば、テキスト及び区切り）にマッピングされ、これにより、ドキュメントのすべて又は一部分が再構築される。

符号化システム
図３Ａは、トークンスペースレポジトリのためのドキュメントを符号化するための符号化システム３００の実施形態を示すブロック図である。符号化システム３００は、オプションとしてのプリプロセッサ３０２と、オプションとしてのデルタエンコーダ３０４と、可変長データエンコーダ３０６とを含む。可変長データは、整数、文字列、浮動小数点数、固定小数点数などの様々なデータタイプを制限することなく含み得る。可変長データは、テキスト、画像、図形、オーディオサンプルなどを含むが、これらに制限されるものではない。

いくつかの実施形態においては、情報のリストがプリプロセッサ３０２によって受信され、プリプロセッサ３０２は、効率的な符号化のために情報を順序付ける。プリプロセッサ３０２は、１つ以上のソートアルゴリズムを使用して、データを単調なシーケンスに順序付けることがある。たとえば、１セットの整数が値によってソートされた場合、隣接する整数の大きさが接近し、したがって、デルタエンコーダ３０４が、符号化するために小さい値の整数であるデルタ値を生成することが可能となる。順序付けられたデータは、デルタエンコーダ３０４によって受信され、このデルタエンコーダは、順序付けられたデータの隣接する対の間の差を計算し、小さい値の整数を得る。小さい値の整数は、可変長データエンコーダ３０６によって受信され、この可変長データエンコーダは、データを効率的に復号され得る圧縮形式に符号化する。好適な可変長データエンコーダ３０６の一例が、「可変長データを符号化する及び復号するシステム及び方法（Ｓｙｓｔｅｍ ａｎｄ Ｍｅｔｈｏｄ Ｆｏｒ Ｅｎｃｏｄｉｎｇ Ａｎｄ Ｄｅｃｏｄｉｎｇ Ｖａｒｉａｂｌｅ−Ｌｅｎｇｔｈ Ｄａｔａ）」と題された、同時係属中の米国特許出願第１０／９１７,７４５号明細書（２００４年８月１３日出願）に詳しく記載されている。

ドキュメント処理システム１０２によって生成された様々な情報は、符号化システム３００のすべて又は一部を使用して符号化され得る。いくつかの実施形態においては、それぞれのミニレキシコン２０８内のＧＴｏｋｅｎＩＤは、大きさの最も近い整数値がデルタ符号化されることを確実にするよう、プリプロセッサ３０２を使用してソートされる。次いで、順序付けられたＧＴｏｋｅｎＩＤが、デルタエンコーダ３０４によってデルタ符号化され、差値又は残値が提供される。次いで、その差値が、可変長データエンコーダ３０６を使用して、圧縮形式にグループ（たとえば、４つの値のグループ）で符号化される（encoded in groups）。いくつかの実施形態においては、図４について詳しく記載するように、逆インデックス内のトークン位置のリストも同様に、速くかつ効率的な位置の復号化が容易となるように符号化される。

可変長データエンコーダ３０６は、速くかつ効率的な復号化を容易にする圧縮形式を提供するが、他の公知の符号化スキームも、情報のリストを圧縮するために、ドキュメント処理システム１０２において使用され得る（たとえば、ＣＣＩＴＴ−Ｇ４、ＬＺＷなど）。

復号化システム
図３Ｂは、トークンスペースレポジトリ内のドキュメントを復号するための復号化システム３０８の実施形態を示すブロック図である。復号化システム３０８は、可変長データデコーダ３１０と、オプションとしてのデルタデコーダ３１２とを含む。いくつかの実施形態においては、符号化されたグループのデータが、可変長データデコーダ３１０によって受信される。可変長データデコーダ３１０は、１つ以上のオフセット／マスクテーブルの利用して、グループを復号する。復号されたデータは、デルタデコーダ３１２によって受信され、デルタデコーダ３１２は、ランニングサム（running sum）を計算し、これにより、元の情報のリストに相当する、デルタ復号されたデータが作成される。グループ符号化された可変長整数値を復号する際にオフセット／マスクテーブルを使用することが、「可変長データを符号化する及び復号するシステム及び方法（Ｓｙｓｔｅｍ ａｎｄ Ｍｅｔｈｏｄ Ｆｏｒ Ｅｎｃｏｄｉｎｇ Ａｎｄ Ｄｅｃｏｄｉｎｇ Ｖａｒｉａｂｌｅ−Ｌｅｎｇｔｈ Ｄａｔａ）」と題された、同時係属中の米国特許出願第１０／９１７,７４５号明細書（２００４年８月１３日出願）に詳しく記載されている。

属性符号化／復号化システム
図３Ｃは、ドキュメント属性を符号化する／復号するための属性符号化／復号化システム３１４の実施形態を示すブロック図である。属性符号化／復号化システム３１４は、符号化／復号化システム３２０を含む。符号化／復号化システム３２０は、属性情報３２２を符号化し、属性テーブル３１６内に格納するための属性レコード３１８を得る。ドキュメントの属性はトークン毎に判断され、０又は１ビット値が、所与のトークンのそれぞれの属性の有無を表すのに使用される。たとえば、属性テーブル内の属性レコード３１８が、Ａ×Ｋビットマップとして概念的に表されることがある。ここで、Ａは符号化された属性の数であり、Ｋはその属性がレコード３１８によって表されたトークンの数である。次いで、Ａが８であり、Ｋが３２である場合、それぞれの属性レコード３１８は、３２のトークンのそれぞれについて８つの属性を格納する。それぞれの属性レコード３１８が、属性テーブルによって占有されるスペースの量を圧縮するように、また、クエリ処理中に、選択された属性レコードを非常に速く復号することが可能となるように、符号化される。属性レコード３１８を符号化する及び復号するための１つの好適な方法が、「可変長データを符号化する及び復号するシステム及び方法（Ｓｙｓｔｅｍ ａｎｄ Ｍｅｔｈｏｄ Ｆｏｒ Ｅｎｃｏｄｉｎｇ Ａｎｄ Ｄｅｃｏｄｉｎｇ Ｖａｒｉａｂｌｅ−Ｌｅｎｇｔｈ Ｄａｔａ）」と題された、同時係属中の米国特許出願第１０／９１７,７４５号明細書（２００４年８月１３日出願）に記載されている。代替形態として、それぞれの属性レコード内の情報は、ランレングス符号化されることがある。

属性テーブル３１６内に記録された１セットの属性は、１つ以上のフォント属性（たとえば、太字、下線付きなど）と、１つ以上のドキュメント位置属性（たとえば、タイトル、ヘッディング）と、メタデータと、１セットのドキュメント内のトークンの間を区別するのに使用され得る他の任意の機能又は特性を含み得る。いくつかの実施形態においては、上述したように、１セットのドキュメント内のトークンの属性は、トークン化されたドキュメントが符号化され、トークンスペースレポジトリ内に格納されるのと同時に、識別され符号化される。符号化された属性は、図５について詳しく記載するように、関連性スコアリングの１つ以上の段階において使用される。

ドキュメントレポジトリの符号化及び復号化システム−第２の実施形態
図８Ａ及び図８Ｂは、トークン化されたドキュメントのコレクション（「トークンスペースレポジトリ」）が、上述した方法とはやや異なる方法で符号化される実施形態を示すブロック図である。上述したように、グローバルレキシコンビルダ２０２が、１セットのドキュメント１０６をトークン化し、すべてのユニークトークンを識別し、グローバルトークン識別子をすべてのユニークトークンに割り当てる。その結果がグローバルレキシコン２０６である。次に、（トークン化された）１セットのドキュメントが、領域レキシコンビルダ８０４によって処理される。概念的には、１セットのドキュメントは、領域８２０に分割され、それぞれの領域８２０がブロック８２２に分割される。領域レキシコンビルダ８０４は、それぞれの領域のための「レキシコン」又はディクショナリ８３０を構築し、符号化システム８１０が、それぞれの領域の１セットの符号化されたトークン８３２、さらに、それぞれの領域の１セットのブロックオフセット８３４を生成する。領域レキシコン８３０、符号化されたトークン８３２、ブロックオフセット８３４（次に、このそれぞれについてより詳細に記載する）が共に、１セットのドキュメントの各領域８２０の符号化された表現（representation）を形成する。

一実施形態においては、１セットのドキュメントは領域８２０に分割され、そのそれぞれ（おそらく最後の領域を除いて）が、８１９２のトークン（又は他の任意の適切なサイズ）などの、所定の固定サイズを有する。領域８２０のそれぞれのブロック８２２も、６４のトークン（又は他の任意の適切なサイズ）などの、予め定義された固定サイズを有する。

一実施形態においては、各領域８２０のための「レキシコン」８３０は、最高の繰り返し速度を有する最長のトークンシーケンスの順序付きリスト（an ordered listing of the longest sequences of tokens having the highest repeat rates）、又は任意の同様の構造である。レキシコン８３０は、領域内の候補トークンストリングのテーブルを構築し、領域内のそれらの繰り返しカウント数を判断し、次いで、最大のレキシコンサイズに到達するまで最良の候補を選択することによって、構築されてもよい。例示的実施形態においては、最大のレキシコンサイズは、６４のトークンであるが、他の実施形態においては、他の任意の適切なサイズ限度が使用されることがある。次に記載するように、レキシコン８３０は、各領域８２０のブロック８２２のそれぞれを符号化するためのコンテキストとして使用され、領域の非常に圧縮された表現を可能とする。いくつかの実施形態においては、領域レキシコン８３０の１つ以上が、たとえば、本文書の上記で言及した、「可変長データを符号化する及び復号するシステム及び方法（Ｓｙｓｔｅｍ ａｎｄ Ｍｅｔｈｏｄ Ｆｏｒ Ｅｎｃｏｄｉｎｇ Ａｎｄ Ｄｅｃｏｄｉｎｇ Ｖａｒｉａｂｌｅ−Ｌｅｎｇｔｈ Ｄａｔａ）」と題された、米国特許出願第１０／９１７,７４５号明細書（２００４年８月１３日出願）に記載されている符号化方法を使用して、圧縮形式に符号化されることがある。

図９Ａ及び図９Ｂについて述べると、一実施形態においては、符号化システム８１０は、以下の通り、トークンのそれぞれのブロック８２２を符号化する。対応する領域のレキシコン８３０は、そのブロックのトークンの直前に先行する、１セットのトークンとして扱われる。そのブロックのトークンは、各トークン及びできる限り多くのその後のトークンと、先行するトークンシーケンス（レキシコン８３０を含む）内の最も長く一致するトークンシーケンスとを突き合わせながら、最初から最後へと順に処理される。一致する先行シーケンスが見つかった場合には、「コピーコード」が生成される。見つからなかった場合には、そのトークンを表すために「リテラルコード」が生成される。次いで、現行コードによってカバーされるすべてのトークンが、そのブロック内の（あれば）次のトークンのその後の処理のための、先行トークンとして扱われる。図９Ｂに示されているように、ブロック内の１セットのトークンを表すそれぞれの「コード」が、タイプフィールド９０２を含むことがある。コードが「リテラルコード」である場合、そのコードの第２の部分９０４は、グローバルトークン識別子を表す。いくつかの実施形態においては、このタイプフィールド９０２は、グローバルトークン識別子を表すのに必要なビット数を示す。たとえば、一実施形態においては、タイプコード９０２は、それぞれが対応するグローバルトークン識別子長を有する、最大７つの互いに異なるリテラルコードを示し得る。他の実施形態においては、互いに異なるタイプコードの数は、８より多い場合もあれば少ない場合もある（たとえば、１つがコピーコードを示し、残りがリテラルコードを示す）。リテラルコードが「コピーコード」である場合、そのコードの第２の部分９０６は、ポインタ９０８と長さ９１０とを含むことがある。ここで、ポインタ９０８は、先行テキスト内のどこで開始すべきかを示し、長さ９１０は、一致するシーケンスの長さ（即ち、復号化中にコピーされるトークンの数）を示す。したがって、場所３１で現在の位置に先行するトークンから開始して、たとえば４つのトークンの一致するシーケンスが、符号化システム８１０によって見つかった場合、このシーケンスのためのコードは、
＜ｔｙｐｅ＝ｃｏｐｙ，ｐｔｒ＝３１，ｌｅｎｇｔｈ＝４＞
となる。

（ビットで測定される）コピーコードの長さは、領域レキシコン８３０の最大トークン長及びブロックの最大トークン長と、一致するシーケンスの最大許容長と、互いに異なるコードの数とに依存する。一例においては、タイプフィールド９０２は３ビット（８タイプコードが可能となる）であり、ポインタフィールド９０８は７ビット、長さフィールド９１０は２ビットであり、全部で１２ビットである。他の実施形態においては、コピーコードのそれぞれのフィールドの他のビット長が使用されることがある。（ビットで測定される）それぞれのリテラルコードの長さは、リテラルコードのタイプによって指定される。

再び図８Ｂについて述べると、符号化システム８１０は、領域のブロックを符号化する時に、１セットのブロックオフセット８３４を生成する。ブロックオフセット８３４は、領域のそれぞれのブロックの符号化されたトークンの場所を示す。一実施形態においては、領域の第１のブロックのブロックオフセットは、トークンレポジトリに対するポインタであり、領域のための他のブロックオフセットのそれぞれは、領域内の第１のブロックの開始位置に対する相対オフセットである。一実施形態においては、領域レキシコン８３０及びブロックオフセット８３４は、固定領域サイズによって分割された領域８２０の開始位置に従って索引が付けられた、テーブル又はこれに相当するデータ構造内に格納される。別の観点からは、それぞれの領域８２０に領域番号が割り当てられ、かかる領域番号は、固定領域サイズによって分割された場合の領域の開始位置を含む。領域レキシコン８３０及びブロックオフセット８３４が格納されているデータ構造には、領域番号によって索引が付けられる。

領域８２０のブロック８２２を復号することが、これに対応する領域の領域レキシコン８３０の位置を突き止めることと、領域のためのブロックオフセット８３４を使用して、符号化されたブロックの位置を突き止めることと、次いで、グローバルトークン識別子のシーケンスを作成するために、そのブロックの１セットのコードを復号することとによって、達成される。次いで、この結果生じたグローバルトークン識別子のシーケンス又はその任意のサブセットは、グローバルレキシコン２０６を使用して、対応する１セットの記号又は用語に転換することができる。

クエリ処理システム
図４は、トークンスペースレポジトリと共に使用されるクエリ処理システム１０４の第１段階の実施形態を示すブロック図である。クエリ処理システム１０４は、グローバルレキシコン４０２と、トークンスペース逆インデックス４０８と、第１段階ルックアップテーブル４０６と、第２段階ルックアップテーブル４１０とを含む。クエリ用語又はストリングが、グローバルレキシコン４０２によって受信され、グローバルレキシコン４０２は、グローバルレキシコン４０２のエントリから構築された翻訳テーブル又はマッピングを使用して、クエリ用語をＧＴｏｋｅｎＩＤに翻訳する。ＧＴｏｋｅｎＩＤは、逆インデックス４０８によって受信される。逆インデックス４０８は、ＧＴｏｋｅｎＩＤを逆インデックス４０８内に格納されているインデックスレコード４１２にマッピングするためのマップ４０４を含む。マップ４０４を使用して識別されるそれぞれのインデックスレコード４１２は、トークンスペースレポジトリ１１２内のトークン位置に直接対応する、トークン位置のリストを含む。いくつかの実施形態においては、逆インデックス４０８は、グローバルレキシコンが生成された後に生成され、ミニレキシコンを生成するのに使用されるのドキュメントを介して同じパス中に（during the same pass through the documents that is used to generate the mini-lexicons）生成されることがある。

いくつかの実施形態においては、逆インデックス４０８は、第１段階ルックアップテーブル４０６に、インデックスとして使用され得る位置のリストを提供する。クエリが多くの用語を含む場合には、多くの位置のリストが、逆インデックス４０８によって作成される。位置のリスト内のそれぞれの位置に対応するエントリのためにＤｏｃＩＤマップ４１０全体をサーチしなければならないことを回避するために、第１段階ルックアップテーブル４０６は、トークンスペースレポジトリ内のそれぞれの位置のブロックに対する（for each block of positions in the tokenspace repository）、１つのエントリを有する。たとえば、それぞれのブロックが、３２,７６８位置のサイズを有し、それぞれのエントリが、対応する位置のブロックに対して、ＤｏｃＩＤルックアップテーブル４１０内の第１のエントリに対するポインタを有することがある。したがって、第１段階ルックアップテーブル４０６は、位置のリストを、第２段階ルックアップテーブル４１０（これは、時にＤｏｃＩＤテーブル４１０と呼ばれる）内のドキュメント識別子（ＤｏｃＩＤ）エントリ４１２の始点位置に翻訳する。代替形態として、テーブル４０６及び４１０は、合わせて、ＤｏｃＩＤルックアップテーブルと呼ばれることがある。第２段階ルックアップテーブル４１０内のそれぞれのエントリ４１２は、ＤｏｃＩＤ（ドキュメント識別子）と、対応するドキュメントのための開始レポジトリ位置とを含む。任意のドキュメント内の最後のトークンは、第２段階ルックアップテーブル内の次のエントリ４１２によって識別される開始位置の直前の位置である。ＤｏｃＩＤのための始点位置Ｓｔａｒｔ＿Ｐｏｓ_Ａ−Ｚは、第２のルックアップテーブル４１０によって受信される。第２のルックアップテーブル４１０は、始点位置をクエリ用語のそれぞれのためのＤｏｃＩＤのリストに翻訳する。

いくつかの実施形態においては、第１段階クエリプロセッサは、結果セットを作成するためのロジック４１６を含む。ＤｏｃＩＤのリストは、ＤｏｃＩＤの結果セットを形成するために、クエリ又はクエリツリーによって指定されたブーリアン論理に従って、ロジック４１６によって併合される。ロジック４１６はまた、任意に、結果セット内のＤｏｃＩＤに対応するドキュメント内に置かれていないトークン位置を消去するために、トークン位置のリストにフィルタをかけることがある。さらに、スコア（時に、クエリスコアと呼ばれる）を結果セット内のそれぞれのＤｏｃＩＤに関連付けるために、ＤｏｃＩＤ及びＤｏｃＩＤによって識別されたそれぞれのドキュメント内のトークン位置を使用して、スコアリング関数が結果セットに適用されることがある。

多段クエリ処理
図５は、トークンスペースレポジトリ５２４と共に使用される多段クエリ処理システム５００の実施形態を示すブロック図である。いくつかの実施形態においては、クエリ処理システム５００は、第１段階クエリプロセッサ５１０と、第２段階クエリプロセッサ５１４と、第３段階クエリプロセッサ５１８と、第４段階クエリプロセッサ５２０とを含む、クエリ処理及び関連性スコアを生成する４つの段階を含む。アプリケーションによって、より多くの又はより少ないクエリプロセッサ段階がシステム５００において使用され得ることに留意されたい。それぞれの段階において、アプリケーションによって、ユーザに戻され得る及び／又は以前の段階で生成された関連性スコアと組み合わせられ得る、１セット以上の関連性スコアが計算される。

クエリ処理−段階Ｉ
第１段階クエリプロセッサ５１０については、図４において一般に記載した。クエリストリング５０２は、トークン化され、クエリパーサ５０４により構文解析され、クエリ用語が得られる（即ち、クエリ内のそれぞれの互いに異なる用語がトークンとして扱われる）。トークン化されたクエリ用語は、図２及び図４について上述したように、グローバルレキシコン５０８により、翻訳テーブル又はマッピングを使用して、対応するＧＴｏｋｅｎＩＤに翻訳される。ユーザは、ブーリアン、隣接演算子、又は近接演算子を含む、クエリストリング内の特別な演算子を用いることがあるので、システム５００は、クエリを構文解析して、クエリ用語及び演算子を得る。これらの演算子は、予約区切り（たとえば、引用符）、又は特別な形式（たとえば、ＡＮＤ、ＯＲ）の予約用語の形態で発生することがある。自然言語処理（ＮＬＰ）システムの場合には、演算子は、たとえどのように表現されていても（たとえば、前置詞、接続詞、順序付けなど）、使用される言語において非明示的に認識され得る。ストップワード（たとえば、「ａ」、「ｔｈｅ」など）を削除する及び用語の余分なものを切り捨てる（即ち、ワードの接尾語を取り除く）などの、他のクエリ処理も、第１段階クエリプロセッサ５１０内に含まれることがある。

次に、ＧＴｏｋｅｎＩＤのリストは、クエリエキスパンダ５０６によって処理される。クエリエキスパンダ５０６は、クエリストリング内で使用される任意の演算子（たとえば、ブーリアン式）を考慮するクエリツリー又は他のクエリ表示を生成する。任意に、クエリエキスパンダ５０６はまた、様々な方法でクエリを拡張することがある。たとえば、クエリ用語が、その用語及び１つ以上の同義語又はそのクエリ用語に関係する他の用語を含むサブツリーに転換されることがあり、サブツリー内の用語は、ＯＲ演算子又は親ノードにより互いに関係する。

以下により詳細に記載するが、いくつかの実施形態においては、クエリが、図５に示されているクエリ処理段階のシーケンスにより、一回以上処理される。（最後以外の）それぞれのパスで、追加のクエリ拡張用語が生成され（以下に説明する）、次いで、これらの追加用語がクエリツリーに追加される。クエリツリーはまた、スコアリングツリーとしても使用され、重みがクエリツリー内の用語に関連付けられる。拡張されたクエリツリーはまた、補足用語と用語のサブツリーとを含み得る。これらは、クエリに対応するドキュメント内に存在する必要はないが、クエリに対応するドキュメントの関連性をスコアリングする際に使用される。１つ以上のクエリ用語がある場合、サーチ結果を向上させるために、第１のパス中にクエリ用語のための重みが計算されることがある。

いくつかの実施形態においては、システム５００を通る第１のパスで、ドキュメントコーパスからのドキュメントのランダムサンプルを処理する。ランダムサンプルのサイズは、１つ以上のより小さいランダムサンプルに基づいて選択され得る。かかる、より小さいランダムサンプルは、ドキュメントコーパス全体にわたってクエリにマッチするいくつかのドキュメントを予想するために、システム５００によって使用され得る。他の実施形態においては、第１のドキュメントコーパス（たとえば、１セットのクエリセッション）が、システム５００を通る第１のパスにおいて使用され、第２の異なるコーパスが、システム５００を通る第２の又はその後のパスにおいて使用される。以前のセットのクエリセッションを使用することにより、システム５００が、同様のクエリで一般に同時に用いられる（commonly co-occur in similar queries）他の関連用語を判断することが可能となる。これらの関連用語は、その後のパスのためにクエリを拡張するよう、クエリエキスパンダ５０６によって使用され得る。

第１段階クエリプロセッサ５１０は、クエリ用語を使用して、トークンスペース逆引きインデックス５１２をサーチし、クエリに一致するドキュメントを識別する。第１段階クエリプロセッサ５１０は、クエリツリー内の用語のトークン位置（トークンスペースレポジトリ位置とも呼ばれる）のリストを作成するために、逆インデックス５１２にアクセスし、そのトークン位置に対応するドキュメントのＤｏｃＩＤのセットを作成するために、ＤｏｃＩＤマップ５１６にアクセスする。更に、第１段階プロセッサ５１０は、クエリに応答するＤｏｃＩＤのセットを生成するために、クエリ又はクエリツリーによって指定されたブーリアン論理を遂行する。いくつかの実施形態においては、第１段階クエリプロセッサ５１０はまた、１つ以上のスコアリングアルゴリズムに基づいて、クエリとそれぞれのドキュメントとの間の第１のセットの関連性スコアＳ_１を計算する。一般に、スコアリングアルゴリズムは、１つ以上のクエリ特徴に基づいて一致するドキュメントの関連性ランキングを提供する。クエリ特徴は、クエリ用語の有無、用語頻度、ブーリアン論理の充足性、クエリ用語の重み、ドキュメントの普及度（popularity）（たとえば、ドキュメントの重要度又は普及度又は相関度という、クエリとは無関係なスコア）、クエリ用語間の近接度、コンテキスト、属性などを含むが、これらに限定されるものではない。一実施形態においては、第１のセットの関連性スコアＳ_１は、クエリ用語の存在、用語頻度、及びドキュメントの普及度を含む、１セットの因子に基づく。

いくつかの実施形態においては、第１のセットの関連性スコアＳ_１は、順序付きリストとしてユーザに提示するためのドキュメントを選択するのに使用され得る。次いで、ユーザは、選択されたドキュメントに対する内部ポインタ（internal pointers）を単にクリックして、たどることができる。他の実施形態においては、第１のセットの関連性スコアＳ_１は、ＤｏｃＩＤ及びこれに対応する位置と共に、さらなる処理のために第２段階クエリプロセッサ５１４に提供される。

クエリ処理−段階ＩＩ
第２段階クエリプロセッサ５１４は、第１段階クエリプロセッサ５１０から、１セットのＤｏｃＩＤ、これに対応するドキュメントのトークンスペースレポジトリ位置のリスト、及び、第１のセットの関連性スコアＳ_１を受信する。第２段階クエリプロセッサ５１４は、その位置のリストを使用して、ドキュメント内で見つかったクエリ用語の近接度又は相対位置に基づく第２のセットの関連性スコアＳ_２を生成する。ドキュメント内でクエリ内の用語が互いの近くで発生した場合には、用語がより大きい距離を隔てて発生した場合に比べて、そのドキュメントがそのクエリに関連している可能性が高い。したがって、第２のセットの関連性スコアＳ_２は、クエリ用語が互いに隣接して又は密接して発生した場合、用語が距離を隔てて発生するドキュメントと比較して、ドキュメントをより高くランク付けするのに使用される。いくつかの実施形態においては、第２のセットの関連性スコアＳ_２は、ユーザに順序付きリストとして提示するための、トップＸ個のドキュメントを選択するのに使用され得る。次いで、ユーザは、選択されたドキュメントに対する内部ポインタを単にクリックして、たどることができる。いくつかの実施形態においては、第２のセットの関連性スコアＳ_２は、ユーザに提示するために及び／又は第３段階クエリプロセッサ５１８によってさらに処理するために、（第２のセットの関連性スコアＳ_２に従って順序付けられた）ドキュメントの順序付きリストを生成すべく、（たとえば、第２段階クエリプロセッサ５１４によって使用される追加のスコアリング因子に従ってスコアＳ_１を調整することにより）第１のセットの関連性スコアＳ_１から一部導き出される。

クエリ処理−段階ＩＩＩ
いくつかの実施形態においては、図３Ｃについて上述したように、第２段階クエリプロセッサ５１４は、属性テーブル５２２内で符号化されている用語属性（たとえば、フォント属性、タイトル、ヘッディング、メタデータなど）を取り扱うために、第３段階クエリプロセッサ５１８に結合される。第３段階クエリプロセッサ５１８は、第２段階クエリプロセッサ５１４から、１セットのＤｏｃＩＤ、これに対応するドキュメントのためのトークンスペースレポジトリ位置のリスト、及び、第２のセットの関連性スコアＳ_２を受信する。代替形態として、第３段階クエリプロセッサは、第１のセットの関連性スコアＳ_１及び第２のセットの関連性スコアＳ_２を受信する。

いくつかの研究においては、ドキュメント内の用語の場所がそのドキュメントの重要性を示すことが示されている。たとえば、クエリ用語に一致するドキュメントのタイトルに発生する用語が、そのドキュメントの本体に発生するクエリ用語より重く重み付けされることがある。同様に、ドキュメントのヘッディングセクション又は第１のパラグラフに発生するクエリ用語は、そのドキュメント内のより目立たない位置に発生する用語より、クエリに対するそのドキュメントの関連性をより示している可能性がある。関連性の指標として使用される他の属性には、太字のテキスト、下線付きテキスト、及びフォントサイズが含まれる。したがって、第３のセットのスコアＳ_３は、クエリ用語に一致するドキュメント内のトークンの属性を使用して判断される。図３Ｃを参照すると、ドキュメント内のクエリ用語の属性（即ち、クエリ用語に一致する又は関連するトークンの属性）にアクセスするために、ドキュメント内のクエリ用語のトークン位置が、属性テーブル３１６（図５の５２２）に索引を付けるのに使用される。より具体的には、その属性が各属性レコード３１８によって符号化されるトークンの数がＫである場合、Ｋによって分割されるトークン位置は、属性テーブル３１６に索引を付けるのに使用される。いくつかの実施形態においては、識別された属性レコード３１８は、符号化され圧縮された形態で格納されており、したがって、各クエリ用語に関連付けられた属性を判断するために復号されなければならない。

いくつかの実施形態においては、第３のセットの関連性スコアＳ_３が、ユーザに順序付きリストとして提示するためのトップＹ個のドキュメントを選択するのに使用され得る。次いで、ユーザは、選択されたドキュメントに対する内部ポインタをクリックして、たどることができる。いくつかの実施形態においては、第３のセットの関連性スコアＳ_３は、ユーザに提示するためのドキュメントの順序付きリストを生成するために、及び／又は第４段階クエリプロセッサ５２０によってさらに処理するために、第１及び第２のセットの関連性スコアＳ_１及びＳ_２の１つ以上から一部導き出される。一実施形態においては、スコアＳ_３は、第３段階クエリプロセッサ５１８によって作成された追加のスコアリング因子に従って、Ｓ_２スコアを調整することによって作成される。

クエリ処理−段階ＩＶ
第４段階クエリプロセッサ５２０は、第３段階クエリプロセッサ５１８から、１セットのＤｏｃＩＤ、そのＤｏｃＩＤに対応するドキュメント内の位置のリスト、及び、第３のセットの関連性スコアＳ_３を受信する。第４段階クエリプロセッサ５２０は、任意に、第１の及び／又は第２のセットの関連性スコアＳ_１及びＳ_２も受信することがある。第４段階クエリプロセッサ５２０は復号化システム５２７に結合され、この復号化システム５２７は、１つ以上のミニレキシコンマップ５２３、トークンスペースレポジトリ５２４、及び１つ以上のグローバルレキシコンマップ５０８に結合される。ミニレキシコンマップ５２３、トークンスペースレポジトリ５２４、及びグローバルレキシコンマップ５０８についてはすべて、図１及び図２において上述した。

第４段階クエリプロセッサ５２０は、コンテキストに基づいて第４のセットの関連性スコアＳ_４を生成し、また、結果セット内に列挙されたドキュメントの１つ以上のための「スニペット」を生成することがある。スニペットとは、ドキュメントからのテキストの小さい部分であり、通常、サーチされているキーワードの周囲に現れるテキストを含む。一実施形態においては、結果セット内に列挙されたドキュメントのためのスニペットを生成するために、クエリプロセッサは、ドキュメント内に存在するそれぞれのクエリ用語の最初の発生箇所（first occurrence）の前後に位置する予め定義された数のトークンを復号し、これにより、ドキュメントの１つ以上のテキスト部分が再構築され、次いで、スニペットに含むための１サブセットのテキスト部分が選択される。結果セット内の位置のリストを使用して、復号化システム５２７は、ドキュメント内のクエリ用語の発生箇所に先行し、又は後行するドキュメントの一部分を復号することが必要なミニレキシコン５２３を選択し得る。図２について上述したように、選択されたミニレキシコン５２３及びグローバルレキシコン５０８は、トークンスペースレポジトリ内のＬＴｏｋｅｎＩＤをＧＴｏｋｅｎＩＤに翻訳し、次いで、そのＧＴｏｋｅｎＩＤをトークンに翻訳するのに使用される。

いくつかの実施形態においては、第４のセットの関連性スコアＳ_４が、ユーザに順序付きリストとして提示するためのトップＺ個のドキュメントを選択するのに使用され得る。次いで、ユーザは、選択されたドキュメントに対する内部ポインタをクリックして、たどることができる。いくつかの実施形態においては、第４のセットの関連性スコアＳ_４は、ユーザに提示するためのドキュメントの順序付きリストを生成するために、及び／又は関連性フィードバックモジュール５１７によるさらなる処理のために、第１、第２、及び第３のセットの関連性スコアＳ_１、Ｓ_２及びＳ_３の１つ以上から一部導き出される。代替実施形態においては、最後の段階クエリプロセッサは、先行するクエリプロセッサ段階で作成された関連性スコアにおいて最高のスコアを有するドキュメントのためのスニペットを生成するが、新しいセットの関連性スコアＳ_４を生成しない。

いくつかの実施形態においては、最終セットの関連性スコアが、関連性フィードバックモジュール５１７に提供され、関連性フィードバックモジュール５１７は、最後のクエリ段階で作成された結果セット内のドキュメントに基づいて１つ以上の新しいクエリ拡張用語を生成する。たとえば、関連性フィードバックモジュール５１７は、１つ以上の公知の関連性フィードバックアルゴリズムを実施し得る。これは、フルドキュメントアプローチに基づく擬似関連性フィードバックアルゴリズム（全ウェブページに基づく擬似関連性フィードバック）、ドキュメントオブジェクトモデル（ＤＯＭ）セグメンテーション、ビジョンベースページセグメンテーション（ＶＩＰＳ）、概念ラティスを使用する概念関連性フィードバック（conceptual relevance feedback using concept lattices）などを含むが、これらに限定されるものではない。関連性フィードバックアルゴリズムは、先のクエリ処理段階から検査された（vetted）ドキュメントを分析し、その分析結果に基づいてクエリ拡張用語を生成し得る。新しいクエリ拡張用語は、クエリエキスパンダ５０６に提供され、クエリエキスパンダ５０６は、クエリプロセッサ５１０、５１４、５１８、及び５２０の１つ以上によって処理される新しいクエリ表現を生成する。したがって、多段クエリ処理システム５００は、クエリで２つ以上のパスを実行し、それぞれのパスからの情報を使用して、改良されたクエリを生成することが可能であり、この結果、最終的に、ユーザはより関連するドキュメントを受信する。

一実施形態においては、最後のクエリ段階プロセッサ５２０は、クエリの第１のパス処理を遂行する場合に、長いスニペットを作成する。スニペットは、たとえばドキュメント内のクエリ用語のそれぞれの発生箇所に先行する、又は後行するＮ（たとえば、１０〜４０）トークンを含む。スニペットは、予め定義された長さを超えた場合、切り捨てが行われることがある。クエリ及び最後のクエリ段階５２０によって作成された長いスニペットは、１セットのクエリ拡張用語、及び任意に１セットのクエリ用語の重みを生成するために、関連性スコアと共に、関連性フィードバックモジュール５１７に提供される。拡張されたクエリの第２のパス処理中に、最後のクエリ段階５２０は、長さが好適であり、最高の又は最良のスコアを有する結果セットのドキュメントのリストとともに表示するのに適した、短いスニペットを作成する。

一実施形態においては、クエリ処理システムは、Ｌ個のパラレルクエリ処理サブシステムを含み、そのそれぞれが、ドキュメントコレクションの各サブセットのための、逆インデックス５１２とトークンスペースレポジトリ５２４とを含む。たとえば、クエリ処理システムは、１０００を超えるパラレルクエリ処理サブシステムを含むことがある。関連性フィードバックモジュール５１７（図５）は、すべてのクエリ処理サブシステムによって共用されることがある。クエリ処理システムを通る第１のパス中に、クエリはパラレルクエリ処理サブシステムの小さい部分によって処理され、第２のパス中に、クエリはクエリ処理システム全体によって処理される。たとえば、クエリ処理システムは、Ｓサブセット（たとえば、３２サブセット）に分割され、それぞれのクエリが、ハッシュ関数を正規化したバージョンのクエリに適用した結果に従って、サブセットの１つに割り当てられ、次いで、モジュロ関数をハッシュ関数によって作成された結果に適用する。クエリ処理システムの各サブセットは、クエリ処理システムの「パーティション」と呼ばれることがあり、各クエリ処理サブシステムは、「サブパーティション」と呼ばれることがある。

クエリの第１のパス処理の主要目的は、クエリの第２のパス処理によって作成されるクエリ結果の品質を向上させるために、１セットのクエリ拡張用語、及びクエリ用語の重みを作成することである。クエリ処理システム内のドキュメントがクエリ処理サブシステム全体にかなりランダムに分散されている限り、クエリは、１セットのクエリ拡張用語を作成するために、ほんの少数のサブシステムによって処理されるだけで良い。クエリ拡張用語は、拡張クエリツリー又はクエリ表現を作成するために、クエリエキスパンダ５０６によって使用され、次いで、上述したように、（クエリの第２のパス処理における）クエリ処理段階で処理される。たとえば、クエリ「new york pictures」は、「new york（pictures or images or image or picture）」に拡張されることがある。第２のパス中の最後のクエリ段階で作成された結果セット及びスニペットは、（クエリがそこから受信された）コンピュータ又はデバイスによって表示するために（又は、より一般に提示するために）フォーマット化されることがある。

一実施形態においては、クエリの第１のパス処理は、その後のパスとは異なるデータベースで遂行される。たとえば、第１のパスのための初期データベースは、以前に処理されたクエリのデータベースであり、その後のパスのために使用されるデータベースは、クエリ用語をデータベース内のドキュメントにマッピングするための逆インデックスを有する１セットのドキュメントであり得る。

ドキュメント処理サーバ
図６は、トークンスペースレポジトリサーバ６００の実施形態を示すブロック図である。サーバ６００は、スタンドアロンコンピュータシステム、又は多くのコンピュータシステムを含む分散型処理システムの一部であり得る。サーバ６００は、一般に、１つ以上の演算処理装置（ＣＰＵ）６０４と、１つ以上のネットワーク又は他の通信インターフェース６０８と、メモリ６０２と、これらの構成要素と相互接続するための１つ以上の通信バス６０６とを含む。サーバ６００は、任意に、ユーザインターフェース、たとえばディスプレイ及びキーボードを含むことがある。メモリ６０２は、高速ランダムアクセスメモリを含み、また、１つ以上の磁気ディスク記憶装置などの不揮発性メモリを含むことがある。メモリ６０２は、中央演算処理装置６０４から遠隔に置かれている大容量記憶装置を含むことがある。

メモリ６０２は、オペレーティングシステム６１０（たとえば、リナックス又はユニックス）、ネットワーク通信モジュール６１２、レキシコンジェネレータ６１４（たとえば、レキシコンジェネレータ１０８）、符号化システム６１６（たとえば、符号化システム３００）、１つ以上のグローバルレキシコン６１８（たとえば、グローバルレキシコン２０６）、１つ以上のミニレキシコン６２０（たとえば、ミニレキシコン２０８）、トークンスペースレポジトリ６２２（たとえば、トークンスペースレポジトリ１１２）、属性レコード６２４（たとえば、属性レコードテーブル３１６）、及び

有効範囲マップ６２６（たとえば、有効範囲マップ２１０）を格納する。これらの構成要素のそれぞれのオペレーションについては、図１〜図５において上述した。

クエリ処理サーバ
図７は、クエリ処理サーバ７００の実施形態を示すブロック図である。サーバ７００は、スタンドアロンコンピュータシステム、又は多くのコンピュータシステムを含む分散型処理システムの一部であり得る。サーバ７００は、一般に、１つ以上の演算処理装置（ＣＰＵ）７０４と、１つ以上のネットワーク又は他の通信インターフェース７０８と、メモリ７０２と、これらの構成要素と相互接続するための１つ以上の通信バス７０６とを含む。サーバ７００は、任意に、ユーザインターフェース、たとえばディスプレイ及びキーボードを含むことがある。メモリ７０２は、高速ランダムアクセスメモリを含み、また、１つ以上の磁気ディスク記憶装置などの不揮発性メモリを含むことがある。メモリ７０２は、中央演算処理装置７０４から遠隔に置かれている大容量記憶装置を含むことがある。

メモリ７０２は、オペレーティングシステム７１０（たとえば、リナックス又はユニックス）、ネットワーク通信モジュール７１２、トークンスペース逆インデックス７１４（たとえば、トークンスペース逆インデックス４０８）、復号化システム７１６（たとえば、復号化システム３０８）、１つ以上のレキシコン翻訳テーブル又はマッピング７１８（たとえば、グローバルレキシコン２０６及びミニレキシコン２０８から導き出された）、有効範囲マップ７２０（たとえば、有効範囲マップ２１０）、ＤｏｃＩＤマップ７２２（たとえば、ＤｏｃＩＤマップ４１０）、クエリパーサ７２４（たとえば、クエリパーサ５０４）、クエリツリー７２６、１つ以上のクエリプロセッサ７２８（たとえば、クエリプロセッサ５１０、５１４、５１８、及び５２０）、属性レコード７３０（たとえば、属性レコードテーブル３１６）、及びトークンスペースレポジトリ７３２（たとえば、トークンスペースレポジトリ１１２）を格納する。これらの構成要素のそれぞれのオペレーションについては、図１〜図５において上述した。

上記の説明は、例示目的であり、特有の実施形態を参照しながら記載してきた。しかし、例を用いた上記の説明は、網羅的なものではなく、また本発明を開示されている形態だけに制限するものでもない。上記の教示を考慮すれば、多くの変更形態及び変形形態が可能となる。本発明の原理及びその実際的な適用形態を最もうまく説明するために、いろいろな実施形態が選ばれ、記載されている。したがって、当業者には、本発明及び様々な実施形態を、考えられる特定の使用に適した様々な変更形態と共に最良の方法で利用することが可能である。

情報検索システムの実施形態を示すブロック図である。 図１のレキシコンジェネレータの実施形態を示す概念ブロック図である。 トークンスペースレポジトリ用のドキュメントを符号化するための符号化システムの実施形態を示すブロック図である。 トークンスペースレポジトリのドキュメントを復号するための復号化システムの実施形態を示すブロック図である。 ドキュメント属性を符号化する／復号するための属性符号化／復号化システムの実施形態を示すブロック図である。 トークンスペースレポジトリと共に使用されるクエリ処理システムの実施形態を示すブロック図である。 トークンスペースレポジトリと共に使用される多段クエリ処理システムの実施形態を示すブロック図である。 トークンスペースレポジトリサーバの実施形態を示すブロック図である。 クエリ処理サーバの実施形態を示すブロック図である。 トークン化されたドキュメントレポジトリの第２の実施形態を示すブロック図である。 図１のレキシコンジェネレータの第２の実施形態を示す概念ブロック図である。 レキシコンジェネレータの実施形態において使用される符号化プロセスを示す概念図である。 符号化されたトークンを表すための例示的データ構造を示す図である。

Claims (21)

1. 多段クエリ処理システムにおいてクエリを処理する方法であって、
   前記多段クエリ処理システムは、１つ以上のプロセッサと、前記方法を実行するために前記１つ以上のプロセッサによって実行される１つ以上のプログラムを格納するメモリとを有し、
   前記１つ以上のプロセッサによって実行される第１のクエリ処理ステップであって、
   前記１つ以上のプロセッサが、１つ以上のクエリ用語に応答してインデックスから第１のセットのドキュメント識別子を検索するステップと、
   前記１つ以上のプロセッサが、クエリ用語の存在、用語頻度、ドキュメントの普及度のうち１つ以上に基づいて、前記第１のセットのドキュメント識別子の少なくとも１サブセットに対応する第１のセットの圧縮ドキュメントのために第１のセットの関連性スコアを生成し、前記第１のセットの関連性スコアを前記メモリに格納するステップと、を含む第１のクエリ処理ステップと、
   前記１つ以上のプロセッサによって実行される第２のクエリ処理ステップであって、
   前記１つ以上のプロセッサが、トークン位置のリスト、ドキュメントにおけるクエリ用語間の距離、ドキュメントにおけるトークンの属性、前記第１のセットの圧縮ドキュメントの１ドキュメントにおいて使用されるクエリ用語の周囲に現れるテキストのうち１つ以上に基づいて、前記第１のセットの圧縮ドキュメントのために第２のセットの関連性スコアを生成し、前記第２のセットの関連性スコアを前記メモリに格納するステップを含む第２のクエリ処理ステップと、
   前記１つ以上のプロセッサが、前記メモリから前記第１及び第２のセットの関連性スコアを読み出し、前記第１及び第２のセットの関連性スコアに基づいて更に処理するためにドキュメントの順序付きリストを生成するステップと、
   前記１つ以上のプロセッサが、前記順序付きリストのドキュメントから、追加のクエリ用語を自動的に生成するステップと、
   前記１つ以上のプロセッサが、前記追加のクエリ用語を使用して、新しいクエリを作成するステップと、
   前記１つ以上のプロセッサが、前記インデックスから第２のセットのドキュメント識別子を検索するために、かつ、前記追加のクエリ用語に少なくとも一部基づく第３のセットの関連性スコアを生成するために、前記新しいクエリを処理するステップと、
   前記１つ以上のプロセッサが、前記第３のセットの関連性スコアを用いて、ユーザに提示するための１セットの上位のドキュメントを選択するステップと、
   を含む方法。
2. 前記第２のセットの関連性スコアは、ドキュメントにおけるトークンの属性に少なくとも基づいており、前記属性は、ドキュメントにおけるトークンのフォント属性を含んでいる、請求項１記載の方法。
3. 前記第１のセットのドキュメント識別子は、１セットの圧縮ドキュメントを格納するトークンスペースレポジトリにおける、クエリ用語に対応するトークンの場所に対応している、請求項１記載の方法。
4. 前記第１のセットのドキュメント識別子を検索するステップは、前記インデックスを用いて前記１以上のクエリ用語のトークン位置のリストを生成し、前記トークン位置に対応する１セットのドキュメント識別子を作成するためのマップにアクセスするステップを含む、請求項１記載の方法。
5. 前記１つ以上のプロセッサが、第２のセットのトークンを回復するために、前記１セットの圧縮ドキュメントの少なくとも一部分を復元するステップであって、前記第２のセットの回復されたトークンが、前記第２のセットのドキュメント識別子に対応する前記１セットの圧縮ドキュメントの位置に関連付けられる、ステップと、
   前記１つ以上のプロセッサが、前記第２のセットの回復されたトークンを使用して、前記１セットの圧縮ドキュメントの１つ以上の部分を再構築するステップとをさらに含む請求項１乃至４のいずれか１項に記載の方法。
6. 前記１つ以上のプロセッサが、前記順序付きリストの上位のドキュメントのセットにおいて、前記再構築された部分をユーザに提示するステップをさらに含む請求項５に記載の方法。
7. 前記第３のセットの関連性スコアが、前記第２のセットのドキュメント識別子に対応する前記１セットの圧縮ドキュメント内の前記クエリ用語の１つ以上の位置に基づく請求項１乃至４のいずれか１項に記載の方法。
8. １つ以上のプロセッサと、少なくとも１つの前記プロセッサによって実行される１つ以上のプログラムを格納するメモリと、を有する多段クエリ処理システムであって、
   前記１つ以上のプログラムは、
   第１のクエリ処理段階のための命令であって、
   １つ以上のクエリ用語に応答してインデックスから第１のセットのドキュメント識別子を検索するための命令と、
   クエリ用語の存在、用語頻度、ドキュメントの普及度のうち１つ以上に基づいて、前記第１のセットのドキュメント識別子の少なくとも１サブセットに対応する第１のセットの圧縮ドキュメントのために第１のセットの関連性スコアを生成し、前記第１のセットの関連性スコアを前記メモリに格納するための命令とを含む、第１のクエリ処理段階を実行するための命令と、
   第２のクエリ処理段階のための命令であって、
   トークン位置のリスト、ドキュメントにおけるクエリ用語間の距離、ドキュメントにおけるトークンの属性、前記第１のセットの圧縮ドキュメントの１ドキュメントにおいて使用されるクエリ用語の周囲に現れるテキストのうち１つ以上に基づいて、前記第１のセットの圧縮ドキュメントのために第２のセットの関連性スコアを生成し、前記第２のセットの関連性スコアを前記メモリに格納するための命令を含む、第２のクエリ処理段階を実行するための命令と、
   前記メモリから前記第１及び第２のセットの関連性スコアを読み出し、前記第１及び第２のセットの関連性スコアに基づいて更に処理するためにドキュメントの順序付きリストを生成するための命令と、
   前記順序付きリストのドキュメントから、追加のクエリ用語を自動的に生成するための命令と、
   前記追加のクエリ用語を使用して、新しいクエリを作成するための命令と、
   前記インデックスから第２のセットのドキュメント識別子を検索するために、かつ、前記追加のクエリ用語に少なくとも一部基づいて第３のセットの関連性スコアを生成するために、前記新しいクエリを処理するための命令と、
   前記第３のセットの関連性スコアを用いて、ユーザに提示するための１セットの上位のドキュメントを選択するための命令と、を含む、多段クエリ処理システム。
9. 前記第２のセットの関連性スコアは、ドキュメントにおけるトークンの属性に少なくとも基づいており、前記属性は、ドキュメントにおけるトークンのフォント属性を含んでいる、請求項８記載のシステム。
10. 前記第１のセットのドキュメント識別子は、１セットの圧縮ドキュメントを格納するトークンスペースレポジトリにおける、クエリ用語に対応するトークンの場所に対応している、請求項８記載のシステム。
11. 前記第１のセットのドキュメント識別子を検索するための命令は、前記インデックスを用いて前記１以上のクエリ用語のトークン位置のリストを生成し、前記トークン位置に対応する１セットのドキュメント識別子を作成するためのマップにアクセスする命令を含む、請求項８記載のシステム。
12. 前記１つ以上のプログラムは、
    第２のセットのトークンを回復するために、前記１セットの圧縮ドキュメントの少なくとも一部分を復元する命令であって、前記第２のセットの回復されたトークンが、前記第２のセットのドキュメント識別子に対応する前記１セットの圧縮ドキュメント内の位置に関連付けられる、命令と、
    前記第２のセットの回復されたトークンを使用して、前記１セットの圧縮ドキュメントの１つ以上の部分を再構築する命令とをさらに含む請求項８乃至１１にいずれか１項に記載のシステム。
13. 前記１つ以上のプログラムは、
    前記順序付きリストの上位のドキュメントのセットにおいて、前記再構築された部分をユーザに提示する手段をさらに含む請求項１２に記載のシステム。
14. 前記第３のセットの関連性スコアが、前記第２のセットのドキュメント識別子に対応する前記１セットの圧縮ドキュメント内の前記クエリ用語の１つ以上の位置に基づく請求項８乃至１１にいずれか１項に記載のシステム。
15. １つ以上のプロセッサによって実行される１つ以上の格納されたプログラムを有する、コンピュータ読取可能記憶媒体であって、前記１つ以上のプログラムが、
    第１のクエリ処理段階のためのコンピュータ実行可能命令であって、
    １つ以上のクエリ用語に応答してインデックスから第１のセットのドキュメント識別子を検索するための命令と、
    クエリ用語の存在、用語頻度、ドキュメントの普及度のうち１つ以上に基づいて、前記第１のセットのドキュメント識別子の少なくとも１サブセットに対応する第１のセットの圧縮ドキュメントのために第１のセットの関連性スコアを生成し、前記第１のセットの関連性スコアを前記メモリに格納するための命令とを含む、第１のクエリ処理段階のためのコンピュータ実行可能命令と、
    第２のクエリ処理段階のためのコンピュータ実行可能命令であって、
    トークン位置のリスト、ドキュメントにおけるクエリ用語間の距離、ドキュメントにおけるトークンの属性、前記第１のセットの圧縮ドキュメントの１ドキュメントにおいて使用されるクエリ用語の周囲に現れるテキストのうち１つ以上に基づいて、前記第１のセットの圧縮ドキュメントのために第２のセットの関連性スコアを生成し、前記第２のセットの関連性スコアを前記メモリに格納するための命令を含む、第２のクエリ処理段階を実行するためのコンピュータ実行可能命令と、
    前記メモリから前記第１及び第２のセットの関連性スコアを読み出し、前記第１及び第２のセットの関連性スコアに基づいて更に処理するためにドキュメントの順序付きリストを生成するためのコンピュータ実行可能命令と、
    前記順序付きリストのドキュメントから、追加のクエリ用語を自動的に生成するためのコンピュータ実行可能命令と、
    前記追加のクエリ用語を使用して、新しいクエリを作成するためのコンピュータ実行可能命令と、
    前記インデックスから第２のセットのドキュメント識別子を検索するために、かつ、前記追加のクエリ用語に少なくとも一部基づいて第３のセットの関連性スコアを生成するために、前記新しいクエリを処理するためのコンピュータ実行可能命令と、
    前記第３のセットの関連性スコアを用いて、ユーザに提示するための１セットの上位のドキュメントを選択するためのコンピュータ実行可能命令と、
    を含む、コンピュータ読取可能記憶媒体。
16. 前記第２のセットの関連性スコアは、ドキュメントにおけるトークンの属性に少なくとも基づいており、前記属性は、ドキュメントにおけるトークンのフォント属性を含んでいる、請求項１５記載のコンピュータ読取可能記憶媒体。
17. 前記第１のセットのドキュメント識別子は、１セットの圧縮ドキュメントを格納するトークンスペースレポジトリにおける、クエリ用語に対応するトークンの場所に対応している、請求項１５記載のコンピュータ読取可能記憶媒体。
18. 前記第１のセットのドキュメント識別子を検索するための命令は、前記インデックスを用いて前記１以上のクエリ用語のトークン位置のリストを生成し、前記トークン位置に対応する１セットのドキュメント識別子を作成するためのマップにアクセスする命令を含む、請求項１５記載のコンピュータ読取可能記憶媒体。
19. 前記１つ以上のプログラムはさらに、
    第２のセットのトークンを回復するために、前記１セットの圧縮ドキュメントの少なくとも一部分を復元するためのコンピュータ実行可能命令であって、前記第２のセットの回復されたトークンが、前記第２のセットのドキュメント識別子に対応する前記１セットの圧縮ドキュメントの位置に関連付けられる、命令と、
    前記第２のセットの回復されたトークンを使用して、前記１セットの圧縮ドキュメントの１つ以上の部分を再構築するためのコンピュータ実行可能命令とをさらに含む請求項１５乃至１８のいずれか1項に記載のコンピュータ読取可能記憶媒体。
20. 前記１つ以上のプログラムは、
    前記順序付きリストの上位のドキュメントのセットにおいて、前記再構築された部分をユーザに提示するためのコンピュータ実行可能命令をさらに含む請求項１９に記載のコンピュータ読取可能記憶媒体。
21. 前記第３のセットの関連性スコアが、前記第２のセットのドキュメント識別子に対応する前記１セットの圧縮ドキュメント内の前記クエリ用語の１つ以上の位置に基づく請求項１５乃至１８のいずれか1項に記載のコンピュータ読取可能記憶媒体。

Images