JP2008026963A - 検索処理装置及びプログラム - Google Patents

Abstract

【課題】検索によく利用される語句の索引を自動的に作成できるようにする。
【解決手段】部分一致型検索部５５は、与えられた検索式が文字列を指定する文字列関数を含む場合、当該文字列関数で指定される文字列を語句とする語句索引（目的の語句索引）が存在するかを判定する。目的の語句索引が存在しない場合、部分一致型検索部５５は、索引部４２２に格納されているＮ−グラム索引を利用して、上記文字列の位置情報を取得すると共に当該文字列を語句とする語句索引を生成し、当該生成された語句索引を上記取得された位置情報と対応付けて辞書テーブル１１０に格納する。目的の語句索引が存在する場合、部分一致型検索部５５は、当該目的の語句索引を利用して上記文字列の位置情報を取得する。文書検索部５６は、上記文字列を含む構造化文書を、上記取得された位置情報に基づいて文書ＤＢ４２から検索する。
【選択図】 図２

Description

本発明は、複数の構造化文書が格納された文書データベースから索引を利用して検索条件に合致するデータを検索するのに好適な検索処理装置及びプログラムに関する。

従来から、複数の構造化文書が格納された文書データベースから検索条件に合致するデータを検索するのに索引を利用する検索処理装置が開発されている。このような検索処理装置のデータベースにテキストデータを含む文書を登録する場合、登録対象となるデータに索引付けをするのが一般的である。このような索引付けの手法としてＮ−グラム（N-gram）手法が知られている。Ｎ−グラム手法とは、例えば特許文献１に背景技術として記載されているように、文書に含まれる全ての文字をある固定の長さＮの連続する文字列（Ｎ−グラム）として扱い、索引登録と検索を行う手法である。

Ｎ−グラム手法における索引登録（Ｎ−グラム索引登録）は、次のように行われる。まず、データベースに登録される文書の文頭から機械的に１文字ずつずらしながら、長さＮの文字列（Ｎ−グラム）が順に切り出される。この長さＮの文字列（Ｎ−グラム）を便宜的に「語彙」と呼ぶ。但し、一般に良く知られている語彙と異なり、Ｎ−グラム手法で切り出される「語彙」には、意味を持たない「語彙」も存在する。１文字ずつずらして長さＮの文字列を切り出すことにより、文書に含まれる全ての部分文字列を網羅して取り出すことができる。このようにして切り出される語彙の全てが索引登録の対象となる。次に、データベース内での文書の位置及び当該文書中での各語彙の出現位置を含む位置情報が、その語彙に対応付けて登録される。長さＮには、言語や文字の種類によって適切な値が選ばれる。検索の際は、例えば検索条件として与えられた検索語句（文字列）が語彙に分割される。この語彙毎に索引（Ｎ−グラム索引）が検索される。これにより、語彙に一致する索引に対応付けて登録されている位置情報（文書位置−語彙出現位置）を得ることができる。
特開２００５−２３４９３０（段落０００２）

上述したようにＮ−グラム手法を適用する検索処理装置においては、索引登録及び検索のアルゴリズムが単純であるため、データベースに登録される文書に含まれている語句を抜けがなく完全に検索できるという利点がある。その一方、Ｎ−グラム手法を適用する検索処理装置は、辞書を利用した単語索引（語句索引）を持つ検索処理装置に比べて、語彙単位の索引の取り出し負荷が増えるために、検索処理に時間かかかるという問題がある。このような問題は、ＸＭＬ（Extensible Markup Language）形式の文書（ＸＭＬ文書）のような構造化文書（つまり階層型データ）が登録されたデータベースを持つ検索処理装置においても同様である。

本発明は上記事情を考慮してなされたものでその目的は、検索によく利用される語句の索引を自動的に生成することにより検索処理を高速化できる検索処理装置及び及びプログラムを提供することにある。

本発明の１つの観点によれば、複数の構造化文書が格納された文書データベースから、与えられた検索式の示す検索条件に合致する構造化文書を検索する検索処理装置が提供される。この検索処理装置は、前記文書データベースに格納されている構造化文書の各々をＮ−グラムの部分文字列に分割することによって生成されるＮ−グラム索引であって、当該部分文字列の位置を示す位置情報と対応付けられたＮ−グラム索引を格納するＮ−グラム索引格納手段と、語句の位置を示す位置情報と対応付けられた語句索引を格納する語句索引格納手段と、前記検索式が文字列を指定する文字列関数を含む場合、当該文字列関数で指定される文字列を語句とする語句索引が前記語句索引格納手段に存在するかを判定する判定手段と、前記文字列関数で指定される文字列を語句とする語句索引が存在しない場合、前記Ｎ−グラム索引を利用して当該文字列の位置情報を取得する第１の位置取得手段と、前記文字列関数で指定される文字列を語句とする語句索引が存在しない場合、当該文字列を語句とする語句索引を生成し、当該生成された語句索引を前記第１の位置取得手段によって取得された位置情報と対応付けて前記語句索引格納手段に格納する語句索引生成手段と、前記文字列関数で指定される文字列を語句とする語句索引が存在する場合、当該語句索引を利用して当該文字列の位置情報を取得する第２の位置取得手段と、
前記検索式の示す検索条件に合致する、前記文字列関数で指定される文字列を含む構造化文書を、前記第１または第２の位置取得手段によって取得された位置情報に基づいて前記文書データベースから検索する文書検索手段とを具備する。

本発明によれば、検索によく利用される語句の索引が自動的に生成されるため、検索式が文字列を指定する文字列関数を含み、且つ当該文字列を語句とする語句索引が存在する場合には、当該語句索引を利用することによって検索処理を高速化できる。

以下、本発明の実施の形態につき図面を参照して説明する。
図１は本発明の一実施形態に係る検索処理装置を含むクライアント−サーバシステムのハードウェア構成を示すブロック図である。クライアント−サーバシステムは、主として、データベースサーバ（データベースサーバコンピュータ）１０と、複数のクライアント端末とから構成される。複数のクライアント端末はクライアント端末２０を含む。クライアント端末２０上では、データベースサーバ１０を利用するクライアントソフトウェアが動作する。クライアントソフトウェアは例えばブラウザである。クライアント端末２０を含む複数のクライアント端末は、ローカルエリアネットワーク（ＬＡＮ）のようなネットワーク３０を介してデータベースサーバ１０と接続されている。なお、図１にはクライアント端末２０以外のクライアント端末は省略されている。

データベースサーバ１０は、主メモリのようなメモリ１１を含む。データベースサーバ１０は、ハードディスクドライブのような外部記憶装置４０と接続されている。この外部記憶装置４０は、データベースサーバ１０による検索処理に用いられる検索処理プログラム４１を格納する。データベースサーバ１０及び外部記憶装置４０は検索処理装置５０を構成する。

図２は検索処理装置５０の主として機能構成を示すブロック図である。検索処理装置５０は、インタフェース５１、解析部５２、構造検索部５３、完全一致型検索部５４、部分一致型検索部５５、文書検索部５６及び結果生成部５７を含む。本実施形態において、これらの各部５１乃至５７は、図１のデータベースサーバ１０が外部記憶装置４０に格納されている検索処理プログラム４１をメモリ１１に読み込んで実行することにより実現される。このプログラム４１は、コンピュータ読み取り可能な記憶媒体に予め格納して頒布可能である。また、このプログラム４１が、ネットワーク３０を介してデータベースサーバ１０にダウンロードされても構わない。

検索処理装置５０はまた、メモリ１１及び外部記憶装置４０を含む。外部記憶装置４０は、図１に示される検索処理プログラム４１に加えて、文書データベース（文書ＤＢ）４２及び辞書ファイル４３を格納する。文書ＤＢ４２は、文書部４２１及び索引部４２２を含む。文書部４２１は複数の構造化文書（構造化文書データ）、例えばＸＭＬ文書（ＸＭＬ文書データ）を格納する。索引部４２２は、文書ＤＢ４２に格納されている全てのＸＭＬ文書に含まれる語彙（Ｎ−グラム）毎に、その語彙の索引（Ｎ−グラム索引）を格納する。各Ｎ−グラム索引（Ｎ−グラム索引データ）は、対応する語彙に関する位置情報とリンクされている。この位置情報は、当該位置情報に対応する語彙を含む全てのＸＭＬ文書の文書ＤＢ４２内での位置（文書位置）と、当該ＸＭＬ文書において当該語彙が出現する全ての位置（語彙出現位置）とを表す。また索引部４２２は、文書ＤＢ４２に格納されている全てのＸＭＬ文書に含まれる文書構造毎に、当該文書構造の索引（構造索引）を格納する。各構造索引（構造索引データ）は、対応する構造を持つノードの位置を表す情報（位置情報）とリンクされている。

辞書ファイル４３は、文書ＤＢ４２に格納されているＸＭＬ文書に含まれる文字列であって、後述する文字列関数で指定された文字列が語句として登録されるエントリ（語句エントリ）を有する。各語句エントリは、語句（語句を構成する文字列）と当該語句に関する位置情報とを対応付けて格納する。この位置情報は、当該位置情報と対応付けられている語句の文書ＤＢ４２内での位置（文書位置−語句出現位置）を示す。各語句エントリに登録される語句は、上述のように文字列関数で指定された文字列であることから、索引部４２２に格納されるＮ−グラム索引の語彙とは異なる。

メモリ１１は辞書テーブル１１０を格納する。図３は辞書テーブル１１０のデータ構造例を示す。辞書テーブル１１０は、辞書ファイル４３と同様に、文書ＤＢ４２に格納されているＸＭＬ文書に含まれる文字列であって、文字列関数で指定された文字列が語句として登録されるエントリ（語句エントリ）を有する。

各語句エントリは、語句と参照回数と位置情報とを対応付けて格納する。参照回数は、当該参照回数と対応付けられている語句が参照される回数を示す。位置情報は、当該位置情報と対応付けられている語句の文書ＤＢ４２内での位置（文書位置−語句出現位置）を示す。各語句エントリは、索引部４２２に格納されているＮ−グラム索引に対して、語句索引であるといえる。なお、語句と対応付けられている参照回数及び位置情報は、当該語句から辿ることができるならば、当該語句が格納されている語句エントリに必ずしも格納されている必要はない。

辞書ファイル４３及び辞書テーブル１１０に語句として格納される文字列は、クライアント端末からの構造化文書問い合わせで実際に使用された検索式で指定される文字列に限られる。本実施形態では、このような検索式として、文字列取り出しを指定する文字列関数を含む検索式が該当する。

再び図２を参照すると、インタフェース５１は、クライアント端末２０等のクライアント端末からの構造化文書問い合わせ（構造化文書問い合わせ命令）を受け付ける。インタフェース５１はまた、この問い合わせに対する結果をクライアント端末に返す。本実施形態では、構造化文書問い合わせに、ＷＷＷ（World Wide Web）コンソーシアムで策定されているＸＱｕｅｒｙと呼ばれる問い合わせ言語が用いられる。ＸＱｕｅｒｙでは、ＸＭＬ文書の階層構造をパス指定で絞り、目的のデータを得るための演算式、関数などが用意されている。

解析部５２はインタフェース５１によって受け付けられた構造化文書問い合わせで使用される検索式（ＸＱｕｅｒｙの式）を解析し、その解析結果に応じて構造検索部５３、完全一致型検索部５４または部分一致型検索部５５を動作させる。構造検索部５３は、ＸＭＬ文書のノードの階層を上記構造化文書問い合わせで指定されたパスに従って辿り、そのパス以下のノードを特定する位置情報を索引部４２２内の構造索引から取得する。即ち構造検索部５３は、指定されたパスの構造に基づき、検索されるべきデータを絞り込むための構造検索を実行する。

完全一致型検索部５４は、特定のタグのテキスト要素や属性値が、上記構造化文書問い合わせで指定された値に一致するデータを取得するための完全一致型検索処理を実行する。この完全一致型検索処理では、予め定められた構造のデータ位置に対して比較処理が行われる。このため索引部４２２には、文字列一致比較のための文字列索引を設定する。

部分一致型検索部５５は、特定のタグのテキスト要素や属性値に上記構造化文書問い合わせで指定された値（指定文字列）を含むデータを取得するための部分一致型検索処理を実行する。図４は部分一致型検索部５５の機能構成を示す。部分一致型検索部５５は、判定部５５０、位置取得部（第１の位置取得部）５５１、位置取得部（第２の位置取得部）５５２、参照回数管理部５５３、エントリ生成部５５４及びロード部５５５を含む。

判定部５５０は、指定文字列に対応する語句エントリ（指定文字列のエントリ）が辞書テーブル１１０及び辞書ファイル４３のいずれに存在するかを判定する。判定部５５０は、この判定結果に応じて、位置取得部５５１及び５５２のいずれにより指定文字列の位置情報を取得させるかを決定する。判定部５５０は、指定文字列のエントリが辞書テーブル１１０及び辞書ファイル４３のいずれにも存在しない場合、位置取得部５５１を動作させる。判定部５５０はまた、指定文字列のエントリが辞書テーブル１１０または辞書ファイル４３に存在する場合、位置取得部５５２ａを動作させる。

位置取得部５５１は、指定文字列のエントリが辞書テーブル１１０及び辞書ファイル４３のいずれにも存在しない場合、当該指定文字列を含むデータの位置情報を索引部４２２（Ｎ−グラム索引）を用いて取得する。位置取得部５５２は、指定文字列のエントリが辞書テーブル１１０に存在する場合、当該指定文字列の位置情報を辞書テーブル１１０から取得する。位置取得部５５２はまた、指定文字列のエントリが辞書ファイル４３のみに存在する場合、当該指定文字列の位置情報を辞書ファイル４３から取得する。

参照回数管理部５５３は、辞書テーブル１１０内の語句エントリにおける参照回数を管理する。参照回数管理部５５３は、辞書テーブル１１０に基づいて指定文字列を含むデータの位置情報が取得される際に、その指定文字列に対応する語句エントリ（指定文字列のエントリ）中の参照回数を１インクリメントする。

エントリ生成部５５４は、辞書テーブル１１０内の指定文字列のエントリにおける参照回数が予め定められた閾値を超え、且つ辞書ファイル４３内に指定文字列のエントリが存在しない場合に、当該指定文字列のエントリを生成して当該辞書ファイル４３に追加する。ロード部５５５は、辞書ファイル４３に存在する指定文字列のエントリの情報を辞書テーブル１１０にロードする。

次に本実施形態の動作について、部分一致型検索部５５によって実行される処理を例に、図５Ａ及び図５Ｂのフローチャートを参照して説明する。
今、クライアント端末２０から検索処理装置５０に対し、構造化文書問い合わせがネットワーク３０を介して与えられたものとする。検索処理装置５０内のインタフェース５１は、このクライアント端末２０からの構造化文書問い合わせを受け付けると、当該問い合わせを解析部５２に渡す。解析部５２は、この問い合わせで使用される検索式を解析することにより、構造検索部５３、完全一致型検索部５４及び部分一致型検索部５５のいずれを動作させるかを決定する。ここで、上記検索式が、ＸＱｕｅｒｙの式であるものとする。ＸＱｕｅｒｙの式に含まれる関数として、ｓｔｒｉｎｇ（文字列）処理系と呼ばれる、文字列を扱う関数（つまり文字列関数）が知られている。文字列関数としては、指定の文字列から指定の条件に合致する部分文字列を取り出すためのｓｕｂｓｔｒｉｎｇ関数や、指定の文字列の連結を指定するｃｏｎｃａｔ関数などが定義されている。また、部分一致型検索に利用される文字列関数としては、ｃｏｎｔａｉｎｓ関数、ｓｔａｒｔ−ｗｉｔｈ関数、ｅｎｄ−ｗｉｔｈ関数などが定義されている。

本実施形態において、解析部５２によって解析された検索式が、部分一致型検索に利用される文字列関数、例えば
/Catalog/Book[contains(./Name/text(),”ルネッサンス”)]
のような、ｃｏｎｔａｉｎｓ関数「contains(./Name/text(),”ルネッサンス”)」を含むＸＱｅｒｙの式であるものとする。このｃｏｎｔａｉｎｓ関数を含むＸＱｅｒｙの式は、「/Catalog/Book」と一致する構造のノード（Ｂｏｏｋノード）のうち、その題目（Ｎａｍｅ）に「ルネッサンス」という文字列を含むノード（書籍）を検索することを指定する。

このように、部分一致型検索に利用される文字列関数（ｃｏｎｔａｉｎｓ関数）を含む検索式（ＸＱｅｒｙの式）の場合、解析部５２は、部分一致型検索処理が必要であるとして、構造検索部５３及び部分一致型検索部５５を動作させる。なお、完全一致型検索処理が必要な場合、解析部５２は構造検索部５３及び完全一致型検索部５４を動作させる。

構造検索部５３は、解析部５２によって解析された検索式（ＸＱｅｒｙの式）の指定するパス「/Catalog/Book」に従って、そのパス以下のノードを特定する位置情報を索引部４２２内の構造索引から取得する。構造検索部５３によって取得された位置情報は文書検索部５６に渡される。

一方、部分一致型検索部５５では、判定部５５０が、解析部５２によって解析された検索式（ＸＱｅｒｙの式）に、文字列取り出しを指定する文字列関数が含まれているか否かを判定する（ステップＳ１）。このステップＳ１での判定がＹＥＳの場合、判定部５５０はステップＳ２を実行する。このステップＳ２において、判定部５５０は、上記検索式（ＸＱｅｒｙの式）に含まれている文字列関数によって指定される文字列（指定文字列）「ルネッサンス」で辞書テーブル１１０を参照する。そして判定部５５０は、この指定文字列に一致する語句が格納されているエントリ（指定文字列のエントリ）が辞書テーブル１１０に存在するか否かを判定する。

もし、指定文字列のエントリが辞書テーブル１１０に存在する場合、判定部５５０は辞書テーブル１１０内の当該エントリの位置を位置取得部５５２及び参照回数管理部５５３に通知する。すると参照回数管理部５５３は、辞書テーブル１１０内の指定文字列のエントリに設定されている参照回数を１インクリメントする（ステップＳ３）。一方、エントリ生成部５５４は、辞書テーブル１１０内の指定文字列のエントリから、当該エントリに設定されている位置情報、つまり指定文字列の位置情報を取得する（ステップＳ４）。

明らかなように、上記ステップＳ４の処理、即ち辞書テーブル１１０を利用して指定文字列の位置情報を取得する処理は、当該指定文字列を構成する全ての語彙（Ｎ−グラム）毎に索引部４２２のＮ−グラム索引を検索して、当該語彙毎の位置情報を取得することにより、指定文字列の位置情報を取得する処理（後述するステップＳ１２乃至Ｓ１４の処理）に比べて高速に実行できる。なお、ステップＳ４がステップＳ３より先に実行されても構わない。

参照回数管理部５５３は、指定文字列のエントリに設定されている参照回数をインクリメントすると、そのインクリメント後の参照回数を閾値と比較することにより、当該参照回数が閾値（基準の回数）を超えているか否かを判定する（ステップＳ５）。もし、インクリメント後の参照回数が閾値を超えていないならば、部分一致型検索部５５での処理は終了となる。このとき、位置取得部５５２によって取得された位置情報が、部分一致型検索部５５から文書検索部５６に渡される。

文書検索部５６は、構造検索部５３及び部分一致型検索部５５の各々から渡された位置情報をマージし、一致する位置情報の指定する文書を、インタフェース５１によって受け付けられた構造化文書問い合わせで使用される検索式に合致する文書として、文書ＤＢ４２から検索する。

一方、インクリメント後の参照回数が閾値を超えているならば、判定部５５０は今度は、指定文字列のエントリが辞書ファイル４３に存在するか否かを判定する（ステップＳ６）。もし、指定文字列のエントリが辞書ファイル４３に存在するならば、部分一致型検索部５５での処理は終了となる。

これに対し、指定文字列のエントリが辞書ファイル４３に存在しないならば、判定部５５０はエントリ生成部５５４を起動する。するとエントリ生成部５５４は、辞書テーブル１１０内の指定文字列のエントリの参照頻度が高いものとして、当該指定文字列のエントリに基づき、辞書ファイル４３内に指定文字列のエントリを追加する（ステップＳ７）。ここでは、辞書テーブル１１０内の指定文字列のエントリの情報のうち、参照回数を除く情報が設定されたエントリが生成されて、辞書ファイル４３に追加される。

上記ステップＳ７により、検索処理装置５０が電源オフされてメモリ１１に格納されている辞書テーブル１１０のエントリ情報が消失した場合に対処できる。即ち、後述するステップＳ１０から明らかなように、検索処理装置５０の再起動後に辞書ファイル４３内のエントリの情報を辞書テーブル１１０にロードすることにより、当該エントリの情報（つまり参照頻度が高いエントリ情報）を再利用できる。ステップＳ７の処理が実行されると部分一致型検索部５５での処理は終了となる。

次に、上記ステップＳ２において、指定文字列のエントリが辞書テーブル１１０に存在しないと判定された場合について説明する。このようにステップＳ２での判定がＮＯの場合、判定部５５０は指定文字列のエントリが辞書ファイル４３に存在するか否かを判定する（ステップＳ８）。

もし、指定文字列のエントリが辞書ファイル４３に存在する場合、判定部５５０は辞書ファイル４３内の当該エントリの位置を位置取得部５５２及びロード部５５５に通知する。すると位置取得部５５２は、辞書ファイル４３内の指定文字列のエントリから、当該エントリに設定されている位置情報、つまり指定文字列の位置情報を取得する（ステップＳ９）。明らかなように、この辞書ファイル４３を利用して指定文字列の位置情報を取得する処理は、辞書テーブル１１０を利用して指定文字列の位置情報を取得する処理と同様に、索引部４２２のＮ−グラム索引を検索して指定文字列の位置情報を取得する処理に比べて高速に実行できる。

一方、ロード部５５５は、辞書ファイル４３内の指定文字列のエントリから指定文字列の位置情報が取得されると、辞書テーブル１１０に１つエントリを追加して、当該エントリに上記指定文字列のエントリの情報をロードする（ステップＳ１０）。すると参照回数管理部５５３は、ロード部５５５によって追加された辞書テーブル１１０内のエントリ（指定文字列のエントリ）に、値が“１”の参照回数を追加設定する（ステップＳ１１）。なお、ステップＳ９において、辞書ファイル４３内の指定文字列のエントリから指定文字列の位置情報を取得することは、ロード部５５５によって追加された辞書テーブル１１０内のエントリから指定文字列の位置情報を取得することと等価である。

次に、上記ステップＳ８において、指定文字列のエントリが辞書ファイル４３に存在しないと判定された場合について説明する。この場合、判定部５５０はその旨を指定文字列と共に位置取得部５５１に通知する。すると位置取得部５５１は、指定文字列をＮ−グラム（語彙）に分割する（ステップＳ１２）。位置取得部５５１は、分割されたＮ−グラム（語彙）毎に、索引部４２２内のＮ−グラム索引を検索することにより、Ｎ−グラム（語彙）毎に位置情報を取得する（ステップＳ１３）。位置取得部５５１は、Ｎ−グラム（語彙）毎の位置情報をマージして、指定文字列を構成するＮ−グラム（語彙）の各々の相対位置に対応する語彙出現位置を示す位置情報の集合を検出することにより、当該指定文字列の位置情報を取得する（ステップＳ１４）。

ステップＳ１４において位置取得部５５１によって取得された指定文字列の位置情報は、指定文字列と共にエントリ生成部５５４に渡される。エントリ生成部５５４は、この指定文字列、当該指定文字列の位置情報及び値が１（初期値）の参照回数が設定されたエントリを辞書テーブル１１０に追加する（ステップＳ１５）。このステップＳ１５の処理が実行されると部分一致型検索部５５での処理は終了となる。

上述したように、本実施形態において自動生成されて辞書ファイル４３に登録され、当該辞書ファイル４３から辞書テーブル１１０にロードされる語句エントリの情報は、ユーザからの構造化文書問い合わせに基づく検索で頻繁に利用される語句の索引（語句索引）を構成している。このため、構造化文書問い合わせに基づく検索で語句索引を利用する確率を高めることができる。ここで、辞書ファイル４３を予め用意することも考えられる。しかし、そのためには検索で頻繁に利用される語句を予測しなければならない。もし、この予測が外れると、構造化文書問い合わせに基づく検索で語句索引を利用する確率が低くなる。本実施形態では、ユーザからの構造化文書問い合わせに基づく検索で利用される語句の索引のみが自動生成されるため、このようなおそれは少ない。つまり、本発明によれば、使われない語句のために語句索引が生成されることはなく、語句索引の生成コスト（辞書生成コスト）を軽減できる。

上記実施形態では、説明の簡略化のために、辞書テーブル１１０のサイズ、或いは辞書テーブル１１０のエントリの数の上限について考慮されていない。もし、辞書テーブル１１０のサイズまたはエントリ数の上限が予め定められている場合には、当該辞書テーブル１１０を例えばＬＲＵ（Least Recently Used）法により管理すればよい。即ち、ステップＳ１５において辞書テーブル１１０にエントリを追加することにより辞書テーブル１１０のサイズまたはエントリ数が上限を超える場合には、辞書テーブル１１０のエントリのうち、その時点で最も以前に参照されたエントリを削除すれば良い。この管理手法は、辞書ファイル４３内の語句エントリにも適用可能である。また、上記閾値、辞書テーブル１１０のサイズまたはエントリ数の上限を、クライアント端末２０から指定可能としても良い。

［変形例］
次に上記実施形態の変形例について説明する。
上記実施形態においては、辞書テーブル１１０を利用することにより、索引部４２２のＮ−グラム索引を利用する場合に比べて、指定文字列の位置情報を高速で取得できる。但し、この効果は、指定文字列を構成する文字数ｎが少ない場合には低くなる。そこで本変形例では、辞書テーブル１１０のエントリから辞書ファイル４３に保存すべきエントリを決定する条件に、参照回数Ｎrだけでなく、文字数が加えられる。更に具体的に述べるならば、文字数ｎによって決まる重みｗnであって、当該文字数ｎが少ないほど小さな値となる重みｗnを参照回数Ｎrに乗じて得られる値Ｎr×ｗn（つまり重み付けされた参照回数Ｎr×ｗn）が、上記ステップＳ５において参照回数Ｎrに代えて用いられる。

なお、本発明は、上記実施形態またはその変形例そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態またはその変形例に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態またはその変形例に示される全構成要素から幾つかの構成要素を削除してもよい。

本発明の一実施形態に係る検索処理装置を含むクライアント−サーバシステムのハードウェア構成を示すブロック図。 図１中の検索処理装置５０の主として機能構成を示すブロック図。 図２中の辞書テーブル１１０のデータ構造例を示す図。 図２中の部分一致型検索部５５の機能構成を示す図。 同実施形態において部分一致型検索部５５によって実行される処理の手順の一部を示すフローチャート。 同実施形態において部分一致型検索部５５によって実行される処理の手順の残りを示すフローチャート。

符号の説明

１０…データベースサーバ、１１…メモリ、２０…クライアント端末、３０…ネットワーク、４０…外部記憶装置、４１…検索処理プログラム、４２…文書データベース（文書ＤＢ）、４３…辞書ファイル（第２の語句索引格納手段）、５１…インタフェース、５２…解析部、５３…構造検索部、５４…完全一致型検索部、５５…部分一致型検索部、５６…文書検索部、５７…結果生成部、１１０…辞書テーブル（第１の語句索引格納手段）、４２１…文書部、４２２…索引部（Ｎ−グラム索引格納手段）、５５０…判定部、５５１…位置取得部（第１の位置取得手段）、５５２…位置取得部（第２の位置取得手段）、５５３…参照回数管理部、５５４…エントリ生成部（語句索引生成手段）、５５５…ロード部。

Claims (6)

1. 複数の構造化文書が格納された文書データベースから、与えられた検索式の示す検索条件に合致する構造化文書を検索する検索処理装置において、
   前記文書データベースに格納されている構造化文書の各々をＮ−グラムの部分文字列に分割することによって生成されるＮ−グラム索引であって、当該部分文字列の位置を示す位置情報と対応付けられたＮ−グラム索引を格納するＮ−グラム索引格納手段と、
   語句の位置を示す位置情報と対応付けられた語句索引を格納する語句索引格納手段と、
   前記検索式が文字列を指定する文字列関数を含む場合、当該文字列関数で指定される文字列を語句とする語句索引が前記語句索引格納手段に存在するかを判定する判定手段と、
   前記文字列関数で指定される文字列を語句とする語句索引が存在しない場合、前記Ｎ−グラム索引を利用して当該文字列の位置情報を取得する第１の位置取得手段と、
   前記文字列関数で指定される文字列を語句とする語句索引が存在しない場合、当該文字列を語句とする語句索引を生成し、当該生成された語句索引を前記第１の位置取得手段によって取得された位置情報と対応付けて前記語句索引格納手段に格納する語句索引生成手段と、
   前記文字列関数で指定される文字列を語句とする語句索引が存在する場合、当該語句索引を利用して当該文字列の位置情報を取得する第２の位置取得手段と、
   前記検索式の示す検索条件に合致する、前記文字列関数で指定される文字列を含む構造化文書を、前記第１または第２の位置取得手段によって取得された位置情報に基づいて前記文書データベースから検索する文書検索手段と
   を具備することを特徴とする文書検索処理装置。
2. 前記語句索引格納手段は、前記語句索引生成手段によって生成された語句索引を当該語句索引が参照される回数を表す参照回数と対応付けて格納する揮発性の第１の語句索引格納手段と、前記第１の語句索引格納手段に格納されている語句索引の中から選択された語句索引を再利用可能なように格納する不揮発性の第２の語句索引格納手段とを含み、
   前記判定手段は、前記文字列関数で指定される文字列を語句とする語句索引が前記第１及び第２の語句索引格納手段のいずれに存在するかを判定し、
   前記語句索引生成手段は、前記文字列関数で指定される文字列を語句とする語句索引が前記第１の語句索引格納手段のみに存在し、且つ当該語句索引と対応付けられている参照回数が予め定められた閾値を超えている場合に当該語句索引を前記第２の語句索引格納手段に追加し、
   前記文字列関数で指定される文字列を語句とする語句索引が前記第１の語句索引格納手段に存在する場合、当該語句索引に対応付けられている前記参照回数をインクリメントする参照回数管理手段と、
   前記文字列関数で指定される文字列を語句とする語句索引が前記第１の語句索引格納手段に存在しないが、前記第２の語句索引格納手段には存在する場合、当該語句索引を前記第２の語句索引格納手段から前記第１の語句索引格納手段にロードして、当該ロードされた語句索引に値が初期値の参照回数を対応付けるロード手段とを更に具備する
   ことを特徴とする請求項１記載の検査処理装置。
3. 前記語句索引生成手段は、前記文字列関数で指定される文字列を語句とする語句索引と対応付けられている参照回数を、当該文字列の文字数で決まる当該文字数が多いほど値が大きくなる重みで重み付けし、その重み付けされた参照回数を前記閾値と比較することを特徴とする請求項２記載の検査処理装置。
4. 複数の構造化文書が格納された文書データベースから、与えられた検索式の示す検索条件に合致する構造化文書をコンピュータが検索するのに用いられるプログラムであって、 前記コンピュータに、
   前記検索式が文字列を指定する文字列関数を含むかを判定するステップと、
   前記検索式が文字列を指定する文字列関数を含む場合、当該文字列を語句とする語句索引が語句索引格納手段に存在するかを判定するステップと、
   前記文字列関数で指定される文字列を語句とする語句索引が存在しない場合、前記文書データベースに格納されている構造化文書の各々をＮ−グラムの部分文字列であるＮ−グラム文字列に分割することによって生成されてＮ−グラム索引格納手段に格納されているＮ−グラム索引であって、当該Ｎ−グラム文字列の位置を示す位置情報と対応付けられたＮ−グラム索引のうち、前記文字列関数で指定される文字列を構成するＮ−グラム文字列に対応するＮ−グラム索引を利用して当該文字列の位置情報を取得するステップと、
   前記文字列関数で指定される文字列を語句とする語句索引が存在しない場合、当該文字列を語句とする語句索引を生成して、当該生成された語句索引を前記取得された位置情報と対応付けて前記語句索引格納手段に格納するステップと、
   前記文字列関数で指定される文字列を語句とする語句索引が存在する場合、当該語句索引を利用して当該文字列の位置情報を取得するステップと、
   前記検索式の示す検索条件に合致する、前記文字列関数で指定される文字列を含む構造化文書を、前記語句索引または前記Ｎ−グラム索引を利用して取得された位置情報に基づいて前記文書データベースから検索するステップと
   を実行させるためのプログラム。
5. 前記語句索引格納手段は、前記語句索引生成手段によって生成された語句索引を当該語句索引が参照される回数を表す参照回数と対応付けて格納する揮発性の第１の語句索引格納手段と、前記第１の語句索引格納手段に格納されている語句索引の中から選択された語句索引を再利用可能なように格納する不揮発性の第２の語句索引格納手段とを含み、
   前記判定するステップは、前記文字列関数で指定される文字列を語句とする語句索引が前記第１の語句索引格納手段に存在するかを判定する第１の判定ステップと、存在しない場合に当該語句索引が前記第２の語句索引格納手段に存在するかを判定する第２の判定ステップとを含み、
   前記コンピュータに実行させるための、
   前記文字列関数で指定される文字列を語句とする語句索引が前記第１の語句索引格納手段に存在すると判定された場合、当該語句索引に対応付けられている前記参照回数をインクリメントするステップと、
   前記インクリメント後の参照回数を予め定められた閾値と比較するステップと、
   前記参照回数が前記閾値を超えている場合、前記文字列関数で指定される文字列を語句とする語句索引が前記第２の語句索引格納手段に存在するかを判定する第３の判定ステップと、
   前記文字列関数で指定される文字列を語句とする語句索引が前記第２の語句索引格納手段に存在しないと前記第３のステップで判定された場合、前記第１の語句索引格納手段に存在すると前記第１のステップで判定された当該文字列を語句とする語句索引を前記第２の語句索引格納手段に追加するステップと、
   前記文字列関数で指定される文字列を語句とする語句索引が前記第２の語句索引格納手段に存在すると前記第２のステップで判定された場合、当該語句索引を前記第２の語句索引格納手段から前記第１の語句索引格納手段にロードして、当該ロードされた語句索引に値が初期値の参照回数を対応付けるステップとを更に含む
   ことを特徴とする請求項４記載のプログラム。
6. 前記閾値と比較される参照回数として、前記インクリメント後の参照回数と対応付けられている前記語句索引の語句の文字数で決まる当該文字数が多いほど値が大きくなる重みで重み付けされた当該インクリメント後の参照回数が用いられることを特徴とする請求項５記載のプログラム。

Images