(57)【特許請求の範囲】
【請求項１】
分散された文書集合が、各担当する文書集合として、単語の出現位置情報とともに格納される複数の転置インデクスと、前記複数の転置インデクスに対して木構造状に配置された複数の句シグネチャと、前記複数の転置インデクスに対して木構造状に配置された複数の近接シグネチャと、入力された検索語を含む文書を検索する検索手段と、前記検索手段の検索結果を統合する検索結果統合手段とを備え、
前記複数の句シグネチャのうち、上位の句シグネチャには、下位の複数個の句シグネチャの配下の転置インデクスのいずれかに、当該転置インデクスが担当する文書中に２つの語が句として出現するか否かが記録され、下位の句シグネチャには、転置インデクスのいずれかに、当該転置インデクスが担当する文書中に２つの語が句として出現するか否かが記録され、
前記複数の近接シグネチャのうち、上位の近接シグネチャには、下位の複数個の近接シグネチャの配下の転置インデクスのいずれかに、当該転置インデクスが担当する文書中に２つの語どうしが設定された距離だけ離れて出現するか否かが記録され、下位の近接シグネチャには、転置インデクスのいずれかに、当該転置インデクスが担当する文書中に２つの語どうしが設定された距離だけ離れて出現するか否かが記録され、
入力された検索語について、検索語を構成する２つの語が句として出現するか否かを検索するときに、前記検索手段は、前記複数の句シグネチャのうち、上位の句シグネチャについて、当該句シグネチャの配下の転置インデクスに前記２つの語が句として出現するか否かを調査し、出現しない場合は下位の句シグネチャの調査を行なわず、
出現する場合は下位の句シグネチャについて前記調査を行い、当該下位の句シグネチャに前記２つの語が句として出現する場合にその句シグネチャの配下の転置インデクスを用いて検索を行い、前記検索結果統合手段は、前記検索結果を統合して出力し、
入力された検索語について、検索語を構成する２つの語どうしが設定された距離だけ離れて出現するか否かを検索するときに、前記検索手段は、前記複数の近接シグネチャのうち、上位の近接シグネチャについて、当該近接シグネチャの配下の転置インデクスに前記２つの語どうしが設定された距離だけ離れて出現するか否かを調査し、出現しない場合は下位の近接シグネチャの調査を行なわず、
出現する場合は下位の近接シグネチャについて前記調査を行い、当該下位の近接シグネチャに前記２つの語どうしが設定された距離だけ離れて出現する場合にその近接シグネチャの配下の転置インデクスを用いて検索を行い、前記検索結果統合手段は、前記検索結果を統合して出力することを特徴とする分散型文書検索装置。
【請求項２】
分散された文書集合が、各担当する文書集合として、単語の出現位置情報とともに格納される複数の転置インデクスと、前記複数の転置インデクスに対して木構造状に配置された複数の句シグネチャと、前記複数の転置インデクスに対して木構造状に配置された複数の近接シグネチャと、入力された検索語を含む文書を検索する検索手段と、前記検索手段の検索結果を統合する検索結果統合手段とを備え、
前記複数の句シグネチャのうち、上位の句シグネチャには、下位の複数個の句シグネチャの配下の転置インデクスのいずれかに、当該転置インデクスが担当する文書中に２つの語が句として出現するか否かが記録され、下位の句シグネチャには、転置インデクスのいずれかに、当該転置インデクスが担当する文書中に２つの語が句として出現するか否かが記録され、
前記複数の近接シグネチャのうち、上位の近接シグネチャには、下位の複数個の近接シグネチャの配下の転置インデクスのいずれかに、当該転置インデクスが担当する文書中に２つの語どうしが設定された距離だけ離れて出現するか否かが記録され、下位の近接シグネチャには、転置インデクスのいずれかに、当該転置インデクスが担当する文書中に２つの語どうしが設定された距離だけ離れて出現するか否かが記録された装置における分散型文書検索方法であって、
入力された検索語について、検索語を構成する２つの語が句として出現するか否かを検索するときに、
前記検索手段が、前記複数の句シグネチャのうち、上位の句シグネチャについて、当該句シグネチャの配下の転置インデクスに前記２つの語が句として出現するか否かを調査する第１の調査ステップと、
前記第１の調査ステップの調査の結果、出現しない場合は下位の句シグネチャの調査を行なわず、出現する場合は下位の句シグネチャについて前記調査を行う第２の調査ステップと、
前記第２の調査ステップの調査の結果、前記下位の句シグネチャに前記２つの語が句として出現する場合にその句シグネチャの配下の転置インデクスを用いて検索を行うステップと、
前記検索結果統合手段が、前記検索結果を統合して出力するステップと、
入力された検索語について、検索語を構成する２つの語どうしが設定された距離だけ離れて出現するか否かを検索するときに、
前記検索手段が、前記複数の近接シグネチャのうち、上位の近接シグネチャについて、当該近接シグネチャの配下の転置インデクスに前記２つの語どうしが設定された距離だけ離れて出現するか否かを調査する第３の調査ステップと、
前記第３の調査ステップの調査の結果、出現しない場合は下位の近接シグネチャの調査を行なわず、出現する場合は下位の近接シグネチャについて前記調査を行う第４の調査ステップと、
前記第４の調査ステップの調査の結果、前記下位の近接シグネチャに前記２つの語どうしが設定された距離だけ離れて出現する場合にその近接シグネチャの配下の転置インデクスを用いて検索を行うステップと、
前記検索結果統合手段が、前記検索結果を統合して出力するステップとを備えたことを特徴とする分散型文書検索方法。
【請求項３】
コンピュータを請求項１に記載の各手段として機能させる分散型文書検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書集合の中から利用者が入力した検索語を含むような文書を検索し出力する文書検索の装置、方法、プログラムに関するものである。
【背景技術】
【０００２】
文書集合を対象に、高速な検索を行うためには、従来より、転置インデクスと呼ばれる、単語をキーとしてその単語が出現するような文書の番号を記録した索引情報が広く利用されている。
【０００３】
さらに、さらに大規模な文書集合を対象に検索する場合、単一の計算機にはすべての文書集合を保持することが困難であるため、複数の計算機を用いる方法が知られている。これは、複数の計算機に配置された複数の転置インデクスを用い、各転置インデクスを用いて検索を行った結果を組合せることによって、大規模な文書集合を対象とした検索を実現するものである（非特許文献１参照）。
【０００４】
さて、検索語として複数のキーワードが入力された場合には、それぞれのキーワードを文書内に少なくともひとつ含むような文書の検索（ＡＮＤ検索）を実行することが一般的であるが、一方で、複数のキーワードを個別に扱うのではなく、検索語を句として含むような文書検索を行いたいという需要がある。さらに、近年、入力された複数のキーワードが文書中で互いに近接して出現する文書に対してより高いスコアを与えることにより、検索精度を高めることができることが注目を浴びている（非特許文献２参照）。
【０００５】
尚、本発明で利用することができるブルームフィルタの技術については、下記非特許文献３に記載されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】竹野浩、井上孝史、「分散型高速情報収集／全文検索システムＩｎ  ｆｏＢｅｅ／Ｅｖａｎｇｅｌｉｓｔ」、ＮＴＴ  Ｒ＆Ｄ、ｖｏｌ．５２、ｎｏ．２、２００３、ｐｐ７８−８４
【非特許文献２】Ｔａｏ，Ｔ．ａｎｄＺｈａｉ，Ｃ．“Ａｎ  Ｅｘｐｌｏｒａｔｉｏｎ  ｏｆ  Ｐｒｏｘｉｍｉｔｙ  Ｍｅａｓｕｒｅｓ  ｉｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｒｅｔｒｉｅｖａｌ”、ＳＩＧＩＲ  ２００７．ｐｐ２９５−３０２
【非特許文献３】Ｂｕｒｔｏｎ  Ｈ．Ｂｌｏｏｍ、“Ｓｐａｃｅ／Ｔｉｍｅ  Ｔｒａｄｅ−ｏｆｆｓ  ｉｎ  Ｈａｓｈ  Ｃｏｄｉｎｇ  ｗｉｔｈ  Ａｌｌｏｗａｂｌｅ  Ｅｒｒｏｒｓ”、Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ、Ｖｏｌｕｍｅ１３／Ｎｕｍｂｅｒ７／Ｊｕｌｙ、１９７０、ｐｐ４２２−４２６
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述の句の検索や近接性を考慮した検索を単純な転置インデクスのみを用いて行う場合、計算のための負荷が大きいという問題がある。
【０００８】
なぜなら、検索語を構成する各語が句として出現することを確認するためには、文書中で順序を保って隣接して出現することを確認する必要がある。このためには、句を構成する各語をキーとして得られる転置索引の値（転置リスト）を併合し、その結果のリストを逐次確認し、要求された順序で隣接して出現しているかどうかを確認する必要があるためである。
【０００９】
近接性の調査についても同様で、検索語を構成する各語が文書中で近接して出現することを確認すためには、句を構成する各語をキーとして得られる転置リストを併合し、その結果のリストを逐次確認し、近接して出現しているかどうかを確認する必要があり、計算のための負荷が大きい。
【００１０】
本発明は上記課題を解決するものであり、その目的は、転置インデクスへの参照回数を減らして検索時の計算負荷を軽減することができる分散型文書検索装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【００１１】
上記課題を解決するための請求項１に記載の分散型文書検索装置は、分散された文書集合が、各担当する文書集合として、単語の出現位置情報とともに格納される複数の転置インデクスと、前記複数の転置インデクスに対して木構造状に配置された複数の句シグネチャと、前記複数の転置インデクスに対して木構造状に配置された複数の近接シグネチャと、入力された検索語を含む文書を検索する検索手段と、前記検索手段の検索結果を統合する検索結果統合手段とを備え、
前記複数の句シグネチャのうち、上位の句シグネチャには、下位の複数個の句シグネチャの配下の転置インデクスのいずれかに、当該転置インデクスが担当する文書中に２つの語が句として出現するか否かが記録され、下位の句シグネチャには、転置インデクスのいずれかに、当該転置インデクスが担当する文書中に２つの語が句として出現するか否かが記録され、
前記複数の近接シグネチャのうち、上位の近接シグネチャには、下位の複数個の近接シグネチャの配下の転置インデクスのいずれかに、当該転置インデクスが担当する文書中に２つの語どうしが設定された距離だけ離れて出現するか否かが記録され、下位の近接シグネチャには、転置インデクスのいずれかに、当該転置インデクスが担当する文書中に２つの語どうしが設定された距離だけ離れて出現するか否かが記録され、
入力された検索語について、検索語を構成する２つの語が句として出現するか否かを検索するときに、前記検索手段は、前記複数の句シグネチャのうち、上位の句シグネチャについて、当該句シグネチャの配下の転置インデクスに前記２つの語が句として出現するか否かを調査し、出現しない場合は下位の句シグネチャの調査を行なわず、
出現する場合は下位の句シグネチャについて前記調査を行い、当該下位の句シグネチャに前記２つの語が句として出現する場合にその句シグネチャの配下の転置インデクスを用いて検索を行い、前記検索結果統合手段は、前記検索結果を統合して出力し、
入力された検索語について、検索語を構成する２つの語どうしが設定された距離だけ離れて出現するか否かを検索するときに、前記検索手段は、前記複数の近接シグネチャのうち、上位の近接シグネチャについて、当該近接シグネチャの配下の転置インデクスに前記２つの語どうしが設定された距離だけ離れて出現するか否かを調査し、出現しない場合は下位の近接シグネチャの調査を行なわず、
出現する場合は下位の近接シグネチャについて前記調査を行い、当該下位の近接シグネチャに前記２つの語どうしが設定された距離だけ離れて出現する場合にその近接シグネチャの配下の転置インデクスを用いて検索を行い、前記検索結果統合手段は、前記検索結果を統合して出力することを特徴としている。
【発明の効果】
【００１２】
本発明によれば、不必要な転置インデクスヘの問合せが減るため、検索システム全体のスループット、すなわち、単位時間あたりに処理できる検索要求数を高めることが可能となる。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施形態例による情報検索装置の構成図。
【図２】本発明の一実施形態例における句検索実施時の処理を示すフローチャート。
【図３】本発明の一実施形態例における近接性の調査実施時の処理を示すフローチャート。
【発明を実施するための形態】
【００１４】
以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施形態例に限定されるものではない。図１は本発明の一実施形態例による情報検索装置１００の構成を示している。
【００１５】
図１において、情報検索装置１００は、ユーザーが入力した検索語を含む文書を検索し出力する分散型文書検索装置である。１０１は本発明の検索手段としての検索部であり、１０２は本発明の検索結果統合手段としての検索結果統合部である。
【００１６】
ＴＩＣ，ＴＩＤ，ＴＩＥ，ＴＩＦは、図示省略の情報収集部より収集された検索対象の文書集合が分散して格納される複数の転置インデクスである。
【００１７】
この転置インデクスＴＩＣ〜ＴＩＦは、前記分散された文書集合を、各担当する文書集合として、単語の出現位置情報とともに格納する。
【００１８】
前記検索対象文書集合の各分散ユニット（転置インデクスＴＩＣ〜ＴＩＦ）ヘの分散方法は任意の方法で良いが、本発明がより有効に機能するには、互いに似通った文書が同一の分散ユニットヘ含まれる方が望ましい。なお、一般にＷｅｂを対象とした検索のために文書を収集する場合、同じホストに含まれる文書や同じドメインに含まれる文書を連続して収集することが多いため、この場合は収集した順に格納することにより、自動的にある程度似通った文書が同一の分散ユニットに含まれることになる。
【００１９】
Ｃ，Ｄ，Ｅ，Ｆは各転置インデクスＴＩＣ，ＴＩＤ，ＴＩＥ，ＴＩＦが担当する文書集合に各々担当する句シグネチャであり、Ａ，Ｂは複数の転置インデクスが担当する文書集合に相当する木構造状に配置された句シグネチャである。
【００２０】
すなわち、転置インデクスＴＩＣおよびＴＩＤが担当する文書集合に相当する句シグネチャＣ，Ｄの上位に句シグネチャＡが配置され、転置インデクスＴＩＥおよびＴＩＦが担当する文書集合に相当する句シグネチャＥ，Ｆの上位に句シグネチャＢが配置されている。
【００２１】
したがって図１の場合、句シグネチャＡ，Ｂが上位（最上位）の句シグネチャ、Ｃ，Ｄ，Ｅ，Ｆが下位の句シグネチャとして構成されている。
【００２２】
これら句シグネチャＡ〜Ｆは、各々が配下とする転置インデクスＴＩＣ〜ＴＩＦのいずれかに２つの語が句として出現するかどうかの情報を各々記録しており、２つの語を入力として、担当する文書集合中にその語対が句として出現するかどうかの情報を出力する。
【００２３】
これには、２つの語をキーとするようなハッシュテーブルを用いることもできるが、大量の組合せに対してより少ないメモリで動作するために、非特許文献３で示されるようなブルームフィルタといった技術を用いることもできる。
【００２４】
なお、ブルームフィルタは確率的なアルゴリズムであるため、ブルームフィルタを用いた場合には、本来は文書集合中には出現しない語対についても句であると出力する可能性があるが、本装置の動作には影響はない。
【００２５】
ｇＣ，ｇＤ，ｇＥ，ｇＦは各転置インデクスＴＩＣ，ＴＩＤ，ＴＩＥ，ＴＩＦが担当する文書集合に各々担当する近接シグネチャグループであり、ｇＡ，ｇＢは複数の転置インデクスが担当する文書集合に相当する木構造状に配置された近接シグネチャグループである。
【００２６】
すなわち、転置インデクスＴＩＣおよびＴＩＤが担当する文書集合に相当する近接シグネチャグループｇＣ，ｇＤの上位に近接シグネチャグループｇＡが配置され、転置インデクスＴＩＥおよびＴＩＦが担当する文書集合に相当する近接シグネチャグループｇＥ，ｇＦの上位に近接シグネチャグループｇＢが配置されている。
【００２７】
したがって図１の場合、近接シグネチャグループｇＡ，ｇＢが上位（最上位）の近接シグネチャグループ、ｇＣ，ｇＤ，ｇＥ，ｇＦが下位の近接シグネチャグループとして構成されている。
【００２８】
これら近接シグネチャグループｇＡ〜ｇＦは、各々が配下とする転置インデクスＴＩＣ〜ＴＩＦのいずれかに、２つの語同士が、事前に定められた距離ｄだけ離れて出現するかどうかの情報を各々記録しており、２つの語を入力として、担当する文書集合中にその語対が定められた距離だけ離れて出現するかどうかを出力する。
【００２９】
各近接シグネチャグループｇＡ〜ｇＦ内には各々ｄ個の近接シグネチャが設けられ、この近接シグネチャは１単語だけ離れている（隣あっている）かどうかを格納した１-近接シグネチャ、２単語だけ離れているかどうかを格納した２-近接シグネチャといったように、距離の短いものから順に複数保持する。
【００３０】
同一の対象に対する１-近接シグネチャからｄ-近接シグネチャまでのｄ個の近接シグネチャをひとつずつ集めたものが近接シグネチャグループである(尚、以下の説明では、１-近接シグネチャからｄ-近接シグネチャまでのいずれか１つの近接シグネチャをｋ-近接シグネチャと呼ぶこともある）。
【００３１】
この近接シグネチャは、前記句シグネチャ同様に、ハッシュテーブルやブルームフィルタといった技術を用いることができる。
【００３２】
図１に示したように、本実施例では句シグネチャ、近接シグネチャグループ（ｄ個のｋ-近接シグネチャをまとめたもの）はそれぞれ木構造状に配置し、上位（図中左側）のシグネチャは、下位の複数個のシグネチャの配下のインデクスのいずれかに２つの語が句として、あるいは近接して出現するかどうかを記録する。
【００３３】
木構造状に配置することにより、２つの語が句としてあるいは近接して出現するかどうかを上位のシグネチャに問合せることで、下位のシグネチャそれぞれに問い合わせることなく検索対象となっている語対がどの文書にも含まれていない場合には即座に含まれていないということを知ることができる。
【００３４】
各シグネチャの構造はいずれも同様である。尚、木は深さが１でも構わない。この場合、各転置インデクスに１対１に対応するシグネチャのみを用いる。
【００３５】
尚、前記図示省略の情報収集部が、収集した文書集合を分散して転置インデクスＴＩＣ〜ＴＩＦに格納する処理、ユーザーが使用する、例えばコンピュータ端末から入力される検索語の入力処理、検索部１０１が行う後述の各処理及び検索結果統合部１０２が行う後述の各処理は、例えばコンピュータによって実行される。このコンピュータが備えるハードウェアリソース、例えばＲＯＭ，ＲＡＭ，ＣＰＵ，通信インタフェース，ハードディスク，記録媒体およびその駆動装置は図示省略している。
【００３６】
このハードウェアリソースとソフトウェアリソースとの協働の結果、情報検索装置１００は、検索部１０１、句シグネチャＡ〜Ｆ、近接シグネチャグループｇＡ〜ｇＦ、転置インデクスＴＩＣ〜ＴＩＦ、検索結果統合部１０２を実現する。
【００３７】
次に上記のように構成された装置の動作を述べる。
【００３８】
検索部１０１は、ユーザー（の使用するコンピュータ端末）から入力された検索語を受け取り、句検索あるいは近接性の調査が必要な場合は以下に述べる動作を行う。そうではない場合は、従来の転置インデクスを用いた検索装置同様に各転置インデクスＴＩＣ〜ＴＩＦを利用して検索を行い検索結果統合部１０２へ結果を送り、それをユーザーへ返す。
【００３９】
（１）句検索が必要な場合
図２に、ユーザー側から入力された検索語について句検索が必要な場合の処理の流れ図を示す。尚、図２の流れ図において、ループＬ１ａａは後述のステップＳ４を検索語中の連続するすべての２単語対について繰り返し実行することを表し、ループＬ１ａは、後述のステップＳ３、前記ループＬ１ａａおよび後述のステップＳ５〜Ｓ７を、現在の選択シグネチャ集合の各シグネチャについて繰り返し実行することを表し、ループＬ１は前記ループＬ１ａを、選択シグネチャ集合が空になるまで繰り返し実行することを表している。またループＬ２は後述のステップＳ９を検索対象シグネチャ集合について繰り返し実行することを表している。
【００４０】
まず検索部１０１は、ステップＳ１において、これから調査が必要なために選択しているシグネチャを格納する選択シグネチャ集合と、最終的に転置インデクスＴＩＣ〜ＴＩＦを用いた検索が必要な文書集合に対応するシグネチャを格納した検索対象シグネチャ集合を初期化する。
【００４１】
検索部１０１は、ステップＳ２において、最上位のシグネチャ（図１では最左にある句シグネチャ（Ａ）と、句シグネチャ（Ｂ））を選択シグネチャ集合に加える。
【００４２】
次にステップＳ３において、選択シグネチャ集合中から対象となる句シグネチャを先頭から順に取り出し、これを句シグネチャｓとする。そしてステップＳ４において、入力された検索語中の連続するすべての２単語対について、句シグネチャｓを用いて、配下の転置インデクスに当該句が含まれている可能性があるかどうかを確認（判定）する。
【００４３】
検索語中の連続する２単語対のうち、いずれか１対でも配下の転置インデクスに当該句が含まれていないことが確認できれば（ステップＳ４の判定結果がＮＯの場合）、その配下に検索結果がないことが確認できたことになる。
【００４４】
すべての単語対について句シグネチャがＴｒｕｅを返した場合（ステップＳ４の判定結果がＹＥＳの場合）は、ステップＳ５において句シグネチャｓが木の葉節点（図１の例では句シグネチャ（Ｃ）、（Ｄ）、（Ｅ）、（Ｆ）のいずれか）であるか否かを判定する。
【００４５】
そして句シグネチャｓが木の葉節点であればステップＳ６において句シグネチャｓを検索対象シグネチャ集合に加える。また句シグネチャｓが木の葉節点ではない場合、ステップＳ７において句シグネチャｓの直下のシグネチャ（例えば句シグネチャｓが図１の（Ａ）の場合であれば（Ｃ）と（Ｄ））を選択シグネチャ集合に加える。
【００４６】
以上のループＬ１ａ内の操作（処理）を選択シグネチャ集合が空になるまで繰り返す（ループＬ１）。
【００４７】
次にステップＳ８において、検索対象シグネチャ集合に要素が含まれているか否かを判定する。そして要素が含まれている場合、ステップＳ９において検索対象シグネチャ集合内の各シグネチャが担当する文書集合に対応する転置インデクスを用いた検索結果を検索結果統合部１０２へ送る（ループＬ２）。
【００４８】
これは一般の転置インデクスを用いた句検索と同様の処理を用いることができる。すなわち、転置インデクスＴＩＣ〜ＴＩＦを展開して得られた出現箇所を比較し、検索語を構成するすべての単語が順序を保って連続して出現する箇所があるかを調べるものである。
【００４９】
（２）近接性の調査が必要な場合
図３にユーザー側から入力された検索語について、近接性の調査が必要な場合の処理の流れ図を示す。
【００５０】
尚、図３の流れ図において、ループＬ１１ａは、後述のステップＳ１６を、近接シグネチャグループｇ内の１-近接シグネチャからｄ-近接シグネチャまでの各近接シグネチャ（ｓ）について繰り返し実行することを表し、ループＬ１１は、後述のステップＳ１５、前記ループＬ１１ａ、ステップＳ１７〜Ｓ１９を、選択シグネチャグループ集合が空になるまで繰り返し実行することを表し、ループＬ１２は後述のステップＳ２１を検索対象シグネチャグループ集合について繰り返し実行することを表している。
【００５１】
まず検索部１０１は、ステップＳ１１において、求められる近接性の調査として「与えられた単語対が距離ｄ以内かどうか」を判定する。もし、分散ユニットで保持している近接シグネチャの最大距離よりもｄが大きい場合、近接シグネチャを用いての確認はできないので、ステップＳ１２において転置インデクスＴＩＣ〜ＴＩＦを用いて検索し、その結果を出力する。これは一般の転置インデクスを用いた句検索と同様の処理を用いることができる。
【００５２】
次にステップＳ１３において、これから調査が必要なために選択しているシグネチャを格納する選択シグネチャグループ集合と、最終的に転置インデクスを用いた検索が必要な文書集合に対応するシグネチャを格納した検索対象シグネチャ集合を初期化する。
【００５３】
次にステップＳ１４において、最上位のシグネチャグループを選択シグネチャグループ集合に加える。
【００５４】
次にステップＳ１５において、選択シグネチャ集合中から対象となる近接シグネチャグループを先頭から順に取り出し、これを近接シグネチャグループｇとする。
【００５５】
次にステップＳ１６において、近接シグネチャグループｇ内の１-近接シグネチャから順に、ｄ-近接シグネチャまでの各近接シグネチャについて、与えられた単語対が、定められた距離だけ離れて出現するかどうかを確認（判定）する。
【００５６】
このステップＳ１６の判定において、すべてがＦａｌｓｅを返した場合（判定結果がＮＯの場合）、配下の転置インデクスでは当該単語対は距離ｄ以内では出現しないことが分かる。
【００５７】
一方で少なくとも１つのｋ-近接シグネチャがＴｒｕｅを返した場合（ステップＳ１６の判定結果がＹＥＳの場合）は配下の転置インデクスで近接して出現している可能性がある。
【００５８】
そこで、ステップＳ１７において近接シグネチャグループｇが木の葉節点（図１の例では近接シグネチャグループｇＣ，ｇＤ，ｇＥ，ｇＦのいずれか）であるか否かを判定する。
【００５９】
そしてもし近接シグネチャグループｇが木の葉節点であれば、ステップＳ１８においてｇを検索対象シグネチャグループ集合に加える。また近接シグネチャグループｇが木の葉節点でなければ、ステップＳ１９においてｇの直下のシグネチャグループ（例えば近接シグネチャグループｇが図１のｇＡであればｇＣとｇＤ）を選択シグネチャグループ集合に加える。
【００６０】
以上のループＬ１１内の操作（処理）を選択シグネチャグループ集合が空になるまで繰り返す。
【００６１】
次にステップＳ２０において、検索対象シグネチャグループ集合に要素が含まれているか否かを判定する。そして要素が含まれている場合、ステップＳ２１において、検索対象シグネチャグループ集合内の各シグネチャが担当する文書集合に対応する転置インデクスを用いた検索結果を検索結果統合部１０２へ送る。これは一般の転置インデクスを用いた句検索と同様の処理を用いることができる。
【００６２】
（３）尚、本実施例の情報検索装置１００では、上記（１）、（２）のいずれにも該当しない場合は転置インデクスＴＩＣ〜ＴＩＦを用いて検索を行う。これは一般の転置インデクスを用いた句検索と同様の処理を用いることができる。
【００６３】
そして最後に検索結果統合部１０２は、各分散ユニットからの結果（転置インデックスを用いた検索結果）をひとつにまとめ、ユーザーに対して出力する。
【００６４】
以上のように本実施例によれば、計算の負荷が小さいシグネチャによって、その配下の転置インデクスには句あるいは近接して出現しないような検索語を知ることができるので、計算の負荷が大きい転置インデクスヘの参照回数が減る。
【００６５】
大規模な分散検索を行う場合、語の出現には偏りがあるため、ある転置インデクスの配下には存在する句であっても他の転置インデクスには存在しない場合が往々にしてある。これに対して、分散された各転置インデクスに対してシグネチャを配置しているので、全体としては転置インデクスヘの参照回数を減らすことができる。
【００６６】
また、本実施形態の分散型文書検索装置における各手段の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、本実施形態の分散型文書検索方法における手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもなく、コンピュータでその機能を実現するためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えばＦＤ（Ｆｌｏｐｐｙ（登録商標）  Ｄｉｓｋ）や、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ  ｄｉｓｋ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、メモリカード、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ）−ＲＯＭ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＨＤＤ、リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【符号の説明】
【００６７】
１００…情報検索装置
１０１…検索部
１０２…検索結果統合部
Ａ〜Ｆ…句シグネチャ
ｇＡ〜ｇＦ…近接シグネチャグループ
ＴＩＣ〜ＴＩＦ…転置インデックス
【図１】
0005345981.tif 000002
【図２】
0005345981.tif 000003
【図３】
0005345981.tif 000004