(57)【特許請求の範囲】
【請求項１】
プログラムを実行するプロセッサを備えるコンピュータ装置によって実現される検索ドメイン内の複数のドキュメントを検索する方法であって、
前記プロセッサが前記プログラムを実行することによって、一連の連続する可変長ドキュメントＩＤデルタエントリであって、複数のドキュメントのうちキーワードを含む各々について１つのエントリがあるドキュメントＩＤデルタエントリを有する圧縮ドキュメントＩＤデルタリストを生成するステップと、
前記プロセッサが前記プログラムを実行することによって、一連の連続する可変長キーワードオカレンスカウントエントリであって、前記圧縮ドキュメントＩＤデルタリスト内の複数のドキュメントのうちの少なくとも一部の各々について１つのエントリがあるキーワードオカレンスカウントエントリを有するオカレンスカウントリストを生成するステップと、
前記プロセッサが前記プログラムを実行することによって、各キーワードオカレンスカウントエントリを有限セットのカテゴリのうちの１つと関連付けるステップであって、各カテゴリはオカレンスエントリサイズを有し、各キーワードオカレンスカウントエントリは前記関連付けられたカテゴリに対する前記オカレンスエントリサイズに等しいサイズであり、前記有限セットのカテゴリの各々は、ベース値を含み、前記圧縮ドキュメントＩＤデルタリスト内のエントリの各々は、カテゴリのベース値および関連ドキュメントＩＤデルタエントリの和であるシンボルを表す、ステップと、
前記プロセッサが前記プログラムを実行することによって、前記圧縮ドキュメントＩＤデルタリストを圧縮するために使用される符号化テーブルを生成するステップであって、前記符号化テーブルのコードの順序は、前記有限セットのカテゴリ内のシンボルの順序に対応し、前記符号化テーブル内の各コードに対応するシンボルが、前記コードの順序に基づいて計算される、ステップと、
前記プロセッサが前記プログラムを実行することによって、前記圧縮ドキュメントＩＤデルタリスト、前記オカレンスカウントリスト、および前記符号化テーブルを使用することによって、前記複数のドキュメントを検索するステップと
を含むことを特徴とする方法。
【請求項２】
１つのカテゴリは、前記キーワードオカレンスカウントエントリがオカレンスカウントリストに格納されていないことを示すオカレンスエントリサイズを有することを特徴とする請求項１に記載の方法。
【請求項３】
前記シンボルの値は、前記有限セットのカテゴリ内のすべてのカテゴリにわたる単一の連続する一連の数を形成することを特徴とする請求項１に記載の方法。
【請求項４】
さらに、単一セットのドキュメントＩＤデルタ値を使用して前記圧縮ドキュメントＩＤデルタリストは表現され、前記有限セットのカテゴリの各々はセット全体を表し、各個別のドキュメントＩＤデルタ値は異なるシンボル値と共に各々の前記カテゴリに現れることによって、各々のシンボル値は異なるドキュメントＩＤデルタ値およびオカレンスエントリサイズのペアを表すことを特徴とする請求項１に記載の方法。
【請求項５】
さらに、
前記プロセッサが前記プログラムを実行することによって、ドキュメントＩＤデルタサイズに上限しきい値を指定することによって改良されたハフマン符号化を使用して、前記圧縮ドキュメントＩＤデルタリストを圧縮するステップと、
前記プロセッサが前記プログラムを実行することによって、前記上限しきい値より大きいすべてのドキュメントＩＤデルタ値を符号化しないステップと、
前記プロセッサが前記プログラムを実行することによって、前記上限しきい値より大きいすべてのドキュメントＩＤデルタ値を、前記圧縮ドキュメントＩＤデルタリストに明示的に格納するステップと
を含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記圧縮ドキュメントＩＤデルタリストは複数のキーワードに基づいてドキュメントのセットを特定し、
さらに、前記プロセッサが前記プログラムを実行することによって、前記圧縮ドキュメントＩＤデルタリストを使用して、与えられたキーワードを含むドキュメントサブセットを特定し、前記オカレンスカウントリストを使用して、前記与えられたキーワードがドキュメントのサブセットの各ドキュメントに現れる回数を特定することによって、前記ドキュメントのセットを検索するステップを含むことを特徴とする請求項１に記載の方法。
【請求項７】
プログラムを実行するプロセッサを備えるコンピュータ装置によって実現される検索ドメイン内の複数のドキュメントに現れるキーワードを検索する方法であって、
前記プロセッサが前記プログラムを実行することによって、インデックスを使用して、キーワードを含むドキュメントを特定するステップであって、前記インデックスは符号化ドキュメントＩＤデルタリストを有し、前記符号化ドキュメントＩＤデルタリストは複数のエントリを有し、各々の前記エントリはシンボルを使用して、前記検索ドメイン内の前記複数のドキュメントのうちキーワードを含む各々に対するドキュメントＩＤデルタ値を表す、ステップと、
前記プロセッサが前記プログラムを実行することによって、前記符号化ドキュメントＩＤデルタリスト内の前記シンボルの各々を有限セットのカテゴリの１つおよび前記有限セットのカテゴリ内の順序と関連付けるステップであって、各カテゴリはベース値を含み、前記符号化ドキュメントＩＤデルタリスト内の各シンボルは、関連ドキュメントの前記ベース値および前記シンボルが表す前記ドキュメントＩＤデルタ値の和である、ステップと、
前記プロセッサが前記プログラムを実行することによって、符号化テーブルを使用する方法によって前記符号化ドキュメントＩＤデルタリストを符号化するステップであって、前記符号化テーブル内のコードの順序は前記有限セットのカテゴリ内の関連シンボルの順序に対応し、前記符号化テーブル内の各コードに対応するシンボルは前記コードの順序に基づいて計算される、ステップと
を含むことを特徴とする方法。
【請求項８】
さらに、単一のセットのドキュメントＩＤデルタ値を使用して前記符号化ドキュメントＩＤデルタリストは表現され、各々の前記カテゴリはエントリ全体を表し、各個別のドキュメントＩＤデルタ値は、異なるシンボル値と共に各々の前記カテゴリに現れることを特徴とする請求項７に記載の方法。
【請求項９】
さらに、
前記プロセッサが前記プログラムを実行することによって、ドキュメントＩＤデルタサイズに上限しきい値を指定することによって改良されたハフマン符号化を使用して、前記符号化ドキュメントＩＤデルタリストを符号化するステップと、
前記プロセッサが前記プログラムを実行することによって、前記上限しきい値より大きいすべてのドキュメントＩＤデルタ値を符号化しないステップと、
前記プロセッサが前記プログラムを実行することによって、前記上限しきい値より大きいすべてのドキュメントＩＤデルタ値を前記符号化ドキュメントＩＤデルタリストに明示的に格納するステップと
を含むことを特徴とする請求項７に記載の方法。
【請求項１０】
さらに、前記プロセッサが前記プログラムを実行することによって、オカレンスカウントリストを使用して、各ドキュメントにキーワードが現れるオカレンスの数を判定するステップを含み、前記オカレンスカウントリストは、前記符号化ドキュメントＩＤデルタリスト内のエントリのうちの少なくとも一部と関連付けられたキーワードオカレンスカウントエントリを有することを特徴とする請求項７に記載の方法。
【請求項１１】
前記オカレンスカウントリストは、一連の連続する可変長エントリを含み、各エントリの長さは有限セットの固定値から選択されることを特徴とする請求項１０に記載の方法。
【請求項１２】
さらに、
前記プロセッサが前記プログラムを実行することによって、各カテゴリをオカレンスエントリサイズと関連付けるステップと、
前記プロセッサが前記プログラムを実行することによって、カテゴリと関連付けられたドキュメントＩＤデルタリストエントリに対する各オカレンスカウントリストエントリを、当該カテゴリと関連付けられたサイズに等しいサイズを持つフィールドに格納するステップと
を含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
１つのカテゴリは、オカレンスカウントが前記オカレンスカウントリストに格納されていないことを示すオカレンスエントリサイズを有することを特徴とする請求項１２に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索インデックスフォーマットの最適化に関する。
【背景技術】
【０００２】
複数のドキュメントからなる検索ドメイン内でキーワードまたは類似のデータ項目を検索するには、インデックスの使用を伴うのが一般的である。これは、キーワードをドキュメントと関連付ける逆インデックス(inverted index)であることがよくある。
【０００３】
検索インデックスが性質上汎用である場合には、さまざまなタイプの検索をサポートしなければならない。１つの一般的な例がキーワード検索であり、この場合、ユーザは１つまたは複数のキーワード、つまり、値を与えており、その検索結果はすべてが、検索ドメイン内にあってすべてのキーワードを含むドキュメントである。別の例としてフレーズ検索(phrase search)があり、この場合、ユーザは、指定した順序で２以上のワードからなるフレーズを与えている。このケースでの検索結果は、すべてが検索ドメインからのドキュメントで、ユーザが与えた通りのキーワードを含むドキュメント（すなわち、すべてが隣接し、同じ順序にあるワード）である。フレーズクエリ(phrase query)をサポートするインデックスは、フレーズクエリをサポートしないインデックスよりも大幅に多いデータを含まなければならないが、これは、ワードのすべてのオカレンスについて、ドキュメント内の位置をインデックスが含んでいなければならないからである。
【０００４】
ユーザの要求を満たすためには、検索は高速であると共に正確でなければならない。インデックスのレベルでは、このことは計算上の要求事項になっている。インデックスは正確であるためには完全でなければならないが、このためにインデックスを大きくする必要が起っている。インデックスはアクセスを高速化するためには小さくなければならないが、このためにはデータを除去する必要が起っている。圧縮手法を用いることにより、読み込まなければならないデータの量を縮減できるが、これは結果を高速化するユーザの必要性を十分に満足しない場合がある。
【発明の概要】
【０００５】
本概要は、以下の「発明を実施するための形態」でさらに説明される概念から選択したものを簡略化した形式で紹介するために提供するものである。本概要は、特許請求の範囲に記載されている主題の重要な特徴または本質的な特徴を特定することを意図するものでも、特許請求の範囲に記載されている主題の範囲を決定する際の一助として使用することを意図するものでもない。
【０００６】
本明細書に開示された主題のさまざまな態様は、検索インデックス構造に関係するものであり、そこでは、既存構造に対する拡張を用いて、非フレーズ(non-phrase)検索を最適化する。この最適化には、ドキュメント内のキーワードオカレンスの位置に関する情報を除去することが含まれている。
【０００７】
その他の態様は、格納するのではなく計算するのを可能にする方法でインデックスを構成することにより、データを除去することに関係している。可変長オカレンスカウントフィールドを論理的カテゴリ(logical category)に関連付けることにより、フィールドのサイズを格納するのではなく、そのカテゴリから推論することができる。連続するシンボル値をカテゴリ内で、およびカテゴリにわたって使用することにより、シンボル値を格納するのではなく、カテゴリ内で計算することができる。カテゴリ内でシンボルエントリを順成付けて、その順序付けを符号化テーブルにマッチングすることにより、コードに対応するシンボルを格納するのではなく、計算することができる。
【０００８】
以下で説明している手法は、コンピュータプロセスとしても、コンピューティングシステムとしても、コンピュータプログラム製品のような製造物品としても実装することができる。コンピュータプログラム製品は、コンピュータシステムによって読み取り可能で、コンピュータプロセスを実行するための命令からなるコンピュータプログラムを符号化しているコンピュータ記憶媒体とすることができる。また、コンピュータプログラム製品は、コンピュータシステムによって読み取り可能で、コンピュータプロセスを実行するための命令からなるコンピュータプログラムを符号化している搬送波上の伝播信号とすることもできる。
【０００９】
以下で簡単に要約されている添付図面、以下に詳述している本実施形態の説明、および請求項を参照することにより、上述した概要をより完全に理解することができる。
【図面の簡単な説明】
【００１０】
【図１】複合検索インデックスの構造の実施形態を例示する図である。
【図２】マルチワードで非フレーズのクエリを実行する方法の実施形態のハイレベル論理的フローを示す図である。
【図３】フレーズクエリを実行する方法の実施形態のハイレベル論理的フローを示す図である。
【図４】コンテンツインデックス拡張のトップレベル構造の実施形態を例示する図である。
【図５】圧縮テーブルページの構造の実施形態を例示する図である。
【図６】カテゴリ記述子の構造の実施形態を例示する図である。
【図７】データページの構造の実施形態を例示する図である。
【図８】ページディレクトリエントリの構造の実施形態を例示する図である。
【図９】ドキュメントＩＤビットストリームエントリの構造の実施形態を例示する図である。
【図１０】圧縮プロセスの全体的フローを示す図である。
【図１１】解凍プロセスの全体的フローを示す図である。
【発明を実施するための形態】
【００１１】
本明細書の一部を形成し、特定の実施形態を例示している添付図面を参照して、以下で詳細に説明する。これらの実施形態は、この分野の精通者が以下に教示されている内容を実施するのを可能にするように十分に詳しく説明されているが、当然に理解されるように、その他の実施形態が利用されることもあり、主題の精神または範囲から逸脱することなく論理的、機械的、電気的、およびその他の変更が行なわれることもある。
【００１２】
（概要）
本開示事項は、検索ドメイン内のドキュメント（またはファイル）のセットを検索して、ユーザに最も関連性のあるものを見付けることを取り扱っている。検索は、一般的に、キーワードのセットをユーザから取得して検索を指示し、検索ドメイン内にあり、これらのキーワードに一致するすべてのドキュメントを特定することを伴う。これらの候補ドキュメントの特定を試みる際に、検索エンジンは、ドキュメントの本体内またはドキュメントの特定のセクション内のキーワード、すなわち、プロパティ（例えば、タイトル、抄録など）を探し出すことができる。
【００１３】
その結果得られたドキュメントのセットは、検索ドメインからのドキュメントであって、関連する可能性のあるすべてのドキュメントを含む。その後、候補ドキュメントにランク付けアルゴリズムを適用して、ドキュメントとユーザとの関連性を予測することができる。候補ドキュメントは、一般的に、予測された関連性の高いものから順にユーザに提示される。
【００１４】
このタイプの検索の実施形態では、一般的に、キーワードをドキュメントと関連付ける逆インデックス構造が利用される。図１を参照すると明らかであるように、この種のインデックス１００は、複数のコンポーネントから構成され得る。本開示事項で主に関心があるのは、コンテンツインデックス１０２と、コンテンツインデックス拡張１０６である。検索プロセス全体としては重要であるが、基本スコープインデックス１０４と複合スコープインデックス１０８は本開示事項とは直接に関連性がない。
【００１５】
コンテンツインデックス１０２は、検索ドメイン内のドキュメントに見られるキーワードの完全インデックスである。これは、さまざまなタイプの検索をサポートするように構成され、コンテンツインデックス拡張１０６とは独立して使用することができる。コンテンツインデックス１０２内のフラグは、使用可能な情報がコンテンツインデックス拡張１０６にあるかどうかを示している。このフラグは各キーワードに対して存在し、拡張された情報がどのように使用され、いつ使用されるかを制御している。
【００１６】
コンテンツインデックス１０２がサポートしている１つのタイプの検索は、「フレーズクエリ」である。これは、特定の順序で現れるワードの特定の組み合わせをユーザが探し出す場合のクエリである。単純な例は、“the quick brown fox”というフレーズを探す検索である。ドキュメントがその正確なフレーズを含む場合、そのドキュメントは候補であるが、ドキュメント全体にわたって散在しているすべてのワードを含む場合、または異なる順序ですべてのワードを含む場合は、そのドキュメントは候補とはならない。効率化のために、このタイプのクエリでは、インデックスが、各キーワードがドキュメント内のどこに現れているかに関する情報を含み、これらのキーワードが隣接していて正しい順序になっているかどうかを検索エンジンが判定できるようになっていることが要件である。この情報によりインデックスのサイズは大きくなり、インデックスを含んでいる記憶媒体（例えば、データドライブ）から読み込むべきデータの量が増加する。与えられたキーワードの１つまたは複数が高い割合でドキュメントの中に現れる大きな検索ドメインでは、このデータを読み込むのに必要な時間は、検索を実行するのに必要な時間の大部分を含んでいる。
【００１７】
コンテンツインデックス拡張１０６は、非常に多数のドキュメントの中に現れるキーワードを伴う非フレーズクエリ用に最適化されている。１つの用途は、ユーザがキーワードのセットを与え、そのすべてのキーワードが各候補ドキュメントの中に現れるが、特定の順序で必ずしも現れないような状況の場合である。別の用途はフレーズクエリに対する初期フィルタであり、その場合、すべてのワードを含まないドキュメントを除去してから、コンテンツインデックス１０２を使用して、特定のフレーズが残りのドキュメント内に含まれるかどうかのよりコストのかかる判定を行なっている。
【００１８】
コンテンツインデックス拡張１０６はフレーズクエリをサポートする必要がないので、各キーワードが各ドキュメント内に現れる特定の位置に関する情報（オカレンスデータ(occurrence data)と呼ばれる）を含める必要がない。せいぜい、ワードが何回現れるかのカウント、すなわち、オカレンスカウント(Occurrence Count)を格納しているだけである。この単一値は、特にそのワードがドキュメントの中で幅広く使用される場合に、ドキュメント内の各位置を表わすために必要な数のセットよりもはるかに小さくなっている。このデータの除外により、各キーワードについてストレージから読み込まなければならないデータの量が減少する。この結果、各キーワードを処理するために必要な時間が短縮されるので検索が高速化される。
【００１９】
本開示事項において説明を単純化し、明確化するために、インデックスは、コンポーネントの各々について別個のファイルからなるものとして説明されている。明らかなように、ファイルの使用は単なる一実施形態であり、本開示事項を限定するものではない。また、インデックスは、「ドキュメント」内に存在する「キーワード」を中心に説明されている。キーワードは「ワード」に限定されない。キーワードは、ドキュメント内で検索されるフレーズ、数字、コード、または類似の値とすることができる。同じように、用語「ドキュメント」は、検索され、キーワードを含むエンティティを意味するために使用される。これらのエンティティは、ドキュメント、ファイル、カード、または必要な特性を持つその他の論理的構造とすることができる。
【００２０】
ストレージから読み込まれる必要のあるデータの量をさらに減少するために、コンテンツインデックス拡張１０６の一部は以下に説明するように圧縮される。一実施形態では、比較的頻繁に現れるデータ項目には短いコードを使用する特性を持つ無損失エントロピー符号化方式(lossless entropy encoding scheme)であるハフマン符号化が利用されている。符号化をドキュメントＩＤ間の差異（すなわちステップサイズ）に適用する場合には、検索ドメイン内にそのキーワードが現れる頻度が増加すると、圧縮はより効率化される。これは、コンテンツインデックス拡張が高い頻度で使用されるキーワードにだけ使用される場合に開示した手法に良く適合している。
【００２１】
コンテンツインデックス拡張１０６は多数の使い方がされてキーワード検索をサポートしている。１つの使い方が図２に例示されているが、そこでは、マルチワードの非フレーズクエリのハイレベル論理的フローが示されている。ステップ２００において、キーワードをユーザから取得する。ループ判定２０２は、各キーワードの処理を制御する。このループ内で、ステップ２０４において、各キーワードがコンテンツインデックス１０２内で別々に調べられ、コンテンツインデックス拡張（ＣＩＸ）がキーワードに対して使用可能であるかどうかが判定される。必要なデータはキーワードのヘッダ情報の中に格納できるので、これは大量のオカレンスデータを読み込むことなく行なうことができる。フラグがコンテンツインデックス１０２内にセットされている場合は、ワードが位置するコンテンツインデックス拡張１０６までのオフセットが付属している。これにより、関連性のある情報に直接アクセスすることができる。この場合、コンテンツインデックス拡張１０６からインデクシングする情報を用いて、ステップ２０８において、現在のワードを含むドキュメントのリストを判定する。使用可能なコンテンツインデックス拡張１０６のエントリがない場合には、ステップ２０６において、コンテンツインデックス１０２内のオカレンスデータを使用して候補ドキュメントのリストが生成される。各キーワードに対して個別に候補ドキュメントのリストを取得したあと、これらのリストの共通集合を形成し（２１０）、すべてのキーワードが現れるすべてのドキュメントの単一リストが生成される。これは、ユーザに利用可能にされる検索結果である。
【００２２】
第２の使い方は、フレーズクエリを実行するために使用できるハイレベルステップを例示している図３に例示されている。ステップ３００、３０２、３０４、および３０８は、図２に関連して上述したステップ２００、２０２、２０４、および２０８と同じである。ループ内の処理の流れは、キーワードでの使用のための、使用可能なコンテンツインデックス拡張１０６がない場合に、コンテンツインデックスを使用してリストを生成するのではなく、スキップされる点で異なっている。これは、ループ内の処理の流れがフィルタとして作用し、最終的回答を生成するわけではいからである。あるフレーズを検索するとき、必要になるのは、すべてのキーワードが現れるファイルのために、そのフレーズについてチェックするだけである。このファイルのセットは、キーワードの組み合わせが現れるファイルのサブセットである必要がある。すべてのキーワードについて候補リストを開発してから共通集合を形成することが望ましいが、必ずしも必要ではない。単一ワードでフィルタリングを行なっても、検索を高速化するのに十分にオーバヘッドを減らすことができる。候補ドキュメントリストのすべての共通集合を形成したあと（３１０）、残りのドキュメントをコンテンツインデックス１０４を使用して処理して（３１２）、正確なフレーズを含むドキュメントがあれば、どのドキュメントであるかが判定される。そのリストはユーザに使用可能にされる検索結果である。
【００２３】
（コンテンツインデックス拡張）
図４を参照して説明すると、図４はコンテンツインデックス拡張１０６のトップレベル構造を示す図である。インデックスには、各キーワードに対する別個のセグメント４００がある。一実施形態では、各セグメントは４０９６バイトのページ境界から始まっている。この場合、セグメントは、データを保持するのに必要な数だけのページにわたることができる。各キーワードセグメント内には、２つの個別(discrete)データセットが存在する。初期ページ境界からは圧縮テーブルページ４０２が始まっている。このあと、一連の１つまたは複数のデータページ(Data Pages)４０４が次のページ境界から始まっている。なお、ページ位置合わせは、本開示事項の概念を実現するために必要ではないが、パフォーマンス向上を得ることができる。
【００２４】
本開示事項の実施形態では、各ワードのデータは別個に符号化される。この手法によると、キーワードデータの各セットについて別個の符号化テーブル５０４（図５参照）を使用できるので、各ワード内の圧縮を最適化することができる。データを解凍するためには、各キーワードに対する復号化情報が利用可能になっている必要がある。一実施形態では、キーワードと共に符号化テーブル５０４を、圧縮テーブルページの一部として格納する。これは、必要な復号化テーブルを符号化テーブル５０４から引き出すことができ、符号化テーブル５０４が小さくなることにより、ストレージスペースが節約されるからである。いったん復号化テーブルが生成されると、データページ４０４を解凍して、使用し得る。
【００２５】
図５は、圧縮テーブルページ４０２の構造を例示している。この構造は、図７に示すようなデータページ４０４も参照すると理解しやすくなる。ハイレベルでは、各キーワードについて格納されるデータは、キーワードを含むドキュメントへの一連の参照である。各ドキュメントについて、２つの情報項目が必要である。すなわち、ドキュメントＩＤ（ＤｏｃＩＤ）と、キーワードがドキュメントに現れる回数のオカレンスカウント（ＯｃｃｕｒＣｎｔ）である。これらはデータページの別個のセクション、すなわち、ＤｏｃＩＤビットストリーム７０８とＯｃｃｕｒＣｕｔビットストリーム７１０に格納される。これは、一部では、オカレンスデータが常に必要であるとは限らず、それを別個に格納することがＤｏｃＩＤと共に検索される必要がないことを意味するという事実によるものである。これらの情報項目の両方は圧縮テーブルページ４０２を使用して符号化されるが、符号化の仕方は異なっている。
【００２６】
ＯｃｃｕｒＣｎｔは、一連の可変長ビットフィールドとしてＯｃｃｕｒＣｎｔビットストリーム７１０に格納される。ＯｃｃｕｒＣｎｔ値はドキュメントにわって幅広く変化することがある。そのために、ＯｃｃｕｒＣｎｔを格納するために必要なビット数も変化する。一実施形態では、ＯｃｃｕｒＣｎｔを格納するために一定数の異なるサイズが使用される。例えば、このフィールドは０、３、７、１２または２０ビットのいずれかの長さとすることができる。その結果として、各ドキュメントは、これらの有限数の長さの１つであるフィールドに格納されるＯｃｃｕｒＣｎｔを持つことになる。この属性を使用して、ドキュメントはそれぞれの対応するＯｃｃｕｒＣｎｔの長さ別にグループ化することができる。圧縮テーブルページ４０２内では、これらのグループはカテゴリと名付けられ、各グループはカテゴリ記述子５０２によって表される。特定のカテゴリ内のすべてのドキュメントはＯｃｃｕｒＣｎｔフィールド長が同じになっているので、その長さは、各ＤｏｃＩＤと共にではなく、カテゴリ記述子５０２内のオカレンスフィールド６０６内のビット数として一度だけ格納される必要がある。これにより、コンテンツインデックス拡張１０６からは相当量の冗長データが排除される。オカレンスのビット数に対する０の値は、ＯｃｃｕｒＣｎｔ値が先行ＤｏｃＩＤの場合と同じであることを示すために使用される。これらのエントリに対するエントリはＯｃｃｕｒＣｎｔビットストリーム７１０にはない。最初のカテゴリはこの特性を持つすべてのＤｏｃＩＤデルタを含む。
【００２７】
図６はカテゴリ記述子５０２の実施形態を例示している。シンボルカウント６０２は、カテゴリ内のシンボルの数を指定している。ＤｏｃＩＤデルタしきい値６０４は、このカテゴリ内で符号化されるＤｏｃＩＤデルタの上限値を指定している。オカレンスのビット数６０６は、カテゴリ内のシンボルに対応する各ＯｃｃｕｒＣｎｔエントリをＯｃｃｕｒＣｎｔビットストリーム７１０に格納するために使用されるビットの数を指定している。ベースシンボル値(BSV)は、ＤｏｃＩＤデルタをこのカテゴリに対して一意になるよう各ＤｏｃＩＤデルタ値に加えられる値を定義している。
【００２８】
カテゴリ内で使用される各シンボルは、ＤｏｃＩＤおよびそのカテゴリのＢＳＶの和である。各カテゴリのＤｏｃＩＤデルタ値はゼロ（０）から（ＤｏｃＩＤしきい値−１）までの範囲である。最初のカテゴリのＢＳＶはゼロ（０）であり、他のすべてのカテゴリのＢＳＶは、先行カテゴリのＢＳＶにカテゴリ内のシンボルの数を加えたものに等しくなっている。その結果として、すべてのカテゴリで表現されるシンボルのフルセットは、最小ＤｏｃＩＤデルタ（０）から最終カテゴリのＢＳＶに最大符号化ＤｏｃＩＤデルタを加えたものまでの連続する一連の数である。この一連の数では、異なるＤｏｃＩＤデルタのセットは各カテゴリ内で繰り返され、異なるＢＳＶを使用して異なるシンボルとして符号化されている。この手法によると、各ＤｏｃＩＤデルタ値は各カテゴリに現れるので、オカレンスのビット数として利用可能な各値とペアになっている。
【００２９】
実施形態では、各カテゴリ内の順次ＤｏｃＩＤデルタ値も使用されている。各カテゴリは、同じ一連の値を含む。これにより、ＤｏｃＩＤデルタ値はシンボルおよびカテゴリ記述子から計算することができる。シンボルの値は、カテゴリによって表された一連のＤｏｃＩＤデルタまでのインデックスの働きをする。それがどのカテゴリに属するかによって、対応するオカレンスのビット数およびカテゴリのＢＳＶが判定される。シンボルからＢＳＶを差し引くと、ＤｏｃＩＤデルタ値が判定される。順序付けにより各カテゴリ内のシンボル値を定義しているので、シンボルを格納する必要はない。むしろ、シンボル値は必要に応じて計算することができる。カテゴリ内の値のその他の一定の順序付けを使用しても、同じ結果が得られる。
【００３０】
符号化テーブル５０４内では、コードはカテゴリ記述子５０２内のエントリに対応する順序で格納される。符号化テーブル５０４内のエントリの数は、組み合わされたカテゴリのすべてにおけるエントリの総数に等しくなっている。このような対応により、符号化テーブル５０４内のコードのインデックスを使用してカテゴリまでインデクシングすると、コードをシンボルにマッピングすることができる。この結果、ＤｏｃＩＤデルタを直接計算することができ、またカテゴリ定義と符号化テーブル５０４から復号化テーブルを生成することができる。上記のように復号化を実行できるので、個別のシンボル値は、ハフマン符号化方式では一般的であるようにコードと共に符号化テーブル５０４に格納する必要がない。
【００３１】
本開示事項の概念の１つは、コンテンツインデックス拡張１０６内のオカレンス情報は、キーワードが関連ドキュメント内のどこに現れるかに関するどのデータも含んでいないことである。唯一のデータはキーワードがドキュメントに現れる回数である。このオカレンスカウントデータは、ワードが何回現れるかに基づいて候補ドキュメントを区別する、関連性ランク付けアルゴリズム(relevance ranking algorithm)を使用するクエリをサポートしている。本開示事項のコンテンツインデックス拡張１０６が特にサポートしていないフレーズクエリの場合に必要になるデータ量よりもはるかに少ないデータで、これを行なうことができる。本開示事項の別の概念は、オカレンスカウントデータがＤｏｃＩＤデルタ情報からの別個のビットストリームに格納されることである。この結果、オカレンスデータを検索することなくＤｏｃＩＤデータを検索することができる。このことは、ＤｏｃＩＤ単独でも十分な場合に使用されるようにインデックスをさらに最適化する。また、いくつかの関連性ランク付けアルゴリズムで使用されるドキュメント長もコンテンツインデックス拡張１０６に格納されないので、格納されるデータ量がさらに削減される。
【００３２】
次に図７を参照して説明すると、ＤｏｃＩＤはハフマン符号化アルゴリズムによって生成される一連のシンボルとしてＤｏｃＩＤビットストリーム７０８に格納される。最初のステップは、各ＤｏｃＩＤを先行ＤｏｃＩＤからのステップサイズ（すなわちデルタ）に変換することである。このＤｏｃＩＤデルタは、２つの連続するＤｏｃＩＤ間の数値の差である。現在のＤｏｃＩＤが分かっていれば、デルタ値は次のＤｏｃＩＤを計算することができる。デルタはＤｏｃＩＤより小さいので、デルタを使用することにより、格納されるデータ量が削減される。また、これは一意なＤｏｃＩＤのリストを、ハフマン圧縮が必要とするよりはるかに小さな有限セットの数値にマッピングする。
【００３３】
起り得る値の数をさらに限定するために、選択したＤｏｃＩＤデルタしきい値６０４よりも大きいすべてのＤｏｃＩＤデルタは、符号化した値としてではなくＤｏｃＩＤビットストリーム７０８内に明示的に格納される。図９に示すように、符号化したＤｏｃＩＤエントリは、シンボルコード９０２だけを持っている。デルタ値がＤｏｃＩＤデルタしきい値よりも大きいこれらのＤｏｃＩＤは特殊シンボル値によって表わされ、デルタ値は符号化されていないＤｏｃＩＤデルタ９０４として次のフィールドに明示的に格納される。実施形態では、（ＢＳＶ＋ＤｏｃＩＤデルタしきい値）の値を特殊シンボルとして使用する。これは標準ハフマン符号化方式を改良したものである。これには、符号化する必要があるシンボルの数を減少するという利点があり、最小限のサイズペナルティを受ける。これは、キーワードを含むドキュメントの割合が大きい検索ドメインでは、一般的に、ＤｏｃＩＤデルタ値は比較的小さな値にわたって分散されるからである。大きなデルタ値が現れるのは稀である。ハフマン符号化方式では、この結果として最大コードにデルタ値が割り当てられている。使用されるコードとデルタ値自体との間の長さの差は比較的小さいので、デルタ値を符号化されていない値として格納するコストは最小である。場合によっては、符号化されていないデルタおよび関連の特殊シンボル値の合計長さは実際には、標準符号化手法で割り当てられていたシンボルよりも小さくなる可能性がある。別の実施形態では、２つの異なる特殊シンボル値を使用して（すなわち、２バイト対４バイト）、明示的ＤｏｃＩＤデルタ値に対して２つの異なるストレージサイズを選択し、ストレージ利用効率をさらに最適化している。
【００３４】
再び図７を参照して説明すると、図７から明らかであるように各データページ４０４はハウスキーピング情報から始まっている。一実施形態では、これは、このページに格納された最終ドキュメントを指定している最終ＤｏｃＩＤおよびカレントページ上のドキュメントＩＤも含めて、残りのドキュメントＩＤの数を指定している、残っているＤｏｃＩＤの数７０４を含んでいる。これらは、データページ４０４を通り抜けるナビゲートの際に使用される。データページ４０４の次のセクションはカレントページ上のＤｏｃＩＤのディレクトリであるページディレクトリ７０６である。各ＤｏｃＩＤには、ページディレクトリエントリ８００が存在する。図８に実施形態が示されている。ＤｏｃＩＤフィールド８０２はそのエントリが適用される特定のドキュメントＩＤを指定している。ＤｏｃＩＤ  Ｃｎｔフィールド８０４は現在のＤｏｃＩＤに先行するページ内のＤｏｃＩＤの数を指定している。ＤｏｃＩＤオフセットフィールド８０６は、ＤｏｃＩＤビットストリーム７０８の先頭からＤｏｃＩＤビットストリーム７０８内の符号化ＤｏｃＩＤエントリの位置までのオフセットをビット数で指定している。ＯｃｃｕｒＣｎｔオフセットフィールド８０８は、ＯｃｃｕｒＣｎｔビットストリーム７１０からＯｃｃｕｒＣｎｔビットストリーム７１０内のＯｃｃｕｒＣｎｔエントリの位置までのオフセットをビット数で指定している。これらの値は、情報を見つけるためにリストを走査することが望ましくない場合には、データページ４０４内の選択したＤｏｃＩＤの情報に直接アクセスすることを可能にする。
【００３５】
（圧縮の概要）
コンテンツインデックス拡張１０６用の圧縮データを生成するには、２つの個別ハイレベルプロセスが関係する。すなわち、符号化データを生成することと、各エントリを符号化することである。これらの各々は、コンテンツインデックス拡張１０６にリストされる各キーワードについて繰り返される。１つの手法は以下に説明され、図１０に例示されている。
【００３６】
（符号化データの生成）
符号化データ生成の最初のステップは、検索ドメインにあり、キーワードを含むドキュメントのリストを判定することである（１００２）。各ドキュメントについて、ＤｏｃＩＤデルタ値とＯｃｃｕｒＣｎｔ値がＯｃｃｕｒＣｎｔを保持するために必要なＯｃｃｕｒＣｎｔ値のビット数と共に判定される（１００４）。すべての関連するドキュメントにわたるこれらの値のフルセットは、単一ドキュメントリストに格納される。カテゴリのために使用されるＤｏｃＩＤデルタしきい値は、このリストを使用して、ＤｏｃＩＤデルタ値に基づいて判定される。
【００３７】
ドキュメントリストからの使用可能なドキュメントを用いて、カテゴリを定義することができ（１００６）、カテゴリ記述子５０２を指定することができる。各カテゴリについて、シンボルカウント６０２はＤｏｃＩＤデルタしきい値よりも１だけ少なく定義される。シンボルカウント６０２とＤｏｃＩＤデルタしきい値６０４は、すべてのカテゴリにわたって共通している。各カテゴリには、オカレンスのビット数フィールド６０６に対して、事前定義した値セットから順次に選択される異なる値が割り当てられる。その後、各カテゴリには、各後続カテゴリについてゼロ（０）から始まってシンボルカウント６０２だけ増分する異なるベースシンボル値（ＢＳＶ）６０８が割り当てられる。
【００３８】
定義されたカテゴリを用いて、すべてのカテゴリにわたるフルセットのシンボルが指定される（１００８）。各シンボルは、カテゴリのＢＳＶに該当のＤｏｃＩＤデルタ値を加えたものとして計算される。次に、ドキュメントリストから引き出された頻度情報を利用して、ハフマン符号化を使用して、各シンボル１０１０に対して異なるコードを生成する。ＤｏｃＩＤデルタとオカレンスのビット数の各一意なセットがリストに現れる回数が符号化プロセスに入力され、使用頻度の多いペアに短いコードが与えられる。これらのコードは結合されて、符号化テーブル５０４が上述したフォーマットで作成される。その後、カテゴリ記述子５０２と符号化テーブル５０４の結合されたセットは、キーワードに対する圧縮テーブルページ４０２としてコンテンツインデックス拡張１０６に書くことができる。
【００３９】
（各ドキュメントのデータ符号化）
使用可能な符号化データを用いて、ドキュメントリスト内のＤｏｃＩＤデルタ／ＯｃｃｕｒＣｎｔのペアを符号化することができる。リスト内の各ドキュメントについて（１０１４）、オカレンス値の関連ビット数６０６を用いて、どのカテゴリ内のデータが符号化されるかを判定する。カテゴリに対するＢＳＶをＤｏｃＩＤデルタに加えて、シンボルを判定する（１０１８）。このシンボルは、符号化テーブルを使用して関連コードにマッピングされ（１０２０）、このコードはＤｏｃＩＤビットストリーム７０８の終わりに付加される。オカレンスのビット数が非ゼロであれば、ＯｃｃｕｕＣｎｔがＯｃｃｕｒＣｎｔビットストリーム７１０の終わりにそのビット数で付加される。
【００４０】
ＤｏｃＩＤデルタがＤｏｃＩＤデルタしきい値６０４より大きい特殊ケースでは、特殊シンボルに対応するコードがステップ１０２０から使用され、ＤｏｃＩＤデルタは、図９に示すように符号化シンボルの直後に続いてＤｏｃｉＤビットストリーム７０８に書き出される（１０２６）。
【００４１】
十分なデータがステップ１０２８でＤｏｃＩＤビットストリーム７０８およびＯｃｃｕｒＣｎｔビットストリーム７１９に累積されてデータページ４０４が満たされると、最終  ＤｏｃＩＤと残っているＤｏｃＩＤの数７０４およびページディレクトリ７０６を含むヘッダ情報が生成され、図７に示すフォーマットで完全なデータページがコンテンツインデックス拡張１０６に書かれ（１０３０）、新しいデータページ４０４が開始する。これは、すべてのドキュメント情報が符号化され、コンテンツインデックス拡張１０６に書かれるまで継続し、その後、部分的である可能性のある最終データページを書く（１０３２）。その後、処理はコンテンツインデックス拡張１０６に挿入される次のキーワードに移る。
【００４２】
（復号化の概要）
圧縮と同じように、復号化では２つの主要プロセスが行なわれる。すなわち、復号化する情報を生成することと、その後各キーワードの情報を復号化することである。代表例として、これは個々のキーワードについて行なわれ、キーワードリスト全体に対して一度に行なわれるのではなく、クエリで指定されたキーワードについて行なわれる。１つの手法が以下に説明され、図１１に例示されている。
【００４３】
（復号化テーブルの生成）
圧縮テーブルページ４０２に格納された符号化テーブル５０４は、カテゴリ記述子５０２を参照することによって復号化テーブルに変換される（１１０２）。符号化テーブル５０４内のコードは、シンボルがカテゴリ内に現れるのと同じ順序で格納されているので、コードとシンボルとのマッピングは、シンボルを列挙し、これらのシンボルが符号化テーブル５０４に格納されている順にシンボルをコードにマッチングすることによって、復号化テーブルとして再作成される。
【００４４】
（各ドキュメントのデータの復号化）
各ドキュメントについて、コードがＤｏｃＩＤビットストリーム７０８から読み取られ（１１０６）、復号化テーブルを使用してシンボル１１０８にマッピングされる。シンボルをカテゴリ記述子５０２のＢＳＶと比較することにより、正しいカテゴリを判定することができる。これにより、使用されるオカレンスのビット数６０６の値が判定される。シンボルをチェックして、シンボルが通常のシンボルであるか、特殊なシンボルであるかを判定する（１１１２）。通常のシンボルであれば、ＤｏｃＩＤデルタが計算される（１１１４）。カテゴリのＢＳＶ６０８をシンボルから差し引くと、対応するＤｏｃＩＤデルタ値が生成される。ＤｏｃＩＤデルタを前に処理されたＤｏｃＩＤに加えることにより、現在のＤｏｃＩＤが生成される。ＯｃｃｕＣｎｔが必要であれば、これは、オカレンスのビット数６０６の値を使用してＯｃｃｕｒＣｎｔビットストリーム７１０から読み取ることができる（１１１８）。
【００４５】
ＤｏｃＩＤビットストリーム７０８から読み取られたコードがＤｏｃＩＤデルタしきい値６０４を超えるＤｏｃＩＤデルタを示している特殊シンボルにマッピングしている特殊なケースでは、ＤｏｃＩＤデルタ値はそのコードの直後に続くＤｏｃＩＤビットストリーム７０８から読み取られる（１１１６）。ステップ１１１８のあと、フローはステップ１１０４に戻る。
【００４６】
一実施形態では、ビットストリームへの２つのアクセスモードがサポートされている。順次アクセスは、各ビットストリームの先頭から始まり、各ストリームおけるカレント位置へのポインタを維持することによって利用可能である。ＤｏｃＩＤビットストリーム７０８に対するポインタは、各コードが読み取られるたびに一度にシングルバイトだけ前進する。ハフマン符号化はプレフィックスフリーコード(prefix free code)を使用するので、コードは長さが変化し、そのビット列によって認識することができる。これは、コードが読み取られるどのビットでも認識可能であることを意味している。ＯｃｃｕｒＣｎｔビットストリーム７１０に対するポインタは、シンボルに対応するオカレンスのビット数の値だけインクリメントする。直接アクセスは、ページディレクトリ７０６を介しても使用可能である。ディレクトリを検索して、アクセスしているドキュメントに対応するＤｏｃＩＤフィールド８０２を含むページディレクトリエントリ８００を見つけることができる。ＤｏｃＩＤオフセット８０４は、ＤｏｃＩＤビットストリーム７０８までのオフセットを供給し、ＯｃｃｒＣｎｔオフセット８０８は、ＯｃｃｕｒＣｎｔビットストリーム７１０までのオフセットを供給する。アクセスしているドキュメントのデータをその後検索することも、順次アクセスをそのポイントから開始することもできる。
【００４７】
本発明の主題事項を構造的特徴および／または方法論的動作に固有の言語で説明したが、添付の特許請求の範囲で定義される本発明の主題は、必ずしも説明した特定の特徴または動作に必ずしも限定されないことを理解されたい。むしろ、特定の特徴および動作は、本発明を実装する例示的な形態として開示されている。当業者であれば理解されるように、構成の多くの変更および幅広く異なる実施形態と応用が、開示した主題の範囲から逸脱しないことを示唆している。
【図１】
0005415529.tif 000002
【図２】
0005415529.tif 000003
【図３】
0005415529.tif 000004
【図４】
0005415529.tif 000005
【図５】
0005415529.tif 000006
【図６】
0005415529.tif 000007
【図７】
0005415529.tif 000008
【図８】
0005415529.tif 000009
【図９】
0005415529.tif 000010
【図１０】
0005415529.tif 000011
【図１１】
0005415529.tif 000012