(57)【要約】【課題】転置インデックスにおいて、索引語が出現する文書の文書識別番号と出現位置のリストを分離する際に、各文書に対応する位置情報にアクセスする手段を、記憶領域の消費を抑えつつ提供する。【解決手段】複数の文書を含む文書集合から、検索対象の索引語を検索する装置における文書管理方法であって、プロセッサが、文書集合に含まれる複数の文書から単語又は連続する複数の文字からなる文字列を、前記索引語として切り出し、索引語が含まれる個々の文書における、索引語の出現位置を示す位置情報の集合である第１の位置リストを作成し、文書集合に含まれる文書の全ての第１の位置リストから構成される第２の位置リストを作成し、第２の位置リストから第１の位置リストを取得するために、第１の値と第２の値との２種類の値から構成されるビットベクトルを作成することを特徴とする。【選択図】図７
2010198425.tif 000002
【特許請求の範囲】
【請求項１】
複数の文書を含む文書集合から、検索対象の索引語を検索する装置における文書管理方法であって、
前記装置は、プロセッサ、及び前記プロセッサに接続される記憶装置を備え、
前記方法は、
前記プロセッサが、前記記憶装置に格納される前記文書集合を読み出し、前記読み出された文書集合に含まれる前記複数の文書から単語又は連続する複数の文字からなる文字列を、前記索引語として切り出し、前記切り出された索引語を前記記憶装置に格納するステップと、
前記プロセッサが、前記各文書を一意に識別するための文書識別子を、前記各文書に割り当てるステップと、
前記プロセッサが、前記索引語が含まれる前記複数の文書の文書識別子の集合である文書リストを作成し、前記作成された文書リストを前記記憶装置に格納するステップと、
前記プロセッサが、前記索引語が含まれる個々の文書における、前記索引語の出現位置を示す位置情報の集合である第１の位置リストを作成し、前記作成された第１の位置リストを前記記憶装置に格納するステップと、
前記プロセッサが、前記文書集合に含まれる文書の全ての第１の位置リストから構成される第２の位置リストを作成し、前記作成された第２の位置リストを前記記憶装置に格納するステップと、
前記プロセッサが、前記第２の位置リストから前記第１の位置リストを取得するための、第１の値と第２の値との２種類の値から構成されるビットベクトルを作成し、前記作成されたビットベクトルを前記記憶装置に格納するステップと、を含むことを特徴とする文書管理方法。
【請求項２】
前記ビットベクトルを作成するステップでは、前記プロセッサが、前記第２の位置リストに含まれる前記第１の位置リストのうち、最初の前記位置情報が格納される位置に前記第１の値を設定することを特徴とする請求項１に記載の文書管理方法。
【請求項３】
前記装置が前記索引語の位置情報を含めた検索をする場合に、前記プロセッサが、前記ビットベクトルに設定された前記第１の値が前記ビットベクトルのどの位置に格納されているかを算出することによって、前記第２の位置リストから前記第１の位置リストを取得するステップを含むことを特徴とする請求項２に記載の文書管理方法。
【請求項４】
前記索引語に、品詞又は文節の少なくともいずれかの属性と、索引語識別子とが付与されることを特徴とする請求項３に記載の文書管理方法。
【請求項５】
前記ビットベクトルを作成するステップでは、前記プロセッサが、前記文書集合に含まれる全ての前記索引語と、前記索引語に付与された属性とを、前記文書識別子が小さい順位に並べたリストを作成し、前記文書識別子が小さい順位に並べたリストを前記記憶装置に格納するステップと、
前記プロセッサが、前記索引語及び前記索引語に付与された前記属性に索引語識別子を割り当てるステップと、
前記プロセッサが、前記リストの長さと等しいビットベクトルを用いて、前記索引語のうち、最初の文字又は最後の文字が同一の索引語が格納されている領域の最初の位置又は最後の位置に前記第１の値を設定する、第１のビットベクトルを作成し、前記作成された第１のビットベクトルを前記記憶装置に格納するステップと、
前記プロセッサが、前記領域に含まれる各々の前記索引語の最初の文字が格納されている位置に前記第１の値を設定する第２のビットベクトルを作成し、前記作成された第２のビットベクトルを前記記憶装置に格納するステップと、
前記プロセッサが、前記リストの長さと等しい前記ビットベクトルを用いて、前記領域に含まれる索引語のうち、検索時に検索対象から除外する前記索引語の最初の文字又は最後の文字が格納されている位置に前記第１の値を設定する第３のビットベクトルを作成し、前記作成された第３のビットベクトルを前記記憶装置に格納するステップと、を含むことを特徴とする請求項４に記載の文書管理方法。
【請求項６】
複数の文書を含む文書集合から、検索対象の索引語を検索する装置であって、
前記装置は、
プロセッサ、及び前記プロセッサに接続される記憶装置を備え、
前記記憶装置は、
前記文書から索引語を切り出す索引語切り出し部と、
前記文書における前記索引語の位置に関する位置情報を抽出する索引語位置抽出部と、
前記文書を一意に識別するための文書識別子を前記文書に割り当てる文書識別番号割当部と、
前記索引語を含む文書に関する情報を含む文書リストから作成される文書レベル転置インデックスを作成する文書レベル転置インデックス作成部と、
前記文書における前記索引語の出現位置に関する位置情報を含む位置リストから作成される位置レベル転置インデックスを作成する位置レベル転置インデックス作成部と、
前記文書レベル転置インデックスを用いた検索から、前記位置レベル転置インデックスに含まれる前記文書における索引語の出現位置に関する前記位置情報にアクセスするための、第１の値と第２の値との２種類の値から構成されるビットベクトルを作成するビットベクトル作成部と、
前記索引語が含まれる文書と、当該文書における前記索引語の位置とを検索する位置レベル検索部と、を備え、
前記索引語切り出し部は、前記文書から単語又は連続する複数の文字からなる文字列を、前記索引語として切り出し、
前記索引語位置抽出部は、前記切り出された索引語の位置情報を抽出し、
前記文書識別番号割当部は、前記文書を一意に識別するための前記文書識別子を、前記各文書に割り当て、
前記文書レベル転置インデックス作成部は、
前記文書リストを作成し、
前記作成された文書リストから前記文書レベル転置インデックスと作成し、
前記位置レベル転置インデックス作成部は、
前記索引語の個々の文書における出現位置を示す位置情報の集合である第１の位置リストを作成し、
前記文書集合に含まれる文書の全ての第１の位置リストから構成される第２の位置リストを作成し、
前記作成された第２の位置リストから前記位置レベル転置インデックスを作成し、
前記文書レベル転置インデックスと前記位置レベル転置インデックスとは別々に管理され、
前記ビットベクトル作成部は、前記ビットベクトルを作成することを特徴とする装置。
【請求項７】
前記ビットベクトル作成部は、前記ビットベクトルを作成する場合に、前記第２の位置リストに含まれる前記第１の位置リストのうち、最初の前記位置情報が格納される位置に前記第１の値を設定することを特徴とする請求項６に記載の装置。
【請求項８】
前記位置レベル検索部は、前記索引語の位置情報を含めた検索をする場合に、前記ビットベクトルに設定された前記第１の値が前記ビットベクトルのどの位置に格納されているかを算出することによって、前記索引語が含まれる文書の位置リストを取得することを特徴とする請求項７に記載の装置。
【請求項９】
前記索引語に、品詞又は文節の少なくともいずれかの属性と、索引語識別子とが付与されることを特徴とする請求項８に記載の文書検索方法。
【請求項１０】
前記ビットベクトル作成部は、
前記ビットベクトルを作成する場合に、前記文書集合に含まれる全ての前記索引語と、前記索引語に付与された属性とを、前記文書識別子が小さい順位に並べたリストを作成し、
前記索引語及び前記索引語に付与された前記属性に索引語識別子を割り当て、
前記リストの長さと等しい前記ビットベクトルを用いて、
前記索引語のうち、最初の文字又は最後の文字が同一の索引語が格納されている領域の最初の位置又は最後の位置に前記第１の値を設定する、第１のビットベクトルを作成し、
前記領域に含まれる各々の前記索引語の最初の文字が格納されている位置に前記第１の値を設定する第２のビットベクトルを作成し、
前記領域に含まれる索引語のうち、検索時に検索対象から除外する前記索引語の最初の文字又は最後の文字が格納されている位置に前記第１の値を設定する第３のビットベクトルを作成することを特徴とする請求項９に記載の装置。
【請求項１１】
複数の文書を含む文書集合から、検索対象の索引語ｗを検索する装置における文書管理方法であって、
前記装置は、プロセッサ、及び前記プロセッサに接続される記憶装置を備え、
前記方法は、
前記プロセッサが、前記文書から単語又は連続する複数の文字からなる文字列を、前記索引語ｗとして切り出し、前記索引語ｗを前記記憶装置に格納するステップと、
前記プロセッサが、前記文書集合に前記索引語ｗが含まれる前記文書がｎ個ある場合、前記文書を一意に識別するための文書識別子を、ｉ番目の前記文書に対してｄ（ｗ，ｉ）として割り当てるステップと、
前記プロセッサが、前記文書識別子からなる数列である文書リストＤ（ｗ）を作成し、前記作成された文書リストＤ（ｗ）を前記記憶装置に格納するステップと、
前記プロセッサが、前記文書リストＤ（ｗ）を圧縮したデータＤ'（ｗ）を作成し、前記データＤ'（ｗ）を前記記憶装置に格納するステップと、
前記プロセッサが、前記文書識別子がｄ（ｗ，ｉ）である前記文書における、前記索引語ｗのｊ番目の出現位置ｐ（ｗ，ｉ，ｊ）からなる数列である、前記文書識別子がｄ（ｗ，ｉ）である文書における前記索引語ｗの位置リストＰ（ｗ，ｉ）を作成し、作成された位置リストＰ（ｗ，ｉ）を前記記憶装置に格納するステップと、
前記プロセッサが、前記索引語ｗについてのすべての前記位置リストＰ（ｗ，ｉ）を連結して得られる、前記索引語ｗの位置リストＰ（ｗ）を作成し、前記作成された位置リストＰ（ｗ）を前記記憶装置に格納するステップと、
前記プロセッサが、前記索引語ｗの位置リストＰ（ｗ）を圧縮したデータＰ'（ｗ）を作成し、前記作成されたデータＰ'（ｗ）を前記記憶装置に格納するステップと、
前記データＰ'（ｗ）と長さが等しく、前記文書リストＤ（ｗ）に含まれる前記文書における索引語ｗの位置リストＰ（ｗ，ｉ）にアクセスするための、０と１との２種類の文字から構成される、ビットベクトルＢＢ（ｗ）を作成し、前記作成されたビットベクトルＢＢ（ｗ）を前記記憶装置に格納するステップと、を含むこと特徴とする文書管理方法。
【請求項１２】
前記ビットベクトルＢＢ（ｗ）を作成するステップは、前記ビットベクトルＢＢ（ｗ）のｋ番目の位置が、前記索引語ｗが含まれる文書の位置リストＰ（ｗ，ｉ）の最初の出現位置ｐ（ｗ，ｉ，１）である場合、当該ｋ番目を１に設定することを特徴とする請求項１１に記載の文書管理方法。
【請求項１３】
前記方法は、前記索引語ｗの位置を含めた検索をする場合に、前記索引語ｗを含むｉ番目の位置リストＰ（ｗ，ｉ）にアクセスするために、下式（１）を用いて、前記ビットベクトルＢＢ（ｗ）における前記位置リストＰ（ｗ，ｉ）の位置を算出するステップと、を含むことを特徴とする請求項１２に記載の文書管理方法。
式（１）ｓｅｌｅｃｔ（ＢＢ（ｗ），ｉ）＝（ｉ番目の１は、ビットベクトルＢの先頭から何番目の文字か）
【請求項１４】
前記索引語ｗの位置リストＰ（ｗ）のそれぞれの前記索引語ｗの出現位置を、ｖａｒｉａｂｌｅ  ｂｙｔｅ法を用いて表現することを特徴とする請求項１２に記載の文書管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書の全文検索を行なうための転置インデックス作成方法に関し、特に、位置情報を含む転置インデックスを使用して検索を実行する装置に関する。
【背景技術】
【０００２】
現代社会では、膨大な量の電子文書が日々作成され、その量はますます増え続けている。オフィスでは文書作成やプレゼンテーションに電子文書は不可欠であり、インターネットの拡大も、爆発的な数の電子文書が生み出される要因となっている。
【０００３】
電子文書の量の増大とともに、多数の膨大な文書から必要な情報が記された文書を、短時間で検索し、検索された文書を出力する文書検索技術が必須となっており、技術開発も進んでいる。
【０００４】
文書検索の典型的なスタイルは、与えられた文書集合から、指定された単語を含む文書を、極力短時間で出力するというものである。前述の目的を達成するために、転置インデックスと呼ばれるデータ構造が使用される（例えば、非特許文献３参照）。
【０００５】
日本語、韓国語又は中国語は、英語、フランス語、又はスペイン語のように単語がスペースで区切られている言語と異なり、文書を正確に単語に分割することが困難である。
【０００６】
前述の問題を解決するため、連続するｎ文字からなる、文書中の任意の部分文字列を、一つの単語として転置インデックスを構築するｎ−ｇｒａｍと呼ばれる方法を用いる場合があり、実用上有用であることが知られている。ここで、ｎは、主に１〜１０の整数である。
【０００７】
本明細書では、転置インデックスの作成に使用される、単語又は長さｎの部分文字列を、索引語と呼ぶ。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００８−１４０３５７号公報
【非特許文献】
【０００９】
【非特許文献１】G.Navarro and V.Makinen, Compressed full-text Indexes, ACM Computing Surveys, 39(1): Article 2, 2007.
【非特許文献２】F. Scholer, H.E. Williams, J. Zobel, Compression of Inverted Indexes for Fast Query Evaluation, Proc. 25th Ann. Int'l ACM SIGIR Conf. Research and Development in Information Retrieval, pp.222-229, 2002.
【非特許文献３】北研二・津田和彦・獅々堀正幹著、「情報検索アルゴリズム」、共立出版、２００２年
【発明の概要】
【発明が解決しようとする課題】
【００１０】
はじめに、本明細書で使用する表記法及び用語を定義する。
【００１１】
図１９は、本発明における表記法及び用語の定義を示す説明図である。
【００１２】
本明細書において、任意の索引語を「ｗ」と表記する。索引語ｗが出現する文書１０４（図２０参照）の数をｎ（ｗ）とし、また、文書１０４に付される文書識別番号１０５（図２０参照）をｄ（ｗ，１）、ｄ（ｗ，２）、…ｄ（ｗ，ｎ（ｗ））とする。
【００１３】
ただし、文書識別番号１０５は、各文書１０４を一意に識別するために割り当てられた整数である。なお、以降、文書識別番号１０５がｄ（ｗ，ｉ）の文書のことを単に文書ｄ（ｗ，ｉ）とも記載する。
【００１４】
索引語ｗが出現する文書１０４の集合を表す数値の列Ｄ（ｗ）を以下のように定義する。
Ｄ（ｗ）＝＜ｄ（ｗ，１）、ｄ（ｗ，２）、…ｄ（ｗ，ｎ（ｗ））＞…（１）
当該Ｄ（ｗ）を索引語ｗの文書リストとし、文書リストＤ（ｗ）が圧縮されたデータをＤ'（ｗ）とする。
【００１５】
文書ｄ（ｗ，ｉ）（１≦ｉ≦ｎ（ｗ））における索引語ｗの出現回数をｆ（ｗ，ｉ）とし、文書ｄ（ｗ，ｉ）（１≦ｉ≦ｎ（ｗ））における索引語ｗの出現位置をｐ（ｗ，ｉ，１）、ｐ（ｗ，ｉ，２）、…、ｐ（ｗ，ｉ，ｆ（ｗ，ｉ））とする。
【００１６】
また、出現位置ｐ（ｗ，ｉ，ｆ（ｗ，ｉ））の集合を示す数値の列Ｐ（ｗ，ｉ）を以下のように定義する。
Ｐ（ｗ，ｉ）＝＜ｐ（ｗ，ｉ，１）、…、ｐ（ｗ，ｉ，ｆ（ｗ，ｉ））＞…（２）
当該Ｐ（ｗ，ｉ）を文書ｄ（ｗ，ｉ）における索引語ｗの位置リストとする。
【００１７】
さらに、文書ｄ（ｗ，ｉ）における索引語ｗの位置リストＰ（ｗ，ｉ）の集合を表す数値の列Ｐ（ｗ）を以下のように定義する。
Ｐ（ｗ）＝＜Ｐ（ｗ，１）、…、Ｐ（ｗ，ｎ（ｗ））＞…（３）
当該Ｐ（ｗ）を索引語ｗの位置リストとし、索引語ｗの位置リストＰ（ｗ）が圧縮されたデータをＰ'（ｗ）とする。
【００１８】
まず、従来の技術について説明する。
【００１９】
図２０は、検索対象となる文書集合１０１と、文書集合１０１に基づいて構築される従来の転置インデックス１０２の概略を示す説明図である。
【００２０】
文書集合１０１には、複数の文書１０４が含まれ、それぞれに文書識別番号ｄ（ｗ，ｉ）１０５が付与される。転置インデックス１０２には、索引語ｗ１０３と、索引語ｗ１０３の出現する文書１０４の文書識別番号ｄ（ｗ，ｉ）１０５とが対応づけられている。これによって、指定された索引語ｗ１０３が含まれる文書１０４を短時間で出力できる。
【００２１】
また、文書識別番号ｄ（ｗ，ｉ）１０５だけでなく、各文書１０４における索引語ｗ１０３の出現回数ｆ（ｗ，ｉ）１０６も対応づけて記録しておけば、指定された索引語ｗ１０３を含む文書１０４が複数あるときに、その中で重要な文書１０４を発見するためのスコア計算をすることも可能となる。
【００２２】
図２１は、検索対象となる文書集合１０１と、文書集合１０１に基づいて構築される従来の転置インデックス１０２の異なる形態の概略を示す説明図である。
【００２３】
文書検索では図２１に示すように、転置インデックス１０２に各索引語ｗ１０３の出現位置ｐ（ｗ，ｉ，ｊ）２０１を記録することも有用である。ここで、ｊは１≦ｊ≦ｆ（ｗ，ｉ）である整数である。
【００２４】
このようにすれば、文章１０４における索引語ｗ１０３の有無に基づく検索だけでなく、複数種類の索引語が連続して現れる文書１０４を検索するフレーズ検索が可能となり、また、条件を緩和し、複数種類の索引語が指定された距離の範囲に出現する文書１０４を探す近傍検索も可能となる。
【００２５】
しかし、転置インデックス１０２において位置リストＰ（ｗ，ｉ）も格納する場合、位置リストＰ（ｗ，ｉ）が占める割合は大きく、特に大規模な文書集合１０１に対しては、位置リストＰ（ｗ，ｉ）は転置インデックス１０２を肥大化させる要因となる。
【００２６】
また、位置情報を用いない検索が要求された場合、図２１に示すように、文書リストＤ（ｗ）と混在して格納されていると位置リストＰ（ｗ，ｉ）を読み飛ばす処理時間が必要となり、検索速度が低下する。
【００２７】
前述した問題を回避するため、位置リストＰ（ｗ，ｉ）はしばしば省略されるが、位置情報が全く無い場合、フレーズ検索又は近傍検索は不可能である。
【００２８】
図２２は、検索対象となる文書集合１０１と、文書集合１０１に基づいて構築される転置インデックス１０２の概略を示す説明図である。この図は文書リストＤ（ｗ）と位置リストＰ（ｗ）とを分割する概念を説明するためのものである。
【００２９】
前述した問題を解決するために、図２２に示すように、転置インデックス１０２を、全索引語ｗのＤ'（ｗ）のみを格納する文書レベル転置インデックス３０１と、全索引語ｗのＰ'（ｗ）のみを格納する位置レベル転置インデックス３０２とに分離することが考えられる。
【００３０】
これによって、利用されない位置情報を読み飛ばす処理が不要となる。また、位置情報の使用頻度が少ない場合には、文書レベル転置インデックス３０１を主記憶装置（図８参照）に格納し、位置レベル転置インデックス３０２を補助記憶装置（図８参照）に格納してもよい。
【００３１】
しかし、文書レベル転置インデックス３０１と位置レベル転置インデックス３０２とを分離する場合、位置レベル転置インデックス３０２内の、各索引語ｗの各文書１０４における位置リストＰ（ｗ，ｉ）へ効率よくアクセスする手段が必要になる。
【００３２】
図２３は、検索対象となる文書集合１０１と、文書集合１０１に基づいて構築される従来の転置インデックス１０２の概略を示す説明図である。
【００３３】
位置レベル転置インデックス３０２内の、各索引語ｗの各文書１０４における位置リストＰ（ｗ，ｉ）へ効率よくアクセスする手段の１つとして、図２３に示すように、文書レベル転置インデックス３０１のすべて文書識別番号ｄ（ｗ，ｉ）１０５に対して、位置リストＰ（ｗ，ｉ）が格納されるＰ'（ｗ）内にアクセスするためのポインタ４０１を格納する方法がある。
【００３４】
しかし、今日広く用いられている３２ｂｉｔ又は６４ｂｉｔアーキテクチャの計算機では、ポインタ（４０１）１つあたり、４バイト又は８バイトの領域が必要になる。そのため、転置インデックス１０２全体のサイズが大幅に増大してしまう。
【００３５】
一方、ポインタ４０１を格納せずに、位置リストＰ（ｗ，ｉ）を先頭から逐次読みだし、目的の位置リストＰ（ｗ，ｉ）を探索することもできる。しかし、この場合、他の文書１０４における位置リストを読み飛ばす処理が必要となり、さらに、Ｐ'（ｗ）内部で各文書ｄ（ｗ，ｉ）の位置リストＰ（ｗ，ｉ）の境界を知る手段が必要になる。
【００３６】
本発明は、前述の問題点を鑑みてなされたものである。つまり、転置インデックス１０２を文書レベル転置インデックス３０１と位置レベル転置インデックス３０２とに分離する場合に、記憶領域の消費を抑えつつ、各文書１０４に対応する位置情報にアクセスする手段を提供することである。
【課題を解決するための手段】
【００３７】
本発明の代表的な一例を示せば以下の通りである。すなわち、複数の文書を含む文書集合から、検索対象の索引語を検索する装置における文書管理方法であって、前記装置は、プロセッサ、及び前記プロセッサに接続される記憶装置を備え、前記方法は、前記プロセッサが、前記記憶装置に格納される前記文書集合を読み出し、前記読み出された文書集合に含まれる前記複数の文書から単語又は連続する複数の文字からなる文字列を、前記索引語として切り出し、前記切り出された索引語を前記記憶装置に格納するステップと、前記プロセッサが、前記各文書を一意に識別するための文書識別子を、前記各文書に割り当てるステップと、前記プロセッサが、前記索引語が含まれる前記複数の文書の文書識別子の集合である文書リストを作成し、前記作成された文書リストを前記記憶装置に格納するステップと、前記プロセッサが、前記索引語が含まれる個々の文書における、前記索引語の出現位置を示す位置情報の集合である第１の位置リストを作成し、前記作成された第１の位置リストを前記記憶装置に格納するステップと、前記プロセッサが、前記文書集合に含まれる文書の全ての第１の位置リストから構成される第２の位置リストを作成し、前記作成された第２の位置リストを前記記憶装置に格納するステップと、前記プロセッサが、前記第２の位置リストから前記第１の位置リストを取得するための第１の値と第２の値との２種類の値から構成される、ビットベクトルを作成し、前記作成されたビットベクトルを前記記憶装置に格納するステップと、を含むことを特徴とする。
【発明の効果】
【００３８】
本発明によれば、各索引語ｗの各文書における位置にアクセスする手段が提供される。
【００３９】
ビットベクトルを用いることによって、データ量を削減できる。
【図面の簡単な説明】
【００４０】
【図１】ビットベクトルの処理におけるディクショナリの構成要素である表ｓｍａｌｌｒａｎｋの一例を示す説明図である。
【図２】ビットベクトルの処理におけるディクショナリの構成要素であるｓｕｐｅｒｂｌｏｃｋｒａｎｋの一例を示す説明図である。
【図３】ビットベクトルの処理におけるディクショナリの構成要素である表ｓｍａｌｌｓｅｌｅｃｔの一例を示した説明図である。
【図４】ビットベクトルの処理におけるディクショナリの構成要素であるｓｕｐｅｒｂｌｏｃｋｓｅｌｅｃｔ、ｓｕｐｅｒｌｏｎｇｏｒｄｅｒ、ｌｏｎｇｓｕｐｅｒｓｅｌｅｃｔ、ｍｉｎｉｂｌｏｃｋｓｅｌｅｃｔ、ｍｉｎｉｌｏｎｇｏｒｄｅｒ、及びｌｏｎｇｍｉｎｉｓｅｌｅｃｔの一例を示す説明図である。
【図５】ビットベクトルの処理におけるビットベクトルＢ、ｒａｎｋ（Ｂ，ｋ）、及びｓｅｌｅｃｔ（Ｂ，ｉ）を示す説明図である。
【図６】ビットベクトルの処理におけるビットベクトルＢ、ｒａｎｋ（Ｂ，ｋ）、及びｓｅｌｅｃｔ（Ｂ，ｉ）を示す説明図である。
【図７】本発明の第１の実施形態における文書集合と、文書集合に基づいて構築される転置インデックスの概略を示す説明図である。
【図８】本発明の第１の実施形態の装置構成を説明するブロック図である。
【図９】本発明の第１の実施形態のデータ及び処理の流れを示す説明図である。
【図１０】本発明の第１の実施形態の中央演算装置（ＣＰＵ）が実行する文書レベル転置インデックス作成プログラムの処理の詳細を説明するフローチャートである。
【図１１】本発明の第１の実施形態の中央演算装置（ＣＰＵ）が実行する位置レベル転置インデックス作成プログラムの処理の詳細を説明するフローチャートである。
【図１２】本発明の第１の実施形態の中央演算装置（ＣＰＵ）が実行するビットベクトル作成プログラムの処理の詳細を説明するフローチャートである。
【図１３】本発明の第１の実施形態における、文書レベルの検索の処理について説明するフローチャートである。
【図１４】本発明の第１の実施形態における、位置レベルの検索の処理について説明するフローチャートである。
【図１５】本発明の第１の実施形態の効果を説明する図である。
【図１６】本発明の第１の実施形態の効果を説明する図である。
【図１７】本発明の第２の実施形態における検索対象の文書集合の一例を示す説明図である。
【図１８】本発明の第２の実施形態における属性インデックスの一例を示す説明図である。
【図１９】本発明における表記法及び用語の定義を示す説明図である。
【図２０】検索対象となる文書集合と、文書集合に基づいて構築される従来の転置インデックスの概略を示す説明図である。
【図２１】検索対象となる文書集合と、文書集合に基づいて構築される従来の転置インデックスの異なる形態の概略を示す説明図である。
【図２２】検索対象となる文書集合と、文書集合に基づいて構築される転置インデックスの概略を示す説明図である。
【図２３】検索対象となる文書集合と、文書集合に基づいて構築される従来の転置インデックスの概略を示す説明図である。
【発明を実施するための形態】
【００４１】
まず、本発明の概要について説明する。
【００４２】
本発明では転置インデックス１０２を、文書レベル転置インデックス３０１と位置レベル転置インデックス３０２とに分離して格納する。そして、各文書ｄ（ｗ，ｉ）における索引語ｗの位置リストＰ（ｗ，ｉ）にアクセスするために、ビットベクトルと呼ばれる手法を用いる。
【００４３】
ここで、ビットベクトルとは、例えば、「１０１０１０１００１０１１０１０」のように、「０」及び「１」の２種類の文字からなる文字列である。また、索引語ｗの位置リストにアクセスするために構築されるビットベクトルをビットベクトルＢＢ（ｗ）と記載する。
【００４４】
Ｂを、任意のビットベクトルとする。Ｂに対して、ディクショナリと呼ばれるデータ構造を追加することで、以下の２種類の計算を高速に実行できる手法が知られている（例えば、非特許文献１参照）。
ｒａｎｋ（Ｂ，ｋ）＝（先頭からｋ番目の文字の中に、１がいくつあるか？）…（４）
ｓｅｌｅｃｔ（Ｂ，ｉ）＝（ｉ番目の１は、ビットベクトルＢの先頭から何番目の文字か？）…（５）
【００４５】
図５は、ビットベクトルの処理におけるビットベクトルＢ、ｒａｎｋ（Ｂ，ｋ）、及びｓｅｌｅｃｔ（Ｂ，ｉ）を示す説明図である。
【００４６】
図５に示すように、ビットベクトルＢには、ｒａｎｋ（Ｂ，ｋ）の値が、先頭からｋ番目までの文字の中に、１がいくつあるかを表す値として定義される。
【００４７】
また、変数ｊは先頭から何番目の１を考慮しているかを示し、当該変数ｊに対するｓｅｌｅｃｔ（Ｂ，ｊ）の値は前記１がビットベクトルＢにおいて何番目の文字であるかを表す数値として定義されている。
【００４８】
本発明の実施方法の記述を本明細書で完結させるために、非特許文献１に記載の方法に基づくディクショナリ構築方法の一形態について説明する。
【００４９】
以下、Ｂをディクショナリ構築対象のビットベクトル、ビットベクトルＢの長さをＭとする。
【００５０】
下記のディクショナリ構築方法の説明において、ｘ／ｙは、ｘをｙで割って小数部分を切り捨てた整数とする。また、ｘ％ｙはｘをｙで割った余り、ｘ＃ｙはｘ−ｘ％ｙ、ｘ＾ｙは１にｘをｙ回掛けて得られる値とする。
【００５１】
また、ｌｏｇＸは、底を２とするＸ＋１の対数の小数部分を切り上げた整数、ｔはｌｏｇＭを２で割って小数部分を切り上げた整数、κ＝（ｌｏｇＭ）＾２、ξ＝（ｌｏｇκ）＾２、Ξ＝（κ＋ξ−１）／ξ、ｓ（ｉ）＝ｓｅｌｅｃｔ（Ｂ，（ｊ／Ξ）＊κ＋（ｊ％Ξ）＊ξ＋１）、Ｂ［ｘ．．ｙ］はBのｘ文字目からｙ文字目までを抽出して作られるビットベクトルとする。Ｍは大きな整数と仮定する。
【００５２】
ディクショナリは、以下で説明する複数の表から構成される。まず、ｒａｎｋ用のディクショナリ構築方法を述べる。
【００５３】
・表ｓｍａｌｌｒａｎｋの構築：
長さｔの任意のビットベクトルｂ、及び１≦ｉ≦ｔなる整数ｉに対し、ｒａｎｋ（ｂ，ｉ）の値を全て記録した表ｓｍａｌｌｒａｎｋを作る。すなわち、ｓｍａｌｌｒａｎｋ［ｂ，ｉ］＝ｒａｎｋ（ｂ，ｉ）である。
【００５４】
図１は、ビットベクトルの処理におけるディクショナリの構成要素である表ｓｍａｌｌｒａｎｋの一例を示す説明図である。
【００５５】
図１では、ｔ＝４の場合の表ｓｍａｌｌｒａｎｋの例を示す。この表の大きさは、要素数が（２＾ｔ）＊ｔ、１つの値の大きさがｌｏｇ（ｔ）ビットで表現できるので、（２＾ｔ）＊ｔ＊ｌｏｇ（ｔ）ビットである。
・表ｓｕｐｅｒｂｌｏｃｋｒａｎｋの構築：
０≦ｉ＜（Ｍ／κ）なる整数ｉに対し、ｒａｎｋ（Ｂ，ｉ＊κ＋１）の値を記録した表ｓｕｐｅｒｂｌｏｃｋｒａｎｋを作る。すなわち、ｓｕｐｅｒｂｌｏｃｋｒａｎｋ［ｉ］＝ｒａｎｋ（Ｂ，ｉ＊κ＋１）である。
【００５６】
図２は、ビットベクトルの処理におけるディクショナリの構成要素であるｓｕｐｅｒｂｌｏｃｋｒａｎｋの一例を示す説明図である。
【００５７】
表ｓｕｐｅｒｂｌｏｃｋｒａｎｋの大きさは、１つの値の大きさがｌｏｇＭビットで表現できるので（Ｍ／κ）＊ｌｏｇＭビットである。
・表ｂｌｏｃｋｒａｎｋの構築：
０≦ｉ＜（Ｍ／ｌｏｇＭ）なる整数ｉに対し、ｂｌｏｃｋｒａｎｋ［ｉ］＝ｒａｎｋ（Ｂ，ｉ＊ｌｏｇＭ＋１）−ｒａｎｋ（Ｂ，（（ｉ＊ｌｏｇＭ）＃κ）＋１）である表ｂｌｏｃｋｒａｎｋを作る。
【００５８】
この表の大きさは、（ｉ＊ｌｏｇＭ）−（ｉ＊ｌｏｇＭ）＃κ≦κより、１つの値の大きさがｌｏｇκビットで表現できるので、（Ｍ／ｌｏｇＭ）＊ｌｏｇκビットである。
【００５９】
前述の３つの表を合わせたものが、ｒａｎｋを算出するためのディクショナリである。
【００６０】
ディクショナリの大きさをＭで除した値は、Ｍが十分大きいとき０へ収束する。したがって、ｒａｎｋ用のディクショナリの大きさは、Ｍが十分大きければ相対的に小さなデータになると期待できる。
【００６１】
ディクショナリを使うと、ｒａｎｋ（Ｂ，ｉ＋１）は、ｉ％ｌｏｇＭ＜ｔのとき、
ｒａｎｋ（Ｂ，ｉ＋１）＝ｓｕｐｅｒｂｌｏｃｋｒａｎｋ［ｉ／κ］
＋ｂｌｏｃｋｒａｎｋ［ｉ／ｌｏｇＭ］
＋ｓｍａｌｌｒａｎｋ［Ｂ［（ｉ＃ｌｏｇＭ）＋１．．（ｉ＃ｌｏｇＭ）＋ｔ］，（ｉ％ｌｏｇＭ）＋１］
また、ｉ％ｌｏｇＭ＞ｔのとき、
ｒａｎｋ（Ｂ，ｉ＋１）＝ｓｕｐｅｒｂｌｏｃｋｒａｎｋ［ｉ／κ］
＋ｂｌｏｃｋｒａｎｋ［ｉ／ｌｏｇＭ］
＋ｓｍａｌｌｒａｎｋ［Ｂ［（ｉ＃ｌｏｇＭ）＋１．．（ｉ＃ｌｏｇＭ）＋ｔ］，ｔ＋１］
＋ｓｍａｌｌｒａｎｋ［Ｂ［（ｉ＃ｌｏｇＭ）＋１＋ｔ．．（ｉ＃ｌｏｇＭ）＋２ｔ］，（ｉ％ｌｏｇＭ）＋１−ｔ］
として、高々４回の表引きで計算できる。
【００６２】
次に、ｓｅｌｅｃｔ用のディクショナリ構築方法を述べる。
【００６３】
以下、Ｂに含まれる１の数をＭ'とする。ディクショナリ構築時に限り、ｉ＞Ｍ'のときｓｅｌｅｃｔ（Ｂ，ｉ）＝０と定義する。
【００６４】
・表ｓｍａｌｌｓｅｌｅｃｔの構築：
長さtの任意のビットベクトルｂ、１≦ｉ≦ｔなる整数ｉに対し、ｓｅｌｅｃｔ＝（ｂ，ｉ）の値を全て記録した表ｓｍａｌｌｓｅｌｅｃｔを作る。すなわち、ｓｍａｌｌｓｅｌｅｃｔ［ｂ，ｉ］＝ｓｅｌｅｃｔ（ｂ，ｉ）である。ただし、ｉ＞ｒａｎｋ（ｂ，ｉ）の場合、ｓｅｌｅｃｔ（ｂ，ｉ）の値は存在しないためｓｍａｌｌｓｅｌｅｃｔ［ｂ，ｉ］＝０とする。
【００６５】
図３は、ビットベクトルの処理におけるディクショナリの構成要素である表ｓｍａｌｌｓｅｌｅｃｔの一例を示した説明図である。
【００６６】
図３では、ｔ＝４の場合の表ｓｍａｌｌｓｅｌｅｃｔの例を示す。この表では、１つの値の大きさをｌｏｇ（ｔ）ビットで表現する。要素数が（２＾ｔ）＊ｔなので、表の大きさは（２＾ｔ）＊ｔ＊ｌｏｇ（ｔ）ビットである。
【００６７】
・表ｓｕｐｅｒｂｌｏｃｋｓｅｌｅｃｔの構築：
０≦ｉ＜（Ｍ'／κ）なる整数ｉに対し、ｓｅｌｅｃｔ（Ｂ，ｉ＊κ＋１）の値を記録した表ｓｕｐｅｒｂｌｏｃｋｓｅｌｅｃｔを作る。この表の大きさは、各ｉについての値がｌｏｇＭビットで表現できるので、（Ｍ'／κ）＊ｌｏｇＭビットである。
【００６８】
・表ｓｕｐｅｒｌｏｎｇｏｒｄｅｒの構築：
０≦ｉ＜（Ｍ'／κ）なる整数ｉに対し、値がＭ'／κ以下である整数を記録した表ｓｕｐｅｒｌｏｎｇｏｒｄｅｒを作成する。ここで、各要素ｓｕｐｅｒｌｏｎｇｏｒｄｅｒ［ｉ］の値は、下記の通りとする。
ｓｕｐｅｒｂｌｏｃｋｓｅｌｅｃｔ［ｊ＋１］−ｓｕｐｅｒｂｌｏｃｋｓｅｌｅｃｔ［ｊ］＜κ＾２のとき
⇒０
それ以外のとき
⇒ｓｕｐｅｒｂｌｏｃｋｓｅｌｅｃｔ［ｊ＋１］−ｓｕｐｅｒｂｌｏｃｋｓｅｌｅｃｔ［ｊ］≧κ＾２、かつ、０≦ｊ≦ｉなる整数ｊの数
この表の大きさは、各ｉについて値をｌｏｇ（Ｍ'／κ）ビットで表現できるので（Ｍ'／κ）＊ｌｏｇ（Ｍ'／κ）ビットである。
【００６９】
・表ｌｏｎｇｓｕｐｅｒｓｅｌｅｃｔの構築：
０≦ｉ＜Ｍ'／κなる整数ｉ、０≦ｊ＜κなる整数ｊに対し、ｓｕｐｅｒｌｏｎｇｏｒｄｅｒ［ｉ］が０でないとき、ｌｏｎｇｓｕｐｅｒｓｅｌｅｃｔ［ｓｕｐｅｒｌｏｎｇｏｒｄｅｒ［ｉ］＊κ＋ｊ］＝ｓｅｌｅｃｔ（Ｂ，ｉ＊κ＋ｊ＋１）である表ｌｏｎｇｓｕｐｅｒｓｅｌｅｃｔを作成する。
【００７０】
各要素はｌｏｇＭビットで表現でき、要素数は最大（Ｍ'／κ＾２）＊κ≦Ｍ'／κなので、ｌｏｎｇｓｕｐｅｒｓｅｌｅｃｔの大きさは（Ｍ'／κ）＊ｌｏｇＭビット以下である。
【００７１】
・表ｍｉｎｉｂｌｏｃｋｓｅｌｅｃｔの構築：
０≦ｉ＜（２Ｍ'／ξ）なる各整数ｉに対し、整数値を１つ記録する表ｍｉｎｉｂｌｏｃｋｓｅｌｅｃｔを構築する。ｍｉｎｉｂｌｏｃｋｓｅｌｅｃｔ［ｉ］の値は、下記とする。
ｓｕｐｅｒｌｏｎｇｏｒｄｅｒ［ｉ＃Ξ］＝０、かつ、ｓ（ｉ＋１）−ｓ（ｉ）≦ｌｏｇＭ⇒ｓ（ｉ）−ｓｕｐｅｒｂｌｏｃｋｓｅｌｅｃｔ［ｉ／Ξ］
ｓｕｐｅｒｌｏｎｇｏｒｄｅｒ［ｉ＃Ξ］≠０、又は、ｓ（ｉ＋１）−ｓ（ｉ）＞ｌｏｇＭ⇒０
この表の大きさは、要素数が２Ｍ'／ξ、１つの値の大きさが最大κ＾２＝（ｌｏｇＭ）＾４なので、（２Ｍ'／ξ）＊４＊（ｌｏｇ（ｌｏｇＭ））ビットである。
【００７２】
・表ｍｉｎｉｌｏｎｇｏｒｄｅｒの構築：
０≦ｉ＜２Ｍ'／ξなる整数ｉに対し、値が２Ｍ'／ξ以下である整数を記録した表ｍｉｎｉｌｏｎｇｏｒｄｅｒを作成する。ｍｉｎｉｌｏｎｇｏｒｄｅｒ［ｉ］の値は、下記とする。
ｓｕｐｅｒｌｏｎｇｏｒｄｅｒ［ｉ＃Ξ］≠０、又は、ｓ（ｉ＋１）−ｓ（ｉ）≦ｌｏｇＭ⇒０
ｓｕｐｅｒｌｏｎｇｏｒｄｅｒ［ｉ＃Ξ］＝０、かつ、ｓ（ｉ＋１）−ｓ（ｉ）＞ｌｏｇＭ⇒０≦ｊ≦ｉ、ｓｕｐｅｒｌｏｎｇｏｒｄｅｒ［ｊ＃Ξ］＝０、かつ、ｓ（ｊ＋１）−ｓ（ｊ）＞ｌｏｇＭである整数ｊの数
この表の大きさは、要素数が２Ｍ'／ξ、各要素がｌｏｇ（２Ｍ'／ξ）ビットで表現できるで（２Ｍ'／ξ）＊ｌｏｇ（２Ｍ'／ξ）ビットである。
【００７３】
・表ｌｏｎｇｍｉｎｉｓｅｌｅｃｔの構築：
０≦ｉ＜２Ｍ'／ξなる整数ｉ、０≦ｊ＜ξなる整数ｊに対し、ｍｉｎｉｌｏｎｇｏｒｄｅｒ［ｉ］が０でなく、（（ｉ％κ）＃ξ）＋ｊ≦κのとき、ｌｏｎｇｍｉｎｉｓｅｌｅｃｔ［ｍｉｎｉｌｏｎｇｏｒｄｅｒ［ｉ］＊ξ＋ｊ］
＝ｓｅｌｅｃｔ（Ｂ，（ｉ／Ξ）＊κ＋（ｉ％Ξ）＊ξ＋ｊ＋１）−ｓｅｌｅｃｔ（Ｂ，（ｉ／Ξ）＊κ＋１）
である表ｌｏｎｇｍｉｎｉｓｅｌｅｃｔを作成する。各要素の値はκ＾２＝（ｌｏｇＭ）＾４以下であり、要素数は最大（２Ｍ'／ｌｏｇＭ）＊ξなので、この表の大きさは（２Ｍ'／ｌｏｇＭ）＊ξ＊４＊ｌｏｇ（ｌｏｇＭ）ビット以下である。
【００７４】
図４は、ビットベクトルの処理におけるディクショナリの構成要素であるｓｕｐｅｒｂｌｏｃｋｓｅｌｅｃｔ、ｓｕｐｅｒｌｏｎｇｏｒｄｅｒ、ｌｏｎｇｓｕｐｅｒｓｅｌｅｃｔ、ｍｉｎｉｂｌｏｃｋｓｅｌｅｃｔ、ｍｉｎｉｌｏｎｇｏｒｄｅｒ、及びｌｏｎｇｍｉｎｉｓｅｌｅｃｔの一例を示す説明図である。
【００７５】
前述の７つの表を合わせたものが、ｓｅｌｅｃｔを算出するためのディクショナリである。
【００７６】
ディクショナリの大きさをＭで除した値は、Ｍが十分大きいとき０へ収束する。したがって、ｓｅｌｅｃｔ用のディクショナリの大きさも、Ｍが十分大きければ相対的に小さなデータになると期待できる。
【００７７】
ディクショナリを使い、ｓｅｌｅｃｔ（Ｂ，ｉ＋１）は下記のように算出される。
・ｉ≧Ｍ'ならば「答え無し」と回答。
・もしｓｕｐｅｒｌｏｎｇｏｒｄｅｒ［ｉ／κ］＞０ならば、
ｌｏｎｇｓｕｐｅｒｓｅｌｅｃｔ［（ｓｕｐｅｒｌｏｎｇｏｒｄｅｒ［ｉ／κ］−１）＊κ＋（ｉ％κ）］を回答。
・ｋ＝ｍｉｎｉｌｏｎｇｏｒｄｅｒ［（ｉ／κ）＊Ξ＋（ｉ％κ）／ｌｏｇＭ］とする。ｋ＞０ならば、下記の値を回答。
ｓｕｐｅｒｂｌｏｃｋｓｅｌｅｃｔ［ｉ／κ］＋ｌｏｇｍｉｎｉｓｅｌｅｃｔ［（ｋ−１）＊ｌｏｇＭ＋（（ｉ％κ）％ｌｏｇＭ）］
・変数Ｉ＝（ｉ％κ）％ｌｏｇＭ、変数Ｊ＝ｓｕｐｅｒｂｌｏｃｋｓｅｌｅｃｔ［ｉ／κ］＋ｂｌｏｃｋｓｅｌｅｃｔ［ｉ／ｌｏｇＭ］と初期化する。
・Ｉ＜ｔならば、Ｊ＋ｓｍａｌｌｓｅｌｅｃｔ［Ｂ［Ｊ＋１．．Ｊ＋ｔ］，Ｉ］を回答する。
それ以外の場合は、ＩをＩ−ｓｍａｌｌｒａｎｋ［Ｂ［Ｊ＋１．．Ｊ＋ｔ］，ｔ］、ＪをＪ＋ｔで置き換えて、前述の処理を繰り返す。
【００７８】
最後の繰り返しは、ｍｉｎｉｌｏｎｇｏｒｄｅｒの作り方からｓｅｌｅｃｔ（Ｂ，ｉ＋１）−ＪがｌｏｇＭ以下であることが保証されているため、最大２回である。したがって、高々７回の表引きによって、ｓｅｌｅｃｔ（Ｂ，ｉ＋１）が計算できる。
【００７９】
以下、ビットベクトルを用いて、各索引語ｗの、文書ｄ（ｗ，ｉ）における位置リストＰ（ｗ，ｉ）にアクセスする方法について説明する。
【００８０】
まず、各索引語ｗに対し、Ｐ'（ｗ）の長さに等しいビットベクトルＢＢ（ｗ）を用意する。
【００８１】
そして、ビットベクトルＢＢ（ｗ）のｋ番目の文字を以下で定義する。なお、ビットベクトルＢＢ（ｗ）のｋ番目の文字をＢＢ（ｗ，ｋ）と記載する。
ＢＢ（ｗ，ｋ）＝１（Ｐ'（ｗ）において、ｋバイト目から始まる位置リストＰ（ｗ，ｉ）が存在する場合）…（６）
ＢＢ（ｗ，ｋ）＝０（Ｐ'（ｗ）において、ｋバイト目から始まる位置リストＰ（ｗ，ｉ）が存在しない場合）…（７）
ビットベクトルＢＢ（ｗ）を用いると、ｓｅｌｅｃｔ（Ｂ，ｉ）が指し示す場所から、ｉ番目の文書ｄ（ｗ，ｉ）の位置リストＰ（ｗ，ｉ）が格納されていることが分かる。
【００８２】
なお、Ｐ（ｗ）を圧縮されたデータＰ'（ｗ）に変換する場合、ｖａｒｉａｂｌｅ  ｂｙｔｅ法（例えば、非特許文献２参照）のような、各数値の境界がバイト境界に整列される方法を用いることが好ましい。そのようにすれば、ビットベクトルＢＢ（ｗ）の長さをＰ'（ｗ）のバイト数とできるためである。
【００８３】
ここで、ｖａｒｉａｂｌｅ  ｂｙｔｅ法について説明する。
【００８４】
図６は、ビットベクトルの処理におけるｖａｒｉａｂｌｅ  ｂｙｔｅ法の一例を説明する図である。
【００８５】
以下、ｖａｒｉａｂｌｅ  ｂｙｔｅ法を用いて、任意の整数xをデータ列に変換する方法を説明する。
【００８６】
ｘの２進数表現を下位から順に７桁ずつ区切ったものをｘ（１）、ｘ（２）、…、ｘ（ｋ−１）、ｘ（ｋ）とする。このとき、ｖａｒｉａｂｌｅ  ｂｙｔｅ法ではデータ列としてｘ（ｋ）＋１２８、ｘ（ｋ−１）＋１２８、…、ｘ（２）、ｘ（１）が出力される。
【００８７】
なお、出力されたデータ列から元の値を得る方法は次の通りである。
【００８８】
まず、変数ｘを０に初期化する。そしてデータ列を読み、１２８以上の値ｘ'が読み出されるたびにｘをｘ＊１２８＋ｘ'−１２８で置き換える。１２７以下の値ｘ'が現れたときには、ｘ＊１２８＋ｘ'が元のｘの値である。
【００８９】
図６は、整数１２３４５６（２進法では、１１１１０００１００１００００００）がデータ列に変換された例を示している。
【００９０】
なお、Ｐ（ｗ）内の各Ｐ（ｗ，ｉ）に含まれる位置を表す数値を記録するときは、その数値そのものではなく、それらの数値を事前に昇順に並べ替えた上で、直前の数値との差分を記録することが好ましい。なぜなら、差分を取ることで記録すべき値が小さくなり、ｖａｒｉａｂｌｅ  ｂｙｔｅ法によって変換されるデータ列が短くなると期待されるためである。Ｐ（ｗ）の最初の値だけは、差分を取らずにそのまま記録する。
【００９１】
もし、ビット単位の圧縮を行ない位置リストＰ（ｗ，ｉ）の境界がバイト境界と必ずしも一致しないとすれば、ビットベクトルＢＢ（ｗ）の長さはＰ'（ｗ）のビット数となり大幅に長くなってしまう。
【００９２】
以下では、Ｐ（ｗ）はｖａｒｉａｂｌｅ  ｂｙｔｅ法を用いてＰ'（ｗ）へ圧縮されたものとする。
【００９３】
［第１の実施形態］
図７は、本発明の第１の実施形態における文書集合１０１と、文書集合１０１に基づいて構築される転置インデックス１０２の概略を示す説明図である。
【００９４】
図７に示すように、位置レベル転置インデックス３０２には、位置リストＰ（ｗ，ｉ）とビットベクトルＢＢ（ｗ）とが対応づけられて格納されている。
【００９５】
前述したように、ビットベクトルＢに対しｓｅｌｅｃｔ（Ｂ，ｉ）を計算するためのディクショナリの大きさは、ビットベクトルＢが十分に長い場合、ビットベクトルＢの長さに対して相対的に０に近づくように構築できることが知られており、小さなデータで表現できる。
【００９６】
ここで、ポインタ４０１の１つのサイズを４バイトと仮定する。すべての索引語ｗのｎ（ｗ）の総和をＮとし、Ｐ'（ｗ）の長さの総和をＬとする。
【００９７】
この場合、図２３に示す例のようにポインタ４０１を用いる場合、ポインタ４０１のサイズの総和は、４Ｎバイトである。
【００９８】
一方、ビットベクトルＢの長さＬに対し、ディクショナリの大きさがαＬビットとすれば、ビットベクトルＢとディクショナリとの大きさの和は、（１＋α）Ｌビットである。
【００９９】
従って、索引語ｗが現れる各文書ｄ（ｗ，ｉ）について、位置リストＰ（ｗ，ｉ）を表すデータの長さの平均Ｌ／Ｎが、３２／（１＋α）バイト未満であれば、ビットベクトルＢを用いたほうが少ないデータ量となる。
【０１００】
このため、個々の索引語ｗが同一文書中に現れる回数が少なければ、データ量削減の効果が高くなると期待される。
【０１０１】
図８は、本発明の第１の実施形態の装置構成を説明するブロック図である。
【０１０２】
本発明の第１の実施形態における装置は、中央演算装置（ＣＰＵ）６０１、主記憶装置６０２、補助記憶装置６０３を備え、これらは互いに接続される。また、中央演算装置（ＣＰＵ）６０１には、ネットワーク６０４及びユーザ端末６０５に接続される。
【０１０３】
中央演算装置（ＣＰＵ）６０１は、主記憶装置６０２上に展開されている各プログラムを実行する。主記憶装置６０２は、メモリ又はその他の記憶媒体である。補助記憶装置６０３は、例えば、ハードディスク又はその他の記憶媒体である。
【０１０４】
主記憶装置６０２は、索引語切り出しプログラムＳ７０１、索引語位置抽出プログラムＳ７０２、文書識別番号割当プログラムＳ７０３、文書レベル転置インデックス作成プログラムＳ７０４、位置レベル転置インデックス作成プログラムＳ７０５、ビットベクトル作成プログラムＳ７０６、文書レベル検索プログラムＳ７０７、位置レベル検索プログラムＳ７０８、及び属性インデックス作成プログラム７０９を備える。
【０１０５】
なお、属性インデックス作成プログラム７０９の詳細は第２の実施形態で説明する。
【０１０６】
また、主記憶装置６０２は、文書レベル転置インデックス３０１を格納する。なお、文書レベル転置インデックス３０１は、主記憶装置６０２に格納されることが望ましいが、補助記憶装置６０３に格納されてもよい。
【０１０７】
補助記憶装置６０３は、文書集合１０１、及び位置レベル転置インデックス３０２を格納する。
【０１０８】
以下の説明では、文書レベル転置インデックス３０１、及び位置レベル転置インデックス３０２は補助記憶装置６０３に格納されているものとする。
【０１０９】
図９は、本発明の第１の実施形態のデータ及び処理の流れを示す説明図である。
【０１１０】
中央演算装置（ＣＰＵ）６０１は、補助記憶装置６０３に格納される文書集合１０１から検索対象の文書１０４を１つずつ取得する。取得された各々の検索対象の文書１０２に、以下の処理が実行される。
【０１１１】
まず、中央演算装置（ＣＰＵ）６０１は、索引語切り出しプログラムＳ７０１を実行する。これによって、索引語ｗが文書１０４から切り出される。索引語ｗの切り出し方法として、前述のように、形態素解析方法、又はｎ−ｇｒａｍを用いる方法が考えられる。なお、本発明はこれ限定されず、他の方法を用いてもよい。
【０１１２】
次に、中央演算装置（ＣＰＵ）６０１は、索引語位置抽出プログラムＳ７０２を実行する。これによって、切り出された索引語ｗが、文書１０４中の何文字目に現れたのかが計算され、位置リストＰ（ｗ，ｉ）が構成される。
【０１１３】
また、中央演算装置（ＣＰＵ）６０１は、文書識別番号割当プログラムＳ７０３を実行する。これによって、処理中の文書１０４に文書識別番号１０５が割り当てられる。これによって、切り出された索引語ｗの文書リストＤ（ｗ，ｉ）が構成される。
【０１１４】
なお、文書識別番号１０５の割り当て方法とし、例えば、「１」に初期化された整数変数を１つ保持し、新しい文書識別番号が割り当てられるときに、当該変数の値を割り当て、次に割り当てる場合に、当該変数に１を加算した値を割り当てる方法が考えられる。
【０１１５】
索引語位置抽出プログラムＳ７０２、及び文書識別番号割当プログラムＳ７０３が実行されることによって、各索引語ｗの各文書ｄ（ｗ，ｉ）における文書リストＤ（ｗ，ｉ）及び位置リストＰ（ｗ，ｉ）が得られる。
【０１１６】
次に、中央演算装置（ＣＰＵ）６０１は、得られた各索引語ｗの各文書ｄ（ｗ，ｉ）における文書リストＤ（ｗ，ｉ）及び位置リストＰ（ｗ，ｉ）を用いて、文書レベル転置インデックス作成プログラムＳ７０４及び位置レベル転置インデックス作成プログラムＳ７０５を実行する。これによって、Ｄ'（ｗ）及びＰ'（ｗ）が得られる。
【０１１７】
中央演算装置（ＣＰＵ）６０１は、ビットベクトル作成プログラムＳ７０６を実行する。これによって、各索引語ｗのビットベクトルＢＢ（ｗ）が作成され、式（５）に示すｓｅｌｅｃｔを計算するためのディクショナリが構築される。
【０１１８】
以下、文書レベル転置インデックス作成プログラムＳ７０４、位置レベル転置インデックス作成プログラムＳ７０５、及びビットベクトル作成プログラムＳ７０６の詳細な処理について説明する。
【０１１９】
図１０は、本発明の第１の実施形態の中央演算装置（ＣＰＵ）６０１が実行する文書レベル転置インデックス作成プログラムＳ７０４の処理の詳細を説明するフローチャートである。
【０１２０】
文書レベル転置インデックス作成プログラムＳ７０４は、文書集合１０１に未処理の文書１０４があるか否かを判定する（Ｓ７０４１）。
【０１２１】
文書集合１０１に未処理の文書１０４があるかと判定された場合、文書レベル転置インデックス作成プログラムＳ７０４は、順次、未処理の文書１０４を読み出し、当該文書１０４に現れる索引語ｗを入力する（Ｓ７０４２）。具体的には、未処理の文書１０４に割り当てられた文書識別番号１０５（以下、この番号をｄとする）を入力し、また、当該文書１０４に現れる索引語ｗを入力する。
【０１２２】
次に、文書レベル転置インデックス作成プログラムＳ７０４は、変数ｉに「１」を代入する（Ｓ７０４３）。ここで、変数ｉは、文書１０４に現れるそれぞれの索引語ｗの番号を表すものであり、ｎは文書ｄ中の互いに異なる索引語の数を表すものである。
【０１２３】
文書レベル転置インデックス作成プログラムＳ７０４は、文書リストＤ（ｗi）が存在するか否かを判定する（Ｓ７０４４）。当該判定によって、索引語ｗiが、文書１０４の中において初めて現れたか否かが判定される。
【０１２４】
文書リストＤ（ｗi）が存在すると判定された場合、文書レベル転置インデックス作成プログラムＳ７０４は、Ｓ７０４６に進む。
【０１２５】
文書リストＤ（ｗi）が存在しないと判定された場合、文書レベル転置インデックス作成プログラムＳ７０４は、新たに文書リストＤ（ｗi）を空リストとして生成する（Ｓ７０４５）。当該処理によって、新規索引語ｗiの文書リストＤ（ｗi）が生成される。
【０１２６】
文書レベル転置インデックス作成プログラムＳ７０４は、文書リストＤ（ｗi）の末尾に文書識別番号ｄ１０５を追加する（Ｓ７０４６）。当該処理によって、索引語ｗiが現れる文書１０４が文書リストＤ（ｗi）に追加される。
【０１２７】
次に、文書レベル転置インデックス作成プログラムＳ７０４は、変数ｉに１を加算し（Ｓ７０４７）、変数ｉがｎより大きいか否かを判定する（Ｓ７０４８）。つまり、文書１０４に他の索引語ｗが含まれるか否かが判定される。
【０１２８】
変数ｉがｎより小さいと判定された場合、文書レベル転置インデックス作成プログラムＳ７０４は、Ｓ７０４４に戻り、前述した処理を実行する。
【０１２９】
変数ｉがｎより大きいと判定された場合、文書レベル転置インデックス作成プログラムＳ７０４は、Ｓ７０４１に戻り、前述した処理を実行する。
【０１３０】
Ｓ７０４１において、文書集合１０１に未処理の文書１０４がないと判定された場合、文書レベル転置インデックス作成プログラムＳ７０４は、全索引語ｗに対し、文書リストＤ（ｗ）を圧縮してＤ'（ｗ）に変換し、Ｄ'（ｗ）を結果として出力する（Ｓ７０４９）。
【０１３１】
以上の処理によって、文書レベル転置インデックス３０１が作成される。
【０１３２】
なお、Ｄ'（ｗ）を作成する場合に、文書識別番号１０５のほかに、文書１０４における索引語ｗの出現回数１０６も含めて格納することが好ましい（例えば、特許文献１参照）。
【０１３３】
特許文献１に記載の方法では、予め、出現回数１０６を表現するためのビット数ｂを決めておく。文書識別番号１０５を記録するときには、記録すべき値を小さくするために、文書識別番号１０５そのものではなく文書リストＤ（ｗ）内の直前の文書番号との差分ｄを記録する。
【０１３４】
もし出現回数ｆ１０６が２＾ｂ未満であれば、ｄ＊（２＾ｂ）＋ｆが前述したｖａｒｉａｂｌｅ  ｂｙｔｅ法を用いてデータ列へ変換される。
【０１３５】
出現回数ｆ１０６が２＾ｂ以上であれば、ｄ＊（２＾ｂ）が前述したｖａｒｉａｂｌｅ  ｂｙｔｅ法を用いてデータ列へ変換され、さらに出現回数ｆ１０６をｖａｒｉａｂｌｅ  ｂｙｔｅ法を用いて変換されたデータ列が後置される。
【０１３６】
図１１は、本発明の第１の実施形態の中央演算装置（ＣＰＵ）６０１が実行する位置レベル転置インデックス作成プログラムＳ７０５の処理の詳細を説明するフローチャートである。
【０１３７】
位置レベル転置インデックス作成プログラムＳ７０５は、文書集合１０１に未処理の文書１０４があるか否かを判定する（Ｓ７０５１）。
【０１３８】
文書集合１０１に未処理の文書１０４があるかと判定された場合、位置レベル転置インデックス作成プログラムＳ７０５は、未処理の文書１０４に現れる全索引語ｗ及び各索引語ｗの出現位置のリストＰ（ｗ，ｋ）を入力する（Ｓ７０５２）。ただし、ｋはｄ（ｗ，ｋ）＝ｄなる整数である。
【０１３９】
次に、位置レベル転置インデックス作成プログラムＳ７０５は、変数ｉに「１」を代入する（Ｓ７０５３）。ここで、変数ｉは、文書１０４に現れるそれぞれの索引語ｗの番号を表すものであり、ｎは文書ｄ中の互いに異なる索引語の数を表すものである。
【０１４０】
位置レベル転置インデックス作成プログラムＳ７０５は、索引語ｗiの位置リストＰ（ｗi）が存在するか否かを判定する（Ｓ７０５４）。当該判定によって、索引語ｗiが、文書１０４において初めての現れた単語であるか否かが判定される。
【０１４１】
位置リストＰ（ｗi）が存在すると判定された場合、位置レベル転置インデックス作成プログラムＳ７０５は、Ｓ７０５６に進む。
【０１４２】
位置リストＰ（ｗi）が存在しないと判定された場合、位置レベル転置インデックス作成プログラムＳ７０５は、新たに位置リストＰ（ｗi）を空リストとして生成する（Ｓ７０５５）。当該処理によって、新規索引語ｗiの位置リストＰ（ｗi）が生成される。
【０１４３】
位置レベル転置インデックス作成プログラムＳ７０５は、位置リストＰ（ｗi）の末尾に処理中の文書１０４における検索語ｗiの位置リストＰ（ｗi，ｊ）を追加する（Ｓ７０５６）。
【０１４４】
次に、位置レベル転置インデックス作成プログラムＳ７０５は、変数ｉに１を加算し（Ｓ７０５７）、変数ｉがｎより大きいか否かを判定する（Ｓ７０５８）。つまり、文書１０４に他の索引語ｗが含まれるか否かが判定される。
【０１４５】
変数ｉがｎより小さいと判定された場合、位置レベル転置インデックス作成プログラムＳ７０５は、Ｓ７０５４に戻り、前述した処理を実行する。
【０１４６】
変数ｉがｎより大きいと判定された場合、位置レベル転置インデックス作成プログラムＳ７０５は、Ｓ７０５１に戻り、前述した処理を実行する。
【０１４７】
Ｓ７０５１において、文書集合１０１に未処理の文書１０４が無いと判定された場合、位置レベル転置インデックス作成プログラムＳ７０５は、全索引語ｗに対し、位置リストＰ（ｗ）をＰ'（ｗ）に変換し、Ｐ'（ｗ）を結果として出力する（Ｓ７０５９）。
【０１４８】
以上の処理によって位置レベル転置インデックス３０２が作成される。
【０１４９】
図１２は、本発明の第１の実施形態の中央演算装置（ＣＰＵ）６０１が実行するビットベクトル作成プログラムＳ７０６の処理の詳細を説明するフローチャートである。
【０１５０】
ビットベクトル作成プログラムＳ７０６は、作成すべきビットベクトルの長さｎを入力し、さらに、ビットベクトルにおいて「１」に設定すべき条件Ｃを入力する（Ｓ７０６１）。例えば、式（６）及び式（７）を満たすビットベクトルを構築する場合、条件Ｃの内容は「当該位置から始まる位置リストが存在すること」である。
【０１５１】
ビットベクトル作成プログラムＳ７０６は、主記憶装置６０２に長さｎの文字列を格納するための記憶領域を確保する（Ｓ７０６２）。例えば、１文字あたり１ビットの記憶領域が確保される場合、長さｎの文字列を格納するためにｎビットの記憶領域が確保される。
【０１５２】
以下の説明では、１文字あたり１ビットの記憶領域が確保されるものとする。
【０１５３】
ビットベクトル作成プログラムＳ７０６は最初に、長さｎの文字列をすべて「０」に初期化する（Ｓ７０６３）。
【０１５４】
次に、ビットベクトル作成プログラムＳ７０６は、変数ｉに「１」に設定する（Ｓ７０６４）。ここで、変数ｉは、ビットベクトルＢの位置を示すものである。
【０１５５】
ビットベクトル作成プログラムＳ７０６は、変数ｉの値が条件Ｃを満たすか否かを判定する（Ｓ７０６５）。
【０１５６】
変数ｉの値が条件Ｃを満たさないと判定された場合、ビットベクトル作成プログラムＳ７０６は、Ｓ７０６７に進む。
【０１５７】
変数ｉの値が条件Ｃを満たさないと判定された場合、ビットベクトル作成プログラムＳ７０６は、変数ｉが示すビットベクトル中の文字を「１」に設定する（Ｓ７０６６）。
【０１５８】
ビットベクトル作成プログラムＳ７０６は、変数ｉに１を加算し（Ｓ７０６７）、変数ｉがｎより大きいか否かを判定する（Ｓ７０６８）。
【０１５９】
変数ｉがｎより小さいと判定された場合、ビットベクトル作成プログラムＳ７０６は、Ｓ７０６５に戻り、前述した処理を実行する。
【０１６０】
変数ｉがｎより大きいと判定された場合、ビットベクトル作成プログラムＳ７０６は、処理を終了する。
【０１６１】
ビットベクトル作成プログラムＳ７０６は、以上の処理によって、ビットベクトルを構築する。
【０１６２】
ビットベクトル作成プログラムＳ７０６を用いて、全索引語ｗのそれぞれについてビットベクトルＢＢ（ｗ）を構築される。そのためには、前述した処理において条件Ｃを「Ｐ'（ｗ）において位置ｉから格納される位置リストＰ（ｗ，ｋ）が存在する」とし、ｎをＰ'（ｗ）の長さとすればよい。さらに、前述したディクショナリ構築方法によって、ｓｅｌｅｃｔを算出するためのディクショナリが構築される。
【０１６３】
次に、本発明における転置インデックス１０２を用いた検索方法について説明する。なお、以下の説明において、索引語ｗが出現する文書リストＤ（ｗ）を求める検索は文書レベルの検索と呼び、索引語ｗの出現するｉ番目の文書ｄ（ｗ，ｉ）における位置リストＰ（ｗ，ｉ）を求める検索は位置レベルの検索と呼ぶ。
【０１６４】
図１３は、本発明の第１の実施形態における、文書レベルの検索の処理について説明するフローチャートである。
【０１６５】
中央演算装置（ＣＰＵ）６０１が文書レベル検索プログラムＳ７０７を実行することによって処理が開始される。
【０１６６】
文書レベル検索プログラムＳ７０７は、検索対象の索引語ｗを取得する（Ｓ７０７１）。
【０１６７】
次に、文書レベル検索プログラムＳ７０７は、文書レベル転置インデックス３０１からＤ'（ｗ）を取得し（Ｓ７０７２）、取得されたＤ'（ｗ）から文書リストＤ（ｗ）を抽出する（Ｓ７０７３）。
【０１６８】
図１４は、本発明の第１の実施形態における、位置レベルの検索の処理について説明するフローチャートである。
【０１６９】
中央演算装置（ＣＰＵ）６０１が位置レベル検索プログラムＳ７０８を実行することによって処理が開始される。
【０１７０】
位置レベル検索プログラムＳ７０８は、検索対象の索引語ｗを取得する（Ｓ７０８１）。
【０１７１】
位置レベル検索プログラムＳ７０８は、索引語ｗが出現する何番目の文書における位置リストを取得したいかを知るために、１≦ｉ≦ｎ（ｗ）なる整数ｉを入力する（Ｓ７０８２）。整数ｉに基づき、位置レベル検索プログラムＳ７０８は文書ｄ（ｗ，ｉ）における索引語ｗの位置リストＰ（ｗ，ｉ）を、Ｐ'（ｗ）から下記の通り抽出する。
【０１７２】
位置レベル検索プログラムＳ７０８は、位置レベル転置インデックス３０２内のＰ'（ｗ）において、文書識別番号１０５がｄ（ｗ，ｉ）の文書１０４の位置リストＰ（ｗ，ｉ）が格納されている位置をｓｅｌｅｃｔ（ＢＢ（ｗ），ｉ）を計算して取得する（Ｓ７０８５）。
【０１７３】
当該処理によって、位置レベル検索プログラムＳ７０８は、文書レベル転置インデックス３０１から、位置レベル転置インデックス３０２内の適切な文書１０４の位置リストＰ（ｗ，ｉ）へアクセスできる。Ｐ（ｗ，ｉ）を取得するためには、Ｐ（ｗ）を先頭から読むときと同様に、圧縮されたＰ'（ｗ）のデータを当該位置から元の値に復元していけばよい。
【０１７４】
最後に、位置レベル検索プログラムＳ７０８は、位置リストＰ（ｗ，ｉ）を出力する（Ｓ７０８６）。
【０１７５】
以下、本発明の第１の実施形態の効果について説明する。
【０１７６】
図１５及び図１６は、本発明の第１の実施形態の効果を説明する図である。
【０１７７】
本発明の第１の実施形態における方法を実装した計算機を用いて、メモリ使用及び計算時間を計測する実験を行った。
【０１７８】
実験においては、ＣＰＵにはＩｎｔｅｌ（登録商標）社製のＣｏｒｅ  ２（登録商標）  Ｑｕａｄ  Ｑ９５５０を搭載し、メモリを８ＧＢ、ＨＤＤを１ＴＢ搭載し、ＯＳにはＬｉｎｕｘ（登録商法）を使用した計算機を用いた。
【０１７９】
文書集合１０１、つまり、処理対象は、２００５年の公開特許公報２０００件にテキストデータである。索引語としては、数字、記号、及びアルファベット以外の２文字からなる２グラムを使用した。
【０１８０】
ビットベクトルのｓｅｌｅｃｔの計算には、前述の方法を用いた。文書識別番号ｄ（ｗ，ｉ）を格納するときには、位置リストＰ（ｗ，ｉ）の長さを取得したり、スコア計算を行ったりするために、ｆ（ｗ，ｉ）も格納した。
【０１８１】
また、ｖａｒｉａｂｌｅ  ｂｙｔｅ法では、小さな整数ほど小さく圧縮できるので、文書リストＤ（ｗ）＝＜ｄ（ｗ，１）、…ｄ（ｗ，ｎ（ｗ））＞を昇順の数列となるようにし、ｉ≧２のとき、文書識別番号ｄ（ｗ，ｉ）を以下のように変換した。
ｄ'（ｗ，ｉ）＝ｄ（ｗ，ｉ）−ｄ（ｗ，ｉ−１）…（８）
ｄ（ｗ，１）は、そのままｖａｒｉａｂｌｅ  ｂｙｔｅ法を用いて格納した。また、ｄ'（ｗ，ｉ）とｆ（ｗ，ｉ）とを効率よく格納するために、ｆ（ｗ，ｉ）が小さい値となる場合が多いことを利用してｆ（ｗ，ｉ）＜４のときは、ｄ'（ｗ，ｉ）＊４＋ｆ（ｗ，ｉ）をｖａｒｉａｂｌｅ  ｂｙｔｅ法を用いて格納し、ｆ≧４のときは、ｄ'（ｗ，ｉ）＊４とｆ（ｗ，ｉ）とをそれぞれｖａｒｉａｂｌｅ  ｂｙｔｅ法を用いて格納した。
【０１８２】
位置リストＰ（ｗ，ｉ）も文書リストＤ（ｗ）と同様に、昇順の数列となるようにし、ｊ≧２の場合、ｐ（ｗ，ｉ，ｊ）の代わりにｐ（ｗ，ｉ，ｊ）−ｐ（ｗ，ｉ，ｊ−１）をｖａｒｉａｂｌｅ  ｂｙｔｅ法を用いて格納した。なお、ｐ（ｗ，ｉ，１）は、そのままｖａｒｉａｂｌｅ  ｂｙｔｅ法を用いて格納した。
【０１８３】
本実験において、位置情報を含む転置インデックス１０２としては、次の３つの手法を比較した。
（Ａ）文書リストＤ（ｗ）中に位置リストＰ（ｗ，ｉ）を混在させたもの。
（Ｂ）文書レベル転置インデックス３０１及び位置レベル転置インデックス３０２を分離して格納し、各索引語ｗが出現する各文書ｄ（ｗ，ｉ）に対し、Ｐ'（ｗ）内での出現位置を表す４バイトの整数値である、ポインタ４０１を格納したもの。
（Ｃ）文書レベル転置インデックス３０１及び位置レベル転置インデックス３０２を分離して格納し、各索引語ｗが出現する各文書ｄ（ｗ，ｉ）に対し、ｓｅｌｅｃｔ（ＢＢ（ｗ），ｉ）を算出してＰ'（ｗ）内での出現位置を求めるもの。
【０１８４】
ここで、（Ａ）は、図２１に示した転置インデックス１０２を用いたものに対応し、（Ｂ）は、図２３に示した転置インデックス１０２を用いたものに対応し、（Ｃ）は、図７に示した転置インデックス１０２を用いたもの、つまり、本発明に対応するものである。
【０１８５】
図１５に、各手法で構築した転置インデックス１０２のサイズを示す。
【０１８６】
（Ａ）は、索引サイズが全データ構造の大きさである。（Ｂ）は、索引サイズ及びポインタの合計値が全データ構造の大きさである。（Ｃ）は、索引サイズ、及びビットベクトルとディクショナリとを足し合わせた値の合計値が全データ構造の大きさである。
【０１８７】
位置リストＰ（ｗ）にアクセスするための追加のデータ構造を持たない（Ａ）のサイズに近いほど、追加のデータ構造が小さく抑えられていることを示す。
【０１８８】
（Ｂ）では、追加のデータが約１３．７ＭＢ必要であった。これに対し、（Ｃ）では、追加データが約５．８ＭＢの増加であり、データ増加量は、５．８／１３．７＝４２％に留めることができた。
【０１８９】
図１６は、転置インデックス１０２の読取時間を示す。
【０１９０】
当該読取処理では、文書識別番号１０５と出現頻度とを算出する処理と、文書識別番号１０５、出現頻度、及び位置情報を算出する処理の２種類の処理についての結果を示す。
【０１９１】
文書識別番号１０５と出現頻度とを算出する処理では、（Ｂ）及び（Ｃ）は、同等の処理結果となり、位置情報の読み飛ばしが必要な（Ａ）に比べて、４倍以上高速なアクセスが可能であった。
【０１９２】
文書識別番号１０５、出現頻度、及び位置情報を算出する処理では、（Ｃ）の処理結果は、（Ａ）の約１．８倍、（Ｂ）の１．６倍の時間であった。
【０１９３】
この結果から、本発明は、通常は位置情報を使わない検索を主に実行し、低頻度で位置情報を用いる検索が要求される状況において、位置情報をコンパクトに格納するために有用な技術と言える。
【０１９４】
［第２の実施形態］
文書検索において、ユーザが求める文書を的確に検索するためには、文書の表面的なテキスト情報だけでなく、文書の内容を考慮して検索することが求められる。
【０１９５】
前述のような検索を実現するために、形態素解析等の自然言語処理の解析結果、及び外部ＤＢとテキストとの対応関係を、属性として検索対象文書の各索引語に付与し、検索条件に指定可能とすることが重要である。
【０１９６】
本発明の第２の実施形態では、前述の位置情報を含む転置インデックス１０２を活用し、属性検索を行なう方法について説明する。
【０１９７】
第２の実施形態における装置構成は、第１の実施形態と同一であるため説明を省略する。
【０１９８】
図１７は、本発明の第２の実施形態における検索対象の文書集合１０１の一例を示す説明図である。
【０１９９】
図１７に示す例では、文書集合１０１は、３つの文書から構成される。個々の文書中の索引語には、品詞及び文節の種類が属性として付与される。これによって、例えば、「自転が名詞として出現する文書」といった条件による検索を可能とする。
【０２００】
また、当該文書集合１０１においては、属性の区切りに応じて、文書中の同一の文字が、複数個の索引語に属することを許す。例えば、文書１の最初の文字「自」は、「自転車」、「自転」、及び「自転車を」の３つの索引語に属する。
【０２０１】
図１８は、本発明の第２の実施形態における属性インデックスの一例を示す説明図である。
【０２０２】
文書１０４に付与されている属性を取得するために、属性インデックスと呼ぶデータ構造を構築する。
【０２０３】
以下、属性インデックスを構築する処理について説明する。中央演算装置（ＣＰＵ）６０１が属性インデックス作成プログラムＳ７０９を実行することによって、当該処理が行われる。
【０２０４】
（Ｃ１）属性インデックス作成プログラムＳ７０９は、検索対象の文書集合１０１の文書数に等しい大きさの、配列Ｄを用意する。属性インデックス作成プログラムＳ７０９は、文書集合１０１中のすべてのｄについて、文書識別番号１０５がｄより小さい文書１０４の長さの総和をＤ［ｄ］として設定する。以下、文書識別番号１０５がｄの文書１０４を、文書ｄとも記載する。
【０２０５】
（Ｃ２）属性インデックス作成プログラムＳ７０９は、全文書１０４の長さの総和に等しい２つのビットベクトルＢＰｆ、及びＢＰｂを用意し、すべての文字を０に初期化する。
【０２０６】
属性インデックス作成プログラムＳ７０９は、ｐ番目の文字が、それぞれ以下の条件が成立するときに、ｐ番目の文字に１に設定する。
（条件１）ＢＰｆ：任意の文書ｄに、位置（ｐ−Ｄ［ｄ］）から始まる索引語が存在する。
（条件２）ＢＰｂ：任意の文書ｄに、位置（ｐ−Ｄ［ｄ］）で終わる索引語が存在する。
【０２０７】
（Ｃ３）属性インデックス作成プログラムＳ７０９は、文書集合１０１中のすべての索引語１０３を並べたリストＱを構築する。リストＱ中の各索引語１０３は、以下に示す順に整列される。文書集合１０１に複数回出現する索引語１０３は、リストＱ中に出現回数と同じ数だけ現れる。
（Ｃ３ａ）出現位置の文書識別番号１０５が小さい方が前。
（Ｃ３ｂ）出現位置の文書識別番号１０５が等しい場合、位置が先頭に近いほうが前。
先頭の文書１０４の、先頭の位置から順に抽出すれば、リストＱが構築できる。
【０２０８】
（Ｃ４）属性インデックス作成プログラムＳ７０９は、変数ｉを、リストＱの長さ｜Ｑ｜に設定する。以下、リストＱに含まれる個々の索引語をＱ［ｉ］（１≦ｉ≦｜Ｑ｜）と記載する。
【０２０９】
属性インデックス作成プログラムＳ７０９は、文書集合１０１を、最後の文書１０４の最後の位置から順に、文書１０４の先頭方向へ読んでいく。文書１０４の先頭に到達したら、１つ前の文書１０４を同様の手順で読む。属性インデックス作成プログラムＳ７０９は、前述の手順で文書１０４を読みながら、以下の処理を行なう。なお、現在読んでいる文書１０４の文書番号をｄとし、読んでいる位置をｐ'とする。
【０２１０】
（Ｃ４ａ）索引語Ｑ［ｉ］の終わる位置が文書ｄの前の文書１０４である場合、又は文書ｄであって位置ｐ'よりも文書ｄの先頭に近い場合、属性インデックス作成プログラムＳ７０９は、次の位置の処理に移る。
【０２１１】
（Ｃ４ｂ）索引語Ｑ［ｉ］の終わる位置が文書ｄの後の文書１０４である場合、又は文書ｄであって位置ｐ'よりも文書ｄの先頭から遠い場合、属性インデックス作成プログラムＳ７０９は、索引語Ｑ［ｉ］に「※」の印をつけて変数ｉから１を減じ、（Ｃ４ａ）からの処理を繰り返し実行する。
【０２１２】
（Ｃ４ｃ）索引語Ｑ［ｉ］の終わる位置が文書ｄであって位置ｐ'に等しい場合、属性インデックス作成プログラムＳ７０９は、変数ｉから１を減じて再度（Ｃ４ｃ）の処理を実行する。当該処理の繰り返し実行する過程で文書ｄの位置ｐ'で終わる索引語がすべて見つかれば、属性インデックス作成プログラムＳ７０９は、最後に現れた索引語Ｑ［ｉ］に「＃」の印をつけ、次の位置の処理に移る。
【０２１３】
（Ｃ４ｄ）属性インデックス作成プログラムＳ７０９は、（Ｃ４ｃ）の処理を繰り返し実行して発見されなかった、文書ｄの位置ｐ'で終わる索引語を、すべて索引語Ｑ［ｉ］の直後に挿入する。属性インデックス作成プログラムＳ７０９は、これらのうち、リストＱの先頭に最も近い位置に挿入された索引語に「＃」の印をつける。
【０２１４】
（Ｃ５）属性インデックス作成プログラムＳ７０９は、リストＱを先頭から読み出し、各索引語の直後に、当該索引語と出現範囲が等しい属性をすべて挿入する。
【０２１５】
（Ｃ６）属性インデックス作成プログラムＳ７０９は、リストＱに含まれる索引語及び属性に、索引語識別番号を付与する。索引語識別番号を付与する方法としては、例えば、１に初期化された整数変数を１つ保持し、新しい索引語識別番号が必要な場合に、当該変数の値を割り当て、その直後に前記変数の値を１増やすことである。すでに索引語識別番号が割り当てられた索引語及び属性をハッシュ表に登録し、ハッシュ表に登録済みか否かを判定することによって、新しい索引語識別番号が必要であるか否かを判定できる。登録済みの索引語及び属性に対しては、登録時と同じ索引語識別番号が付与される。
【０２１６】
（Ｃ７）属性インデックス作成プログラムＳ７０９は、リストＱの各索引語及び属性に、（Ｃ６）において付与された索引語識別番号を、リストＱに含まれる順に圧縮して格納する。圧縮方法として、例えば、ｖａｒｉａｂｌｅ  ｂｙｔｅ法が考えられる。なお、圧縮して得られたデータをＱ'と記載する。
【０２１７】
（Ｃ８）属性インデックス作成プログラムＳ７０９は、Ｑ'の長さに等しい４本のビットベクトルＢＱｆ、ＢＳｆ、ＢＱｂ、及びＢＳｂと、Ｑ'の長さに１を加えた長さのビットベクトルＢＡとを用意する。
【０２１８】
属性インデックス作成プログラムＳ７０９は、ビットベクトル作成プログラムＳ７０６を用いて、それぞれのビットベクトルのすべての文字を「０」に初期化した後にＱ'上の場所ｑについて、それぞれ下記の索引語の索引語番号の先頭の場所であるときに、各ビットベクトルのｑ番目の文字を「１」に設定する。
ＢＡの場合：全索引語
ＢＱｆの場合：（Ｃ３）においてリストＱに挿入された索引語で文書中の同一位置で始まる索引語のうち、最初の索引語
ＢＱｂの場合：（Ｃ４ｃ）又は（Ｃ４ｄ）において「＃」の印がついた索引語
ＢＳｆの場合：（Ｃ４ｄ）において挿入された索引語
ＢＳｂの場合：（Ｃ４ｂ）において「※」の印がついた索引語
【０２１９】
（Ｃ９）ＢＡの末尾の文字を、文字１にセットする。
【０２２０】
（Ｃ１０）属性インデックス作成プログラムＳ７０９は、構築されたすべてのビットベクトル（ＢＰｆ、ＢＰｂ、ＢＤ、ＢＡ、ＢＱｆ、ＢＱｂ、ＢＳｆ、及びＢＳｂ）について、高速アクセスのためのディクショナリを構築する。
【０２２１】
以上の処理によって、図１３に示すような、属性インデックスが構築される。ただし、図１３において、理解を容易にするため便宜上、Ｑ'には、索引語識別番号の代わりに、索引語及び属性そのものが示している。
【０２２２】
以下、前述の処理によって構築された属性インデックスを用いて索引語ｗの属性を取得する方法について説明する。なお、以下の説明では、中央演算装置（ＣＰＵ）６０１が文書レベル検索プログラムＳ７０７および位置レベル検索プログラムＳ７０８を実行し、索引語ｗが文書ｄの位置ｐ'に出現することがわかっている場合を想定する。
【０２２３】
（Ｆ１）位置レベル検索プログラムＳ７０８は、全文書中での位置ｐをｐ＝ｐ'＋Ｄ［ｄ］によって算出する。
【０２２４】
（Ｆ２）位置レベル検索プログラムＳ７０８は、索引語ｗと同じ位置で始まる索引語が記録されているＱ'内の領域の先頭ｑを、以下での式を用いて求める。
ｑ＝ｓｅｌｅｃｔ（ＢＱｆ，ｒａｎｋ（ＢＰｆ，ｐ））…（９）
【０２２５】
（Ｆ３）Ｑ'上で、ｑの指す場所に索引語ｗが記録されていない場合、又はＢＳｆのｑ番目の文字が１の場合、位置レベル検索プログラムＳ７０８は、次の索引語のＱ'上の場所ｑ'を、以下の式を用いて求める。
ｑ'＝ｓｅｌｅｃｔ（ＢＡ，ｒａｎｋ（ＢＡ，ｑ）＋１）…（１０）
そして、位置レベル検索プログラムＳ７０８は、ｑをｑ'に置き換えて、（Ｆ３）の処理を再度実行する。
【０２２６】
（Ｆ４）Ｑ'上で、ｑの指す場所に索引語ｗが記録されている場合、位置レベル検索プログラムＳ７０８は、索引語ｗの属性が記録されている範囲の直後の場所ｑ'を、以下の式を用いて求める。
ｑ'＝ｓｅｌｅｃｔ（ＢＡ，ｒａｎｋ（ＢＡ，ｑ）＋１）…（１１）
【０２２７】
（Ｆ５）位置レベル検索プログラムＳ７０８は、ｑの指す場所に記録されている索引語ｗの直後から、ｑ'が指す場所までに記録されている属性を、すべて読み出す。
【０２２８】
以上の処理によって、索引語とその出現位置又は終了位置から、すべての属性を求めることができる。
【０２２９】
これによって、例えば、「属性Ａを持つ索引語ｗ」が出現するすべての文書と位置とを検索する場合、位置レベル検索プログラムＳ７０８は、索引語ｗが存在する各文書ｄ（ｗ，ｉ）に対して、位置リストＰ（ｗ，ｉ）を求め、位置リストＰ（ｗ，ｉ）中のすべての位置ｐ（ｗ，ｉ，１）、…ｐ（ｗ，ｉ，ｆ（ｗ，ｉ））について、前述した処理を実行して属性Ａの有無を確認すればよい。
【０２３０】
一方、近傍検索において、例えば、「ある索引語ｗの前にある任意の索引語で、属性Ａを持つ位置」という検索を行なう場合、位置レベル検索プログラムＳ７０８は、索引語ｗの始まる位置ではなく、終わる位置から属性を求める必要がある。前述の用に索引語ｗが文書ｄの位置ｐ'で終了する場合には、位置レベル検索プログラムＳ７０８は、以下の処理によって索引語ｗの属性を求めることができる。
【０２３１】
（Ｂ１）位置レベル検索プログラムＳ７０８は、全文書中での位置ｐをｐ＝ｐ'＋Ｄ［ｄ］によって算出する。
【０２３２】
（Ｂ２）位置レベル検索プログラムＳ７０８は、索引語ｗと同じ位置で終わる索引語が記録されているＱ'内の領域の先頭ｑを、以下の式を用いて求める。
ｑ＝ｓｅｌｅｃｔ（ＢＱｂ，ｒａｎｋ（ＢＰｂ，ｐ））…（１２）
【０２３３】
（Ｂ３）Ｑ'上で、ｑの指す場所に索引語ｗが記録されていない場合、又はＢＳｂのｑ番目の文字が１の場合、位置レベル検索プログラムＳ７０８は、次の索引語のＱ'上の場所ｑ'を、以下の式を用いて求める。
ｑ'＝ｓｅｌｅｃｔ（ＢＡ，ｒａｎｋ（ＢＡ，ｑ）＋１）…（１３）
そして、位置レベル検索プログラムＳ７０８は、ｑをｑ'に置き換えて、（Ｂ３）の処理を再度実行する。
【０２３４】
（Ｂ４）Ｑ'上で、ｑの指す場所に索引語ｗが記録されている場合、位置レベル検索プログラムＳ７０８は、索引語ｗの属性が記録されている範囲の直後の場所ｑ'を、以下の式を用いて求める。
ｑ'＝ｓｅｌｅｃｔ（ＢＡ，ｒａｎｋ（ＢＡ，ｑ）＋１）…（１４）
【０２３５】
（Ｂ５）位置レベル検索プログラムＳ７０８は、ｑの指す場所に記録されている索引語ｗの直後から、ｑ'が指す場所までに記録されている属性を、すべて読み出す。
【０２３６】
本発明によれば、位置情報を含む転置インデックス１０２を、文書レベル転置インデックス３０１と位置レベル転置インデックス３０２とに分離して格納できる一方、各索引語１０３の各文書１０４における位置リストにアクセスする手段が提供される。
【０２３７】
また、位置レベル転置インデックス３０２内の各文書１０４における出現位置が格納された場所にアクセスするための付加的なデータの量は、従来のポインタを使用する場合と比較してより小さくなると期待され、転置インデックス１０２全体のサイズを抑制できる。
【０２３８】
本発明によれば、位置情報を含む転置インデックス１０２において、文書レベル転置インデックス３０１と位置レベル転置インデックス３０２とを分離して格納できる一方、各索引語ｗの各文書における位置リストＰ（ｗ）にアクセスする手段が提供される。
【０２３９】
ビットベクトルは、ポインタよりも少ない記憶領域に格納できる場合が多く、転置インデックス１０２全体のデータ量を削減できる。
【０２４０】
また、検索時、索引語ｗが現れる文書を検索する、文書レベルの検索では、位置情報の読み飛ばしが不要になるため、位置情報が文書リストＤ（ｗ，ｉ）に混在して格納されている場合に発生する検索速度の低下が起こらない。
【符号の説明】
【０２４１】
１０１  文書集合
１０２  転置インデックス
１０３  索引語
１０４  文書
１０４  検索対象文書
１０５  文書識別番号
１０６  出現回数
３０１  文書レベル転置インデックス
３０２  位置レベル転置インデックス
４０１  ポインタ
６０１  中央演算装置（ＣＰＵ）
６０２  主記憶装置
６０３  補助記憶装置
６０４  ネットワーク
６０５  ユーザ端末
Ｓ７０１  索引語切り出しプログラム
Ｓ７０２  索引語位置抽出プログラム
Ｓ７０３  文書識別番号割当プログラム
Ｓ７０４  文書レベル転置インデックス作成プログラム
Ｓ７０５  位置レベル転置インデックス作成プログラム
Ｓ７０６  ビットベクトル作成プログラム
Ｓ７０７  文書レベル検索プログラム
Ｓ７０８  位置レベル検索プログラム
Ｓ７０９  属性インデックス作成プログラム
【図１】
2010198425.tif 000003
【図２】
2010198425.tif 000004
【図３】
2010198425.tif 000005
【図４】
2010198425.tif 000006
【図５】
2010198425.tif 000007
【図６】
2010198425.tif 000008
【図７】
2010198425.tif 000009
【図８】
2010198425.tif 000010
【図９】
2010198425.tif 000011
【図１０】
2010198425.tif 000012
【図１１】
2010198425.tif 000013
【図１２】
2010198425.tif 000014
【図１３】
2010198425.tif 000015
【図１４】
2010198425.tif 000016
【図１５】
2010198425.tif 000017
【図１６】
2010198425.tif 000018
【図１７】
2010198425.tif 000019
【図１８】
2010198425.tif 000020
【図１９】
2010198425.tif 000021
【図２０】
2010198425.tif 000022
【図２１】
2010198425.tif 000023
【図２２】
2010198425.tif 000024
【図２３】
2010198425.tif 000025