文書検索装置および文書検索方法
【課題】Ngram解析を用いた文書検索は検索処理に時間がかかる場合がある。
【解決手段】新たな文書ファイルをインデックスに登録する際、登録済みのデータを含め、ポスティングデータを１つ有する登録キーからの、登録キーの個数の累積割合を算出する（Ｓ３０）。しきい値Ｎ以下の数のポスティングデータを有する登録キーのポスティングデータは、登録キーで構成されるＢ＋ツリーのリーフページに格納し（Ｓ４６）、しきい値Ｎより大きい数のポスティングデータを有する登録キーのポスティングデータは、ポスティング格納部のページへ格納する（Ｓ４０、Ｓ４８）。累積登録文書数ｉが所定の文書数目であった場合は（Ｓ３２のＹ）、ポスティングデータ数のしきい値Ｎを、累積割合が６０％を超えない登録キーが有する最大のポスティングデータ数に変更する（Ｓ３４）。
【解決手段】新たな文書ファイルをインデックスに登録する際、登録済みのデータを含め、ポスティングデータを１つ有する登録キーからの、登録キーの個数の累積割合を算出する（Ｓ３０）。しきい値Ｎ以下の数のポスティングデータを有する登録キーのポスティングデータは、登録キーで構成されるＢ＋ツリーのリーフページに格納し（Ｓ４６）、しきい値Ｎより大きい数のポスティングデータを有する登録キーのポスティングデータは、ポスティング格納部のページへ格納する（Ｓ４０、Ｓ４８）。累積登録文書数ｉが所定の文書数目であった場合は（Ｓ３２のＹ）、ポスティングデータ数のしきい値Ｎを、累積割合が６０％を超えない登録キーが有する最大のポスティングデータ数に変更する（Ｓ３４）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は文書処理技術に関し、特に入力されたテキストを含む文書ファイルを検索するための文書検索装置およびそれに適用される文書検索方法に関する。
【背景技術】
【０００２】
情報処理技術やネットワークの充実に伴い、ＰＣ(Personal Computer)や携帯電話などの情報端末からウェブサイトやデータベースへアクセスして必要な情報を取得することが日常的に行われるようになった。一方でデータベース化される情報は膨大化の一途をたどり、それらの情報の中から必要な情報を取得する際の効率性が求められるようになってきた。ウェブサイトやネットワーク上に開示された情報を検索する検索エンジンから、各種のデータベースを検索する検索システムまで、文書検索の機能は適切かつ最新の情報取得には欠かせないものとなっている。
【０００３】
自然言語に基づく文書検索技術のひとつにNgram解析がある。Ngram解析ではまず、検索対象の文書から所定数の文字列、すなわち「キー」を切り出し、文書における出現場所の情報をキーごとに記憶させておく。このようなデータを「インデックス」と呼ぶ。そして検索時は、検索クエリに含まれるキーに基づきインデックスを検索し、検索クエリ内のキーの順序などに基づき、検索クエリを含む文書を特定する（例えば特許文献１参照）。
【特許文献１】特開平５−２７４３５５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
Ngram解析は、意味をなす、なさないに関わらず、文書に含まれるキーを全て切り出してインデックスを生成し、検索クエリに含まれるキーと照合する。そのため意味をなす語句を抽出する形態素解析と比較し検索結果に漏れが生じにくい、という特徴を有するが、一方で検索対象の文書数が増加するのに従い、インデックスのデータ量が急増する。そのため検索クエリを含む所望の文書情報を特定するまでには、膨大なデータ量のインデックスにアクセスする必要があり、処理に時間がかかる場合が多い。
【０００５】
本発明はこうした状況に鑑みてなされたものであり、その目的は、Ngram解析を用いた検索を効率的に行う技術を提供することにある。
【課題を解決するための手段】
【０００６】
本発明のある態様は、文書検索装置に関する。この文書検索装置は、文書から所定数の文字列を登録キーとして抽出するキー抽出部と、登録キーが抽出された文書の識別情報と当該文書における抽出箇所とを含むデータセットを１単位とするポスティングデータを登録キーごとに記憶したポスティング格納部と、ポスティング格納部におけるポスティングデータの格納領域と、対応する登録キーとを関連付けたツリー構造を構成する記憶領域を有するキー格納部と、を含むインデックス保持部と、検索クエリから所定数の文字列を検索キーとして抽出し、インデックス保持部を参照して検索キーに対するポスティングデータを取得することにより検索クエリを含む文書の検索を行う検索部と、を備え、キー格納部におけるツリー構造の最下層のノードを構成する記憶領域の少なくとも一部に、ポスティングデータの少なくとも一部が記憶され、検索部は少なくとも一部の検索キーについて、キー格納部のみを参照してポスティングデータを取得することを特徴とする。
【０００７】
ここで「抽出箇所」は登録キーの開始位置、終了位置などであるが、文書検索装置において共有される所定の規則に従えばその形式は問わない。またポスティングデータは文書の識別情報と抽出箇所以外のパラメータを含んでいてよい。さらに「ツリー構造を構成する記憶領域」とはアルゴリズム上でツリー構造を構成する各ノードに対応した記憶領域のことであり、実際の記憶領域は連続していても分散していてもよい。「検索クエリ」は文書検索を行うためにユーザが入力した文字列であり、語句あるいは文章のいずれでもよく、１つでも複数でもよい。
【０００８】
本発明の別の態様は、文書検索方法に関する。この文書検索方法は、文書から所定数の文字列を登録キーとして抽出するステップと、登録キーが抽出された文書の識別情報と当該文書における抽出箇所とを含むデータセットを１単位とするポスティングデータを登録キーごとに生成するステップと、ポスティングデータを登録キーごとに記憶装置に記憶させるステップと、検索クエリから所定数の文字列を検索キーとして抽出するステップと、記憶装置を参照して検索キーに対する前記ポスティングデータを取得することにより検索クエリを含む文書の検索を行うステップと、を含み、記憶装置におけるポスティングデータの記憶領域を、登録キーごとのポスティングデータ数に応じて異ならせることを特徴とする。
【０００９】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１０】
本発明によれば、ユーザは漏れのない検索を効率的に行うことができる。
【発明を実施するための最良の形態】
【００１１】
図１は、文書検索装置１００による処理の概要を説明するための模式図である。ユーザが文書検索装置１００に対して検索クエリを入力すると、文書検索装置１００はその検索クエリを含む文書ファイルを文書データベース２００から検索する。検索クエリは一定の意味をなす文字列であり、自然文であってもよいしキーワードであってもよい。文書データベース２００の文書ファイルは、ＸＭＬ（eXtensible Markup Language）文書やＸＨＴＭＬ（eXtensible HyperText Markup Language）文書のようにタグによって構造化されたファイルであってもよいし、単なるテキストファイルであってもよい。また文書データベース２００は図示しないネットワークを介して文書検索装置１００と接続されていてもよい。
【００１２】
検索に先立ち、文書検索装置１００は文書データベース２００内の文書についてNgram解析を行いインデックスを作成してインデックス保持部１３０に格納する。インデックス保持部１３０はハードディスクなど大容量の記憶装置、またはその一部で実現できる。インデックスの構造については後に詳述する。文書検索装置１００は検索クエリに基づきインデックスを参照して、文書データベース２００内の適合する文書ファイルを特定し、検索結果として画面表示する。その際、一般的に用いられるスコアリングの手法によって得られたスコアに基づき結果の表示順を決定してもよい。こうして、文書検索装置１００のユーザは、任意の検索クエリを含む文書ファイルを探し出すことができる。
【００１３】
図２は文書検索装置１００の詳細な構成を示している。ここに示す各ブロックは、ハードウェア的には、コンピュータのＣＰＵをはじめとする素子や機械装置で実現でき、ソフトウェア的にはコンピュータプログラム等によって実現されるが、ここでは、それらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックはハードウェア、ソフトウェアの組合せによっていろいろなかたちで実現できることは、当業者には理解されるところである。
【００１４】
文書検索装置１００はユーザによる入力の受け付けや結果の出力を担うユーザインタフェース処理部１１０、検索対象の文書についてのデータをインデックスに登録する登録部１２０、入力された検索クエリに基づき検索を行う検索部１６０、およびインデックス保持部１３０を含む。文書検索装置１００はさらに、各機能ブロックが処理を行うために必要なデータやプログラムを一時的に格納するメモリ１７０を含む。
【００１５】
ユーザインタフェース処理部１１０は、ユーザからの入力処理やユーザに対する情報表示のようなユーザインタフェース全般に関する処理を担当する。本実施の形態においては、ユーザインタフェース処理部１１０により文書検索装置１００のユーザインタフェースサービスが提供されるものとして説明する。別例として、ユーザはインターネットを介して文書検索装置１００を操作してもよい。この場合、図示しない通信部が、ユーザ端末からの操作指示情報を受信し、またその操作指示に基づいて実行された処理結果情報をユーザ端末に送信することになる。
【００１６】
ユーザインタフェース処理部１１０は文書取得部１１２、表示部１１４、および検索クエリ取得部１１６を含む。新規の文書データベース２００を構築した場合や、元からある文書データベース２００に新規の文書ファイルを登録して検索対象とする場合に、文書取得部１１２は当該文書ファイル（以後、登録文書ファイルと呼ぶ）の情報をユーザからの入力によって取得し、登録部１２０へ供給する。この文書ファイルの情報は、文書データベース２００に保存されている文書ファイルを指定する情報でもよいし、別の場所に保存されている文書ファイルを指定する情報でもよい。後者の場合、文書検索装置１００は読み出した文書ファイルを文書データベース２００へ保存するようにしてもよい。検索クエリ取得部１１６は、検索を行いたいユーザによって入力された検索クエリを受け付け、検索部１６０に供給する。
【００１７】
登録部１２０はキー抽出部１２２、ポスティング生成部１２４、ポスティング記憶領域決定部１２６、およびデータ書込み部１２８を含む。キー抽出部１２２は、文書取得部１１２から供給された文書ファイルの情報に従い登録文書ファイルを読み出し、走査することにより、あらかじめ定められた文字数、すなわち所定のグラム数を有するキーを抽出する。例えば「アメリカ合衆国の大統領」というテキストであれば、「アメ：メリ：リカ：・・・：統領」のようにキーを抽出する。この例におけるキーは２グラムである。グラム数は最適な値をあらかじめ設定しておく。以後の説明では登録文書ファイルから抽出されたキーを「登録キー」と呼ぶ。
【００１８】
ポスティング生成部１２４は、登録文書ファイルに対し一意に定めた識別情情報である文書ＩＤを付与するとともに、各登録キーに対するポスティングデータを生成する。ポスティングデータは、各登録キーがどの文書のどの位置に出現したかを表す情報であり、例えば［文書ＩＤ，キー開始位置，キー終了位置］という構造を有するデータセットである。抽出した登録キーの中に同一のものがあれば、対応するポスティングデータをまとめる。例えば「アメ」なるキーが４つ抽出されていれば、キー「アメ」に対し４つのポスティングデータが生成される。
【００１９】
ポスティング記憶領域決定部１２６は、生成されたポスティングデータをインデックス保持部１３０のどの領域に記憶させるかを決定し、データ書込み部１２８は当該決定に従いポスティングデータおよびそれに係る情報をインデックス保持部１３０に追加して書き込む。ポスティング記憶領域決定部１２６は、ポスティングデータを記憶させる記憶領域の決定以外に、記憶領域決定のための各種処理も行う。ポスティングデータの記憶領域については後に詳述する。
【００２０】
検索部１６０はポスティング取得部１６２および文書データ取得部１６４を含む。ポスティング取得部１６２は検索クエリからキーを抽出し、インデックス保持部１３０を参照して当該キーに対応するポスティングデータを取得する。以後、検索クエリから抽出したキーを「検索キー」と呼ぶ。ポスティング取得部１６２は、検索キーが全て含まれる文書を各キーのポスティングデータに含まれる文書ＩＤから特定し、さらにそれらの検索キーが検索クエリにおける順序で連続して出現する文書を、ポスティングデータに含まれるキー開始位置、キー終了位置に基づき絞り込む。これにより検索クエリを含む文書を特定できる。なおここでは基本的な処理内容のみを説明するが、検索処理に一般的に用いられるあらゆる技術を組み合わせてもよい。
【００２１】
文書データ取得部１６４は、特定された文書の文書ＩＤに基づき文書データベース２００から該当文書の少なくとも一部や記憶先のアドレスなどを取得し、ユーザインタフェース処理部１１０の表示部１１４が検索結果として表示できるように表示データを整えメモリ１７０に保存する。
【００２２】
ここでインデックス保持部１３０に保持されたインデックスの構造および記憶領域について説明する。インデックスは、登録文書ファイルから抽出された登録キーとポスティングデータとを関連付けたデータである。登録キーはグラム数に応じて機械的に切り出されるため、同一の登録キーをまとめてもその種類は膨大である。一方、検索時には検索キーに合致した、インデックス内の登録キーを探し出し、それと関連付けられたポスティングデータを特定する処理がなされる。膨大な種類の登録キーの中から検索キーを効率よく検出するために、一般に利用されるのがＢ＋ツリー（Balanced plus tree）のアルゴリズムである。
【００２３】
このとき用いられるＢ＋ツリーは、所定の規則でソートされた登録キーの列の範囲によって下層のノードへの分岐を決定するルートノードおよびブランチノードと、末端のノードであり、ツリーによって最終的に絞り込まれた登録キーの候補と、各登録キーのポスティングデータの記憶領域を示すポインタとが記述されたリーフノードからなるツリー構造を有する。検索処理時には、検索キーに従いルートノードから下層へノードを辿っていけば、行き着いたリーフノードに記述された登録キーの候補の中に検索キーと同一のものが含まれており、最終的に所望のポスティングデータへのポインタが得られることになる。
【００２４】
このような検索処理においてはまず、（１）Ｂ＋ツリー構造が格納された記憶領域にアクセスしてポスティングデータへのポインタを取得し、（２）ポスティングデータが格納された記憶領域にアクセスしてポスティングデータを取得する、という最低２回のアクセスを必要とする。１つの検索クエリからは通常、複数の検索キーが抽出されるため、それらの検索キーに対し同様の処理を繰り返すと、記憶領域へのアクセス回数が増大する。キャッシュメモリなどを用いても、検索条件によっては看過できない程の時間を要する場合がある。
【００２５】
本発明者は検索に要する時間を短縮するため鋭意研究を重ねた結果、インデックスに係る以下の知見を得るに至った。表１は、一般的な文書データベースのインデックスにおける、キーごとのポスティングデータ数の分布を表している。このデータは８７万７７１３の文書ファイルから２グラムの登録キーを抽出した場合であり、このとき抽出された登録キーは１３３９１０３個であった。
【００２６】
【表１】
【００２７】
例えば「ポスティング数」が「３」の行を見ると、３個のポスティングデータを有する登録キーは、「合計」欄のとおり「９４０３８」個あり、ポスティングデータ数が３個までの累積値、すなわち１〜３個のポスティングデータを有する登録キーの個数は「累積」欄のとおり「６１３３６９」個である。そして全登録キーのうち１〜３個のポスティングデータを有する登録キーの割合は、「累積割合」欄のとおり「４５．８％」である。同表によれば、全登録キーのうち５５％程度はポスティングデータ数が５個以下の登録キーであることがわかる。それに対し、１００１個以上のポスティングデータを有する登録キーは全体のわずか０．６％である。
【００２８】
したがって上述のようにＢ＋ツリーからポインタを取得し、ポインタからポスティングデータを取得する構成においては、わずか数個のポスティングデータを取得するために別の記憶領域へアクセスし直している可能性が少なからずあるといえる。本発明者はこの点に改良の余地を見出し、ポスティングデータの取得を効率的に行うために次のような実施の形態に想到した。
【００２９】
本実施の形態でも基本的には上述のアルゴリズムを採用する。そのため、インデックス保持部１３０には、Ｂ＋ツリーを格納するキー格納部１３２および各ポスティングデータを格納するポスティング格納部１３４が含まれる。したがって一般的なＢ＋ツリーのリーフノードにおいて記述されるポスティングデータへのポインタは、ポスティング格納部１３４内の記憶領域を示す。以後、リーフノードやポスティングデータの記憶領域はページを単位として説明し、ポインタはページ番号とする。またこれ以後、登録キーとポスティングデータとの関連付けはＢ＋ツリーを用いて行うものとするが、本実施の形態はこれに限らず、例えばＢツリーなどでもよい。
【００３０】
一方、本実施の形態では、登録キーの絞込みを行うためのＢ＋ツリー構造の中に、ポスティングデータの一部を組み入れる。すなわち、本実施の形態のリーフページ１３６には、登録キーとポスティングデータのページ番号との組み合わせのみならず、登録キーとポスティングデータそのものの組み合わせも記述される。したがってポスティング記憶領域決定部１２６は、ポスティングデータをキー格納部１３２、すなわちＢ＋ツリーのリーフページ１３６に記憶させるか、ポスティング格納部１３４へ記憶させるか、を決定する。
【００３１】
ポスティング記憶領域決定部１２６は、登録キーごとのポスティングデータの数、すなわち、登録文書ファイルから新たに生成された登録キーのポスティングデータと、同一の登録キーに対しインデックスに登録済みのポスティングデータとの合計によって、当該登録キーのポスティングデータの記憶領域を決定する。具体的にはポスティングデータの数にしきい値を設け、しきい値以下の数のポスティングデータしか持たない登録キーであればＢ＋ツリーのリーフページ１３６に記述し、しきい値より大きい数のポスティングデータを有する登録キーについてはポスティング格納部１３４内の領域に記述する。
【００３２】
例えばしきい値を「５」とした場合、表１に示したような文書データベースでは、約５５％の登録キーのポスティングデータは、キー格納部１３２のみにアクセスすることによって取得することができる。また５個程度のポスティングのデータサイズであればリーフページ１３６の記憶容量を圧迫することがなく、Ｂ＋ツリー構造はそのバランスを損なうことなくそのまま用いることができる。結果としてインデックス保持部１３０へのアクセス回数のみが削減され、短期間で効率のよい検索処理が可能となる。
【００３３】
さらにポスティング記憶領域決定部１２６は、所定の文書数が登録されるごとに、全体に対する登録キーの割合に基づき上述のしきい値を変化させる。例えば文書が１０万文書登録されるごとに、１個のポスティングデータを有する登録キーからの累積割合が６０％を超えない登録キーが有する最大のポスティングデータ数へしきい値を変更する。これは、登録される文書数が増加するほど、当然登録キーごとのポスティング数が増加する傾向となるための措置である。そのような状況でしきい値をあるポスティングデータ数で固定してしまうと、登録文書の増加とともに、しきい値より多くのポスティングデータ数を有する登録キーの割合が増加していき、結局アクセス回数の削減効果が薄れてしまう。
【００３４】
そこで累積割合に基づきしきい値を調整し、常にある割合の登録キーについてはリーフページ１３６からポスティングデータが得られるようにする。表１によれば、キーごとのポスティングデータ数が増加するほど累積割合の増加量は小さくなる。すなわち登録文書数が増加しても、累積割合が６０％などとなる登録キーのポスティングデータ数が急激に増加する可能性は低いと考えられる。したがって、上述のようにしきい値を変化させても、リーフページ１３６の容量を圧迫したりＢ＋ツリーのバランスを損なったりする程のポスティングデータが記述される可能性は低く、結果として上述したような効果を登録文書数の多少に関わらず定常的に得ることができる。
【００３５】
ポスティングデータをリーフページ１３６に記述する場合、データ書込み部１２８は、対応する登録キーが記述されているリーフページ１３６にポスティングデータを追加して書き込む。ポスティングデータをポスティング格納部１３４に格納する場合、データ書込み部１２８は、対応する登録キーが記述されているリーフページ１３６を参照し、当該登録キーに対応づけて記述された、ポスティングデータのページ番号を取得して、ポスティング格納部１３４内の該当ページにポスティングデータを追加して書き込む。
【００３６】
図２のキー格納部１３２やポスティング格納部１３４に示した最も小さい単位の矩形はページを表している。上述したとおり、キー格納部１３２およびポスティング格納部１３４はそれぞれＢ＋ツリーおよびポスティングデータを格納するが、Ｂ＋ツリーのリーフページ１３６に記述されたデータにはポスティングデータも含まれる。同図ではそのようなページを網掛けで表している。リーフページ１３６以外のリーフページにもポスティングデータを記述してよいが、ここではリーフページ１３６に代表させている。
【００３７】
ポスティング格納部１３４には当然、ポスティングデータが格納されるため、それを記述したページとして網掛けされた矩形がいくつか示されているが、本実施の形態では登録キーごとのポスティングデータの数により、そのページ構成を異ならせる。具体的には、１ページに複数の登録キーのポスティングデータを記述する共有ページ１３７、１ページ以上に一の登録キーのポスティングデータを記述する専有ページ１３８、文書ＩＤをキーとした２層のＢ＋ツリー構造のリーフページに一の登録キーのポスティングデータを記述した２層ツリーページ１４０、同じく３層のＢ＋ツリー構造により一の登録キーのポスティングデータを記述した３層ツリーページ１４２である。なお各ページの総数はポスティングデータの数によって増減する。それぞれのページ構成の詳細は後に述べる。
【００３８】
図３は、キー格納部１３２に格納されるＢ＋ツリーの構造を模式的に示している。Ｂ＋ツリー２０は、ルートページ２２、ブランチページ２４および２６、リーフページ２８、３０、および１３６を含む。ただしページ数や層の深さはこれに限らない。各ページの左上に示した「＃番号」はそれぞれのページに一意に設定されたページ番号である。
【００３９】
まずページ番号＃１のルートページ２２を見ると、「５」、「キーＣ」、「８」、「キーＦ」といったデータ列が記述されている。ここで「キーＣ」、「キーＦ」は「アメ」、「メリ」など具体的な登録キーの文字列である。同図の場合、ソートされた登録キーの列の先頭から「キーＣ」の前までの登録キーについては下層のページ番号＃５のページに記述されており、「キーＣ」から「キーＦ」の前までの登録キーについては下層のページ番号＃８のページに記述されていることを示している。
【００４０】
ページ番号＃５のブランチページ２４も同様に、先頭から「キーＡ」の前までの登録キーについてはページ番号＃３６のページに、「キーＡ」から「キーＢ」の前までの登録キーについてはページ番号＃４６のページに記述されていることを示している。ページ番号＃８のブランチページ２６も同様である。これに従い、ページ番号＃３６のリーフページ２８には先頭から「キーＡ」の前までの登録キーのポスティングデータについての情報が、ページ番号＃４６のリーフページ３０には「キーＡ」から「キーＢ」の前までの登録キーのポスティングデータについての情報が記述される。
【００４１】
同図では、リーフページ２８、３０などに記述されるデータを、リーフページ１３６を代表させて図示している。上述したとおりリーフページ１３６には、複数の登録キーのそれぞれに対し、ポスティングデータそのもの、またはポスティング格納部１３４におけるポスティングデータを記述したページ番号のいずれかが記述される。同図は、「キーＧ」、「キーＨ」、「キーＪ」、「キーＬ」に対しポスティングデータそのものが記述され、「キーＩ」に対しては図２の共有ページ１３７のページ番号、「キーＫ」に対しては専有ページ１３８の先頭のページ番号、「キーＭ」に対しては２層ツリーページ１４０のルートページのページ番号が記述されていることを示している。
【００４２】
次に、これまで述べた構成を有する文書検索装置１００の動作について説明する。なお検索部１６０が行う検索クエリに基づく検索処理の手順は、上述したとおり一般的な手法を用いることができるため、ここではインデックスへの登録手法に主眼を置き説明する。図４は文書検索装置１００によって登録文書ファイルを解析し、インデックスへ登録する処理手順を示すフローチャートである。ここではインデックス保持部１３０に、それまでに解析を済ませた文書ファイルのインデックスが既に格納されており、新たな登録文書の情報を登録する場合について述べるが、新規にインデックスを生成する場合でも、本実施の形態の特徴的な手順は同様であり、Ｂ＋ツリーの構築などは一般的な手法を適用することができる。
【００４３】
まずユーザが、ユーザインタフェース処理部１１０の文書取得部１１２に対し登録文書ファイルの情報を入力すると、登録部１２０のキー抽出部１２２は当該登録文書ファイルを読み出し、メモリ１７０に保存する（Ｓ１０）。キー抽出部１２２は、登録文書ファイルからテキストデータを抽出し（Ｓ１２）、それを走査することにより所定のグラム数の登録キーを抽出していく（Ｓ１４）。次にポスティング生成部１２４は、登録文書ファイルに文書ＩＤを付与するとともに、キー抽出部１２２が抽出した登録キーごとに、当該文書ＩＤと、テキストデータにおける当該登録キーの開始位置および終了位置とからなるポスティングデータを生成する（Ｓ１６）。
【００４４】
次にポスティング記憶領域決定部１２６が、生成したポスティングデータの格納領域を決定し、データ書込み部１２８がそれに従い書き込みを行う（Ｓ１８）。この際、前述したとおり、インデックスに登録済みのポスティングデータを含めた登録キーごとのポスティングデータ数としきい値との大小関係によって格納場所を決定する。また今回抽出した登録キーのポスティングデータをリーフページ１３６に書き込むことによりその登録キーのポスティングデータ数がしきい値を超えてしまう場合は、リーフページ１３６に記述済みのポスティングデータごとポスティング格納部１３４へ移動させる。具体的な処理手順は図５を参照して説明する。
【００４５】
図５は、Ｓ１８においてポスティング記憶領域決定部１２６がポスティングデータの記憶領域を決定し、データ書込み部１２８が書き込みを行う手順を示すフローチャートである。前提として、文書ファイルの累積数を示す変数ｉは“０”に初期化され、リーフページ１３６に記述できるポスティングデータ数のしきい値Ｎには初期値、たとえば“５”が代入されているとする。まず変数ｉをインクリメントした後（Ｓ２８）、登録文書ファイルの情報を新たに登録した場合のインデックスについて表１に示した各数値を計算し、登録キーごとのポスティング数に対する登録キーの個数の累積割合を算出する（Ｓ３０）。累積割合を含む表１のデータは、メモリ１７０などに一時保存し、文書検索装置１００の処理を終了させる際にインデックス保持部１３０を構成するハードディスクなどに保存しておく。新たな文書登録を行う際は、そのように保存された以前のデータを参照して計算を行い、各値を更新してけばよい。
【００４６】
次に変数ｉに対し所定の文書数Ｍ、例えば１０万で剰余算を行い、解が０でなければ、すなわち今回の登録文書ファイルが１０万の倍数文書目でなければ（Ｓ３２のＮ）、抽出した各登録キーについてＢ＋ツリーを辿り、まずリーフページ１３６に当該登録キーが記述されているかどうかを確認する（Ｓ３７）。登録キーが以前に登録されていなければ、リーフページ１３６には当該登録キーが記述されていないため（Ｓ３７のＮ）、リーフページ１３６に登録キーとそのポスティングデータを書き込む（Ｓ４６）。
【００４７】
登録キーが記述されていた場合は（Ｓ３７のＹ）、さらにリーフページ１３６に当該登録キーのポスティングデータが記述されているかどうかを確認する（Ｓ３８）。ポスティングデータが記述されておらず、ページ番号が記述されている場合は（Ｓ３８のＮ）、ポスティング格納部１３４における当該ページ番号のページにポスティングデータを追加して書き込む（Ｓ４０）。
【００４８】
リーフページ１３６にポスティングデータが記述されている場合は（Ｓ３８のＹ）、新たなポスティングデータの追加によりポスティングデータ数がしきい値Ｎを超えるかどうかを確認する（Ｓ４２）。しきい値Ｎを超えない場合は（Ｓ４２のＹ）、そのリーフページ１３６にポスティングデータを追加して書き込む（Ｓ４６）。ポスティングデータ数がしきい値Ｎを超える場合は（Ｓ４２のＮ）、それまで記述されていた当該登録キーのポスティングデータをポスティング格納部１３４に用意されている共有ページ１３７などに移動させたうえで、新たなポスティングデータを同ページに追加して書き込む（Ｓ４８）。この際、移動元のリーフページ１３６には、当該キーに対応させて移動先のページのページ番号を書き込んでおく。
【００４９】
Ｓ３２において当該登録文書ファイルが所定の文書数Ｍの倍数であった場合は（Ｓ３２のＹ）、Ｓ３０において算出した累積割合に基づきしきい値Ｎを変更する（Ｓ３４）。ここでＮ（６０％）は累積割合が６０％を超えない登録キーの最大のポスティングデータ数を表す。なお６０％は例示であり、データベースの種類や文書検索装置１００の処理性能などに鑑み実験などにより最適値を決定してよい。そしてしきい値Ｎの変更によってリーフページ１３６に記述されるべきとなったポスティングデータがあれば、ポスティング格納部１３４のページからリーフページ１３６に移動する（Ｓ３６）。その後の処理は上述したのと同様である。
【００５０】
以上の手順により、登録されている文書数の増加に伴いポスティングデータ数のしきい値を変化させながら、ポスティングデータをリーフページ１３６およびポスティング格納部１３４へ振り分ける態様を実現することができる。
【００５１】
次にポスティング格納部１３４に格納された、ポスティングデータを記述するページの構成について説明する。上述したように本実施の形態では登録キーごとのポスティングデータ数により、共有ページ１３７、専有ページ１３８、２層ツリーページ１４０、３層ツリーページ１４２のいずれかにポスティングデータを記述し、記憶領域を効率的に使用するとともに検索の処理効率を向上させる。なおツリーページは必要に応じて４層以上でもよい。
【００５２】
図６は共有ページ１３７の構成を模式的に示している。共有ページ１３７には複数のキーのポスティングデータを可能な限り詰めた状態で記述する。リーフページ１３６においてポスティングデータ数がしきい値を超えた登録キーのポスティングデータは、この共有ページ１３７に移動する。１ページのデータ容量、８ＫＢを考慮すると、登録キーごとのポスティングデータ数が最大５００個程度であれば、共有ページ１３７内に記述できる。
【００５３】
共有ページ１３７は、ポスティングデータ領域８２ａ〜８２ｆ、ポインタ領域８４ａ〜８４ｆ、および空き領域８６を含む。同図は、６つの登録キーのポスティングデータが、６つの連続したポスティングデータ領域８２ａ〜８２ｆのぞれぞれに記述されている状態を示している。登録キーごとのポスティングデータ数は一定でないため、ポスティングデータ長も変動する。そこで各ポスティングデータ領域８２ａ〜８２ｆの、ページ先頭からのオフセット値をポインタ領域８４ａ〜８４ｆにそれぞれ記述する。新たなポスティングデータをポスティングデータ領域８２ａ〜８２ｆのいずれかに追加した場合は、以後のポスティングデータ領域のオフセット値を更新する。
【００５４】
リーフページ１３６からポスティングデータを移動する際は、充填率が高くなるような共有ページ１３７を探して格納する。そのために空き領域８６の容量を管理する。例えば２ビットのレジスタ（図示せず）を用意し、空き領域８６の容量について、２５％未満、２５％以上５０％未満、５０％以上７５％未満、７５％以上１００％以下、の４段階を表すデータを保持する。レジスタの値は文書検索装置１００の処理終了時にはハードディスクなどに保存し、次回の登録処理において参照する。
【００５５】
表１によれば、５００個以下のポスティングデータを有する登録キーは全体の９０％程度にも上るため、ポスティングデータをリーフページ１３６に格納するほか、共有ページ１３７に詰めて格納することにより、キーごとに１ページを用意するといった従来の手法に比べて格段に所要容量を削減することができる。また、新たな空きページを確保するなどの領域管理の処理を省略でき、登録処理時の効率が向上する。
【００５６】
共有ページ１３７に記述したある登録キーのポスティングデータが増加し、１ページ以内で収まらなくなった場合は、当該ポスティングデータを専有ページ１３８へ移動させる。専有ページは一の登録キーが専有して使う１以上のページで構成され、ポスティングデータ数によってページを単純連結していく。例えば最大８ページまで連結可能とする。これにより一の登録キーにつき５００〜４０００個程度のポスティングデータが格納できる。
【００５７】
最大に連結した専有ページ１３８の容量をポスティングデータが超えた場合は、当該ポスティングデータをリーフページに格納した２層ツリーページ１４０を構築する。図７は２層ツリーページ１４０の構成を模式的に示している。２層ツリーページ１４０は基本的には図３で示したのと同様のＢ＋ツリー構造を有する。ただしページの分岐は登録キーに代わり文書ＩＤによって行う。
【００５８】
前述したように、検索部１６０が検索処理を行う場合、入力された検索クエリから検索キーを抽出し、検索キーの全てを含み、かつ検索クエリにおける順番で連続して出現する文書を検出する。検索クエリから検索キーとして「キーａ」、「キーｂ」が抽出されたとすると、まず「キーａ」のポスティングデータを取得し、その文書ＩＤをメモリ１７０に保存する。そして「キーｂ」のポスティングデータのうち、メモリ１７０に保存しておいた文書ＩＤを有するポスティングデータを取得すれば、それはすなわち「キーａ」および「キーｂ」を含む文書のポスティングデータである。
【００５９】
ここで「キーｂ」が４０００個を超える膨大なポスティングデータを有するとすると、それらのポスティングデータを単に羅列したデータ構造においては、先頭から全てのポスティングデータを確認し、「キーａ」を含む文書の文書ＩＤと照合していかなければならない。検索キーが多いほど、この処理を繰り返す必要が生じ、結果としてポスティング格納部１３４へのアクセス回数が増大する。
【００６０】
そこで本実施の形態では、４０００個を超えるようなポスティングデータを有する「キーｂ」のポスティングデータを取得する際、「キーａ」を含む文書の文書ＩＤを元に図７に示すようなＢ＋ツリー構造を辿ることにより、「キーａ」を含む文書のポスティングデータのみを確認する。図７において２層ツリーページ１４０は、ルートページ４２、ブランチページ４４および４６、リーフページ４８、５０、５２、５４を含む。図３と同様、ルートページ４２には、ある登録キーに対する全ポスティングデータに記載された文書ＩＤをソートした文書ＩＤ列のうち、先頭から「ＩＤ＿ｃ」の前までの文書ＩＤを有するポスティングデータの情報がページ番号＃１のページに、「ＩＤ＿ｃ」から「ＩＤ＿ｆ」の前までの文書ＩＤを有するポスティングデータの情報がページ番号＃５２のページに記述されていることが示されている。
【００６１】
同様に、ページ番号＃１のブランチページ４４には、先頭から「ＩＤ＿ａ」の前までの文書ＩＤを有するポスティングデータがページ番号＃２のページに、「ＩＤ＿ａ」から「ＩＤ＿ｂ」の前までの文書ＩＤを有するポスティングデータがページ番号＃３のページに記述されていることが示されている。ページ番号＃５２のブランチページ４６も同様である。ページ番号＃２のリーフページ４８、ページ番号＃３のリーフページ５０、ページ番号＃１７のリーフページ５２、ページ番号＃１８のリーフページ５４にはそれぞれ、該当する文書ＩＤを有するポスティングデータが記述されている。
【００６２】
このような構成とすることにより、上述の例では、「キーａ」を含まない文書に対するポスティングデータを読み飛ばすことができ、ポスティング格納部１３４へのアクセス回数を削減することができる。ポスティングの確認に係る処理も省略できるため、結果として検索処理にかかる時間を顕著に削減することができる。
【００６３】
２層ツリーページ１４０には、最大約８ＭＢ、すなわち５０万個程度のポスティングデータを格納することができる。ある登録キーのポスティングデータが２層ツリーページ１４０に格納できる数を超えた場合は、当該ポスティングデータをリーフページに格納した３層ツリーページ１４２を構築する。３層ツリーページ１４２はブランチページが２層になっているほかは２層ツリーページ１４０と同様である。３層ツリーページ１４２には、最大８ＧＢ、すなわち５億個程度のポスティングデータを格納することができる。
【００６４】
以上述べた本実施の形態によれば、登録キーごとのポスティングデータ数に応じて、ポスティングデータの格納領域を、キー格納部１３２におけるＢ＋ツリー構造のリーフページ１３６、ポスティング格納部１３４における共有ページ１３７、専有ページ１３８、２層ツリーページ１４０、３層ツリーページ１４２と変化させる。また、文書の登録数によってポスティングデータ数が増加した場合は、上述の順番でデータを移動させていく。これにより、常にポスティングデータのデータサイズに適合し、かつ無駄のない記憶領域管理を行うことができる。
【００６５】
さらにＢ＋ツリー構造のバランスを損なわない程度のサイズのポスティングデータをキー格納部１３２のＢ＋ツリーのリーフページ１３６に格納することにより、検索処理時にポスティング格納部１３４へアクセスし直す必要がなくなり、全体としてアクセス回数が減るため、検索処理を高速化できる。一般的な文書データベースでは、多くの登録キーのポスティングデータが数個程度であるため、その効果を顕著に得ることができる。
【００６６】
また、ポスティングデータが１ページに満たないサイズの場合は、複数の登録キーのポスティングデータを共有ページ１３７内に詰めて格納する。これにより、余分な記憶領域を確保する必要がなくなり、記憶領域の節約になる。また、リーフページ１３６からポスティングデータを移動させた場合などに新たにページを確保する処理を省略できる可能性が高くなる。さらに、４０００個を超えるような膨大なポスティングデータを有する登録キーについては、Ｂ＋ツリーを構築してリーフページにポスティングデータを格納する。文書ＩＤによってＢ＋ツリーを辿ることにより、不必要なポスティングデータを読み飛ばすことができ、ポスティング格納部１３４へのアクセス回数を削減できるとともにポスティングデータの確認に要する時間を短縮することができる。
【００６７】
さらに本実施の形態では、登録された文書数が増加するのに伴い、キー格納部１３２のＢ＋ツリーのリーフページ１３６に格納するポスティングデータ数のしきい値を調整する。これにより、登録文書数の増加により全体的にポスティングデータ数が増加しても、常にある割合の登録キーのポスティングデータがリーフページ１３６に格納される。一般的な文書データベースでは、文書数が増加しても登録キーごとのポスティングデータ数はそれほど増加しないため、しきい値を多少変化させてもＢ＋ツリーのバランスを損なうことがない。結果として他に影響を及ぼすことなく実施の形態の形骸化を防止することができる。
【００６８】
以上、本発明を実施の形態をもとに説明した。この実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００６９】
例えば上述の実施の形態では、共有ページ、専有ページ、２層ツリーページ、３層ツリーページなる順序で、それまで格納されていたページの容量を超えた時点で、ポスティングデータを移動させた。一方、あらかじめポスティングデータのサイズを予想して、それに応じたページを用意するようにしてもよい。例えば、一般的な文書データベースで出現しやすい登録キーと、登録文書数の範囲ごとのポスティングデータのデータサイズとを対応づけた辞書をあらかじめ作成しておき、所定の文書数が登録されるたびに当該辞書を参照して、登録キーごとに必要と予測されるページを用意してもよい。
【００７０】
また、登録文書の増加に対するポスティングデータの増加速度を学習することにより、定期的に格納するページの見直しを行ってもよい。これらの場合も、上述の実施の形態と同様の効果を得ることができる。またポスティングデータを移動させる処理の実行予定が把握できるため、並列して他の処理を行っている場合などにトータルな処理の効率化を図ることができる。
【００７１】
また本実施の形態では、キー格納部１３２におけるＢ＋ツリーのリーフページへ格納するポスティングデータは、あるしきい値以下のポスティングデータを有する登録キーのものとした。一方、しきい値を設定せずに、登録キーそのものによって決定してもよい。この場合も、登録キーと、登録文書数の範囲ごとの最適な格納先とを対応付けた辞書をあらかじめ作成しておき、それを参照することにより、リーフページまたはその他のページを格納先として決定してもよい。
【図面の簡単な説明】
【００７２】
【図１】本実施の形態の文書検索装置による処理の概要を説明するための模式図である。
【図２】本実施の形態の文書検索装置の詳細な構成を示す図である。
【図３】本実施の形態においてキー格納部に格納されるＢ＋ツリーの構造を模式的に示す図である。
【図４】本実施の形態の文書検索装置によって登録文書ファイルを解析し、インデックスへ登録する処理手順を示すフローチャートである。
【図５】本実施の形態においてポスティングデータを格納する記憶領域を決定し、書き込みを行う手順を示すフローチャートである。
【図６】本実施の形態における共有ページの構成を模式的に示す図である。
【図７】本実施の形態における２層ツリーページの構成を模式的に示す図である。
【符号の説明】
【００７３】
１００ 文書検索装置、 １１０ ユーザインタフェース処理部、 １１２ 文書取得部、 １１６ 検索クエリ取得部、 １２０ 登録部、 １２２ キー抽出部、 １２４ ポスティング生成部、 １２６ ポスティング記憶領域決定部、 １２８ データ書込み部、 １３０ インデックス保持部、 １３２ キー格納部、 １３４ ポスティング格納部、 １３７ 共有ページ、 １３８ 専有ページ、 １４０ ２層ツリーページ、 １４２ ３層ツリーページ、 １６０ 検索部、 １６２ ポスティング取得部、 １６４ 文書データ取得部、 ２００ 文書データベース。
【技術分野】
【０００１】
本発明は文書処理技術に関し、特に入力されたテキストを含む文書ファイルを検索するための文書検索装置およびそれに適用される文書検索方法に関する。
【背景技術】
【０００２】
情報処理技術やネットワークの充実に伴い、ＰＣ(Personal Computer)や携帯電話などの情報端末からウェブサイトやデータベースへアクセスして必要な情報を取得することが日常的に行われるようになった。一方でデータベース化される情報は膨大化の一途をたどり、それらの情報の中から必要な情報を取得する際の効率性が求められるようになってきた。ウェブサイトやネットワーク上に開示された情報を検索する検索エンジンから、各種のデータベースを検索する検索システムまで、文書検索の機能は適切かつ最新の情報取得には欠かせないものとなっている。
【０００３】
自然言語に基づく文書検索技術のひとつにNgram解析がある。Ngram解析ではまず、検索対象の文書から所定数の文字列、すなわち「キー」を切り出し、文書における出現場所の情報をキーごとに記憶させておく。このようなデータを「インデックス」と呼ぶ。そして検索時は、検索クエリに含まれるキーに基づきインデックスを検索し、検索クエリ内のキーの順序などに基づき、検索クエリを含む文書を特定する（例えば特許文献１参照）。
【特許文献１】特開平５−２７４３５５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
Ngram解析は、意味をなす、なさないに関わらず、文書に含まれるキーを全て切り出してインデックスを生成し、検索クエリに含まれるキーと照合する。そのため意味をなす語句を抽出する形態素解析と比較し検索結果に漏れが生じにくい、という特徴を有するが、一方で検索対象の文書数が増加するのに従い、インデックスのデータ量が急増する。そのため検索クエリを含む所望の文書情報を特定するまでには、膨大なデータ量のインデックスにアクセスする必要があり、処理に時間がかかる場合が多い。
【０００５】
本発明はこうした状況に鑑みてなされたものであり、その目的は、Ngram解析を用いた検索を効率的に行う技術を提供することにある。
【課題を解決するための手段】
【０００６】
本発明のある態様は、文書検索装置に関する。この文書検索装置は、文書から所定数の文字列を登録キーとして抽出するキー抽出部と、登録キーが抽出された文書の識別情報と当該文書における抽出箇所とを含むデータセットを１単位とするポスティングデータを登録キーごとに記憶したポスティング格納部と、ポスティング格納部におけるポスティングデータの格納領域と、対応する登録キーとを関連付けたツリー構造を構成する記憶領域を有するキー格納部と、を含むインデックス保持部と、検索クエリから所定数の文字列を検索キーとして抽出し、インデックス保持部を参照して検索キーに対するポスティングデータを取得することにより検索クエリを含む文書の検索を行う検索部と、を備え、キー格納部におけるツリー構造の最下層のノードを構成する記憶領域の少なくとも一部に、ポスティングデータの少なくとも一部が記憶され、検索部は少なくとも一部の検索キーについて、キー格納部のみを参照してポスティングデータを取得することを特徴とする。
【０００７】
ここで「抽出箇所」は登録キーの開始位置、終了位置などであるが、文書検索装置において共有される所定の規則に従えばその形式は問わない。またポスティングデータは文書の識別情報と抽出箇所以外のパラメータを含んでいてよい。さらに「ツリー構造を構成する記憶領域」とはアルゴリズム上でツリー構造を構成する各ノードに対応した記憶領域のことであり、実際の記憶領域は連続していても分散していてもよい。「検索クエリ」は文書検索を行うためにユーザが入力した文字列であり、語句あるいは文章のいずれでもよく、１つでも複数でもよい。
【０００８】
本発明の別の態様は、文書検索方法に関する。この文書検索方法は、文書から所定数の文字列を登録キーとして抽出するステップと、登録キーが抽出された文書の識別情報と当該文書における抽出箇所とを含むデータセットを１単位とするポスティングデータを登録キーごとに生成するステップと、ポスティングデータを登録キーごとに記憶装置に記憶させるステップと、検索クエリから所定数の文字列を検索キーとして抽出するステップと、記憶装置を参照して検索キーに対する前記ポスティングデータを取得することにより検索クエリを含む文書の検索を行うステップと、を含み、記憶装置におけるポスティングデータの記憶領域を、登録キーごとのポスティングデータ数に応じて異ならせることを特徴とする。
【０００９】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１０】
本発明によれば、ユーザは漏れのない検索を効率的に行うことができる。
【発明を実施するための最良の形態】
【００１１】
図１は、文書検索装置１００による処理の概要を説明するための模式図である。ユーザが文書検索装置１００に対して検索クエリを入力すると、文書検索装置１００はその検索クエリを含む文書ファイルを文書データベース２００から検索する。検索クエリは一定の意味をなす文字列であり、自然文であってもよいしキーワードであってもよい。文書データベース２００の文書ファイルは、ＸＭＬ（eXtensible Markup Language）文書やＸＨＴＭＬ（eXtensible HyperText Markup Language）文書のようにタグによって構造化されたファイルであってもよいし、単なるテキストファイルであってもよい。また文書データベース２００は図示しないネットワークを介して文書検索装置１００と接続されていてもよい。
【００１２】
検索に先立ち、文書検索装置１００は文書データベース２００内の文書についてNgram解析を行いインデックスを作成してインデックス保持部１３０に格納する。インデックス保持部１３０はハードディスクなど大容量の記憶装置、またはその一部で実現できる。インデックスの構造については後に詳述する。文書検索装置１００は検索クエリに基づきインデックスを参照して、文書データベース２００内の適合する文書ファイルを特定し、検索結果として画面表示する。その際、一般的に用いられるスコアリングの手法によって得られたスコアに基づき結果の表示順を決定してもよい。こうして、文書検索装置１００のユーザは、任意の検索クエリを含む文書ファイルを探し出すことができる。
【００１３】
図２は文書検索装置１００の詳細な構成を示している。ここに示す各ブロックは、ハードウェア的には、コンピュータのＣＰＵをはじめとする素子や機械装置で実現でき、ソフトウェア的にはコンピュータプログラム等によって実現されるが、ここでは、それらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックはハードウェア、ソフトウェアの組合せによっていろいろなかたちで実現できることは、当業者には理解されるところである。
【００１４】
文書検索装置１００はユーザによる入力の受け付けや結果の出力を担うユーザインタフェース処理部１１０、検索対象の文書についてのデータをインデックスに登録する登録部１２０、入力された検索クエリに基づき検索を行う検索部１６０、およびインデックス保持部１３０を含む。文書検索装置１００はさらに、各機能ブロックが処理を行うために必要なデータやプログラムを一時的に格納するメモリ１７０を含む。
【００１５】
ユーザインタフェース処理部１１０は、ユーザからの入力処理やユーザに対する情報表示のようなユーザインタフェース全般に関する処理を担当する。本実施の形態においては、ユーザインタフェース処理部１１０により文書検索装置１００のユーザインタフェースサービスが提供されるものとして説明する。別例として、ユーザはインターネットを介して文書検索装置１００を操作してもよい。この場合、図示しない通信部が、ユーザ端末からの操作指示情報を受信し、またその操作指示に基づいて実行された処理結果情報をユーザ端末に送信することになる。
【００１６】
ユーザインタフェース処理部１１０は文書取得部１１２、表示部１１４、および検索クエリ取得部１１６を含む。新規の文書データベース２００を構築した場合や、元からある文書データベース２００に新規の文書ファイルを登録して検索対象とする場合に、文書取得部１１２は当該文書ファイル（以後、登録文書ファイルと呼ぶ）の情報をユーザからの入力によって取得し、登録部１２０へ供給する。この文書ファイルの情報は、文書データベース２００に保存されている文書ファイルを指定する情報でもよいし、別の場所に保存されている文書ファイルを指定する情報でもよい。後者の場合、文書検索装置１００は読み出した文書ファイルを文書データベース２００へ保存するようにしてもよい。検索クエリ取得部１１６は、検索を行いたいユーザによって入力された検索クエリを受け付け、検索部１６０に供給する。
【００１７】
登録部１２０はキー抽出部１２２、ポスティング生成部１２４、ポスティング記憶領域決定部１２６、およびデータ書込み部１２８を含む。キー抽出部１２２は、文書取得部１１２から供給された文書ファイルの情報に従い登録文書ファイルを読み出し、走査することにより、あらかじめ定められた文字数、すなわち所定のグラム数を有するキーを抽出する。例えば「アメリカ合衆国の大統領」というテキストであれば、「アメ：メリ：リカ：・・・：統領」のようにキーを抽出する。この例におけるキーは２グラムである。グラム数は最適な値をあらかじめ設定しておく。以後の説明では登録文書ファイルから抽出されたキーを「登録キー」と呼ぶ。
【００１８】
ポスティング生成部１２４は、登録文書ファイルに対し一意に定めた識別情情報である文書ＩＤを付与するとともに、各登録キーに対するポスティングデータを生成する。ポスティングデータは、各登録キーがどの文書のどの位置に出現したかを表す情報であり、例えば［文書ＩＤ，キー開始位置，キー終了位置］という構造を有するデータセットである。抽出した登録キーの中に同一のものがあれば、対応するポスティングデータをまとめる。例えば「アメ」なるキーが４つ抽出されていれば、キー「アメ」に対し４つのポスティングデータが生成される。
【００１９】
ポスティング記憶領域決定部１２６は、生成されたポスティングデータをインデックス保持部１３０のどの領域に記憶させるかを決定し、データ書込み部１２８は当該決定に従いポスティングデータおよびそれに係る情報をインデックス保持部１３０に追加して書き込む。ポスティング記憶領域決定部１２６は、ポスティングデータを記憶させる記憶領域の決定以外に、記憶領域決定のための各種処理も行う。ポスティングデータの記憶領域については後に詳述する。
【００２０】
検索部１６０はポスティング取得部１６２および文書データ取得部１６４を含む。ポスティング取得部１６２は検索クエリからキーを抽出し、インデックス保持部１３０を参照して当該キーに対応するポスティングデータを取得する。以後、検索クエリから抽出したキーを「検索キー」と呼ぶ。ポスティング取得部１６２は、検索キーが全て含まれる文書を各キーのポスティングデータに含まれる文書ＩＤから特定し、さらにそれらの検索キーが検索クエリにおける順序で連続して出現する文書を、ポスティングデータに含まれるキー開始位置、キー終了位置に基づき絞り込む。これにより検索クエリを含む文書を特定できる。なおここでは基本的な処理内容のみを説明するが、検索処理に一般的に用いられるあらゆる技術を組み合わせてもよい。
【００２１】
文書データ取得部１６４は、特定された文書の文書ＩＤに基づき文書データベース２００から該当文書の少なくとも一部や記憶先のアドレスなどを取得し、ユーザインタフェース処理部１１０の表示部１１４が検索結果として表示できるように表示データを整えメモリ１７０に保存する。
【００２２】
ここでインデックス保持部１３０に保持されたインデックスの構造および記憶領域について説明する。インデックスは、登録文書ファイルから抽出された登録キーとポスティングデータとを関連付けたデータである。登録キーはグラム数に応じて機械的に切り出されるため、同一の登録キーをまとめてもその種類は膨大である。一方、検索時には検索キーに合致した、インデックス内の登録キーを探し出し、それと関連付けられたポスティングデータを特定する処理がなされる。膨大な種類の登録キーの中から検索キーを効率よく検出するために、一般に利用されるのがＢ＋ツリー（Balanced plus tree）のアルゴリズムである。
【００２３】
このとき用いられるＢ＋ツリーは、所定の規則でソートされた登録キーの列の範囲によって下層のノードへの分岐を決定するルートノードおよびブランチノードと、末端のノードであり、ツリーによって最終的に絞り込まれた登録キーの候補と、各登録キーのポスティングデータの記憶領域を示すポインタとが記述されたリーフノードからなるツリー構造を有する。検索処理時には、検索キーに従いルートノードから下層へノードを辿っていけば、行き着いたリーフノードに記述された登録キーの候補の中に検索キーと同一のものが含まれており、最終的に所望のポスティングデータへのポインタが得られることになる。
【００２４】
このような検索処理においてはまず、（１）Ｂ＋ツリー構造が格納された記憶領域にアクセスしてポスティングデータへのポインタを取得し、（２）ポスティングデータが格納された記憶領域にアクセスしてポスティングデータを取得する、という最低２回のアクセスを必要とする。１つの検索クエリからは通常、複数の検索キーが抽出されるため、それらの検索キーに対し同様の処理を繰り返すと、記憶領域へのアクセス回数が増大する。キャッシュメモリなどを用いても、検索条件によっては看過できない程の時間を要する場合がある。
【００２５】
本発明者は検索に要する時間を短縮するため鋭意研究を重ねた結果、インデックスに係る以下の知見を得るに至った。表１は、一般的な文書データベースのインデックスにおける、キーごとのポスティングデータ数の分布を表している。このデータは８７万７７１３の文書ファイルから２グラムの登録キーを抽出した場合であり、このとき抽出された登録キーは１３３９１０３個であった。
【００２６】
【表１】
【００２７】
例えば「ポスティング数」が「３」の行を見ると、３個のポスティングデータを有する登録キーは、「合計」欄のとおり「９４０３８」個あり、ポスティングデータ数が３個までの累積値、すなわち１〜３個のポスティングデータを有する登録キーの個数は「累積」欄のとおり「６１３３６９」個である。そして全登録キーのうち１〜３個のポスティングデータを有する登録キーの割合は、「累積割合」欄のとおり「４５．８％」である。同表によれば、全登録キーのうち５５％程度はポスティングデータ数が５個以下の登録キーであることがわかる。それに対し、１００１個以上のポスティングデータを有する登録キーは全体のわずか０．６％である。
【００２８】
したがって上述のようにＢ＋ツリーからポインタを取得し、ポインタからポスティングデータを取得する構成においては、わずか数個のポスティングデータを取得するために別の記憶領域へアクセスし直している可能性が少なからずあるといえる。本発明者はこの点に改良の余地を見出し、ポスティングデータの取得を効率的に行うために次のような実施の形態に想到した。
【００２９】
本実施の形態でも基本的には上述のアルゴリズムを採用する。そのため、インデックス保持部１３０には、Ｂ＋ツリーを格納するキー格納部１３２および各ポスティングデータを格納するポスティング格納部１３４が含まれる。したがって一般的なＢ＋ツリーのリーフノードにおいて記述されるポスティングデータへのポインタは、ポスティング格納部１３４内の記憶領域を示す。以後、リーフノードやポスティングデータの記憶領域はページを単位として説明し、ポインタはページ番号とする。またこれ以後、登録キーとポスティングデータとの関連付けはＢ＋ツリーを用いて行うものとするが、本実施の形態はこれに限らず、例えばＢツリーなどでもよい。
【００３０】
一方、本実施の形態では、登録キーの絞込みを行うためのＢ＋ツリー構造の中に、ポスティングデータの一部を組み入れる。すなわち、本実施の形態のリーフページ１３６には、登録キーとポスティングデータのページ番号との組み合わせのみならず、登録キーとポスティングデータそのものの組み合わせも記述される。したがってポスティング記憶領域決定部１２６は、ポスティングデータをキー格納部１３２、すなわちＢ＋ツリーのリーフページ１３６に記憶させるか、ポスティング格納部１３４へ記憶させるか、を決定する。
【００３１】
ポスティング記憶領域決定部１２６は、登録キーごとのポスティングデータの数、すなわち、登録文書ファイルから新たに生成された登録キーのポスティングデータと、同一の登録キーに対しインデックスに登録済みのポスティングデータとの合計によって、当該登録キーのポスティングデータの記憶領域を決定する。具体的にはポスティングデータの数にしきい値を設け、しきい値以下の数のポスティングデータしか持たない登録キーであればＢ＋ツリーのリーフページ１３６に記述し、しきい値より大きい数のポスティングデータを有する登録キーについてはポスティング格納部１３４内の領域に記述する。
【００３２】
例えばしきい値を「５」とした場合、表１に示したような文書データベースでは、約５５％の登録キーのポスティングデータは、キー格納部１３２のみにアクセスすることによって取得することができる。また５個程度のポスティングのデータサイズであればリーフページ１３６の記憶容量を圧迫することがなく、Ｂ＋ツリー構造はそのバランスを損なうことなくそのまま用いることができる。結果としてインデックス保持部１３０へのアクセス回数のみが削減され、短期間で効率のよい検索処理が可能となる。
【００３３】
さらにポスティング記憶領域決定部１２６は、所定の文書数が登録されるごとに、全体に対する登録キーの割合に基づき上述のしきい値を変化させる。例えば文書が１０万文書登録されるごとに、１個のポスティングデータを有する登録キーからの累積割合が６０％を超えない登録キーが有する最大のポスティングデータ数へしきい値を変更する。これは、登録される文書数が増加するほど、当然登録キーごとのポスティング数が増加する傾向となるための措置である。そのような状況でしきい値をあるポスティングデータ数で固定してしまうと、登録文書の増加とともに、しきい値より多くのポスティングデータ数を有する登録キーの割合が増加していき、結局アクセス回数の削減効果が薄れてしまう。
【００３４】
そこで累積割合に基づきしきい値を調整し、常にある割合の登録キーについてはリーフページ１３６からポスティングデータが得られるようにする。表１によれば、キーごとのポスティングデータ数が増加するほど累積割合の増加量は小さくなる。すなわち登録文書数が増加しても、累積割合が６０％などとなる登録キーのポスティングデータ数が急激に増加する可能性は低いと考えられる。したがって、上述のようにしきい値を変化させても、リーフページ１３６の容量を圧迫したりＢ＋ツリーのバランスを損なったりする程のポスティングデータが記述される可能性は低く、結果として上述したような効果を登録文書数の多少に関わらず定常的に得ることができる。
【００３５】
ポスティングデータをリーフページ１３６に記述する場合、データ書込み部１２８は、対応する登録キーが記述されているリーフページ１３６にポスティングデータを追加して書き込む。ポスティングデータをポスティング格納部１３４に格納する場合、データ書込み部１２８は、対応する登録キーが記述されているリーフページ１３６を参照し、当該登録キーに対応づけて記述された、ポスティングデータのページ番号を取得して、ポスティング格納部１３４内の該当ページにポスティングデータを追加して書き込む。
【００３６】
図２のキー格納部１３２やポスティング格納部１３４に示した最も小さい単位の矩形はページを表している。上述したとおり、キー格納部１３２およびポスティング格納部１３４はそれぞれＢ＋ツリーおよびポスティングデータを格納するが、Ｂ＋ツリーのリーフページ１３６に記述されたデータにはポスティングデータも含まれる。同図ではそのようなページを網掛けで表している。リーフページ１３６以外のリーフページにもポスティングデータを記述してよいが、ここではリーフページ１３６に代表させている。
【００３７】
ポスティング格納部１３４には当然、ポスティングデータが格納されるため、それを記述したページとして網掛けされた矩形がいくつか示されているが、本実施の形態では登録キーごとのポスティングデータの数により、そのページ構成を異ならせる。具体的には、１ページに複数の登録キーのポスティングデータを記述する共有ページ１３７、１ページ以上に一の登録キーのポスティングデータを記述する専有ページ１３８、文書ＩＤをキーとした２層のＢ＋ツリー構造のリーフページに一の登録キーのポスティングデータを記述した２層ツリーページ１４０、同じく３層のＢ＋ツリー構造により一の登録キーのポスティングデータを記述した３層ツリーページ１４２である。なお各ページの総数はポスティングデータの数によって増減する。それぞれのページ構成の詳細は後に述べる。
【００３８】
図３は、キー格納部１３２に格納されるＢ＋ツリーの構造を模式的に示している。Ｂ＋ツリー２０は、ルートページ２２、ブランチページ２４および２６、リーフページ２８、３０、および１３６を含む。ただしページ数や層の深さはこれに限らない。各ページの左上に示した「＃番号」はそれぞれのページに一意に設定されたページ番号である。
【００３９】
まずページ番号＃１のルートページ２２を見ると、「５」、「キーＣ」、「８」、「キーＦ」といったデータ列が記述されている。ここで「キーＣ」、「キーＦ」は「アメ」、「メリ」など具体的な登録キーの文字列である。同図の場合、ソートされた登録キーの列の先頭から「キーＣ」の前までの登録キーについては下層のページ番号＃５のページに記述されており、「キーＣ」から「キーＦ」の前までの登録キーについては下層のページ番号＃８のページに記述されていることを示している。
【００４０】
ページ番号＃５のブランチページ２４も同様に、先頭から「キーＡ」の前までの登録キーについてはページ番号＃３６のページに、「キーＡ」から「キーＢ」の前までの登録キーについてはページ番号＃４６のページに記述されていることを示している。ページ番号＃８のブランチページ２６も同様である。これに従い、ページ番号＃３６のリーフページ２８には先頭から「キーＡ」の前までの登録キーのポスティングデータについての情報が、ページ番号＃４６のリーフページ３０には「キーＡ」から「キーＢ」の前までの登録キーのポスティングデータについての情報が記述される。
【００４１】
同図では、リーフページ２８、３０などに記述されるデータを、リーフページ１３６を代表させて図示している。上述したとおりリーフページ１３６には、複数の登録キーのそれぞれに対し、ポスティングデータそのもの、またはポスティング格納部１３４におけるポスティングデータを記述したページ番号のいずれかが記述される。同図は、「キーＧ」、「キーＨ」、「キーＪ」、「キーＬ」に対しポスティングデータそのものが記述され、「キーＩ」に対しては図２の共有ページ１３７のページ番号、「キーＫ」に対しては専有ページ１３８の先頭のページ番号、「キーＭ」に対しては２層ツリーページ１４０のルートページのページ番号が記述されていることを示している。
【００４２】
次に、これまで述べた構成を有する文書検索装置１００の動作について説明する。なお検索部１６０が行う検索クエリに基づく検索処理の手順は、上述したとおり一般的な手法を用いることができるため、ここではインデックスへの登録手法に主眼を置き説明する。図４は文書検索装置１００によって登録文書ファイルを解析し、インデックスへ登録する処理手順を示すフローチャートである。ここではインデックス保持部１３０に、それまでに解析を済ませた文書ファイルのインデックスが既に格納されており、新たな登録文書の情報を登録する場合について述べるが、新規にインデックスを生成する場合でも、本実施の形態の特徴的な手順は同様であり、Ｂ＋ツリーの構築などは一般的な手法を適用することができる。
【００４３】
まずユーザが、ユーザインタフェース処理部１１０の文書取得部１１２に対し登録文書ファイルの情報を入力すると、登録部１２０のキー抽出部１２２は当該登録文書ファイルを読み出し、メモリ１７０に保存する（Ｓ１０）。キー抽出部１２２は、登録文書ファイルからテキストデータを抽出し（Ｓ１２）、それを走査することにより所定のグラム数の登録キーを抽出していく（Ｓ１４）。次にポスティング生成部１２４は、登録文書ファイルに文書ＩＤを付与するとともに、キー抽出部１２２が抽出した登録キーごとに、当該文書ＩＤと、テキストデータにおける当該登録キーの開始位置および終了位置とからなるポスティングデータを生成する（Ｓ１６）。
【００４４】
次にポスティング記憶領域決定部１２６が、生成したポスティングデータの格納領域を決定し、データ書込み部１２８がそれに従い書き込みを行う（Ｓ１８）。この際、前述したとおり、インデックスに登録済みのポスティングデータを含めた登録キーごとのポスティングデータ数としきい値との大小関係によって格納場所を決定する。また今回抽出した登録キーのポスティングデータをリーフページ１３６に書き込むことによりその登録キーのポスティングデータ数がしきい値を超えてしまう場合は、リーフページ１３６に記述済みのポスティングデータごとポスティング格納部１３４へ移動させる。具体的な処理手順は図５を参照して説明する。
【００４５】
図５は、Ｓ１８においてポスティング記憶領域決定部１２６がポスティングデータの記憶領域を決定し、データ書込み部１２８が書き込みを行う手順を示すフローチャートである。前提として、文書ファイルの累積数を示す変数ｉは“０”に初期化され、リーフページ１３６に記述できるポスティングデータ数のしきい値Ｎには初期値、たとえば“５”が代入されているとする。まず変数ｉをインクリメントした後（Ｓ２８）、登録文書ファイルの情報を新たに登録した場合のインデックスについて表１に示した各数値を計算し、登録キーごとのポスティング数に対する登録キーの個数の累積割合を算出する（Ｓ３０）。累積割合を含む表１のデータは、メモリ１７０などに一時保存し、文書検索装置１００の処理を終了させる際にインデックス保持部１３０を構成するハードディスクなどに保存しておく。新たな文書登録を行う際は、そのように保存された以前のデータを参照して計算を行い、各値を更新してけばよい。
【００４６】
次に変数ｉに対し所定の文書数Ｍ、例えば１０万で剰余算を行い、解が０でなければ、すなわち今回の登録文書ファイルが１０万の倍数文書目でなければ（Ｓ３２のＮ）、抽出した各登録キーについてＢ＋ツリーを辿り、まずリーフページ１３６に当該登録キーが記述されているかどうかを確認する（Ｓ３７）。登録キーが以前に登録されていなければ、リーフページ１３６には当該登録キーが記述されていないため（Ｓ３７のＮ）、リーフページ１３６に登録キーとそのポスティングデータを書き込む（Ｓ４６）。
【００４７】
登録キーが記述されていた場合は（Ｓ３７のＹ）、さらにリーフページ１３６に当該登録キーのポスティングデータが記述されているかどうかを確認する（Ｓ３８）。ポスティングデータが記述されておらず、ページ番号が記述されている場合は（Ｓ３８のＮ）、ポスティング格納部１３４における当該ページ番号のページにポスティングデータを追加して書き込む（Ｓ４０）。
【００４８】
リーフページ１３６にポスティングデータが記述されている場合は（Ｓ３８のＹ）、新たなポスティングデータの追加によりポスティングデータ数がしきい値Ｎを超えるかどうかを確認する（Ｓ４２）。しきい値Ｎを超えない場合は（Ｓ４２のＹ）、そのリーフページ１３６にポスティングデータを追加して書き込む（Ｓ４６）。ポスティングデータ数がしきい値Ｎを超える場合は（Ｓ４２のＮ）、それまで記述されていた当該登録キーのポスティングデータをポスティング格納部１３４に用意されている共有ページ１３７などに移動させたうえで、新たなポスティングデータを同ページに追加して書き込む（Ｓ４８）。この際、移動元のリーフページ１３６には、当該キーに対応させて移動先のページのページ番号を書き込んでおく。
【００４９】
Ｓ３２において当該登録文書ファイルが所定の文書数Ｍの倍数であった場合は（Ｓ３２のＹ）、Ｓ３０において算出した累積割合に基づきしきい値Ｎを変更する（Ｓ３４）。ここでＮ（６０％）は累積割合が６０％を超えない登録キーの最大のポスティングデータ数を表す。なお６０％は例示であり、データベースの種類や文書検索装置１００の処理性能などに鑑み実験などにより最適値を決定してよい。そしてしきい値Ｎの変更によってリーフページ１３６に記述されるべきとなったポスティングデータがあれば、ポスティング格納部１３４のページからリーフページ１３６に移動する（Ｓ３６）。その後の処理は上述したのと同様である。
【００５０】
以上の手順により、登録されている文書数の増加に伴いポスティングデータ数のしきい値を変化させながら、ポスティングデータをリーフページ１３６およびポスティング格納部１３４へ振り分ける態様を実現することができる。
【００５１】
次にポスティング格納部１３４に格納された、ポスティングデータを記述するページの構成について説明する。上述したように本実施の形態では登録キーごとのポスティングデータ数により、共有ページ１３７、専有ページ１３８、２層ツリーページ１４０、３層ツリーページ１４２のいずれかにポスティングデータを記述し、記憶領域を効率的に使用するとともに検索の処理効率を向上させる。なおツリーページは必要に応じて４層以上でもよい。
【００５２】
図６は共有ページ１３７の構成を模式的に示している。共有ページ１３７には複数のキーのポスティングデータを可能な限り詰めた状態で記述する。リーフページ１３６においてポスティングデータ数がしきい値を超えた登録キーのポスティングデータは、この共有ページ１３７に移動する。１ページのデータ容量、８ＫＢを考慮すると、登録キーごとのポスティングデータ数が最大５００個程度であれば、共有ページ１３７内に記述できる。
【００５３】
共有ページ１３７は、ポスティングデータ領域８２ａ〜８２ｆ、ポインタ領域８４ａ〜８４ｆ、および空き領域８６を含む。同図は、６つの登録キーのポスティングデータが、６つの連続したポスティングデータ領域８２ａ〜８２ｆのぞれぞれに記述されている状態を示している。登録キーごとのポスティングデータ数は一定でないため、ポスティングデータ長も変動する。そこで各ポスティングデータ領域８２ａ〜８２ｆの、ページ先頭からのオフセット値をポインタ領域８４ａ〜８４ｆにそれぞれ記述する。新たなポスティングデータをポスティングデータ領域８２ａ〜８２ｆのいずれかに追加した場合は、以後のポスティングデータ領域のオフセット値を更新する。
【００５４】
リーフページ１３６からポスティングデータを移動する際は、充填率が高くなるような共有ページ１３７を探して格納する。そのために空き領域８６の容量を管理する。例えば２ビットのレジスタ（図示せず）を用意し、空き領域８６の容量について、２５％未満、２５％以上５０％未満、５０％以上７５％未満、７５％以上１００％以下、の４段階を表すデータを保持する。レジスタの値は文書検索装置１００の処理終了時にはハードディスクなどに保存し、次回の登録処理において参照する。
【００５５】
表１によれば、５００個以下のポスティングデータを有する登録キーは全体の９０％程度にも上るため、ポスティングデータをリーフページ１３６に格納するほか、共有ページ１３７に詰めて格納することにより、キーごとに１ページを用意するといった従来の手法に比べて格段に所要容量を削減することができる。また、新たな空きページを確保するなどの領域管理の処理を省略でき、登録処理時の効率が向上する。
【００５６】
共有ページ１３７に記述したある登録キーのポスティングデータが増加し、１ページ以内で収まらなくなった場合は、当該ポスティングデータを専有ページ１３８へ移動させる。専有ページは一の登録キーが専有して使う１以上のページで構成され、ポスティングデータ数によってページを単純連結していく。例えば最大８ページまで連結可能とする。これにより一の登録キーにつき５００〜４０００個程度のポスティングデータが格納できる。
【００５７】
最大に連結した専有ページ１３８の容量をポスティングデータが超えた場合は、当該ポスティングデータをリーフページに格納した２層ツリーページ１４０を構築する。図７は２層ツリーページ１４０の構成を模式的に示している。２層ツリーページ１４０は基本的には図３で示したのと同様のＢ＋ツリー構造を有する。ただしページの分岐は登録キーに代わり文書ＩＤによって行う。
【００５８】
前述したように、検索部１６０が検索処理を行う場合、入力された検索クエリから検索キーを抽出し、検索キーの全てを含み、かつ検索クエリにおける順番で連続して出現する文書を検出する。検索クエリから検索キーとして「キーａ」、「キーｂ」が抽出されたとすると、まず「キーａ」のポスティングデータを取得し、その文書ＩＤをメモリ１７０に保存する。そして「キーｂ」のポスティングデータのうち、メモリ１７０に保存しておいた文書ＩＤを有するポスティングデータを取得すれば、それはすなわち「キーａ」および「キーｂ」を含む文書のポスティングデータである。
【００５９】
ここで「キーｂ」が４０００個を超える膨大なポスティングデータを有するとすると、それらのポスティングデータを単に羅列したデータ構造においては、先頭から全てのポスティングデータを確認し、「キーａ」を含む文書の文書ＩＤと照合していかなければならない。検索キーが多いほど、この処理を繰り返す必要が生じ、結果としてポスティング格納部１３４へのアクセス回数が増大する。
【００６０】
そこで本実施の形態では、４０００個を超えるようなポスティングデータを有する「キーｂ」のポスティングデータを取得する際、「キーａ」を含む文書の文書ＩＤを元に図７に示すようなＢ＋ツリー構造を辿ることにより、「キーａ」を含む文書のポスティングデータのみを確認する。図７において２層ツリーページ１４０は、ルートページ４２、ブランチページ４４および４６、リーフページ４８、５０、５２、５４を含む。図３と同様、ルートページ４２には、ある登録キーに対する全ポスティングデータに記載された文書ＩＤをソートした文書ＩＤ列のうち、先頭から「ＩＤ＿ｃ」の前までの文書ＩＤを有するポスティングデータの情報がページ番号＃１のページに、「ＩＤ＿ｃ」から「ＩＤ＿ｆ」の前までの文書ＩＤを有するポスティングデータの情報がページ番号＃５２のページに記述されていることが示されている。
【００６１】
同様に、ページ番号＃１のブランチページ４４には、先頭から「ＩＤ＿ａ」の前までの文書ＩＤを有するポスティングデータがページ番号＃２のページに、「ＩＤ＿ａ」から「ＩＤ＿ｂ」の前までの文書ＩＤを有するポスティングデータがページ番号＃３のページに記述されていることが示されている。ページ番号＃５２のブランチページ４６も同様である。ページ番号＃２のリーフページ４８、ページ番号＃３のリーフページ５０、ページ番号＃１７のリーフページ５２、ページ番号＃１８のリーフページ５４にはそれぞれ、該当する文書ＩＤを有するポスティングデータが記述されている。
【００６２】
このような構成とすることにより、上述の例では、「キーａ」を含まない文書に対するポスティングデータを読み飛ばすことができ、ポスティング格納部１３４へのアクセス回数を削減することができる。ポスティングの確認に係る処理も省略できるため、結果として検索処理にかかる時間を顕著に削減することができる。
【００６３】
２層ツリーページ１４０には、最大約８ＭＢ、すなわち５０万個程度のポスティングデータを格納することができる。ある登録キーのポスティングデータが２層ツリーページ１４０に格納できる数を超えた場合は、当該ポスティングデータをリーフページに格納した３層ツリーページ１４２を構築する。３層ツリーページ１４２はブランチページが２層になっているほかは２層ツリーページ１４０と同様である。３層ツリーページ１４２には、最大８ＧＢ、すなわち５億個程度のポスティングデータを格納することができる。
【００６４】
以上述べた本実施の形態によれば、登録キーごとのポスティングデータ数に応じて、ポスティングデータの格納領域を、キー格納部１３２におけるＢ＋ツリー構造のリーフページ１３６、ポスティング格納部１３４における共有ページ１３７、専有ページ１３８、２層ツリーページ１４０、３層ツリーページ１４２と変化させる。また、文書の登録数によってポスティングデータ数が増加した場合は、上述の順番でデータを移動させていく。これにより、常にポスティングデータのデータサイズに適合し、かつ無駄のない記憶領域管理を行うことができる。
【００６５】
さらにＢ＋ツリー構造のバランスを損なわない程度のサイズのポスティングデータをキー格納部１３２のＢ＋ツリーのリーフページ１３６に格納することにより、検索処理時にポスティング格納部１３４へアクセスし直す必要がなくなり、全体としてアクセス回数が減るため、検索処理を高速化できる。一般的な文書データベースでは、多くの登録キーのポスティングデータが数個程度であるため、その効果を顕著に得ることができる。
【００６６】
また、ポスティングデータが１ページに満たないサイズの場合は、複数の登録キーのポスティングデータを共有ページ１３７内に詰めて格納する。これにより、余分な記憶領域を確保する必要がなくなり、記憶領域の節約になる。また、リーフページ１３６からポスティングデータを移動させた場合などに新たにページを確保する処理を省略できる可能性が高くなる。さらに、４０００個を超えるような膨大なポスティングデータを有する登録キーについては、Ｂ＋ツリーを構築してリーフページにポスティングデータを格納する。文書ＩＤによってＢ＋ツリーを辿ることにより、不必要なポスティングデータを読み飛ばすことができ、ポスティング格納部１３４へのアクセス回数を削減できるとともにポスティングデータの確認に要する時間を短縮することができる。
【００６７】
さらに本実施の形態では、登録された文書数が増加するのに伴い、キー格納部１３２のＢ＋ツリーのリーフページ１３６に格納するポスティングデータ数のしきい値を調整する。これにより、登録文書数の増加により全体的にポスティングデータ数が増加しても、常にある割合の登録キーのポスティングデータがリーフページ１３６に格納される。一般的な文書データベースでは、文書数が増加しても登録キーごとのポスティングデータ数はそれほど増加しないため、しきい値を多少変化させてもＢ＋ツリーのバランスを損なうことがない。結果として他に影響を及ぼすことなく実施の形態の形骸化を防止することができる。
【００６８】
以上、本発明を実施の形態をもとに説明した。この実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００６９】
例えば上述の実施の形態では、共有ページ、専有ページ、２層ツリーページ、３層ツリーページなる順序で、それまで格納されていたページの容量を超えた時点で、ポスティングデータを移動させた。一方、あらかじめポスティングデータのサイズを予想して、それに応じたページを用意するようにしてもよい。例えば、一般的な文書データベースで出現しやすい登録キーと、登録文書数の範囲ごとのポスティングデータのデータサイズとを対応づけた辞書をあらかじめ作成しておき、所定の文書数が登録されるたびに当該辞書を参照して、登録キーごとに必要と予測されるページを用意してもよい。
【００７０】
また、登録文書の増加に対するポスティングデータの増加速度を学習することにより、定期的に格納するページの見直しを行ってもよい。これらの場合も、上述の実施の形態と同様の効果を得ることができる。またポスティングデータを移動させる処理の実行予定が把握できるため、並列して他の処理を行っている場合などにトータルな処理の効率化を図ることができる。
【００７１】
また本実施の形態では、キー格納部１３２におけるＢ＋ツリーのリーフページへ格納するポスティングデータは、あるしきい値以下のポスティングデータを有する登録キーのものとした。一方、しきい値を設定せずに、登録キーそのものによって決定してもよい。この場合も、登録キーと、登録文書数の範囲ごとの最適な格納先とを対応付けた辞書をあらかじめ作成しておき、それを参照することにより、リーフページまたはその他のページを格納先として決定してもよい。
【図面の簡単な説明】
【００７２】
【図１】本実施の形態の文書検索装置による処理の概要を説明するための模式図である。
【図２】本実施の形態の文書検索装置の詳細な構成を示す図である。
【図３】本実施の形態においてキー格納部に格納されるＢ＋ツリーの構造を模式的に示す図である。
【図４】本実施の形態の文書検索装置によって登録文書ファイルを解析し、インデックスへ登録する処理手順を示すフローチャートである。
【図５】本実施の形態においてポスティングデータを格納する記憶領域を決定し、書き込みを行う手順を示すフローチャートである。
【図６】本実施の形態における共有ページの構成を模式的に示す図である。
【図７】本実施の形態における２層ツリーページの構成を模式的に示す図である。
【符号の説明】
【００７３】
１００ 文書検索装置、 １１０ ユーザインタフェース処理部、 １１２ 文書取得部、 １１６ 検索クエリ取得部、 １２０ 登録部、 １２２ キー抽出部、 １２４ ポスティング生成部、 １２６ ポスティング記憶領域決定部、 １２８ データ書込み部、 １３０ インデックス保持部、 １３２ キー格納部、 １３４ ポスティング格納部、 １３７ 共有ページ、 １３８ 専有ページ、 １４０ ２層ツリーページ、 １４２ ３層ツリーページ、 １６０ 検索部、 １６２ ポスティング取得部、 １６４ 文書データ取得部、 ２００ 文書データベース。
【特許請求の範囲】
【請求項１】
文書から所定数の文字列を登録キーとして抽出するキー抽出部と、
前記登録キーが抽出された文書の識別情報と当該文書における抽出箇所とを含むデータセットを１単位とするポスティングデータを前記登録キーごとに記憶したポスティング格納部と、前記ポスティング格納部における前記ポスティングデータの格納領域と、対応する登録キーとを関連付けたツリー構造を構成する記憶領域を有するキー格納部と、を含むインデックス保持部と、
検索クエリから所定数の文字列を検索キーとして抽出し、前記インデックス保持部を参照して前記検索キーに対する前記ポスティングデータを取得することにより前記検索クエリを含む文書の検索を行う検索部と、
を備え、
前記キー格納部における前記ツリー構造の最下層のノードを構成する記憶領域の少なくとも一部に、前記ポスティングデータの少なくとも一部が記憶され、前記検索部は少なくとも一部の検索キーについて、前記キー格納部のみを参照して前記ポスティングデータを取得することを特徴とする文書検索装置。
【請求項２】
前記キー格納部における前記ツリー構造の最下層のノードを構成する記憶領域に記憶されるポスティングデータは、前記ポスティングデータの数が与えられたしきい値以下である前記登録キーのポスティングデータであることを特徴とする請求項１に記載の文書検索装置。
【請求項３】
前記キー抽出部が新たな文書から前記登録キーを抽出した際、当該登録キーごとに前記ポスティングデータを生成するポスティング生成部と、
前記ポスティング生成部が生成した前記ポスティングデータの記憶先を、前記登録キーごとに、前記ツリー構造の最下層のノードを構成する記憶領域および前記ポスティング格納部のいずれかに決定するポスティング記憶領域決定部と、
をさらに備え、
それまで前記ツリー構造の最下層のノードを構成する記憶領域に記憶されていたポスティングデータに新たなポスティングデータを追加することにより、当該登録キーのポスティングデータ数が前記しきい値を超える場合は、前記ポスティング記憶領域決定部は、当該登録キーのポスティングデータを全て、前記ポスティング格納部に移動して記憶させることを特徴とする請求項２に記載の文書検索装置。
【請求項４】
前記ポスティング記憶領域決定部は、前記インデックス保持部に記憶された全登録キーに対して所定の割合をなす前記登録キーのポスティングデータが、前記ツリー構造の最下層のノードを構成する記憶領域に記憶されるように、前記しきい値を調整することを特徴とする請求項３に記載の文書検索装置。
【請求項５】
前記ポスティング格納部は、複数の前記登録キーのそれぞれに与えた可変長の記憶領域が混在する共有記憶領域と、各登録キーが専有する所定単位の記憶領域を有する専有記憶領域と、各登録キーに対し構築され、前記文書の識別情報と前記ポスティングデータとを関連付けたツリー構造を構成する記憶領域を有するツリー記憶領域と、の少なくともいずれかを含み、
前記ポスティング記憶領域決定部は、前記ポスティング格納部に格納する前記ポスティングデータの記憶先を、前記登録キーごとのポスティングデータの数に応じて、前記共有記憶領域、前記専有記憶領域、前記ツリー記憶領域のいずれかに決定することを特徴とする請求項３に記載の文書検索装置。
【請求項６】
文書から所定数の文字列を登録キーとして抽出するステップと、
前記登録キーが抽出された文書の識別情報と当該文書における抽出箇所とを含むデータセットを１単位とするポスティングデータを前記登録キーごとに生成するステップと、
前記ポスティングデータを前記登録キーごとに記憶装置に記憶させるステップと、
検索クエリから所定数の文字列を検索キーとして抽出するステップと、
前記記憶装置を参照して前記検索キーに対する前記ポスティングデータを取得することにより前記検索クエリを含む文書の検索を行うステップと、を含み、
前記記憶装置における前記ポスティングデータの記憶領域を、前記登録キーごとのポスティングデータ数に応じて異ならせることを特徴とする文書検索方法。
【請求項７】
前記登録キーと前記ポスティングデータの前記記憶装置における格納領域とを関連付けたツリー構造を前記記憶装置に記憶させるステップをさらに含み、
前記ポスティングデータを前記記憶装置に記憶させるステップは、前記ポスティングデータの少なくとも一部を、前記ツリー構造の最下層のノードを構成する記憶領域の少なくとも一部に記憶させることを特徴とする請求項６に記載の文書検索方法。
【請求項８】
前記登録キーごとの前記ポスティングデータ数の最新値に応じて、少なくとも一部の前記登録キーの前記ポスティングデータを、別の記憶領域へ移動させるステップをさらに含むことを特徴とする請求項６に記載の文書検索方法。
【請求項９】
文書から所定数の文字列を登録キーとして全て抽出する機能と、
前記登録キーが抽出された文書の識別情報と当該文書における抽出箇所とを１単位とするポスティングデータを前記登録キーごとに生成する機能と、
前記ポスティングデータを前記登録キーごとに記憶装置に記憶させる機能と、
検索クエリから所定数の文字列を検索キーとして抽出する機能と、
前記記憶装置を参照して前記検索キーに対する前記ポスティングデータを取得することにより前記検索クエリを含む文書の検索を行う機能と、
をコンピュータに実現させるコンピュータプログラムであって、
前記記憶装置における前記ポスティングデータの記憶領域を、前記登録キーごとのポスティングデータ数に応じて異ならせることを特徴とするコンピュータプログラム。
【請求項１】
文書から所定数の文字列を登録キーとして抽出するキー抽出部と、
前記登録キーが抽出された文書の識別情報と当該文書における抽出箇所とを含むデータセットを１単位とするポスティングデータを前記登録キーごとに記憶したポスティング格納部と、前記ポスティング格納部における前記ポスティングデータの格納領域と、対応する登録キーとを関連付けたツリー構造を構成する記憶領域を有するキー格納部と、を含むインデックス保持部と、
検索クエリから所定数の文字列を検索キーとして抽出し、前記インデックス保持部を参照して前記検索キーに対する前記ポスティングデータを取得することにより前記検索クエリを含む文書の検索を行う検索部と、
を備え、
前記キー格納部における前記ツリー構造の最下層のノードを構成する記憶領域の少なくとも一部に、前記ポスティングデータの少なくとも一部が記憶され、前記検索部は少なくとも一部の検索キーについて、前記キー格納部のみを参照して前記ポスティングデータを取得することを特徴とする文書検索装置。
【請求項２】
前記キー格納部における前記ツリー構造の最下層のノードを構成する記憶領域に記憶されるポスティングデータは、前記ポスティングデータの数が与えられたしきい値以下である前記登録キーのポスティングデータであることを特徴とする請求項１に記載の文書検索装置。
【請求項３】
前記キー抽出部が新たな文書から前記登録キーを抽出した際、当該登録キーごとに前記ポスティングデータを生成するポスティング生成部と、
前記ポスティング生成部が生成した前記ポスティングデータの記憶先を、前記登録キーごとに、前記ツリー構造の最下層のノードを構成する記憶領域および前記ポスティング格納部のいずれかに決定するポスティング記憶領域決定部と、
をさらに備え、
それまで前記ツリー構造の最下層のノードを構成する記憶領域に記憶されていたポスティングデータに新たなポスティングデータを追加することにより、当該登録キーのポスティングデータ数が前記しきい値を超える場合は、前記ポスティング記憶領域決定部は、当該登録キーのポスティングデータを全て、前記ポスティング格納部に移動して記憶させることを特徴とする請求項２に記載の文書検索装置。
【請求項４】
前記ポスティング記憶領域決定部は、前記インデックス保持部に記憶された全登録キーに対して所定の割合をなす前記登録キーのポスティングデータが、前記ツリー構造の最下層のノードを構成する記憶領域に記憶されるように、前記しきい値を調整することを特徴とする請求項３に記載の文書検索装置。
【請求項５】
前記ポスティング格納部は、複数の前記登録キーのそれぞれに与えた可変長の記憶領域が混在する共有記憶領域と、各登録キーが専有する所定単位の記憶領域を有する専有記憶領域と、各登録キーに対し構築され、前記文書の識別情報と前記ポスティングデータとを関連付けたツリー構造を構成する記憶領域を有するツリー記憶領域と、の少なくともいずれかを含み、
前記ポスティング記憶領域決定部は、前記ポスティング格納部に格納する前記ポスティングデータの記憶先を、前記登録キーごとのポスティングデータの数に応じて、前記共有記憶領域、前記専有記憶領域、前記ツリー記憶領域のいずれかに決定することを特徴とする請求項３に記載の文書検索装置。
【請求項６】
文書から所定数の文字列を登録キーとして抽出するステップと、
前記登録キーが抽出された文書の識別情報と当該文書における抽出箇所とを含むデータセットを１単位とするポスティングデータを前記登録キーごとに生成するステップと、
前記ポスティングデータを前記登録キーごとに記憶装置に記憶させるステップと、
検索クエリから所定数の文字列を検索キーとして抽出するステップと、
前記記憶装置を参照して前記検索キーに対する前記ポスティングデータを取得することにより前記検索クエリを含む文書の検索を行うステップと、を含み、
前記記憶装置における前記ポスティングデータの記憶領域を、前記登録キーごとのポスティングデータ数に応じて異ならせることを特徴とする文書検索方法。
【請求項７】
前記登録キーと前記ポスティングデータの前記記憶装置における格納領域とを関連付けたツリー構造を前記記憶装置に記憶させるステップをさらに含み、
前記ポスティングデータを前記記憶装置に記憶させるステップは、前記ポスティングデータの少なくとも一部を、前記ツリー構造の最下層のノードを構成する記憶領域の少なくとも一部に記憶させることを特徴とする請求項６に記載の文書検索方法。
【請求項８】
前記登録キーごとの前記ポスティングデータ数の最新値に応じて、少なくとも一部の前記登録キーの前記ポスティングデータを、別の記憶領域へ移動させるステップをさらに含むことを特徴とする請求項６に記載の文書検索方法。
【請求項９】
文書から所定数の文字列を登録キーとして全て抽出する機能と、
前記登録キーが抽出された文書の識別情報と当該文書における抽出箇所とを１単位とするポスティングデータを前記登録キーごとに生成する機能と、
前記ポスティングデータを前記登録キーごとに記憶装置に記憶させる機能と、
検索クエリから所定数の文字列を検索キーとして抽出する機能と、
前記記憶装置を参照して前記検索キーに対する前記ポスティングデータを取得することにより前記検索クエリを含む文書の検索を行う機能と、
をコンピュータに実現させるコンピュータプログラムであって、
前記記憶装置における前記ポスティングデータの記憶領域を、前記登録キーごとのポスティングデータ数に応じて異ならせることを特徴とするコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００８−８３７６９（Ｐ２００８−８３７６９Ａ）
【公開日】平成２０年４月１０日（２００８．４．１０）
【国際特許分類】
【出願番号】特願２００６−２６０１０７（Ｐ２００６−２６０１０７）
【出願日】平成１８年９月２６日（２００６．９．２６）
【出願人】（３９００２４３５０）株式会社ジャストシステム (123)
【Ｆターム（参考）】
【公開日】平成２０年４月１０日（２００８．４．１０）
【国際特許分類】
【出願日】平成１８年９月２６日（２００６．９．２６）
【出願人】（３９００２４３５０）株式会社ジャストシステム (123)
【Ｆターム（参考）】
[ Back to top ]