(57)【特許請求の範囲】
【請求項１】
少なくとも１つ以上の検索語が論理演算子によって結合されて形成された検索式が入力され、前記検索式に対応する文書を検索する文書検索装置において、
前記検索式に含まれている各検索語を複数の文字列に分割した後、論理積演算子により結合し、部分検索式を生成する部分検索式生成手段と、
前記部分検索式のそれぞれについて、処理順序を最適化する処理順序最適化手段と、
前記処理順序最適化手段によって最適化された検索式に従って、検索対象となる文書が記録されている記録装置から該当する文書を検索する検索手段と、
前記検索手段がある文字列まで処理した検索候補数と、所定の個数だけ前の文字列まで処理した検索候補数との差分が所定の値より小さい場合には、前記検索手段を制御して次の部分検索式の検索処理に移行させる検索制御手段と、
を有することを特徴とする文書検索装置。
【請求項２】
前記部分検索式生成手段は、各検索語の先頭から１文字ずつずらしながら連続する２文字を順次切り出して得られた文字列を、論理積演算子によって結合することにより、前記部分検索式を生成することを特徴とする請求項１記載の文書検索装置。
【請求項３】
前記記録装置は、文書の先頭から１文字ずつずらしながら連続する２文字を順次切り出して得られた文字列とその文書を特定するための情報とを関連付けて記録していることを特徴とする請求項１記載の文書検索装置。
【請求項４】
少なくとも１つ以上の検索語が論理演算子によって結合されて形成された検索式が入力され、前記検索式に対応する文書をコンピュータに検索させるためのプログラムを記録したコンピュータ読み込み可能な記録媒体において、
前記検索式に含まれている各検索語を複数の文字列に分割した後、論理積演算子により結合し、部分検索式を生成する部分検索式生成手段、
前記部分検索式のそれぞれについて、処理順序を最適化する処理順序最適化手段、
前記処理順序最適化手段によって最適化された検索式に従って、検索対象となる文書が記録されている記録装置から該当する文書を検索する検索手段、
前記検索手段が所定の部分検索式の所定の文字列を検索対象として得られた検索候補の数と、それよりも所定の個数だけ前の文字列を検索対象として得られた検索候補の数の差分が所定の値よりも小さい場合には、前記検索手段を制御して次の部分検索式の検索処理に移行させる検索制御手段、
としてコンピュータを機能させることを特徴とするプログラムを記録したコンピュータ読み込み可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、文書検索装置および記録媒体に関し、特に、少なくとも１つ以上の検索語が論理演算子によって結合されて形成された検索式が入力され、その検索式に対応する文書を検索する文書検索装置および記録媒体に関する。
【０００２】
【従来の技術】
複数の検索語が論理積演算子によって結合されて生成された検索式を用いて、データベース等に格納されている文書等のデータを検索する場合、検索語の順序を適宜変更することにより処理時間を短縮することが可能となる。
【０００３】
即ち、３つ以上の検索語が論理積演算子によって結合されて生成された検索式に基づいて検索を実行する場合、検索候補の少ない検索語から順に実行するのが最も効率が良い。
【０００４】
ここで、3 つの検索語をＷ１，Ｗ２，Ｗ３で表わし、論理積演算子を「＆」で表わし、また、Ｗ１，Ｗ２，Ｗ３を含む文書の論理積を、Ｗ１＆Ｗ２＆Ｗ３と表わすことにする。各検索語を含む文書の数が、Ｗ３，Ｗ２，Ｗ１の順に少ない場合、まず、Ｗ３とＷ２に関する候補を検索してＷ３＆Ｗ２を実行し、その結果得られた集合をＲ１として記憶し、次に、Ｗ１に関する候補を検索してＲ１＆Ｗ１を実行すると最も効率的に処理できる。
【０００５】
以上の方法をデータベースにおける検索処理に適用する方法が、特開平３−５２０６８号公報に示されている。この方法では、先ず、第１の論理条件式内の各条件を満足するレコードの数を得る。続いて、レコードの個数の少ない順番に論理条件式内の条件の順序を並べ替えた第２の論理条件式を作成し、第２の論理条件式にしたがって検索を実行することによって処理速度を向上させている。
【０００６】
【発明が解決しようとする課題】
ところで、検索対象である文書（テキスト情報）の先頭の文字から１文字ずつずらしながら連続する２文字を切り出し、その全ての２文字列を検索キーとして記録装置に記録している文書検索装置に対して、「富士スラックス株式会社」という検索条件を入力した場合を考える。即ち、「富士スラックス株式会社」という語を含む文書を検索する場合について考える。
【０００７】
その場合、先ず、入力された検索語「富士スラックス株式会社」が、「富士＆士ス＆スラ＆ラッ＆ック＆クス＆ス株＆株式＆式会＆会社」という検索式に展開される。そして、先頭の語から検索処理が実行されるとともに、得られた検索候補の間で論理積演算が実行される。
【０００８】
このような方法では、「富士、士ス、... 、会社」の全ての２文字列を、離れた位置に含む文書（ノイズ）も検索の結果として与えられるが、「富士スラックス株式会社」という語を含む文書が漏れることはない。
【０００９】
しかしながら、このような検索方法では、長い検索語が入力されると、論理積演算が多く発生し、処理が遅くなるという問題があった。
そこで、前述したように、検索式に含まれている２文字列の順序を検索候補の数に応じて並べ替えて、論理積演算の順序を最適化することにより処理速度を向上させることも考えられるが、検索語の語長が長い場合には充分な速度の向上を達成できないという問題点もあった。
【００１０】
本発明は以上のような点に鑑みてなされたものであり、２文字列を利用して検索する場合であって、特に長い検索語を処理する場合に、処理時間を短縮することができる文書検索装置および記録媒体を提供することを目的とする。
【００１１】
【課題を解決するための手段】
本発明に係わる文書検索装置では、上記課題を解決するために、少なくとも１つ以上の検索語が論理演算子によって結合されて形成された検索式が入力され、その検索式に対応する文書を検索する文書検索装置において、前記検索式に含まれている各検索語を複数の文字列に分割した後、論理積演算子により結合し、部分検索式を生成する部分検索式生成手段と、前記部分検索式のそれぞれについて、処理順序を最適化する処理順序最適化手段と、前記処理順序最適化手段によって最適化された検索式に従って、検索対象となる文書が記録されている記録装置から該当する文書を検索する検索手段と、前記検索手段がある文字列まで処理した検索候補数と、所定の個数だけ前の文字列まで処理した検索候補数との差分に応じて前記検索手段を制御して次の部分検索式の検索処理に移行させる検索制御手段と、を有することを特徴とする文書検索装置が提供される。
【００１２】
ここで、部分検索式生成手段は、検索式に含まれている各検索語を複数の文字列に分割した後、論理積演算子により結合し、部分検索式を生成する。処理順序最適化手段は、部分検索式のそれぞれについて、処理順序を最適化する。検索手段は、処理順序最適化手段によって最適化された検索式に従って、検索対象となる文書が記録されている記録装置から該当する文書を検索する。検索制御手段は、検索手段がある文字列まで処理した検索候補数と、所定の個数だけ前の文字列まで処理した検索候補数との差分が所定の値より小さい場合には、検索手段を制御して、次の部分検索式の検索処理に移行させる。
【００１３】
【発明の実施の形態】
図1 は本発明の実施の形態の構成例を示す図である。
同図において、部分検索式生成手段１は、入力された検索式を構成している各検索語を、最初の語から１文字ずつずらしながら２文字ずつ切り出すことによって部分検索式を生成する。ここで、部分検索式とは、検索式を構成する検索語を２文字列と論理積演算子との結合によって再構成したものを示している。
【００１４】
処理順序最適化手段２は、部分検索式を構成している２文字列の処理順序を決定する（最適化する）。検索手段３は、処理順序が決定された検索式に応じて、記録装置５に記録されている文書を検索し、検索候補を取得する。
【００１５】
検索制御手段４は、検索手段３が各部分検索式を対象として検索を実行している場合に、検索の候補の数が変動しなくなったことを検知し、次の部分検索式に移行するように検索手段３を制御する。
【００１６】
記録装置５は、少なくとも、登録した文書のテキスト情報の先頭の文字から１文字ずつずらしながら連続する２文字を順次切り出した２文字列と登録した文書を特定する文書番号とを対応付けて記録している。なお、文書番号と文書の内容とを対応付けて記録させてもよい。また、２文字列とその２文字列を含む文書数とを対応付けて記録させてもよい。
【００１７】
次に、この文書検索装置で文書を検索する際の処理の一例について説明する。図２は図１の文書検索装置において実行される処理の一例を説明するフローチャートである。このフローチャートが開始されると、以下のような処理が実行されることになる。なお、以下の例では、検索式として「富士スラックス株式会社＆フルカラー複写機」が入力された場合、即ち、「富士スラックス株式会社」という語と「フルカラー複写機」という語の両方を含む文書を得るための検索式が入力された場合を例に挙げて説明する。
［Ｓ１］検索式が入力されると、部分検索式生成手段１は、検索式に含まれている検索語のそれぞれを２文字列に分割し、論理積演算子によって結合する。
【００１８】
いま、前述のように、検索式として「富士スラックス株式会社＆フルカラー複写機」が入力されたとすると、この検索式を構成している検索語「富士スラックス株式会社」と「フルカラー複写機」からは、部分検索式「富士＆士ス＆スラ＆ラッ＆ック＆クス＆ス株＆株式＆式会＆会社」と「フル＆ルカ＆カラ＆ラー＆ー複＆複写＆写機」とが生成される。なお、検索式は複数の検索語と任意の論理演算子とからなる論理式を対象とすることが可能である。また、このようにして生成された検索式を以下では展開後検索式と呼び、更に、展開後検索式の検索語に対応する部分、例えば、( 富士＆士ス＆・・・＆会社) を部分検索式と呼ぶことにする。
［Ｓ２］処理順序最適化手段２は、部分検索式生成手段１から展開後検索式を受け取り、各部分検索式に含まれている論理積演算を効率的に実行できるように処理の順序を最適化する。なお、処理の順序を最適化する方法としては、例えば、記録装置５に対して、検索の対象となる文書から切り出した２文字列とその２文字列を含む文書数とを対応付けて記録しておき、部分検索式に含まれる２文字列が含まれる文書数を適宜読み出して、その値が小さい順に２文字列を並べ替える方法が考えられる。
【００１９】
また、２文字列の文字の並びパターンによって、処理の順序を設定することも可能である。図３は、２文字列のパターンとその重み値とを対応付けたテーブルの一例である。この例では、ヒット件数が少ない（全ての文書中に出現する頻度が低い）文字パターンほど、大きな重み値となるように設定してある。例えば、パターン番号「２」では「カタカナ」に「漢字」が続くパターンはその出現頻度が低いため重み値が「＋２」に設定してあり、一方、パターン番号「５」では、「漢字」に「ひらがな」が続くパターンはその出現頻度が高いことから重み値が「−２」に設定してある。なお、図３のパターン番号「１」に示した「偶数番目の文字」は、検索語の先頭の文字か、または、「かな」、「漢字」、などの文字種が変わった場合に変わった先頭の文字を１文字目とした場合に「偶数番目」に配置される文字を示している。
【００２０】
このようなテーブルを用いて処理順序を最適化する場合には、先ず、図３のテーブルに示したパターンと２文字列とを比較し、該当するパターンが存在する場合にはその重み値を順次加算し、最終的な値を処理の優先度として優先度の値が大きい順に２文字列の順序を最適化する。なお、優先度の値が等しい場合は、どちらを先に配置しても構わない。
【００２１】
例えば、「富士」は図３に示したどのパターンにも該当しないので、優先度は「０」である。「士ス」はパターン番号「
４」に該当するので、優先度は「＋２」ある。「ラッ」はパターン番号１とパターン番号「９」に該当するので、優先度は「０」（＝＋１−１）である。
【００２２】
図４は、部分検索式「富士スラックス株式会社」に含まれている２文字列の優先度を計算した結果を表わした図である。また、図５は、部分検索式「フルカラー複写機」に含まれている２文字列の優先度を計算した結果を表わした図である。
【００２３】
このようにして得られた優先度に基づいて、２つの部分検索式を最適化すると、次のようになる。ただし、検索処理は部分検索式の左側から実行されるものとする。
【００２４】
( 士ス＆ス株＆クス＆式会＆富士＆スラ＆ラッ＆株式＆会社＆ック)
( ー複＆ルカ＆ラー＆写機＆フル＆カラ＆複写)
ここで、処理順序を設定した部分検索式を特に「順序設定済み部分検索式」と呼び、また、部分検索式の順序を設定した展開後検索式（２文字列の論理積の結合として表された検索式）を特に「順序設定済み展開後検索式」と呼ぶことにする。
［Ｓ３］処理順序最適化手段２は、未処理の部分検索式があるか否かを判定する。その結果、未処理の部分検索式があると判定した場合にはステップＳ２に戻り、また、未処理の部分検索式がないと判定した場合にはステップＳ４に進む。なお、ステップＳ４以降では、順序設定済みの展開後検索式に従って、検索処理が順次実行される。
［Ｓ４］検索制御手段４は、検索未処理の箇所があるか否かを判定する。その結果、検索未処理の箇所があると判定した場合にはステップＳ６に進み、また、検索未処理の箇所がないと判定した場合にはステップＳ５に進む。
［Ｓ５］検索手段３は、検索結果を出力する。
［Ｓ６］検索制御手段４は、検索未処理の箇所が部分検索式であるか否かを判定する。その結果、検索未処理の箇所が部分検索式であると判定した場合には、ステップＳ８に進み、また、未処理の箇所が部分検索式ではないと判定した場合にはステップＳ７に進む。
［Ｓ７］検索手段３は、記録装置５に記録されている文書から該当する文書を検索する。
［Ｓ８］検索手段３は、順序設定済み部分検索式から次の文字列を抽出し、該当する文書を記録装置５から検索する。
［Ｓ９］検索制御手段４は、順序設定済みの部分検索式において、未処理の文字列が存在しているか否かを判定する。その結果、未処理の部分が存在すると判定した場合には、ステップＳ１０に進み、また、未処理の部分が存在しないと判定した場合にはステップＳ８に戻る。
［Ｓ１０］検索制御手段４は、残りの文字列に対する検索処理を実行しても結果が同じになる可能性が高いか否か（終了可能か否か）を判定する。その結果、終了可能であると判定した場合には、残りの文字列に対する検索処理を省略し、その時点での結果を、その順序設定済み部分検索式における結果とし、ステップＳ４に戻る。また、終了可能ではないと判定した場合にはステップＳ８に戻る。
【００２５】
なお、検索制御手段４における終了判定の方法としては、例えば、論理積演算を３回以上実行した場合において、２回前の論理積演算を実行した時のヒット件数と、現在のヒット件数とを比較して、ヒット件数が同じであれば、残りの論理積演算を実行しても結果は同じになる可能性が高いと判定する方法などが考えられる。
【００２６】
例えば、順序設定済み部分検索式「士ス＆ス株＆クス＆式会＆富士＆スラ＆ラッ＆株式＆会社＆ック」において、「士ス＆ス株＆クス＆式会」まで処理した時点でのヒット件数と、「士ス＆ス株＆クス＆式会＆富士＆スラ」まで処理した時点でのヒット件数が同じであったとすると、残りの「ラッ＆株式＆会社＆ック」の処理を省略し、その分の処理時間を短縮する。
【００２７】
また、もうひとつの順序設定済み部分検索式「ー複＆ルカ＆ラー＆写機＆フル＆カラ＆複写」において、「ー複＆ルカ＆ラー＆写機＆フル」の時点で処理を終了したとすると、検索式全体としては、（士ス＆ス株＆クス＆式会＆富士＆スラ）＆( ー複＆ルカ＆ラー＆写機＆フル) だけを実行することになる。
【００２８】
このようにして、全ての順序設定済み部分検索式に対する処理が終了すると、前述のステップＳ４においてＮＯと判定され、ステップＳ５において検索処理結果（例えば、該当した文書番号のリスト）が出力されることになる。
【００２９】
以上に示したように、本実施の形態では検索制御手段４がステップＳ１０において終了可能であると判定すれば、順序設定済み部分検索式内の処理を終了し、次の順序設定済み部分検索式の処理に移行するので、検索処理を高速化することが可能となる。
【００３０】
なお、以上の実施の形態においては、２回前の検索結果と現在の検索結果とを比較してヒット件数が等しい場合には処理を終了するようにしたが、例えば、これらの差分値が所定の閾値よりも小さい場合には処理を終了するようにしてもよい。
【００３１】
また、以上の実施の形態においては、検索語を２文字ずつの文字列に分割するようにしたが、例えば、３文字ずつの文字列に分割してもよいことは言うまでもない。
【００３２】
更に、高速検索モードと通常検索モードを選択できるようにしておき、高速検索モードが選択された場合は本実施例の手順で処理し、通常検索モードが選択された場合には順序設定済み部分検索式内の処理を全て実行するようにすることもできる。
【００３３】
最後に、上記の処理機能は、コンピュータによって実現することができる。その場合、文書検索装置が有すべき機能の処理内容は、コンピュータで読み取り可能な記録媒体に記録されたプログラムに記述されており、このプログラムをコンピュータで実行することにより、上記処理がコンピュータで実現される。
【００３４】
コンピュータで読み取り可能な記録媒体としては、磁気記録装置や半導体メモリ等がある。市場を流通させる場合には、ＣＤ−ＲＯＭ(Compact Disk Read Only Memory) やフロッピーディスク等の可搬型記録媒体にプログラムを格納して流通させたり、ネットワークを介して接続されたコンピュータの記憶装置に格納しておき、ネットワークを通じて他のコンピュータに転送することもできる。コンピュータで実行する際には、コンピュータ内のハードディスク装置等にプログラムを格納しておき、メインメモリにロードして実行する。
【００３５】
【発明の効果】
以上説明したように本発明の文書検索装置は、検索語を２文字列と論理積演算子とからなる部分検索式に展開し、この部分検索式に従って処理を実行する途中の段階で、ヒット件数の変化に応じて処理を終了可能か否かを判定できる構成としたので、長い検索語が入力された場合には、検索処理に要する処理時間を短縮することができる。
【図面の簡単な説明】
【図１】本発明の実施の形態の構成例を示す図である。
【図２】図１の実施の形態において実行される処理の一例を説明するフローチャートである。
【図３】２文字列パターンとその重み値とを対応付けたテーブルの一例である。
【図４】２文字列の優先度を計算した結果を表した図である。
【図５】２文字列パターンとその重みの値を対応付けて示した他の図である。
【符号の説明】
１  部分検索式生成手段
２  処理順序最適化手段
３  検索手段
４  検索制御手段
５  記憶装置
【図１】
0003849274.tif 000002
【図２】
0003849274.tif 000003
【図３】
0003849274.tif 000004
【図４】
0003849274.tif 000005
【図５】
0003849274.tif 000006