(57)【要約】【課題】検索語を構成する単語の連接処理を最適化させ、複数の単語からなる複合語の検索処理全体を高速化させる。【解決手段】文書を検索する情報検索にあたり、併合処理選択手段３１は、検索対象文書群４に含まれる全ての文書の識別子と前記文書の分割で得られた各単語の前記文書における位置情報とを有する転置リストを格納した検索インデックス５から引き出された検索語を構成する各単語の位置情報を有する各転置リストに係る情報に基づき、前記各転置リストに共通して出現する文書の識別子を取得する併合処理に係る探索法を選択する。照合処理選択手段３２は、前記併合処理によって取得された識別子を有する転置リストにおける各単語の位置情報リストに係る情報に基づき、前記取得された識別子に対応した前記各単語の位置情報の照合により前記検索語を有する文書における当該検索語の位置情報を取得する照合処理に係る探索法を選択する。【選択図】図１
2010191624.tif 000002
【特許請求の範囲】
【請求項１】
文書を検索する情報検索方法であって、
併合処理選択手段が、検索対象文書群に含まれる全ての文書の識別子と前記文書の分割によって得られた各単語の前記文書における位置情報とを有する転置リストを格納した検索インデックスから引き出された検索語を構成する各単語の位置情報を有する各転置リストに係る情報に基づき、前記各転置リストに共通して出現する文書の識別子を取得する併合処理に係る探索法を選択するステップと、
併合処理手段が前記選択された併合処理に係る探索法によって前記各転置リストに共通して出現する文書の識別子を取得するステップと、
照合処理選択手段が、前記取得された識別子を有する転置リストにおける各単語の位置情報リストに係る情報に基づき、前記取得された識別子に対応した前記各単語の位置情報の照合により前記検索語を有する文書における当該検索語の位置情報を取得する照合処理に係る探索法を選択するステップと、
照合処理手段が前記選択された照合処理に係る探索法によって前記検索語を有する文書における当該検索語の位置情報を取得するステップと
を有すること
を特徴とする情報検索方法。
【請求項２】
前記各転置リストに係る情報は当該各転置リストに有する文書の識別子の数であり、
前記位置情報リストに係る情報は当該位置情報リストの長さであること
を特徴とする請求項１に記載の情報検索方法。
【請求項３】
併合処理設定手段が前記併合処理に係る探索法として線形探索法を事前に設定するステップと、
照合処理設定手段が前記照合処理法に係る探索法として二分探索法を事前に設定するステップと
をさらに有すること
を特徴とする請求項１または２に記載の情報検索方法。
【請求項４】
文書を検索する情報検索装置であって、
検索対象文書群に含まれる全ての文書の識別子と前記文書の分割によって得られた各単語の前記文書における位置情報とを有する転置リストを格納した検索インデックスから引き出された検索語を構成する各単語の位置情報を有する各転置リストに係る情報に基づき、前記各転置リストに共通して出現する文書の識別子を取得する併合処理に係る探索法を選択する併合処理選択手段と、
前記選択された併合処理に係る探索法によって前記各転置リストに共通して出現する文書の識別子を取得する併合処理手段と、
前記取得された識別子を有する転置リストにおける各単語の位置情報リストに係る情報に基づき、前記取得された識別子に対応した前記各単語の位置情報の照合により前記検索語を有する文書における当該検索語の位置情報を取得する照合処理に係る探索法を選択する照合処理選択手段と、
前記選択された照合処理に係る探索法によって前記検索語を有する文書における当該検索語の位置情報を取得する照合処理手段と
を備えたこと
を特徴とする情報検索装置。
【請求項５】
前記各転置リストに係る情報は当該各転置リストに有する文書の識別子の数であり、
前記位置情報リストに係る情報は当該位置情報リストの長さであること
を特徴とする請求項４に記載の情報検索装置。
【請求項６】
前記併合処理に係る探索法として線形探索法を事前に設定する併合処理設定手段と、
前記照合処理に係る探索法として二分探索法を事前に設定する照合処理設定手段と
をさらに備えたこと
を特徴とする請求項４または５に記載の情報検索装置。
【請求項７】
請求項４から６のいずれか１項に記載の情報検索装置を構成する各手段としてコンピュータを機能させるプログラム。
【請求項８】
請求項７に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、蓄積された文書群に出現する単語の位置情報を用いて、フレーズ検索や複合語の検索を高速に行う検索インデックスに関する技術である。特に、位置情報を持つ検索インデックスが既に構築されている際に、複数の単語から成る複合語の検索を高速に行うための技術に関する。
【背景技術】
【０００２】
一般的には、フレーズや複合語を検索するためには、フレーズや複合語を構成する単語がどの文書のどの位置に出現したかという情報を保持する必要がある。各単語に対応するこの情報を保持したデータ構造を転置リストと呼ぶ。この転置リストは例えば図１に示された情報検索装置１の検索インデックス５に格納されている。
【０００３】
転置リストの一例を図５に示した。図の左側に単語、矢印で接続された右側が対応する転置リストを現している。転置リストは文書の識別子（以下、文書ＩＤ）（ＤｏｃＩＤ）、前記文書における各単語の出現位置（ｐｏｓ）の情報を保持している。この例においてｔｅｒｍ1の転置リストは、ｔｅｒｍ1が、文書ＩＤ１の３，６５，６９番目、文書ＩＤ１４４の１，５，６，８番目、文書ＩＤ１７０の２，６，６８，７０番目に出現するという情報を保持している。ｔｅｒｍ2の転置リストは、ｔｅｒｍ2が、文書ＩＤ１の２，６，７，９番目、文書ＩＤ３の２，５，８番目、文書ＩＤ１４４の２，５６，８０番目に出現するという情報を保持している。このように文書における単語の出現位置を保持しておくことで、複合語やフレーズの検索が可能となる。
【０００４】
図１、図４（ａ）及び図６を参照しながら、複合語（検索語）が入力された際の従来の情報検索処理について説明する。
【０００５】
（１）図６に例示したように「東京都」というクエリが情報検索装置１に入力されると、図１に示された検索結果集合特定部３の単語分割手段６は、前記クエリを各単語に分割して、「東京」「都」の単語を得る。
【０００６】
（２）転置リスト取得手段７は図１に示された検索インデックス５から「東京」「都」の転置リストを取得する。
【０００７】
（３）連接処理の過程では、先ず、併合処理手段９が併合対象転置リスト１１である二つの転置リストに共通して出現する文書の識別子を共通文書ＩＤとして取得する（図４（ａ））。次いで、照合処理手段１０が、前記二つの転置リストに出現した共通文書ＩＤについて、（２）で取得された各単語が連接して出現しているかを確認し、最終的に複合語「東京都」がどの文書のどの位置に出現するかを検出結果１２として取得する（図４（ａ））。
【０００８】
ここで、前記二つの転置リストにおいて出現する文書ＩＤのリストを生成する処理を併合処理と呼ぶ。そして、同一文書の中で単語が連接していることを確認するため、単語の出現位置が連接しているかを確認するために行う併合処理と同様の処理を、区別のため、照合処理と呼ぶ。本明細書では、このふたつの処理によって連接している単語の検索を行う処理を連接処理と呼ぶ。
【０００９】
照合処理では、同じ出現位置ではなく、次の位置に出現しているものを取得するが、基本的には併合処理と同じ問題を扱っており、同じアルゴリズムで解くことができる。これ以降、併合処理、照合処理を行うためのアルゴリズムを併合処理手法と呼ぶ。
【００１０】
図６の説明では併合処理が完了してから照合処理を行う処理を述べているが、実際には処理速度の高速化のため、併合処理においてふたつの転置リストに出現する文書ＩＤが見つかる度に照合処理を行う。
【００１１】
３つ以上の単語から構成される複合語、フレーズの検索を行う場合、まず２つの単語について連接処理を行い、得られた結果リストと次の単語の転置リストの連接処理を行う。
【００１２】
併合処理は、ふたつのソート済み整数リストから共通集合を取得する操作と見なすことができる。併合処理のアルゴリズムには様々な従来手法があり、大きく分けて線形探索に基づく手法と二分探索に基づく手法の二手法に分類できる。以下、それぞれの手法について概略を述べる。
【００１３】
線形探索に基づく手法では、図７に示された事例のように、ふたつのリストＡ，Ｂを先頭から比較していき、同じ値を結果集合に追加してゆく。具体的な処理（ステップ００１〜００９）のフローチャートを図８に示した。
【００１４】
二分探索に基づく手法では、短い方の転置リストのそれぞれの文書ＩＤについて、もう一方の転置リストを二分探索し、当該値が見つかった場合に結果集合に追加する。二分探索に基づく手法は、特に二つのリストの長さが大きく異なる場合に有効に働く。
【００１５】
二分探索法の具体的な処理（ステップ１０１〜１１５）のフローチャートを図１０に示した。図９の事例では、まず転置リストＣの文書ＩＤ３が転置リストＤに含まれていないかを探索する。文書ＩＤ３を見つけることができなかった場合、次に探索を行う文書ＩＤ５は、先ほどの最終探索位置よりも右側にあることが保証されているため、より効率的に探索することができる。
【００１６】
具体的な併合処理手法については様々な手法が提案されており、非特許文献１などにおいて、線形探索に基づく手法、二分探索による最新手法の比較を行っている。
【先行技術文献】
【非特許文献】
【００１７】
【非特許文献１】Ｐ．Ｓａｎｄｅｒｓ  ａｎｄ  Ｆ．Ｔｒａｎｓｉｅｒ．Ｉｎｔｅｒｓｅｃｔｉｏｎ  ｉｎ  ｉｎｔｅｇｅｒ  ｉｎｖｅｒｔｅｄ  ｉｎｄｉｃｅｓ．Ｉｎ  Ｐｒｏｃ．７ｔｈ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ａｌｇｏｒｉｔｈｍ  Ｅｎｇｉｎｅｅｒｉｎｇ  ａｎｄ  Ｅｘｐｅｒｉｍｅｎｔｓ（ＡＬＥＮＥＸ’０７），ｐｐ．７１−８３，Ｎｅｗ  Ｏｒｌｅａｎｓ，Ｌｏｕｉｓｉａｎａ，ＵＳＡ，Ｊａｎｕａｒｙ  ６，２００７．
【発明の概要】
【発明が解決しようとする課題】
【００１８】
従来技術では、文書ＩＤのみを保持する転置リスト同士を高速に併合処理するアルゴリズムを提案しており、位置情報を持つ転置リストにおける併合処理・照合処理の組み合わせについては言及していない。また、従来技術の実装では位置情報を保持した転置リストの場合でもひとつの併合処理手法を用いて併合処理、照合処理を行っている。
【００１９】
実際には文書ＩＤの転置リスト長の分布と、単語の位置情報リスト長の分布は大きく異なり、文書ＩＤの転置リストにおける最適な併合処理手法が照合処理でも最適であるとは限らないという問題があった。
【課題を解決するための手段】
【００２０】
前記課題を解決するための発明は、連接処理を構成する併合処理、照合処理を行う際、処理対象の転置リストに対して適切な併合処理手法を選択する。
【００２１】
本発明の情報検索方法の態様としては、文書を検索する情報検索方法であって、併合処理選択手段が、検索対象文書群に含まれる全ての文書の識別子と前記文書の分割によって得られた各単語の前記文書における位置情報とを有する転置リストを格納した検索インデックスから引き出された検索語を構成する各単語の位置情報を有する各転置リスト係る情報に基づき、前記各転置リストに共通して出現する文書の識別子を取得する併合処理に係る探索法を選択するステップと、併合処理手段が前記選択された併合処理に係る探索法によって前記各転置リストに共通して出現する文書の識別子を取得するステップと、照合処理選択手段が、前記取得された識別子を有する転置リストにおける各単語の位置情報リストに係る情報に基づき、前記取得された識別子に対応した前記各単語の位置情報の照合により前記検索語を有する文書における当該検索語の位置情報を取得する照合処理に係る探索法を選択するステップと、照合処理手段が前記選択された照合処理に係る探索法によって前記検索語を有する文書における当該検索語の位置情報を取得するステップとを有する。
【００２２】
本発明の情報検索装置の態様としては、文書を検索する情報検索装置であって、検索対象文書群に含まれる全ての文書の識別子と前記文書の分割によって得られた各単語の前記文書における位置情報とを有する転置リストを格納した検索インデックスから引き出された検索語を構成する各単語の位置情報を有する各転置リストに係る情報に基づき、前記各転置リストに共通して出現する文書の識別子を取得する併合処理に係る探索法を選択する併合処理選択手段と、前記選択された併合処理に係る探索法によって前記各転置リストに共通して出現する文書の識別子を取得する併合処理手段と、前記取得された識別子を有する転置リストにおける各単語の位置情報リストに係る情報に基づき、前記取得された識別子に対応した前記各単語の位置情報の照合により前記検索語を有する文書における当該検索語の位置情報を取得する照合処理に係る探索法を選択する照合処理選択手段と、前記選択された照合処理に係る探索法によって前記検索語を有する文書における当該検索語の位置情報を取得する照合処理手段とを備える。
【００２３】
前記情報検索方法とその装置において、各転置リストに係る情報として各転置リストに有する文書の識別子の数に基づき、併合処理に係る探索法を選択するとよい。また、前記位置情報リストに係る情報として前記位置情報リストの長さに基づき照合処理に係る探索法を選択するとよい。
【００２４】
前記課題を解決するための発明は、前記情報検索装置を構成する各手段としてコンピュータを機能させるプログラムまたはこれを記録したコンピュータ読み取り可能な記録媒体の態様とすることもできる。
【発明の効果】
【００２５】
以上の発明によれば、検索語を構成する単語の連接処理が最適化されるので、複数の単語からなる複合語などの検索処理全体を高速化できる。
【図面の簡単な説明】
【００２６】
【図１】発明と従来技術に係る情報検索装置の構成の差異を説明した概略構成図。
【図２】インデックス作成部による検索インデックス作成のフローチャート。
【図３】発明に係る連接処理のフローチャート。
【図４】（ａ）従来技術に係る連接処理のブロックフロー図、（ｂ）本発明に係る連接処理のブロックフロー図。
【図５】単語の出現位置情報を保持した転置リストの実現例。
【図６】具体的な連接処理の説明図。
【図７】線形探索に基づく併合処理、照合処理の説明図。
【図８】線形探索に基づく併合処理、照合処理のフローチャート。
【図９】二分探索に基づく併合処理、照合処理の説明図。
【図１０】二分探索に基づく併合処理、照合処理のフローチャート。
【発明を実施するための形態】
【００２７】
以下に本発明の実施形態について図面を参照しながら説明するが、本発明はこの実施形態によって限定されるものではない。
【００２８】
本発明に係る情報検索装置は、検索対象となる文書群に対して検索インデックスを作成し、フレーズや複合語で高速に検索するため装置である。
【００２９】
図１に示された本発明の実施形態に係る情報検索装置１は、検索インデックス５を作成するインデックス作成部２と、作成した検索インデックス５を参照して検索結果集合を特定する検索結果集合特定部３とを備える。
【００３０】
本発明に係る情報検索装置１では、特に検索結果集合特定部３に着目している。すなわち、情報検索装置１は、図１に示されたように検索集合特定部３における連接処理モジュール（連接処理手段８）において、併合処理（併合処理手段９）と照合処理（照合処理手段１０）を行う前に、それぞれの処理に適切な検索法を選択（併合処理選択手段３１、照合処理選択手段３２）することで連接処理全体の高速化を行う。
【００３１】
インデックス作成部２は、検索対象文書群４に含まれる全ての検索対象文書を構成する各単語の当該検索対象文書における出現位置情報を保持させた転置リストを作成し、これを更新可能に検索インデックス５に格納する。すなわち、インデック作成部２は、検索対象文書群４から処理対象の文書を取得する文書取得手段２１と、前記取得した処理対象の文書を各単語に分割する単語分割手段２２と、前記分割よって得られた各単語の前記文書における出現位置情報を保持させた転置リストを作成する転置リスト作成手段２３とを備える。前記各単語の転置リストの態様としては、図５に例示したように、前記各単語を含んだ検索対象文書の識別子と前記各単語の前記検索対象文書における位置情報とを有する転置リストが挙げられる。前記分割処理には、例えば従来技術に係る形態素解析手段などを用いればよい。
【００３２】
検索結果集合特定部３は単語分割手段６と転置リスト取得手段７と連接処理手段８とを備える。本発明に係る連接処理手段８は、図４（ｂ）に示されたように、従来技術（図４（ａ））に係る併合処理機能（併合処理手段９）及び照合処理機能（照合処理手段１０）に加えて、併合処理選択機能（併合処理選択手段３１）、照合処理選択機能（照合処理選択手段３２）を備える。
【００３３】
単語分割手段６は入力された複合語（検索語）をその構成要素である各単語に分割する。単語分割手段６もインデックス作成部２の分割機能と同様に従来技術に係る周知の形態素解析手段などを用いればよい。
【００３４】
転置リスト取得手段７は前記各単語の転置リストを検索インデックス５から取得する。
【００３５】
連接処理手段８において、併合処理選択手段３１は併合処理を行う併合対象転置リスト１１に係る情報に基づき併合処理に係る探索手法を選択する。具体的には、併合処理選択手段３１は、検索インデックス５から引き出された検索語を構成する各単語の位置情報を有する併合対象転置リスト１１に係る情報に基づき、併合対象転置リスト１１に共通して出現する文書の識別子（共通文書ＩＤ）を取得する併合処理に係る探索法を選択する。本実施形態では、併合処理選択手段３１は、併合対象転置リスト１１に係る情報として、併合対象転置リスト１１に含まれる文書の識別子（ＩＤ）の数を採用している。
【００３６】
併合処理手段９は併合処理選択手段３１が選択した併合処理に係る探索法によって併合対象転置リスト１１に共通して出現する文書の識別子を取得する。
【００３７】
照合処理選択手段３２は併合処理手段９によって得られた共通文書ＩＤについて照合を行う位置情報のリストに基づき照合処理の探索手法を選択する。具体的には、照合処理選択手段３２は、併合処理手段９で取得された識別子（共通文書ＩＤ）を有する転置リストにおける各単語の位置情報リストに係る情報に基づき、前記取得された識別子に対応した前記各単語の位置情報の照合により前記検索語を有する文書における当該検索語の位置情報を取得する照合処理に係る探索法を選択する。本実施形態では、照合処理選択手段３２は、前記位置情報リストに係る情報として、照合を行う共通文書ＩＤを有する転置リストの位置情報リストの長さを採用している。
【００３８】
照合処理手段１０は照合処理選択手段３２が選択した照合処理に係る探索法によって前記検索語を有する文書における当該検索語の位置情報を取得する。
【００３９】
また、情報検索装置１には、前記併合処理に係る探索手法として線形探索法に基づく手法を事前に設定するための併合処理設定手段３３と、前記照合処理に係る探索手法として二分探索に基づく手法を事前に設定するための照合処理設定手段３４が具備されている。
【００４０】
以上の情報検索装置１を構成する機能手段２〜１０，２１〜２３，３１〜３４はコンピュータのハードウェアとプログラムの協働によって実現できる。検索対象文書群４、検索インデックス５はハードディスク装置等の格納手段に格納される。前記機能手段２〜１０，２１〜２３，３１〜３４としてコンピュータを機能させるプログラムは既知の記録媒体（例えば、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＭＯ、ＨＤＤ、Ｂｌｕ−ｒａｙ  Ｄｉｓｋ（登録商標）等）に格納してまたはネットワークを通じて提供できる。
【００４１】
図２を参照しながらインデックス作成部２によって実行される検索インデックス５の作成の具体的な過程（ステップ２０１〜２１０）について説明する。
【００４２】
ステップ２０１：ｄｏｃｉｄに０を代入する。
【００４３】
ステップ２０２：図１の検索対象文書群４に未処理の文書がある場合、ステップ２０３に進む。未処理の文書がない場合は処理を終了する。
【００４４】
ステップ２０３：文書取得手段２１は検索対象文書群４から未処理のｄｏｃｉｄ番目の文書を取得し、この取得した文書をｄとする。
【００４５】
ステップ２０４：単語分割手段２２は前記取得した処理対象の文書ｄを単語に分割する。
【００４６】
ステップ２０５：転置リスト作成手段２３は文書ｄにおける単語の出現位置ｐｏｓに０を代入する。そして、転置リスト作成手段２３は以下のステップ２０６〜２１０を実行する。
【００４７】
ステップ２０６：処理中の文書ｄに未処理の単語がある場合、ステップ２０７に進む。未処理の単語がない場合、ステップ２１０に進む。
【００４８】
ステップ２０７：文書ｄにおける出現位置がｐｏｓ番目の単語を取得し、ｔとする。
【００４９】
ステップ２０８：検索インデックス５から単語ｔに対応する転置リストを取得し、このリストに文書ｄにおける出現位置ｐｏｓを追加する。
【００５０】
ステップ２０９：文書ｄにおける単語の出現位置ｐｏｓにｐｏｓ＋１を代入する。ステップ２０６に戻る。
【００５１】
ステップ２１０：ｄｏｃｉｄにｄｏｃｉｄ＋１を代入し、ステップ２０２に戻る。そして、未処理のｄｏｃｉｄ＋１番目の文書についてステップ２０３〜２０８の処理が実行される。
【００５２】
次に、連接処理手段８によって実行される連接処理の具体的な過程（ステップ３０１〜３０９）について図３を参照しながら述べる。
【００５３】
ステップ３０１：単語分割手段６は入力された検索クエリを単語に分割する。
【００５４】
ステップ３０２：転置リスト取得手段７は検索インデックス５から、前記分割で得た各単語に対応する転置リストを取得する。取得したｋ個の転置リストをＬ1，Ｌ2，…，Ｌkとする。
【００５５】
ステップ３０３：カウント変数ｉに１を代入する。
【００５６】
ステップ３０４：カウント変数ｉ＜ｋの場合、ステップ３０５に進む。一方、そうでない場合は処理を終了する。
【００５７】
ステップ３０５：併合処理選択手段３１は転置リストＬiと転置リストＬi+1に基づき併合処理に係る探索手法を選択する。例えば転置リストＬi，Ｌi+1の文書ＩＤの数に基づき最適な併合処理に係る探索手法を選択する。具体的には、「転置リストＬiの文書ＩＤの数」＜「転置リストＬi+1の文書ＩＤの数」の場合はＲ＝Ｌi／Ｌi+1、その他の場合はＲ＝Ｌi+1／Ｌiとして文書ＩＤ数の比率Ｒを算出する。そして、予め設定した閾値Ｔに基づいてこの２つの文書ＩＤリストに最適な併合処理に係る探索手法を選択する。例えば、閾値Ｔ＜Ｒの場合、二分探索法を選択し、それ以外の場合、線形探索法を選択する。若しくは、併合処理設定手段３３によって事前に設定された併合処理に係る探索手法（例えば線形探索法）を用いる。
【００５８】
ステップ３０６：併合処理手段９はステップ３０５で選択された探索法によって転置リストＬi，Ｌi+1における文書ＩＤの併合処理を行う。尚、併合処理手法に線形探索法が併合処理設定手段３３によって選択されている場合、例えば従来技術の線形探索に基づく手法（非特許文献１参照）などが用いられる。
【００５９】
ステップ３０７：照合処理選択手段３２はステップ３０６で得られた共通文書ＩＤの転置リストＬi，Ｌi+1の位置情報リストに基づき照合処理で使用する探索手法を選択する。例えば、ステップ３０５と同様に、転置リストＬi，Ｌi+1の位置情報リストの長さの比率に基づいて選択する。「転置リストＬiの位置情報リストの長さ」＜「転置リストＬi+1の位置情報リストの長さ」の場合はＲ＝Ｌi／Ｌi+1、その他の場合はＲ＝Ｌi+1／Ｌiとし、予め設定した閾値Ｓに基づいてこの２つの文書ＩＤリストに最適な照合処理に係る探索手法を選択する。例えばＳ＜Ｒの場合、二分探索を選択し、それ以外の場合、線形探索を選択する。若しくは、照合処理設定手段３４によって予め設定された照合処理に係る探索手法（例えば二分探索法）を用いる。
【００６０】
ステップ３０８：照合処理手段１０は、ステップ３０６で得られた共通の文書ＩＤについて、ステップ３０７で選択された探索手法によって位置情報の照合処理を行う。位置情報の照合処理に二分探索法が照合処理設定手段３４によって選択されている場合、例えば従来技術の二分探索に基づく手法（非特許文献１参照）などを用いる。この照合処理の結果リスト（前記検索クエリを有する文書における当該検索クエリの位置情報のリスト）をＬi+1とする。
【００６１】
ステップ３０９：ｉにｉ＋１を代入してステップ３０４に戻る。
【００６２】
以上の処理によって得られた結果リストは図示省略の表示手段（ディスプレイ）によって適宜に表示される。
【００６３】
以上のように、情報検索装置１によれば、単語の位置情報を有する転置リストにおける連接処理を構成する併合処理、照合処理を行う際、処理対象の転置リストに対して適切な探索手法が選択される。したがって、連接処理が最適化され、連接処理を必要とする複合語などの検索処理全体を高速化できる。
【００６４】
また、二つの転置リストの長さが与えられると、その計算量の理論値から、最適な探索手法を選択できる。さらに、検索対象の文書のデータの特性に基づいて、適切な手法の組み合わせを選択することで、連接処理の処理速度が改善する。
【符号の説明】
【００６５】
１…情報検索装置
２…インデックス作成部
３…検索結果集合特定部
４…検索対象文書群
５…検索インデックス
８…連接処理手段
９…併合処理手段
１０…照合処理手段
３１…併合処理選択手段
３２…照合処理選択手段
３３…併合処理設定手段
３４…照合処理設定手段
【図１】
2010191624.tif 000003
【図２】
2010191624.tif 000004
【図３】
2010191624.tif 000005
【図４】
2010191624.tif 000006
【図５】
2010191624.tif 000007
【図６】
2010191624.tif 000008
【図７】
2010191624.tif 000009
【図８】
2010191624.tif 000010
【図９】
2010191624.tif 000011
【図１０】
2010191624.tif 000012