(57)【要約】      （修正有）【課題】同一部分を含む文書に対して効率的でユーザフレンドリな方式で検索クエリを実行する方法を提供する。【解決手段】各文書は、一意のブロックＩＤに関連付けられたブロックの集合に構造化されており、同一のブロックは、同一のブロックＩＤに関連付けられており、特定の検索ターム属性と少なくとも１つのブロックＩＤとの間の相関に関する情報を含む第１のデータ構造２３１を準備するステップと、ブロックと文書との間の相関に関する情報を含む第２のデータ構造２３２を準備するステップと、検索クエリを受け取るステップと、検索クエリを、少なくとも１つの検索ターム属性について第１のデータ構造を検索することによって処理して、第１のクエリ応答を得るステップと、第１のクエリ応答を、第２のデータ構造２３２を用いて第２のクエリ応答にマッピングするステップと、第２のクエリ応答を検索結果として返すステップと、を含む。【選択図】図２
2015109078.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つの検索ターム属性を有する検索タームを含む検索クエリを、複数の文書（１００）に対して実行するための方法であって、前記各文書は、ブロック（１１０）の集合に構造化されており、前記各ブロック（１１０）は、一意のブロックＩＤに関連付けられ、同一のブロックは、同一のブロックＩＤに関連付けられており、前記方法は、
特定の検索ターム属性と少なくとも１つのブロックＩＤとの間の相関に関する情報を含む第１のデータ構造（２３１、５００）を準備するステップと、
ブロックと文書との間の相関に関する情報を含む第２のデータ構造（２３２、６００）を準備するステップと、
検索クエリを受け取るステップと、
前記検索クエリを、少なくとも１つの検索ターム属性について前記第１のデータ構造（５００）を検索することによって処理して、第１のクエリ応答を得るステップと、
前記第１のクエリ応答を、前記第２のデータ構造（２３２、６００）を用いて第２のクエリ応答にマッピングするステップと、
前記第２のクエリ応答を検索結果として返すステップと、
を含む、方法。
【請求項２】
前記第１のデータ構造（２３１、５００）は、複数の索引エントリを含む索引であり、各索引エントリは、特定の検索ターム属性と関連付けられている、請求項１に記載の方法。
【請求項３】
前記各索引エントリは、少なくとも１つのブロックＩＤに関する、前記索引エントリに関連付けられた前記検索ターム属性が前記ブロックＩＤを有するブロック（１１０）内に含まれていることを示す情報を含む、請求項２に記載の方法。
【請求項４】
前記第１のデータ構造（２３１、５００）は、前記各検索ターム属性について、前記ブロック内の前記検索ターム属性の位置に関する付加的な情報、及び／又は、特定のブロック内の前記検索ターム属性の出現頻度に関する付加的な情報を含む、請求項１乃至請求項３のいずれか１項に記載の方法。
【請求項５】
前記第２のデータ構造（２３２、６００）は、どのブロック（１１０）がどの文書（１００）に含まれているかに関する情報、及び／又は、どの文書（１００）がどのブロック（１１０）から成るものであるかに関する情報を提供するリストである、請求項１乃至請求項４のいずれか１項に記載の方法。
【請求項６】
前記検索クエリを処理する前記ステップは、前記検索クエリの構造及び論理演算子を解析し、処理時間を短縮するために処理を最適化する、解析ステップ（１２２０）を含む、請求項１乃至請求項５のいずれか１項に記載の方法。
【請求項７】
前記検索クエリは、論理演算子によって連結された複数の検索ターム属性から成り、前記論理演算子に応じて、前記検索クエリの少なくともサブセットが、前記第１のデータ構造（２３１、５００）のみを用いてブロック・レベルで処理される、請求項１乃至請求項６のいずれか１項に記載の方法。
【請求項８】
前記検索クエリ内の論理演算子に応じて２つの検索結果が生成され、第１の検索結果は、前記第１のデータ構造（２３１、５００）を用いたブロック・レベルの検索クエリ処理の結果得られる、数が減らされた検索ヒットを含み、第２の検索結果は、前記第１のデータ構造（２３１、５００）を用いたブロック・レベルと前記第２のデータ構造（２３２、６００）を用いた文書レベルとの連続した処理の結果得られる、全量の検索ヒットを含む、請求項１乃至請求項７のいずれか１項に記載の方法。
【請求項９】
少なくとも部分的に同一のブロック（１１０）を含む文書（１００）を検索するためのデータ構造を生成する方法であって、前記方法は、
文書（１００）を受け取るステップと、
前記受け取った文書（１００）内のブロック（１１０）を定義し、前記各ブロック（１１０）に一意のブロックＩＤを割り当てるステップであって、同一のブロック（１１０）が同一のブロックＩＤに関連付けられる、ステップと、
前記定義されたブロック（１１０）に索引付けし、ブロック・データと前記ブロック・データを含むブロックＩＤとの間の相関に関する情報を含む第１のデータ構造（２３１、５００）を生成するステップと、
ブロック（１１０）と文書（１００）との間の相関に関する情報を含む第２のデータ構造（２３２、６００）を生成するステップと、
前記第１及び第２のデータ構造（２３１、５００、２３２、６００）を検索クエリ処理のために格納するステップと、
を含む、方法。
【請求項１０】
前記索引付けの前に、索引付けされる各ブロック（１１０）の内容と、既に索引付けされたブロック（１１０）の内容とが比較される、請求項９に記載の方法。
【請求項１１】
前記ブロック（１１０）は、同一内容を有するブロック（１１０）が以前に索引付けされたことがない場合にのみ索引付けされる、請求項１０に記載の方法。
【請求項１２】
前記各ブロック（１１０）について、前記ブロック・データのハッシュ値が生成され、格納される、請求項９乃至請求項１１のいずれか１項に記載の方法。
【請求項１３】
ブロック（１１０）に索引付けすることの決定が、現行ブロック（１１０）の前記ハッシュ値と、以前に索引付けされたブロック（１１０）の前記ハッシュ値とに基づいて行われる、請求項１２に記載の方法。
【請求項１４】
少なくとも１つの検索ターム属性を有する検索タームを含む検索クエリを、複数の文書（１００）に対して実行するためのシステムであって、前記各文書（１００）は、ブロック（１１０）の集合に構造化されており、前記各ブロック（１１０）は、一意のブロックＩＤを含み、同一のブロック（１１０）は、同一のブロックＩＤに関連付けられており、前記システムは、
検索クエリを受け取るための入力インターフェース（２１０）と、
特定の検索ターム属性と少なくとも１つのブロックＩＤとの間の相関に関する情報を含む第１のデータ構造（２３１）を提供するリポジトリ（２３０）と、
ブロック（１１０）と文書（１００）との間の相関に関する情報を含む第２のデータ構造（２３２）を提供するリポジトリ（２３０）と、
データ処理コンポーネント（２２０）であって、
前記検索クエリを、前記第１のデータ構造（２３１）を少なくとも１つの検索ターム属性について検索することによって処理して、第１のクエリ応答をもたらし、
前記第１のクエリ応答を、前記第２のデータ構造（２３２）を用いて第２のクエリ応答にマッピングする、
ように構成された、
データ処理コンポーネント（２２０）と、
前記第２のクエリ応答を検索結果として返すように構成された出力インターフェース（２４０）と、
を含む、システム。
【請求項１５】
プロセッサにより実行されたときに前記プロセッサに請求項１乃至請求項８のいずれか１項に記載の方法を実行させるコンピュータ可読プログラム・コードを含む、コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に文書検索の分野に関する。より具体的には、本発明は、ブロック・レベル索引に基づいて文書レベルの検索クエリを実行するための方法に関する。
【背景技術】
【０００２】
複数の文書が同一内容のセクション、部分又は構成要素を含むということは、よくあることである。例えば、１つの電子メールが何回も返信又は転送されると、返信され又は転送された全ての電子メールには、元の送信された電子メールが含まれる。例えばｗｉｋｉ、ブログなどのソーシャル・メディアからの投稿においても同じことが起こる。添付ファイル又はＺＩＰファイルが添付された電子メールのような複合文書においては、サブ文書全体（例えば、添付ファイル又はＺＩＰ内のファイル）が、多数の異なる上位レベル文書（例えば、異なる電子メール又はＺＩＰファイル）によって共有されることがある。
【０００３】
同一内容部分を含む複数の文書を索引付けする場合、特に全文索引付けを行う場合には、複製された内容部分が複数回索引付けされることになるので、索引内の情報の冗長化、及び索引サイズの肥大化につながる。
【０００４】
文書内の複製されたブロックに関して非冗長的な索引表現を提供する技術は、同一ブロックの再解析及び索引付けに浪費されるコンピューティング能力と、索引を格納するためのリポジトリ、すなわち、例えばハード・ディスクなど任意の種類の永続的ストレージとを節約することができるので、非常に有用である。一方で、この技術は、文書をブロック・レベルではなく通常通りの文書レベルで検索するための手段、すなわち文書の部分の検索及び読出しを指向した手段を提供しなければならない。
【０００５】
従って、同一部分、特に同一テキスト部分を提示する文書、特にテキスト文書に対して検索クエリを実行するための、効率的でユーザフレンドリな方法を提供する必要性が存在する。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の実施形態の目的は、同一部分を含む文書に対して効率的でユーザフレンドリな方式で検索クエリを実行するための、方法、コンピュータ可読媒体及びシステムを提供することである。この目的は、独立請求項の特徴によって解決される。好ましい実施形態は従属請求項において与えられる。特段の指示がない限り、本発明の実施形態を互いに自由に組み合わせることができる。
【課題を解決するための手段】
【０００７】
第１の態様により、少なくとも１つの検索ターム属性を有する検索タームを含む検索クエリを、複数の文書に対して実行するための方法を説明する。各文書は、ブロックの集合に構造化され、各ブロックは、一意のブロックＩＤに関連付けられ、同一のブロックは、同一のブロックＩＤに関連付けられる。この方法は、以下の、
特定の検索ターム属性と少なくとも１つのブロックＩＤとの間の相関に関する情報を含む第１のデータ構造を準備するステップと、
ブロックと文書との間の相関に関する情報を含む第２のデータ構造を準備するステップと、
検索クエリを受け取るステップと、
検索クエリを、少なくとも１つの検索ターム属性について第１のデータ構造を検索することによって処理して、第１のクエリ応答を得るステップと、
第１のクエリ応答を、第２のデータ構造を用いて第２のクエリ応答にマッピングするステップと、
第２のクエリ応答を検索結果として返すステップと、
を含む。
【０００８】
第１のデータ構造は、ブロックに含まれるブロック・データ（これが検索タームの検索ターム属性となる）とブロックＩＤとの間の相関を含むブロック・レベル索引を提供する。同一のブロック・データを含む同一ブロックは、同一のブロックＩＤに関連付けられる。これにより、ブロックの内容は一度だけ索引付けされるので、索引を格納するための容量を削減することにつながる。検索クエリの処理は、第１のステップにおいてブロック・レベルで実行することができ、照会された検索ターム属性を含むゼロ又はそれより多くのブロックがもたらされる。受け取ったブロックは、第１のステップで調査されたブロックを含む文書を判定することによって、文書レベルの検索応答に変換することができる。これにより、同一ブロックを含む複数の文書に対して検索クエリを実行するための計算労力、及び索引を格納するためのストレージ容量を削減することができる。
【０００９】
更なる実施形態によれば、第１のデータ構造は、複数の索引エントリを含む索引であり、各索引エントリは、検索ターム内の検索ターム属性を形成することができる特定のブロック・データに関連付けられている。これにより、索引は、ブロック・データに関連付けられた特定のデータ、例えば、その検索ターム属性をブロック・データとして含むブロックＩＤ、ブロック内のブロック・データの頻度を示す頻度情報、又はブロック内のブロック・データの位置を示す位置データ、を格納するように構成することができる。
【００１０】
更なる実施形態によれば、索引の各エントリは、それぞれの索引エントリに関連付けられたブロック・データ（又は検索ターム用語に従えば検索ターム属性）がそのブロックＩＤを有するブロック内に含まれていることを示す、少なくとも１つのブロックＩＤに関する情報を含む。これにより、第１のデータ構造は、検索ターム属性に関して検索可能であり、その検索ターム属性を含むブロックＩＤを判定することができる。
【００１１】
更なる実施形態によれば、第１のデータ構造は、各検索ターム属性について、ブロック内の検索ターム属性の位置に関する、及び／又は、特定のブロック内の検索ターム属性の出現頻度に関する、付加的な情報を含む。
【００１２】
更なる実施形態によれば、第２のデータ構造は、どのブロックがどの文書に含まれているかに関する情報、及び／又は、どの文書がどのブロックから成るものであるかに関する情報を提供するリストである。別の言い方をすれば、第２のデータ構造は、ブロックと文書との間のマッピング情報を含む補助データ構造である。第２のデータ構造によって、ブロック−文書の関連付けを導出することができる。第２のデータ構造は、ブロックと文書との間の相関を定義する第１のデータ・セットと、文書とブロックとの間の相関を定義する第２のデータ・セットとを含む、双方向データ構造であることが好ましい。
【００１３】
更なる実施形態によれば、検索クエリを処理するステップは、検索クエリの構造及び論理演算子を解析し、処理時間を短縮するために処理を最適化する、解析ステップを含む。解析ステップは、ブロック・レベルのみで処理することが可能な、すなわちブロック・レベルの結果を文書レベルの結果にマッピングせずに処理することが可能な、検索タームの少なくとも１つのサブタームを判定することができる。好ましくは、解析ステップは、ブロック・レベルで直接処理することができる「ｏｒ」演算子又は「ｎｅａｒｂｙ」演算子を判定するように構成することができる。
【００１４】
更なる実施形態によれば、検索クエリは、論理演算子によって連結された複数の検索ターム属性から成り、このとき、論理演算子に応じて、検索クエリの少なくともサブセットが第１のデータ構造のみを使用してブロック・レベルで処理される。「ｏｒ」演算子を含む少なくとも１つのサブタームが判定されることが好ましい。少なくとも１つのサブタームの判定後、そのサブタームは、ブロック・レベルで処理される。具体的には、第１のデータ構造内で２つの検索ターム属性（例えば「ｏｒ」演算子で連結されているもの）を照会し、その結果、各集合が１つの検索ターム属性と相関する２つのブロック集合を得る。その後、２つのブロック集合は、これら２つのブロック集合に対して「ｏｒ」演算子を適用することにより統合されて単一のブロック集合にされる。これにより、該サブタームが完全にブロック・レベルで処理される。
【００１５】
更なる実施形態によれば、検索クエリ内の論理演算子に応じて２つの検索結果が生成され、第１の検索結果は、第１のデータ構造を用いたブロック・レベルの検索クエリ処理の結果得られる、数が減らされた検索ヒットを含み、第２の検索結果は、第１のデータ構造を用いたブロック・レベルと第２のデータ構造を用いた文書レベルとの連続した処理の結果得られる、全量の検索ヒットを含む。この処理は、好ましくは「ａｎｄ」演算を処理するために適用することができる。第１の検索結果は、個々のブロックのみを考慮して、すなわち文書レベルへのマッピングを何ら行うことなく生成することができる。その後で又は同時に、第２の検索結果を生成することができる。第２の検索結果は、第１のデータ構造を使用することにより２つのブロック集合を判定し、これらブロック集合を第２のデータ構造によって文書集合にマッピングし、これら２つの文書集合に対して論理演算子（好ましくは「ａｎｄ」演算子）を適用することによってこれら２つの文書集合を統合することにより、検索クエリの全てのヒットを含むものとすることができる。これにより、それぞれのブロック内で互いに近くに位置する検索ターム属性を含む限られた数の検索ヒットを含む、迅速な第１の検索結果を達成することができる。その後、全ての検索ヒットを含む第２の検索結果が返される。
【００１６】
更なる実施形態により、少なくとも部分的に同一のブロックを含む文書を検索するためのデータ構造を生成する方法を説明する。本方法は、以下の、
文書を受け取るステップと、
受け取った文書内のブロックを定義し、各ブロックに一意のブロックＩＤを割り当てるステップであって、同一のブロックが同一のブロックＩＤに関連付けられる、ステップと、
定義されたブロックに索引付けし、ブロック・データと該ブロック・データを含むブロックＩＤとの間の相関に関する情報を含む第１のデータ構造を生成するステップと、
ブロックと文書との間の相関に関する情報を含む第２のデータ構造を生成するステップと、
第１及び第２のデータ構造を検索クエリ処理のために格納するステップと、
を含む。
【００１７】
上記の方法を実施することにより、文書をブロック・レベルで検索し、ブロック・レベル検索で得られた結果を統合して文書レベル検索の結果にするために用いることができる、データ構造のセットを生成することができる。第１のデータ構造の主な利点は、同一のブロックには一度しか索引付けされないこと、すなわち、文書に索引付けを行う計算労力、及び索引を格納するためのストレージが削減されることである。
【００１８】
更なる実施形態によれば、索引付けの前に、索引付けされる各ブロックの内容と、既に索引付けされたブロックの内容とが比較される。ブロックは、同一内容を有するブロックが以前に索引付けされたことがない場合にのみ索引付けされることが好ましい。これにより、同一内容を含むブロックに重複して索引付けすることを回避することができる。
【００１９】
更なる実施形態によれば、各ブロックについて、ブロック・データのハッシュ値が生成され、格納される。ハッシュ値は、ブロックの全内容にハッシュ関数を適用することで導出することができる。ハッシュ値を用いることにより、索引付けされる新たなブロックと既に索引付けされたブロックとの内容の比較が簡単になる。ブロックに索引付けすることの決定は、索引付けされる現行ブロックのハッシュ値と以前に索引付けされたブロックのハッシュ値とに基づいて行われることが好ましい。ハッシュ値が同一であればブロックの内容もまた同一であり、従って索引付けを行う必要はない。ハッシュ値が同一でない場合には、そのブロックに索引付けする必要があり、第１のデータ構造は更新される必要がある。
【００２０】
更なる態様により、少なくとも１つの検索ターム属性を有する検索タームを含む検索クエリを、複数の文書に対して実行するためのシステムを説明する。各文書は、ブロックの集合に構造化されており、各ブロックは、一意のブロックＩＤを含み、同一のブロックは、同一のブロックＩＤに関連付けられる。このシステムは、
検索クエリを受け取るための入力インターフェースと、
特定の検索ターム属性と少なくとも１つのブロックＩＤとの間の相関に関する情報を含む第１のデータ構造を提供するリポジトリと、
ブロックと文書との間の相関に関する情報を含む第２のデータ構造を提供するリポジトリと、
データ処理コンポーネントであって、
検索クエリを、第１のデータ構造を少なくとも１つの検索ターム属性について検索することにより処理して、第１のクエリ応答をもたらし、
第１のクエリ応答を、第２のデータ構造を用いて第２のクエリ応答にマッピングする、
ように構成されたデータ処理コンポーネントと、
第２のクエリ応答を検索結果として返すように構成された出力インターフェースと、
を含む。
【００２１】
更なる実施形態によれば、システムは、処理を最適化するために検索クエリの構造及び検索クエリの論理演算子を解析する解析コンポーネントをさらに含む。解析コンポーネントは、ブロック・レベルのみで処理することが可能な、すなわちブロック・レベルの結果を文書レベルの結果にマッピングせずに処理することが可能な、検索タームの少なくとも１つのサブタームを判定するように構成することができる。好ましくは、解析器は、ブロック・レベルで直接処理することができる「ｏｒ」演算子又は「ｎｅａｒｂｙ」演算子を判定するように構成することができる。
【００２２】
更なる態様によれば、本発明は、プロセッサにより実行されたときにプロセッサに上述の方法を実行させるコンピュータ可読プログラム・コードが具体化されたコンピュータ可読媒体に関する。
【００２３】
以下、本発明の好ましい実施形態を添付の図面のみを参照して例示の目的で詳細に説明する。
【図面の簡単な説明】
【００２４】
【図１】複数のブロックを含む文書の例示的な略図を示す。
【図２】検索クエリを実行するためのシステムの例示的な略図を示す。
【図３】同一ブロックを含む文書に対して検索クエリを実行するためのデータ構造のセットを生成する例示的な概略フローチャートを示す。
【図４】検索クエリを実行する例示的な概略フローチャートを示す。
【図５】第１のデータ構造の例示的な略図を示す。
【図６】第２のデータ構造の例示的な略図を示す。
【図７】「ａｎｄ」検索クエリを処理する第１の実施形態の概略フローチャートを示す。
【図８】「ａｎｄ」検索クエリを処理する第２の実施形態の概略フローチャートを示す。
【図９】「ｏｒ」検索クエリを処理する第１の実施形態の概略フローチャートを示す。
【図１０】「ｏｒ」検索クエリを処理する第２の実施形態の概略フローチャートを示す。
【図１１】「ｎｏｔ」検索クエリを処理する概略フローチャートを示す。
【図１２】検索最適化ステップを伴う検索クエリを実行する概略フローチャートを示す。
【図１３】プッシュダウン最適化を伴わない検索クエリを実行する概略フローチャートを示す。
【図１４】プッシュダウン最適化を伴う検索クエリを実行する概略フローチャートを示す。
【図１５】プッシュダウン最適化を伴う検索クエリを実行する更なる例の概略フローチャートを示す。
【発明を実施するための形態】
【００２５】
当業者であれば理解するように、本開示の態様は、システム、方法又はコンピュータ・プログラム製品として具体化することができる。従って、本開示の態様は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）、又は、ソフトウェアの態様とハードウェアの態様とを組み合わせた実施形態の形を取ることができ、本明細書においてはこれらの全てを一般に、「回路」、「モジュール」又は「システム」と呼ぶことができる。さらに、本開示の態様は、コンピュータ可読プログラム・コードが組み入れられた１つ又は複数のコンピュータ可読媒体内として具体化されたコンピュータ・プログラム製品の形を取ることができる。
【００２６】
１つ又は複数のコンピュータ可読媒体の任意の組み合わせを用いることができる。コンピュータ可読媒体は、コンピュータ可読信号媒体又はコンピュータ可読ストレージ媒体とすることができる。コンピュータ可読ストレージ媒体は、例えば、電子、磁気、光学、電磁気、赤外線若しくは半導体のシステム、装置、若しくはデバイス、又は上記のもののいずれかの適切な組み合わせとすることができる。コンピュータ可読ストレージ媒体のより具体的な例（非網羅的なリスト）として、以下のもの：即ち、１つ又は複数の配線を有する電気的接続、ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、消去可能なプログラム可能読み出し専用メモリ（ＥＰＲＯＭ又はフラッシュ・メモリ）、光ファイバ、ポータブル・コンパクト・ディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）、光記憶装置、磁気記憶装置、又は上記のもののいずれかの適切な組み合わせが挙げられる。本明細書の文脈においては、コンピュータ可読ストレージ媒体は、命令実行システム、装置若しくはデバイスによって、又はこれらと関連して用いるためのプログラムを収容又は格納することができる任意の有形媒体とすることができる。
【００２７】
コンピュータ可読信号媒体は、例えばベースバンド内に、又は搬送波の一部として、具体化されたコンピュータ可読プログラム・コードをその中に有する、伝搬されるデータ信号を含むことができる。このような伝搬信号は、これらに限定されるものではないが、電磁気、光又はそれらのいずれかの適切な組み合わせを含む、種々の形態のいずれかを取ることができる。コンピュータ可読信号媒体は、コンピュータ可読ストレージ媒体ではなく、かつ、命令実行システム、装置若しくはデバイスによって、又はこれらと関連して用いるためのプログラムを伝達し、伝搬し、又は搬送することができる任意のコンピュータ可読媒体とすることができる。コンピュータ可読媒体上に具体化されたプログラム・コードは、これらに限定されるものではないが、無線、有線、光ファイバ・ケーブル、ＲＦ等、又は上記のもののいずれかの適切な組み合わせを含む、任意の適切な媒体を用いて伝送することができる。
【００２８】
本発明の態様の操作を実行するためのコンピュータ・プログラム・コードは、Ｊａｖａ、ＳｍａｌｌＴａｌｋ、Ｃ＋＋等のようなオブジェクト指向型プログラミング言語、及び、「Ｃ」プログラミング言語又は同様のプログラミング言語のような従来の手続き型プログラミング言語を含む、１つ又は複数のプログラミング言語のいずれかの組み合わせで記述することができる。プログラム・コードは、完全にユーザのコンピュータ上で実行される場合もあり、一部がユーザのコンピュータ上で、独立型ソフトウェア・パッケージとして実行される場合もあり、一部がユーザのコンピュータ上で実行され、一部が遠隔コンピュータ上で実行される場合もあり、又は完全に遠隔コンピュータ若しくはサーバ上で実行される場合もある。一番最後のシナリオにおいては、遠隔コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）若しくは広域ネットワーク（ＷＡＮ）を含むいずれかのタイプのネットワークを通じてユーザのコンピュータに接続される場合もあり、又は外部コンピュータへの接続が為される場合もある（例えば、インターネット・サービス・プロバイダを用いたインターネットを通じて）。
【００２９】
本開示の態様は、本開示の実施形態による方法、装置（システム）及びコンピュータ・プログラム製品のフローチャート図及び／又はブロック図を参照して説明される。フローチャート図及び／又はブロック図の各ブロック、並びにフローチャート図及び／又はブロック図内のブロックの組み合わせは、コンピュータ・プログラム命令によって実装できることが理解されよう。これらのコンピュータ・プログラム命令を、汎用コンピュータ、専用コンピュータ、又は他のプログラム可能データ処理装置のプロセッサに与えてマシンを製造し、それにより、コンピュータ又は他のプログラム可能データ処理装置のプロセッサによって実行される命令が、フローチャート及び／又はブロック図の１つ又は複数のブロック内で指定された機能／動作を実装するための手段を作り出すようにすることができる。
【００３０】
これらのコンピュータ・プログラム命令を、コンピュータ、他のプログラム可能データ処理装置、又は他のデバイスを特定の方式で機能させるように指示することができるコンピュータ可読媒体内に格納し、それにより、そのコンピュータ可読媒体内に格納された命令が、フローチャート及び／又はブロック図の１つ又は複数のブロックにおいて指定された機能／動作を実装する命令を含む製品を製造するようにすることもできる。
【００３１】
コンピュータ・プログラム命令を、コンピュータ、他のプログラム可能データ処理装置、又は他のデバイス上にロードして、一連の動作ステップをコンピュータ、他のプログラム可能データ処理装置、又は他のデバイス上で行わせてコンピュータ実施のプロセスを生成し、それにより、コンピュータ又は他のプログラム可能装置上で実行される命令が、フローチャート及び／又はブロック図の１つ又は複数のブロックにおいて指定された機能／動作を実行するためのプロセスを提供するようにすることもできる。
【００３２】
図面内のブロック図は、本開示の種々の実施形態による、システム、方法、及びコンピュータ・プログラム製品の可能な実装の、アーキテクチャ、機能及び動作を示す。この点に関して、ブロック図内の各ブロックは、指定された論理機能を実装するための１つ又は複数の実行可能命令を含む、モジュール、セグメント、又はコードの一部を表すことができる。幾つかの代替的な実装において、上記で論じられた機能は、開示された順序とは異なる順序で生じることがあることにも留意されたい。例えば、連続して教示された２つの機能は、関与する機能に応じて、実際には実質的に同時に実行されることもあり、又はこれらの機能はときとして逆順で実行されることもある。ブロック図の各ブロック、及びブロック図内のブロックの組み合わせは、指定された機能又は動作を実行する専用ハードウェア・ベースのシステム、又は専用のハードウェアとコンピュータ命令との組み合わせによって実装することができることにも留意されたい。
【００３３】
本明細書で用いられる用語は、特定の実施形態を説明するためのものにすぎず、本発明を限定することを意図したものではない。本明細書で用いられる場合、単数形「１つの（a）」、「１つの（an）」及び「その（the）」は、文脈が明らかにそうでないことを示さない限り、複数形も同様に含むことを意図したものである。「含む（comprise）」及び／又は「含んでいる（comprising）」という用語は、本明細書で用いられる場合、記述された特徴、整数、ステップ、操作、要素、及び／又は構成要素の存在を指定するが、１つ又は複数の他の特徴、整数、ステップ、操作、要素、構成要素、及び／又はこれらの群の存在又は付加を排除するものではないことがさらに理解されるであろう。
【００３４】
以下の特許請求の範囲における全ての「手段又はステップと機能との組み合わせ（ミーンズ又はステップ・プラス・ファンクション）」要素の対応する構造、材料、動作、及び均等物は、その機能を、明確に特許請求される他の特許請求された要素との組み合わせで実行するためのあらゆる構造、材料、又は動作を含むことが意図されている。本発明の説明は、例証及び説明を目的として提示されたものであり、網羅的であること又は本発明を開示された形態に限定することを意図したものではない。本発明の範囲及び趣旨から逸脱しない多くの修正及び変形が当業者には明らかとなるであろう。実施形態は、本発明の原理及び実際的用途を最も良く説明するために、そして、当業者が、企図した特定の用途に適した種々の修正を伴う種々の実施形態に関して本発明を理解できるように、選択され、説明された。
【００３５】
図１を参照すると、文書１００の略図が示されている。文書は、例えばテキスト文書とすることができる。文書は、複数の部分に区分化することができる。例えば、テキスト文書は、複数回にわたって返信又は転送された電子メールとすることができる。テキスト文書の一部分は、電子メール内で連結された単一の電子メール・メッセージとすることができる。以下、この文書の一部分をブロック１１０と呼ぶ。システム、例えば、電子メール・システム、又はツイッター、ｗｅｉｂｏなどのような他の通信プラットフォームは、複数の文書１００を格納することができ、ここで文書１００のサブセットは、同一内容のブロック１１０を含む。さらに、ブロックは、電子メールの添付ファイル、又は電子メールに添付されたｚｉｐファイル内の文書であってもよい。
【００３６】
図２は、検索クエリを実行するためのシステム２００を示す。システムは、検索クエリを受け取るための入力インターフェース２１０と、検索エンジン２２５を有するデータ処理コンポーネント２２０と、データ・リポジトリ２３０と、検索結果を返すための出力インターフェース２４０とを含む。入力インターフェース２１０が受け取った検索クエリを、データ処理コンポーネント２２０の検索エンジン２２５に転送することができる。データ処理コンポーネント２２０、具体的にはデータ処理コンポーネント２２０の検索エンジン２２５は、データ・リポジトリ２３０に接続することができる。データ処理コンポーネント２２０は、データ・リポジトリ２３０内に格納されたデータ構造のセットにアクセスすることができる。データ構造セットは、第１のデータ構造２３１及び第２のデータ構造２３２を提供することができる。第１のデータ構造２３１は、ブロック１１０内に含まれる、ブロック・データとも呼ばれるデータと、ブロックＩＤとの間の相関に関する情報を提供する索引とすることができる。ブロックＩＤは、ブロックの識別可能性を保証する、ブロックと相関する一意の属性とすることができる。全文索引付けの場合、ブロック・データは、ブロック内に含まれる単語とすることも、さらには単語群とすることもできる。別の言い方をすれば、第１のデータ構造２３１は、どのブロック・データがどのブロック（単数又は複数）に含まれているかに関する情報を提供するものであり、すなわち、第１のデータ構造２３１はブロック・レベル索引を提供する。
【００３７】
第２のデータ構造２３２は、ブロック１１０と文書１００との間の関連付けに関する情報を含む。第２のデータ構造２３２は、どのブロックがどの文書に含まれているかを指定する表を提供することができる。各ブロックは、ブロックＩＤで示すことができ、各文書は、一意の文書名で示すことができる。第２のデータ構造２３２は、どのブロックがどの文書に含まれているかという相関と、逆に、どの文書がどのブロックを含むかという相関とを含む、双方向ルックアップ表とすることができる。
【００３８】
少なくとも１つの検索ターム属性、例えば単語、を含む検索タームを含む検索クエリを受け取った後、検索エンジン２２５は、その検索ターム属性について第１のデータ構造２３１内を検索して、第１のクエリ応答を与えることができる。第１のクエリ応答は、そのブロックＩＤに関連付けられたブロック内に該検索ターム属性が含まれていたことを示す少なくとも１つのブロックＩＤを含むことができる。その後、ブロック・レベルから文書レベルへのマッピングを、第２のデータ構造２３２によって実行することができる。検索エンジン２２５は、第２のクエリ応答を受け取るために、第２のデータ構造２３２にアクセスして第１のクエリ応答を第２のデータ構造２３２に提供することができる。第１のクエリ応答は、その検索ターム属性を含むブロックＩＤを含むものとすることができる。ブロックと文書との間の相関、具体的にはブロックＩＤと文書名との間の相関を提供する第２のデータ構造２３２によって、その検索ターム属性を含む少なくとも１つの文書を得ることができる。別の言い方をすれば、第２のデータ構造２３２は、ブロック・レベルから文書レベルへのマッピングを実現する。照会されたブロックと相関する少なくとも１つの文書名が、第２のクエリ応答として、検索エンジン２２５に返される。最後に、この第２のクエリ応答が、検索結果として、出力インターフェース２４０に転送される。
【００３９】
システムは、索引付けエンジン２２６をさらに含むことができる。索引付けエンジン２２６は、データ処理コンポーネント２２０の一部とすることも、又は、独立したコンポーネントとすることもできる。索引付けエンジン２２６は、索引付けすべき文書を受け取ることができる。索引付けエンジン２２６は、受け取った文書内のブロックを識別するように構成することができる。ブロックは、電子メール本文の一部、例えば、単一の電子メールスレッド、又は１つの電子メール内で連結された単一の電子メール・メッセージ、電子メールに添付された文書、電子メールに添付されたＺＩＰファイルの文書など、とすることができる。ブロックを定義した後、同一のブロック内容を有するブロックを既に以前に索引付けしたかどうかを確認するために、チェックを行うことができる。チェックは、受け取った文書の全ブロックについて行うことができる。内容の同一性をチェックするためには、索引付けされるブロックの内容全体を、既に索引付けされたブロックの内容と比較しなければならない。索引付けされるブロックの内容のハッシュ値を計算し、既に索引付けされたブロックの内容のハッシュ値と比較することができることが好ましい。内容又は内容のハッシュ値が同一であれば、同一内容を有するブロックが以前に既に索引付けされているということなので、現行ブロックは索引付けされない。これにより、計算労力を削減することができる。
【００４０】
同一内容を有するブロックが以前に索引付けされたことがない場合、受け取った文書のブロックは、索引付けエンジン２２６によって索引付けされる。どのブロック・データ（例えば、単語又は語句）がそれぞれのブロック内に含まれるかを定義する全文索引を生成することができる。この索引付けの結果は、データ・リポジトリ２３０内の第１のデータ構造２３１内に格納することができる。さらにまた、第２のデータ構造２３２を、受け取った文書にどのブロックが含まれていたかに関する情報で更新することができる。別の言い方をすれば、ブロックと文書との間のマッピングに関する情報を更新することができる。更新された第１及び第２のデータ構造に基づいて、新たな文書に対して検索クエリを実行することができる。
【００４１】
図３は、少なくとも部分的に同一のブロックを含む文書を検索するためのデータ構造を生成する／更新するプロセス３００を示す。最初に、文書を受け取ることができる（ステップ３１０）。文書内のブロックを識別するために文書を構文解析することができる（ステップ３２０）。既に前述のとおり、ブロックは、文書の一部、電子メールに添付されたファイル、電子メールに添付されたｚｉｐフォルダ内のファイル等、とすることができる。識別したブロックをさらに処理する前に、既に索引付けされたブロックが利用できるかどうかを判定するために、チェックステップ３３０を実行することができる。利用できる既に索引付けされたブロックが存在しない場合には、プロセスを後述するステップ３６０で続行することができる。利用できる既に索引付けされたブロックが存在する場合には、受け取った文書内の定義された各々のブロックは、既に索引付けされたブロックに対するその内容の同一性に関してチェックされる（ステップ３４０）。別の言い方をすれば、受け取った文書内の識別された各ブロックの内容が、既に索引付けされた各ブロックの内容と比較される。内容の同一性をチェックするためには、索引付けされるブロックの内容全体を、既に索引付けされたブロックの内容と比較しなければならない。この比較ステップを行うための計算労力を減らすために、以下でブロック識別子とも呼ばれる、ブロック内容のハッシュ値を計算し、既に索引付けされたブロックの内容のハッシュ値、すなわちブロック識別子と比較することができる。ブロック識別子を使用すると、新たなブロックのハッシュ値を以前に索引付けされたブロックのハッシュ値と比較することが必要とされるのみである。同一内容を有するブロックが以前に索引付けされたことがない場合（ステップ３５０）、一意のブロックＩＤがそのブロックに割り当てられる（ステップ３６０）。ブロックＩＤは、ブロック識別子と同一にすることも、又はブロックを識別するための別個の属性とすることもできる。既に前述したとおり、ブロックＩＤを割り当てるこのステップは、既に索引付けされたブロックが利用できなかった場合（ステップ３３０）にも行われる。
【００４２】
図３の実施形態によれば、ブロックは、ブロックＩＤと相関付けされた後で索引付けされる（ステップ３７０）。あるいは、ブロックは、該ブロックを索引付けした後でブロックＩＤと関連付けることができる。索引付けステップは、索引付けエンジンによって、好ましくはテキスト索引付けエンジンによって、行うことができる。索引付けエンジンは、ブロックを構文解析し、どのブロック・データがブロック内で利用可能であるのかを解析するように構成することができる。別の言い方をすれば、索引付けエンジンは、ブロック・データの索引、好ましくはブロックの全文索引を生成するように構成される。索引付け後、索引付け結果を第１のデータ構造に転送することができる。以前に第１のデータ構造が（ブロックの索引付けを行うのが初回であるゆえに）作成されていなかった場合には、第１のデータ構造を生成することができる。それ以外の場合には、既存の第１のデータ構造を現に索引付けされたブロックのデータで更新することができる（ステップ３８０）。第１のデータ構造は、ブロック・データと該ブロック・データを含むブロックとの間の関連付けを含むことができる。具体的には、第１のデータ構造は、単語又は語句と、ブロックＩＤ又はブロック識別子との間の関連付けを含むことができる。従って、本の目次が見出し語（hit word）と本の頁又は段落との間の関連付けを含んでいるのと同様に、第１のデータ構造は、どのブロック・データがどのブロック（単数／複数）内に含まれているかを示すエントリを含むことができる。
【００４３】
第１のデータ構造を生成／更新した後で、第２のデータ構造を生成（第２のデータ構造が存在しない場合）又は更新（既存の第２のデータ構造が存在する場合）することができる（ステップ３９０）。第２のデータ構造は、ブロックと文書との間の関連付けを含み、どのブロックがどの文書（単数／複数）に含まれているかを示している。従って、特定のブロック・データ（例えば、検索タームの単語）が特定のブロック内に含まれていることを識別した後、第２のデータ構造により、そのブロックを含む文書を判定することが可能となる。別の言い方をすれば、第２のデータ構造を使用することで、検索タームの少なくとも一部が含まれているブロックを示す第１のクエリ応答を、そのブロックを含む少なくとも１つの文書を示す第２のクエリ応答にマッピングすることが可能である。さらに別の言い方をすれば、第２のデータ構造は、ブロック・レベルのクエリ応答を文書レベルのクエリ応答にマッピングすることを可能にする補助的データ構造である。
【００４４】
最後に、第１及び第２のデータ構造は、検索クエリ処理のためにリポジトリ内に格納される。第１及び第２のデータ構造は、同じリポジトリ内に格納することも、又は異なるリポジトリ内に格納することもできる。このリポジトリは、検索クエリを実行するデータ処理コンポーネントによるアクセスが可能なものとすることができる。
【００４５】
図４は、検索クエリを実行するための基本構造を示す。検索クエリは、少なくとも１つの検索ターム属性を有する検索タームを含むことができる。検索タームは、単一の検索ターム属性のみを含むことも、又は、論理演算子によって連結された複数の検索ターム属性を含むこともできる。検索クエリによって、複数の文書が、検索タームがそれらの文書内に含まれているかどうかを判定するために解析されることになろう。例えば、検索ターム属性は、単語又は語句とすることができる。プロセスの開始後、検索エンジンによって検索クエリを受け取ることができる（ステップ４１０）。検索クエリは、検索タームを含むことができる。第１のデータ構造に基づくブロック・レベル検索を実行することができる（ステップ４２０）。検索エンジンは、どのブロックがその検索タームを含むか識別するために第１のデータ構造にアクセスすることができる。例えば、第１のデータ構造は、複数のエントリを含む表とすることができる。各エントリは、特定のブロック・データ、例えば単語又は語句と関連付けられたものとすることができる。第１のデータ構造によって、ブロック・データを、どのブロックが該ブロック・データを含むかに関する情報と相関させることができる。第１のデータ構造にアクセスした結果として、そのブロックＩＤ又はブロック識別子を有するブロックが該検索タームを含むことを示す少なくとも１つのブロックＩＤ又はブロック識別子を返すことができる。
【００４６】
ブロック・レベル検索を実行した後、受け取ったブロック・レベル検索結果は、第２のデータ構造にアクセスすることにより文書レベルの検索結果にマッピングされる（ステップ４３０）。既に前述のとおり、第２のデータ構造は、ブロックと文書との間の関連付けを含み、どのブロック（ブロックＩＤ又はブロック識別子により識別される）がどの文書内に含まれているかを示す。その結果として、少なくとも１つの文書（文書名又は文書識別子により識別される）が返される。この少なくとも１つの文書を最終検索結果として返すことができる（ステップ４４０）。
【００４７】
図５は、第１のデータ構造５００の例を示す。第１のデータ構造は、行及び列を有する表として編成することができる。例えば、第１のデータ構造は、ブロック・データ、具体的には単語又は語句を示す第１列５１０と、ブロックＩＤを示す第２列５２０と、補助情報を収容した第３列とを含む。補助情報は、例えば、特定のブロック内のブロック・データの頻度、又はブロック内のブロック・データの位置とすることができる。例えば、図５によるリスト内の最初の行は、ブロック・データ「Ｋ１」が、ブロックＩＤ「Ｂ２」及び「Ｂ５」のブロック内に含まれることを示す。補助情報「Ｂ２，１，１」は、ブロック・データ「Ｋ１」がブロック「Ｂ２」内に頻度「１」（頻度インジケータ、例えば、１回、２回…）で、位置「１」（位置インジケータ）に含まれていることを示す
【００４８】
図６は、第２のデータ構造６００の例を示す。第２のデータ構造６００は、どのブロックがどの文書に含まれているかという情報と、逆に、どの文書がどのブロックを含むかという情報とを含む双方向データ構造であることが好ましい。従って、第２のデータ構造は、２つのセクション６００ａ、６００ｂに細分され、第１のセクション６００ａは、特定の文書ＩＤとブロックＩＤとの間の関係を含み、第２のセクション６００ｂは、特定のブロックＩＤと文書ＩＤとの間の関係を含む。
【００４９】
従って、第２のデータ構造６００の第１のセクション６００ａは、文書ＩＤを示す第１列６１０ａと、ブロックＩＤを示す第２列６２０ａと、付加的な補助情報を示す第３列６３０ａとを含む表とすることができる。付加的な補助情報は、例えばブロック・インジケータとすることができる。ブロック・インジケータは、ブロックの内容にハッシュ関数を適用することにより生成されるブロックのハッシュ値とすることができる。ブロック・インジケータは、ブロックの内容を比較して、同一のブロック内容を有するブロックが以前に索引付けされているか又は処理されているかどうかを判定するために用いることができる。
【００５０】
第２のセクション６００ｂもまた、幾つかの列を含む表とすることができ、第１列６１０ｂは、ブロックＩＤを示し、第２列６２０ｂは、文書ＩＤを示し、第３列６３０ｂは、付加的な補助情報を示す。
【００５１】
図７は、論理演算子「ＡＮＤ」を含む検索クエリの処理７００を示す。検索クエリ「Ｔ１  ａｎｄ  Ｔ２」を受け取った（ステップ７１０）後、ここでＴ１及びＴ２が特定のブロック・データ、例えば単語又は語句であると、検索クエリは、幾つかのサブターム又は検索ターム属性、すなわち検索ターム属性Ｔ１及び検索ターム属性Ｔ２に分割又は細分化される。各検索ターム属性に対して、別個のサブクエリを実行することができる。サブクエリは、連続的に又は同時に処理することができる。
【００５２】
ステップ７２０ａにおいて、検索ターム属性「Ｔ１」を含む全てのブロックが第１のデータ構造に基づいて判定される。続いて、第２のデータ構造に基づいて、検索ターム属性「Ｔ１」を含んでいるブロックを含む文書が調査される（ステップ７３０ａ）。ステップ７２０ａ及び７３０ａが第１のサブクエリを形成する。
【００５３】
同様に、ステップ７２０ｂにおいて、検索ターム属性「Ｔ２」を含む全てのブロックが第１のデータ構造に基づいて判定される。続いて、第２のデータ構造に基づいて、検索ターム属性「Ｔ２」を含んでいるブロックを含む文書が調査される（ステップ７３０ｂ）。ステップ７２０ｂ及び７３０ｂが第２のサブクエリを形成する。
【００５４】
ステップ７４０において、第１及び第２のサブクエリの結果が統合される。ステップ７３０ａ及び７３０ｂは、文書の集合を返す。受け取った２つの文書集合は、これら文書集合に対してＡＮＤ演算を適用することによって統合される。別の言い方をすれば、７４０の結果得られる文書リストは、第１及び第２のサブクエリの結果得られるどちらの文書リストにも含まれている文書のみを含む。統合された文書リストを検索結果として返すことができる。
【００５５】
図８は、論理演算子「ＡＮＤ」を含む検索クエリの代替的な処理８００を示す。検索クエリ「Ｔ１  ａｎｄ  Ｔ２」を受け取った（ステップ８１０）後、ここでＴ１及びＴ２が特定のブロック・データ、例えば単語又は語句であると、プロセスは、２つのフェーズ、すなわちフェーズＩ及びフェーズＩＩに分割される。これらフェーズは、連続的に（好ましくはフェーズＩを先に）又は同時に実行することができる。フェーズＩにおいて、検索ターム「Ｔ１  ａｎｄ  Ｔ２」はブロック・レベルのみで実行され、すなわち、全ての個々のブロックに対して実行されるが、特定の文書の全てのブロックにわたっての実行はなされない（ステップ８２０）。別の言い方をすれば、第１のデータ構造に登録された各ブロックは、そのブロックにタームＴ１及びＴ２が含まれている場合にチェックされる。これにより、条件「Ｔ１  ａｎｄ  Ｔ２」を満たすブロックの集合が得られる。ステップ８３０により、第２のデータ構造に基づいて、このブロック集合内のブロックを含む文書が調査される。従って、フェーズＩによる処理を用いると、検索タームを満たす文書の縮小された集合のみが得られ、該集合内の各文書は、少なくとも１つのブロック内に検索タームを含んでいる。例えば、第１のブロックに「Ｔ１」を含み、かつ、第２のブロックに「Ｔ２」を含むような文書は、見いだされない。
【００５６】
フェーズＩＩの処理（ステップ８２０ａ、８２０ｂ、８３０ａ、８３０ｂ、８４０）は、上記のステップ７２０ａ、７２０ｂ、７３０ａ、７３０ｂ、７４０の処理と同一である。検索クエリに要求される精度及び速度に応じて、迅速な検索結果を得るためにフェーズＩを最初に処理することができる。フェーズＩ及びフェーズＩＩの同時処理も可能であり、この場合、フェーズＩにより得られる結果の方が、処理労力が低いのでより迅速に受け取られる。
【００５７】
図９は、論理演算子「ＯＲ」を含む検索クエリの処理の第１の実施形態９００を示す。検索クエリ「Ｔ１  ｏｒ  Ｔ２」を受け取った（ステップ９１０）後、検索タームは、２つの検索ターム属性「Ｔ１」、「Ｔ２」に分割される。続いて、各検索ターム属性が個々にブロック・レベルで処理され、すなわち「Ｔ１」、「Ｔ２」をそれぞれ満たす各ブロックが判定される（ステップ９２０ａ、９２０ｂ）。これにより、第１の集合が検索ターム属性「Ｔ１」を満たし、第２の集合が検索ターム属性「Ｔ２」を満たす、２つのブロック集合を受け取る。ブロックを判定した後、検索タームの論理演算子を使用することにより、すなわち「ｏｒ」演算子を使用することにより、第１及び第２の集合が統合される。従って、結果として得られる集合は、「Ｔ１  ｏｒ  Ｔ２」を含んでいる全てのブロックを含む（ステップ９３０）。最後に、ブロックの集合は、第２のデータ構造を用いて文書の集合に変換される。これにより、検索ターム「Ｔ１  ｏｒ  Ｔ２」を含む文書の集合を受け取る（ステップ９４０）。
【００５８】
図１０は、論理演算子「ＯＲ」を含む検索クエリの処理の第２の実施形態１０００を示す。検索クエリ「Ｔ１  ｏｒ  Ｔ２」を受け取った（ステップ１０１０）後、検索タームは幾つかの検索ターム属性には分割されず、検索ターム全体がブロック・レベルにプッシュダウンされ、すなわち、検索ターム全体が各ブロックに適用される。論理演算子で連結された少なくとも２つの検索ターム属性を完全にブロック・レベルで処理することを、以下、プッシュダウン・クエリと呼ぶ。これにより、検索ターム属性「Ｔ１  ｏｒ  Ｔ２」を満たすブロックの集合が判定される（ステップ１０２０）。最後に、ブロックの集合は、第２のデータ構造を用いて文書の集合に変換される。これにより、検索ターム「Ｔ１  ｏｒ  Ｔ２」を含む文書の集合を受け取る（ステップ１０３０）。このようなプッシュダウン・クエリは、処理性能がより高いので有益である。図１５との関連で後述するように、プッシュダウン・クエリは、幾つかの「ｏｒ」演算子を含むより複雑な検索タームにも適用することができる。
【００５９】
図１１は、論理演算子「ＮＯＴ（否定）」を含む検索クエリの処理１１００を示す。検索クエリ「ＮＯＴ  Ｔ１」を受け取った（ステップ１１１０）後、ターム「Ｔ１」を含む全てのブロックが第１のデータ構造によって判定される（ステップ１１２０）。「Ｔ１」を含むブロックの集合が判定された後で、該ブロックと相関する文書、すなわち該ブロックを含む文書が判定される（ステップ１１３０）。ステップ１１３０の結果は、検索クエリ「ｎｏｔ  Ｔ１」の応答として返されることになる文書の反転集合を含む中間結果である。検索クエリ「ｎｏｔ  Ｔ１」の正しい応答を得るには、ステップ１１３０の結果として返される文書の集合を反転しなければならない（ステップ１１４０）。別の言い方をすれば、検索クエリ「ｎｏｔ  Ｔ１」の最終結果は、ステップ１１３０の中間結果の中に含まれていない全ての文書を含む。これにより、検索ターム「ｎｏｔ  Ｔ１」を満たす文書の集合を受け取る。
【００６０】
図１２は、図４に示される検索クエリ処理４００を最適化する検索クエリ処理１２００の更に詳細なフローチャートを示す。検索クエリを受け取った（ステップ１２１０）後、検索クエリの処理速度、処理労力をそれぞれ向上させるために最適化解析を実施する（ステップ１２２０）。具体的には、検索タームが複数の論理演算子を含む場合、ブロック・レベルで得られた結果を文書レベルの結果に変換せずにブロック・レベルで処理することが可能なサブタームが調査される。サブタームは、例えば、ｏｒ演算子（また、複数の連結されたｏｒタームも）又はｎｅａｒ−ｂｙ演算子を含むタームとすることができる。最適化が可能である場合（ステップ１２３０）、最適化可能なサブタームは、文書レベルへの中間的マッピングを行うことなくブロック・レベルで処理される（ステップ１２４０）。ブロック・レベルの結果を得た後、ブロック・レベルで得られた結果は、文書レベルの検索結果にマッピング又は変換される（ステップ１２５０）。別の言い方をすれば、ステップ１２４０により、少なくとも論理演算子による２つの検索ターム属性の連結を含む検索ターム又はサブタームのブロックが、文書レベルへマッピングすることなくブロック・レベルで一挙に処理され、これにより処理性能が向上する。
【００６１】
最適化が可能でない場合、検索ターム内の各々の単一タームが、ブロック・レベルで処理され（ステップ１２６０）、文書レベルにマッピングされる（ステップ１２７０）。単一の検索ターム属性を連結する論理演算子を、文書レベルの検索結果に適用することができる（ステップ１２８０）。最後に、検索クエリの結果を返すことができる（ステップ１２９０）。
【００６２】
図１３及び図１４は、図５に示された第１のデータ構造及び図６に示された第２のデータ構造に基づいた、検索ターム（（Ｋ１  ｏｒ  Ｋ２）ａｎｄ  Ｋ３）ａｎｄ（ｎｏｔ  Ｋ４）の処理を示す。図１３では最適化解析が行われていないのに対し、図１４は、最適化ステップ実行後の検索ターム処理を示す。図１３によれば、検索ターム属性「Ｋ１」及び「Ｋ２」を含むブロックが判定される。「Ｋ１」は、ブロックＢ２及びＢ５に含まれ、一方「Ｋ２」は、ブロックＢ３及びＢ４に含まれる。それぞれのブロックを調査した（第１のクエリ応答）後、それぞれのブロックを含んでいる文書が判定され、それにより２つの文書集合を受け取る（Ｄ１，Ｄ２，Ｄ３；Ｄ１，Ｄ２，Ｄ３）。これら２つの文書集合を、論理演算子「ＯＲ」を用いることにより組み合わせて、それにより１つの文書集合をサブターム「Ｋ１  ｏｒ  Ｋ２」の第２のクエリ応答として受け取る。同様に、検索ターム属性「Ｋ３」を含むブロック（Ｂ１，Ｂ２）が、第１のデータ構造によって判定され、第２のデータ構造を用いて１つの文書集合（Ｄ１，Ｄ２，Ｄ３）にマッピングされる。さらに続けて、得られた文書集合（Ｄ１，Ｄ２，Ｄ３；Ｄ１，Ｄ２，Ｄ３）を「ａｎｄ」演算子を用いて組み合わせる。その後、サブターム「ｎｏｔ  Ｋ４」が処理される。検索ターム属性「Ｋ４」は、ブロックＢ４に含まれており、ブロックＢ４は、文書Ｄ２及びＤ３に含まれている。従って、ターム「ｎｏｔ  Ｋ４」は、文書Ｄ１のみを含む文書リストを返す。最後に、文書リスト（Ｄ１，Ｄ２，Ｄ３）及び（Ｄ１）に「ａｎｄ」演算子が適用され、文書Ｄ１を返すクエリ応答が得られる。
【００６３】
図１３との関連で説明される処理とは対照的に、図１４は、文書レベルにマッピングせずにブロック・レベルで直接処理することが可能な検索クエリの部分を判定することにより、検索クエリ処理を最適化する。最適化ステップを実行することにより、ブロック・レベルで全体として取り扱うことが可能なサブターム「Ｋ１  ｏｒ  Ｋ２」を検出することができ、すなわち、検索ターム属性「Ｋ１」及び「Ｋ２」を含むブロックを判定することで得られた結果のブロック・リストに対して「ｏｒ」論理演算子を適用することが可能である。これによりブロック・リスト（Ｂ２，Ｂ３，Ｂ４，Ｂ５）が得られ、このブロック・リストが第２のデータ構造によってマッピングされて文書リスト（Ｄ１，Ｄ２，Ｄ３）になる。従って、図１３及び図１４によるサブターム「Ｋ１  ｏｒ  Ｋ２」の処理を比較すると、ブロック・レベルと文書レベルとの間のマッピングは一度だけ行えばよい。
【００６４】
図１５は、図５に示された第１のデータ構造及び図６に示された第２のデータ構造に基づく、検索ターム（Ｋ１  ｏｒ  Ｋ２）ｏｒ  Ｋ３）ａｎｄ（ｎｏｔ  Ｋ４）の処理を示す。図１５に示す処理木の左分岐は２つの「ｏｒ」演算のカスケードを含み、これは、単一のプッシュダウン・クエリによって処理することも可能である。別の言い方をすれば、２つのカスケード式「ｏｒ」演算を全体としてブロック・レベルで行い、その結果ブロック・リスト（Ｂ１，Ｂ２，Ｂ３，Ｂ４，Ｂ５）が得られ、このブロック・リストが最終的に、検索タームの更なる処理のために文書レベル（Ｄ１，Ｄ２，Ｄ３）にマッピングされる。
【符号の説明】
【００６５】
１００：文書
１１０：ブロック
２００：システム
２１０：入力インターフェース
２２０：データ処理コンポーネント
２３０：データ・リポジトリ
２４０：出力インターフェース
５００：第１のデータ構造
６００：第２のデータ構造
６００ａ：第１のセクション
６００ｂ：第２のセクション
【図１】
2015109078.tif 000003
【図２】
2015109078.tif 000004
【図３】
2015109078.tif 000005
【図４】
2015109078.tif 000006
【図５】
2015109078.tif 000007
【図６】
2015109078.tif 000008
【図７】
2015109078.tif 000009
【図８】
2015109078.tif 000010
【図９】
2015109078.tif 000011
【図１０】
2015109078.tif 000012
【図１１】
2015109078.tif 000013
【図１２】
2015109078.tif 000014
【図１３】
2015109078.tif 000015
【図１４】
2015109078.tif 000016
【図１５】
2015109078.tif 000017