JPH1196170A - データベース作成方法および情報検索方法および情報検索装置および記録媒体 - Google Patents

Abstract

(57)【要約】 【課題】テキスト中のキーワードの出現頻度に応じてシ
グネチャを用いた情報検索を行う際のフォルスドロップ
の発生を抑制でき、記憶領域のオーバーヘッドを抑え、
高速に前方一致検索が行えるデータベース作成方法およ
び情報検索方法および情報検索装置を提供する。 【解決手段】入力された情報中のキーワードから部分文
字列を切り出し、この切り出された部分文字列のキーワ
ード中での出現頻度に基づき前記部分文字列に割り当て
られた予め定められた長さのビット列を用いて前記入力
された情報に対する第１のシグネチャを生成し、前記入
力された情報を前記生成された第１のシグネチャと対応
付けて記憶してデータベースを作成する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、データベースの効
率的な検索を行うためのシグネチャ（ビット列）を用い
た情報検索方法およびそれを用いた情報検索装置に関す
る。

【０００２】

【従来の技術】例えば、テキスト情報を処理する情報検
索システムは、任意の文字列を検索対象とする全文検索
方式と、キーワードによる検索を行う方式の２種類に大
別できる。

【０００３】キーワードによる検索を行う方式では、事
前にキーワードに関する補助データベースを作成してお
くことで、検索速度の向上を行っている。作成される補
助データベースとしては、各キーワードごとにそれが出
現するテキスト中での位置を記録する転置ファイルを作
成する方式と、テキストのレコードごとにそこに出現す
るキーワードの情報を簡潔に表現したシグネチャファイ
ルを用いる方式がある。

【０００４】転置ファイルを利用する方式では、高速な
検索が可能となる反面、転置ファイルのサイズが膨大に
なり記憶領域の効率が低下するという問題がある。シグ
ネチャファイルを用いる方式では、テキスト１レコード
中の情報をシグネチャとしてコンパクトに表現している
ため、記憶領域に関しては有利であるが、検索速度に関
する問題が生じる。しかしその単純な方式は、並列コン
ピュータ上での並列実行容易性など多くの可能性を秘め
ており、多くの研究開発が継続されている。

【０００５】ここで、シグネチャファイル法について図
１を参照して説明する。まず、以降の説明で用いる用語
について説明する。レコードとはワード（単語）の集ま
りである。単語のうち、検索対象とされるものを特にキ
ーワードとよぶ。シグネチャファイル法では、各キーワ
ードにシグネチャと呼ぶビット列を対応させる。ビット
列への対応をｂｃｗ関数とよぶ（ｂｉｎａｒｙ ｃｏｄ
ｅ ｗｏｒｄ）。図１では、レコード中に出現する３つ
のキーワード「ｋｅｙｗｏｒｄ１」、「ｋｅｙｗｏｒｄ
２」、「ｋｅｙｗｏｒｄ３」に対して、長さ１０のビッ
ト列が対応している。ここで、ビット列のいずれも３ヶ
所のビットが「１」で、残りのビットは「０」となって
いることに注意する。

【０００６】ビット列の長さをビット長（この場合「１
０」）、このビット列のうち「１」となるビットの個数
（この場合「３」）を重みと呼ぶ。レコードに対するシ
グネチャとは、レコード中に出現するキーワードのシグ
ネチャ全部のビット毎の論理和を取ったものである。

【０００７】この方式での検索方法を図２を参照して説
明する。すなわち、検索語（この場合「ｋｅｙｗｏｒｄ
３」）に対して、先ほどと同じｂｃｗ関数を用いてビッ
ト列を作成する。そして、このビット列中で「１」にな
っているビット位置が全て「１」となっているシグネチ
ャを持つレコードを検索結果として出力する。つまり、
検索語のビット列とレコードのビット列との論理積が、
検索語のビット列に一致する場合に、そのテキストを検
索結果として出力する。このように、ビット列の論理操
作で検索が行えるため、シグネチャファイルによる検索
は十分な高速性を持っている。

【０００８】ところが、この方式ではフォルスドロップ
と呼ばれる問題が生じる。すなわち、図１のように「ｋ
ｅｙｗｏｒｄ１」と「ｋｅｙｗｏｒｄ２」のビット毎の
論理和は「ｋｅｙｗｏｒｄ３」のビット列を完全に含ん
でいるため、「ｋｅｙｗｏｒｄ１」と「ｋｅｙｗｏｒｄ
２」を含むレコードは「ｋｅｙｗｏｒｄ３」を含まない
にもかかわらず、「ｋｅｙｗｏｒｄ３」に対する検索出
力となってしまう。

【０００９】フォルスドロップの除去のためには、全文
文字検索アルゴリズムを適用しなければならず、シグネ
チャファイル法の検索速度を低下させてしまう原因とな
る。上述したようなフォルスドロップをいかに減少させ
るかが、シグネチャファイルを用いる検索システムの実
現の際には重要な問題となる。これは、上で説明したｂ
ｃｗ関数を最適に設計するという問題に他ならない。こ
のときの設計パラメタとしては、（１）ビット長、
（２）重み、（３）与えられたビット長、重みのもとで
ビット列を対応させる具体的方式、の３種類となる。次
に、これらの決定方法について従来技術を説明する。

【００１０】参考文献１（Ｒｏｂｅｒｔｓ、Ｃ．Ｓ．、
Ｐａｒｔｉａｌ−ｍａｔｃｈ ｒｅｔｒｉｅｖａｌ ｖ
ｉａ ｔｈｅ ｍｅｔｈｏｄ ｏｆ ｓｕｐｅｒｉｍｐ
ｏｓｅｄ ｃｏｄｅｓ、 Ｐｒｏｃ． ＩＥＥＥ ６
７、 Ｄｅｃ．、 １６２４− １６４２、 １９７
９．）では、次のような前提条件のもとで、ｂｃｗ関数
の数学的解析を行い、ビット長と重みに関する設計指針
を与えた。

【００１１】（前提条件１）各レコードに出現する相異
なるキーワード数は一定である。 （前提条件２）いずれのキーワードも等確率で出現す
る。 この２つの前提条件のもと、ビット長ｂ、重みｗ、キー
ワード数ｒ、のレコードがフォルスドロップする確率は
次式で与えられる。

【００１２】

【数１】 この式は、ｗがｍよりも十分に小さい場合には次式で近
似できる。

【００１３】

【数２】

【００１４】この式の値が最小になる場合、すなわちフ
ォルスドロップが最小になるのは、ｗ／ｂ＝０．５のと
きであり、レコードのシグネチャ中でちょうど１／２の
ビットが「１」になるようにセットされた場合である。
ｗ／ｂはシグネチャ中で「１」となるビットの割合を示
すものであるから、以降ではビット率とよぶことにす
る。

【００１５】ここで、シグネチャの符号長ｂは記憶領域
サイズと直接関係することに注意する。従って、システ
ムに許されるディスク使用量とフォルスドロップ除去の
ための検索速度低下とを上の式から推測しながら、最適
なｂ、ｗの値を採用することが従来の方法であった。

【００１６】上記の解析においては、各レコードに出現
するキーワード数が一定であるということと（前提条件
１）、キーワードの出現確率が均等であること（前提条
件２）という２つの前提条件を仮定していた。ところ
が、一般のテキストデータベースにおいては、レコード
に現れるキーワード数は大きくばらついている。レコー
ドのフォーマットを強制的に規定することでレコード数
を一定とするのでは、実用上の運用に困難をきたすこと
になる。さらに、良く知られているように、自然言語
（日本語、英語など）においては、出現する単語の分析
は極めて偏ったものになっている。結局、上記の単純な
解析結果からは、実用的なテキストデータベースに対す
る最適な設計値を得ることができないということにな
る。

【００１７】そこで、前提条件１、前提条件２を実用的
なレベルにまで緩和しようとする試みがなされている。
まず前提条件１についてであるが、レコードをキーワー
ド数が一定となるようにした論理的なブロックへと分割
するという方式が広く採用されている。

【００１８】前提条件２に関しては、参考文献２（Ｃｈ
ｕｎ−Ｗｕ Ｒｏｇｅｒ Ｌｅｎｇ、ａｎｄ Ｄｉｋ
Ｌｕｎ Ｌｅｅ：Ｏｐｔｉｍａｌ Ｗｅｉｇｈｔ Ａｓ
ｓｉｇｎｍｅｎｔ ｆｏｒ Ｓｉｇｎａｔｕｒｅ Ｇｅ
ｎｅｒａｔｉｏｎ、ＡＣＭＴｒａｎｓａｃｔｉｏｎｓ
ｏｎ Ｄａｔａｂａｓｅ Ｓｙｓｔｅｍｓ、Ｖｏｌ．１
７、Ｎｏ．２、１９９２．）に、レコードを単純にキー
ワード数一定となるように分割するのではなく、分割さ
れた各々のレコードに対するシグネチャにおいて「１」
にセットされるビット数が同一になるようなレコード分
割を行うような方式が提案されている。この方法は、キ
ーワード偏在という問題への対処療法的解決であり、本
質的な解決とは異なる。例えば、高頻度のキーワードに
より「１」にセットされるビットと、中頻度以下のキー
ワードで「１」にセットされるビットが同一である場
合、そうした中頻度以下のキーワードによる検索の際の
フォルスドロップが大きくなってしまう。一般的なテキ
スト情報データベースにおいては、高頻度や低頻度のキ
ーワードによる検索よりもむしろ、中頻度のキーワード
による検索が重要となる場合が多いため、この従来技術
は十分なものではなかった。

【００１９】次に、前方一致検索に関しては説明する。
前方一致検索とは、例えば「ｃｏｍｐ」なる検索式を与
えることで、「ｃｏｍｐｕｔｅｒ」、「ｃｏｍｐｕｔｅ
ｒｓ」、「ｃｏｍｐｕｔａｔｉｏｎ」などといったキー
ワードの前方部分が検索式「ｃｏｍｐ」と一致するキー
ワードによる検索を行うものであり、情報検索システム
の重要な機能となっている。ところが、単純なシグネチ
ャ法により前方一致検索を行う場合、「ｃｏｍｐ」を前
方の部分文字列とするキーワードを辞書などを利用して
生成し、生成された各々に対する検索を行う必要があ
り、検索速度や辞書保存のための記憶領域オーバヘッド
増大という問題がある。そこで従来技術による改良方式
が提案されている。

【００２０】参考文献３（Ｃ．Ｆａｌｏｕｔｓｏｓ：Ａ
ｃｃｅｓｓ Ｍｅｔｈｏｄｓ ｆｏｒ Ｔｅｘｔ、ＡＣ
Ｍ Ｃｏｍｐｕｔｉｎｇ Ｓｕｒｖｅｙｓ、Ｖｏｌ．１
７、Ｎｏ．１、１９８５．）に記載されている方式で
は、辞書を用いることなく（すなわち記憶領域のオーバ
ーヘッドなしに）前方一致検索を行う方法が提案されて
いる。しかし、単純に参考文献３の方式を適用したので
は、フォルスドロップの増大を招くことになり、現実的
なものではなくなってしまう。前方一致検索を可能にす
る方式は、フォルスドロップを減少させる方法と共に用
いなければ現実上の意味がない。

【００２１】特願平第７−１２１０６５号に記載の索引
型式作成装置においては、シグネチャを用いた情報検索
システムにおいて、キーワードの概念を拡張する発明が
提供されている。すなわち、テキスト中に頻繁に現れる
連続した文字列を統計データに基いて同定し、それをキ
ーワードに代る検索単位として採用しようとする方法で
ある。この方法は、頻繁に現れる文字列がキーワードと
なるため、そうした頻繁に現れる文字列に対する検索能
力を向上させる意味を持っている。しかし同発明におい
ては、頻繁に現れる文字列を見出す方式に主眼が置か
れ、フォルスドロップ数を減少させるための方式は従来
の発明を利用している。従って、頻繁に現れる文字列の
生起頻度に偏りが生じた場合には、フォルスドロップの
増大を招き実用上の利点が失われる可能性がある。

【００２２】特願平第３−１９０６１９号に記載の情報
検索システムにおいては、キーワードに対する索引の構
成をシステムの利用状況に応じて変更するというもので
ある。これは、より頻繁に利用されるキーワードに対す
る検索時間を徐々に高速化しようとするものであり、ニ
ューラルネットワークを利用した利用頻度情報の収集部
分と、キーワード格納装置内部でキーワードの再配置を
行う部分から構成されている。この発明では、システム
が十分に使い込まれないと高速化が達成できないという
問題がある。さらに、複数の利用者が同一のデータベー
スを利用する場合、利用者により異なるキーワードの傾
向を持つ場合への対応が論じられていないなどの問題が
ある。

【００２３】特願平第６−３２４４１号に記載のシグネ
チャの用いた文書検索装置においては、シグネチャを格
納する方式を工夫することで記憶領域サイズを小さくす
る方法が提供されている。この発明はフォルスドロップ
数の減少やデータの内容に合わせたシグネチャ作成方法
調整とは関係しないので、本発明とは独立のものであ
る。

【００２４】その他に、従来技術によるシグネチャファ
イル法の改良方式は多数提案されている。例えば、参考
文献４（Ｄｉｋ Ｌｕｎ Ｌｅｅ、Ｙｏｕｎｇ Ｍａｎ
Ｋｉｍ、ａｎｄ Ｇａｕｒａｖ Ｐａｔｅｌ：Ｅｆｆ
ｉｃｉｅｎｔ Ｓｉｇｎａｔｕｒｅ Ｆｉｌｅ Ｍｅｔ
ｈｏｄｓ ｆｏｒ Ｔｅｘｔ Ｒｅｔｒｉｅｖａｌ、Ｉ
ＥＥＥ Ｔｒａｎｓ．ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎ
ｄ Ｄａｔａ Ｅｎｇ．，Ｖｏｌ．７、Ｎｏ．３、１９
９５．）には、シグネチャを用いるいくつかの方式につ
いて、その方式と数学的な解析が記載されている。例え
ば、レコードに対するシグネチャを用いるだけではな
く、複数のシグネチャに対するシグネチャをも考えるこ
とで、検索を他段階に行う方式が提案されており、ディ
スク装置とのアクセスを減らして検索高速化を行うこと
が可能となる。しかし、フォルスドロップ数を減少させ
るための方法とは独立であり、本発明の装置と共に用い
ることが可能である。

【００２５】

【発明が解決しようとする課題】以上説明したように、
従来のシグネチャを用いた情報検索システムでは、レコ
ード中に現れるキーワード数、各キーワードの出現頻度
のばらつきに応じたフォルスドロップには充分な対策が
講じられていなかった。

【００２６】そこで、本発明は、テキスト中のキーワー
ドの出現頻度に応じてシグネチャを用いた情報検索を行
う際のフォルスドロップの発生を抑制できるとともに、
記憶領域のオーバーヘッドを抑え、高速に前方一致検索
が行えるデータベース作成方法および情報検索方法およ
びそれを用いた情報検索装置を提供することを目的とす
る。

【００２７】

【課題を解決するための手段】本発明のデータベース作
成方法（請求項１）は、入力された情報中のキーワード
から部分文字列を切り出し、この切り出された部分文字
列のキーワード中での出現頻度に基づき前記部分文字列
に割り当てられた予め定められた長さのビット列を用い
て前記入力された情報に対する第１のシグネチャを生成
し、前記入力された情報を前記生成された第１のシグネ
チャと対応付けて記憶してデータベースを作成すること
により、例えばテキスト中のキーワードの出現頻度に応
じて、シグネチャを用いた情報検索を行う際のフォルス
ドロップの発生を抑制できるとともに、記憶領域のオー
バーヘッドを抑え、高速に前方一致検索が行える。

【００２８】本発明の情報検索方法（請求項２）は、情
報とそれに対応する第１のシグネチャとが対応付けられ
て記憶されたデータベースの検索方法であって、入力さ
れた検索情報中のキーワードから部分文字列を切り出
し、この切り出された各部分文字列についてその部分文
字列のキーワード中での出現頻度に基づいて予め割り当
てられたビット列を用いて前記検索情報に対応する第２
のシグネチャを生成し、この生成された第２のシグネチ
ャと前記データベース内の第１のシグネチャとを照合す
ることにより、前記検索情報に関連する情報を前記デー
タベースから検索することにより、例えばテキスト中の
キーワードの出現頻度に応じて、シグネチャを用いた情
報検索を行う際のフォルスドロップの発生を抑制できる
とともに、記憶領域のオーバーヘッドを抑え、高速に前
方一致検索が行える。

【００２９】本発明の情報検索方法（請求項３）は、入
力された情報中のキーワードから部分文字列を切り出
し、この切り出された部分文字列のキーワード中での出
現頻度に基づき前記部分文字列に割り当てられた予め定
められた長さのビット列を用いて前記入力された情報に
対する第１のシグネチャを生成し、前記入力された情報
を前記生成された第１のシグネチャと対応付けて記憶し
てデータベースを作成し、情報検索の際には、入力され
た検索情報中のキーワードから部分文字列を切り出し、
この切り出された各部分文字列についてその部分文字列
のキーワード中での出現頻度に基づいて予め割り当てら
れたビット列を用いて前記検索情報に対応する第２のシ
グネチャを生成し、この生成された第２のシグネチャと
前記データベース内の第１のシグネチャとを照合するこ
とにより、前記検索情報に関連する情報を前記データベ
ースから検索することにより、例えばテキスト中のキー
ワードの出現頻度に応じて、シグネチャを用いた情報検
索を行う際のフォルスドロップの発生を抑制できるとと
もに、記憶領域のオーバーヘッドを抑え、高速に前方一
致検索が行える。

【００３０】本発明の情報検索装置（請求項４）は、入
力された情報中のキーワードから部分文字列を切り出す
切出手段と、この切り出し手段で切り出された部分文字
列の出現頻度に基づき前記部分文字列に予め定められた
長さのビット列を割り当てる割当手段と、前記部分文字
列に割り当てられたビット列を用いて前記入力された情
報に対する第１のシグネチャを生成する生成手段と、前
記入力された情報を前記生成手段で生成された第１のシ
グネチャと対応付けて記憶してデータベースを作成する
手段と、入力された検索情報中のキーワードから部分文
字列を切り出し、この切り出された各部分文字列につい
て前記生成手段で生成されたビット列を用いて、該検索
情報に対応する第２のシグネチャを生成し、この生成さ
れた第２のシグネチャと前記データベース内の第１のシ
グネチャとを照合することにより、前記検索情報に関連
する情報を前記データベースから検索する検索手段と、
を具備したことにより、例えばテキスト中のキーワード
の出現頻度に応じて、シグネチャを用いた情報検索を行
う際のフォルスドロップの発生を抑制できるとともに、
記憶領域のオーバーヘッドを抑え、高速に前方一致検索
が行える。

【００３１】

【発明の実施の形態】以下、本発明の実施形態について
図面を参照して説明する。図３は、本実施形態に係る情
報検索装置の構成例を示したものである。なお、図３に
おいて、実線は情報記憶時のデータの流れを示し、破線
は主に検索時のデータの流れを示している。

【００３２】まず、情報記憶時のデータの流れに沿っ
て、図３の各構成部について説明する。マスターデータ
ベース５は、個々のレコードの実データをその識別子と
ともに格納するためのものである。個々のレコードは、
テキスト形式の情報以外に図形情報や音声情報など計算
機で扱い得る様々な形式のデータを含んでいても良い。
マスターデータベース５の構造は、従来技術を用いて実
現される。本発明の情報検索装置に入力部１を介して入
力された情報をレコードとして蓄積する場合には、まず
このマスターデータベースにレコードの格納が行われ
る。

【００３３】図４に、本実施形態の説明で用いる入力部
１を介して入力された情報、すなわち、レコードの一具
体例を示する。マスターデータベース５へのレコード格
納と並行して、キーワード切り出し部３では、例えば図
４に示すレコードのテキスト情報から図５に示すように
キーワードを抽出する。

【００３４】さらに、部分文字列切り出し部４では、図
５に示したような各キーワードのそれぞれを図６に示す
ように例えば２文字づつの部分文字列に分割する。図７
は、部分文字列切り出し部４における部分文字列切出処
理の手順の一例を示したフローチャートである。部分文
字列切り出し部４では、例えば、符号重み（ビット列中
の「１」となるビットの数）ｗを「５」、切り出す部分
文字列の長さｋを「２」としている（ステップＳ１〜ス
テップＳ２）。キーワードの先頭（ｉ＝１）の文字から
順に２文字づつ、すなわち、１番目と２番目の文字、２
番目と３番目の文字、…５番目と６番目の文字というよ
うに、切り出す２文字の部分文字列の最初の文字の位置
がｉ＝５となるまで部分文字列を切り出していき（ステ
ップＳ３〜ステップＳ７）、部分文字列「ＸＸ」とその
部分文字列の先頭の文字のキーワード中の出現位置（最
初から何文字目か）ｉの組み＜ＸＸ、ｉ＞を出力してい
る（ステップＳ４）。

【００３５】例えば、キーワード「Ｏｂｊｅｃｔｓ」に
おいて、＜Ｏｂ、１＞は、部分文字列「Ｏｂ」が１番め
に出現することを、＜ｂｊ、２＞は部分文字列「ｂｊ」
が２番めに出現することを示している。

【００３６】このようにして切り出された部分文字列
は、シグネチャ作成部９に与えられる。部分文字切り出
し部４では、さらに、部分文字列とその出現位置の組合
わせに対して、それがレコード中に出現する頻度を部分
文字列の統計情報として統計情報データベース７に格納
するようになっている。

【００３７】統計情報データベース７に格納された部分
文字列の統計情報データは、シグネチャ作成用データべ
ース更新部１１で部分文字列のシグネチャを作成する際
に用いられる（後述）。

【００３８】シグネチャ作成部９は、キーワードから切
り出された部分文字列に基づきシグネチャ作成用データ
ベース６を参照して、キーワードのシグネチャおよびレ
コードのシグネチャを作成するものである。なお、ここ
では、例えば、部分文字列、キーワード、テキストのシ
グネチャを１０ビットのビット列とする。

【００３９】シグネチャ作成用データベース６は、各部
分文字列とその出現位置の組み合わせに対して、どのビ
ット位置を「１」にするか（すなわち、部分文字列とそ
の出現位置との組み合わせに対するシグネチャ）を定め
たテーブルを格納しているものである。

【００４０】ここで、図８を参照して、シグネチャ作成
部９でキーワードのシグネチャを作成する手順を説明す
る。シグネチャ作成用データベース６には、部分文字列
切り出し部４で切り出された部分文字列とその出現位置
との組＜ｘｘ、ｉ＞と、それに対応して予め定められた
１０ビットのうちの「１」にするビット位置（すなわ
ち、部分文字列に対するシグネチャ）が対になって記憶
されている。例えば、図８に示すように、キーワード
「Ｏｂｊｅｃｔｓ」において、１０ビットのビット列の
うち、＜Ｏｂ、１＞に対しては１０ビット目、＜ｂｊ、
２＞に対しては３ビット目、＜ｊｅ、３＞に対しては５
ビット目、＜ｅｃ、４＞に対しては７ビット目、＜ｃ
ｔ、５＞に対しては２ビット目が「１」となるようなシ
グネチャが割り当てられている。このように、キーワー
ドに対するシグネチャは、部分文字列とその出現位置と
に対し予め定められたシグネチャのビット毎の論理和を
とることで作成される。例えば、この場合、キーワード
「ｏｂｊｅｃｔ」のシグネチャは「０１１０１０１００
１」となる。

【００４１】レコードのシグネチャは、レコード中の全
てのキーワードに対するシグネチャのビット毎の論理和
を取って作成する。シグネチャ作成部９で作成されたレ
コードのシグネチャは、シグネチャ格納データベース８
に蓄積される。例えば、先にマスターデータベース５に
格納されたレコードに付された識別子と同一の識別子と
組にしてそのシグネチャを格納する。

【００４２】また、このときの格納方式としては、従来
技術（例えば参考文献４）を用いて、検索の高速化が可
能な方式とすることができる。なお、シグネチャ作成用
データベース６に格納されている部分文字列およびその
出現位置に対するシグネチャの割当方法は後述する。

【００４３】次に、部分文字列の切り出しとシグネチャ
作成とについてさらに詳しく説明する。本発明の目的の
１つは、テキスト中のキーワードの出現頻度が偏ってい
るテキストデータベースにおいて、シグネチャによる検
索のフォルスドロップを減少させることであった。従来
技術においては、キーワードから乱数を利用してシグネ
チャを作成しようとしていたのだが、キーワード偏在に
よる影響を大きく受けるものであった。キーワードその
ものに対するデータベースを作成してシグネチャ作成を
統計的にコントロールしようとすると、膨大なキーワー
ドを格納する必要が生じる。中規模の辞書においても、
例えば講談社英和辞典では約９万語、旺文社英和中辞典
では約１０万語の見出し語を持っているため、活用型や
技術専門用語を含めればキーワード単位でシグネチャ作
成をコントロールする方法は大きな記憶領域オーバーヘ
ッドを伴うことになり実用的ではない。また、検索時に
も膨大なキーワードを格納したデータベースをアクセス
することになるので、検索速度低下も問題となる。

【００４４】そこで、本発明では、キーワードから部分
文字を切り出し、その部分文字列に対するシグネチャを
作成するようになっている。部分文字列の可能な組み合
わせ数は、部分文字列の長さを短くとることで、その数
を自在に調整できるという事実に基づいている。例え
ば、文字種総数が「５０」であるとすれば、長さ「２」
の部分文字列総数は「２５０」にしか過ぎない。部分文
字列の長さを幾つにするかという問題は、記憶領域のサ
イズを見ながら決定すれば良い。また、部分文字列その
ものだけではなく、本実施形態のように部分文字列がキ
ーワード中の何番めに出現するのかというような部分文
字列の出現位置の情報との組み合わせに対しシグネチャ
を作成するようにしてもよい。

【００４５】本実施形態の場合には、長さ「２」の部分
文字列でその出現位置を考慮したものを採用している。
この場合、扱う文字種が「５０」であり、出現位置とし
ては本実施形態の場合にはキーワードの先頭から５番目
までの部分文字列しか扱わない。従って、５０・５０・
５＝１２５００種類の見出しを持つテーブルを用意すれ
ば十分である。従って、前方一致検索を行う際には記憶
領域のオーバーヘッドを小さく抑えることができるとい
う効果がある。

【００４６】なお、部分文字列に対するシグネチャのビ
ット長が長い程フォルスドロップの発生回数を抑えるこ
とができるが、逆に記憶領域が大きくなる。従って、シ
グネチャのビット長を決定する際には、これらを考慮し
て装置に最適な値を決定する必要がある。

【００４７】次に、シグネチャ作成用データべース更新
部１１について説明する。シグネチャ作成用データベー
ス更新部１１では、統計情報データベース７に格納され
た部分文字列とその出現位置の組合わせの出現頻度（す
なわち、部分文字列のキーワード中での出現頻度、ある
いは、部分文字列の出現位置に関する頻度）の統計情報
データを参照して、部分文字列とその出現位置の組合わ
せに対するシグネチャ（具体的には、例えば１０ビット
中のどのビット位置を「１」にするかを定めたもの）を
作成し、それを基に、シグネチャ作成用データベース
６、シグネチャ格納データベース８を更新するようにな
っている。

【００４８】部分文字列とその出現位置との組み合わせ
に対してビット位置を決める方法としては、各ビットが
「１」にセットされる確率が等しくなるようにするとい
う原則に従う。以下でその方法を説明する。

【００４９】部分文字列とその出現位置に対するレコー
ド中の出現頻度の統計情報を従来技術を用いて容易に収
集することができる。例えば、部分文字列と出現位置を
見出しとするテーブルを作成し、部分文字列切り出し部
４からの出力が得られるたびに、出現回数を「１」つづ
つカウントアップすれば良い。このようにして計数され
た出現回数を部分文字列およびその出現位置の組み合わ
せについての統計情報データとして統計情報データベー
ス７に格納する。この統計情報データベース７の内容を
参照することにより、任意の時点における部分文字列の
キーワード中での出現頻度を直ちに計算することができ
る。

【００５０】図９に示すフローチャートは、シグネチャ
作成用データベース更新部１１における部分文字列のシ
グネチャ作成処理の手順の一例を示したもので、これに
従えば、ほぼ等確率で１０ビット中の各ビットが「１」
となるように各部分文字列に対する１０ビット中のビッ
ト位置を決定することができる。

【００５１】図９のフローチャートにおいて、まず、１
０ビットのシグネチャの各ビット位置（ｉ＝１〜１０）
について「１」となる確率ｐ［ｉ］を全て「０」に初期
化する（ステップＳ１１〜ステップＳ１３）。そして、
統計情報データベース７から、最も出現確率ｘの高い部
分文字列を選び（ステップＳ１４）、その部分文字列に
対するシグネチャ１０ビット中の「１」にするビット位
置を、その時点で、１０ビットのシグネチャの各ビット
位置（ｉ＝１〜１０）について「１」となる確率ｐ
［ｉ］が最も低いビット位置とする（ステップＳ１５〜
ステップＳ１６）。確率ｐ［ｉ］の値が最も低いビット
位置が複数存在する場合には、それらの中から任意のビ
ット位置を選んで良い。

【００５２】そして、この割り当てられたシグネチャの
ビット位置ｊにおける「１」となる確率ｐ［ｊ］に、そ
の部分文字列の出現確率ｘを加算する（ステップＳ１
７）。次に、２番めの出現確率を持つ部分文字列を選
び、先と同様に、その部分文字列に対するシグネチャ１
０ビット中の「１」にするビット位置を、その時点で１
０ビットのシグネチャの各ビット位置（ｉ＝１〜１０）
について「１」となる確率ｐ［ｉ］が最も低いビット位
置に割り当て、そのビット位置における「１」となる確
率ｐ［ｊ］に、その部分文字列の出現確率ｘを加算す
る。以下同様にして、部分文字列統計データベース７か
ら順次部分文字列を取り出し、それに対して、ｐ［ｉ］
の値が最も低いシグネチャのビット位置を割り当てて行
くということを、全ての部分文字列に対して繰り返し
（ステップＳ１８）、その結果作成された新たなシグネ
チャをシグネチャ作成用データベース６に格納し、部分
文字列に対し割り当てられたシグネチャを更新する。

【００５３】このようにして、各部分文字列ごとにシグ
ネチャの１０ビットのうちの１ビットを「１」にする位
置を決定すれば良いのであるが、これを例えばユーザが
指定するタイミングで行うことにより、情報検索装置の
性能を自動的に向上させることができる。

【００５４】汎用的な情報検索装置においては、どのよ
うなレコードデータが与えられるかを事前に予測するこ
とが困難である。従って、初期状態のシグネチャ作成用
データベース６としては、既存のものを用いて、シグネ
チャ作成部９にてシグネチャを作成することにする。こ
のときには、実際に入力部１を介して入力されるレコー
ドデータとは部分文字列の出現確率が異なるため、フォ
ルスドロップ率は大きくなる可能性がある。しかし、マ
スターデータベース５に格納されるデータが少量である
間は、たとえフォルスドロップが大きくても検索時間オ
ーバーヘッドが問題とはならない。

【００５５】マスターデータベース５へのデータの追加
が継続されデータベースが大きくなるにつれ、フォルス
ドロップ数も増大するようになり検索速度低下が問題と
なり始める。そのとき、シグネチャ作成用データベース
更新部１１で、それまでのデータ追加で統計情報データ
ベース７に収集された部分文字列の統計情報データを利
用して、図９に示したフローチャートに従って部分文字
列に対するシグネチャを作成し直し、シグネチャ作成用
データベース６を更新する。

【００５６】シグネチャ作成用データベース更新部１１
は、シグネチャ作成用データベース６を更新すると、こ
の更新されたシグネチャ作成用データベース６を用い
て、それまでにシグネチャ格納データベース８に格納さ
れている全てのレコードのシグネチャをシグネチャ作成
部９の説明と同様にして作成し直す。シグネチャ格納デ
ータベース８では、作成し直されたシグネチャは、古い
シグネチャと置き換えられるため、この手続きによりシ
グネチャ格納データベース８のサイズが増加することは
ない。

【００５７】次に、情報検索時のデータの流れに沿って
図３の各構成部について説明する。入力部１を介して入
力された検索指示要求に含まれる検索情報から、質問式
処理部２で検索条件となり得るテキスト情報が抽出され
る。

【００５８】質問式処理部２は、検索条件となり得るテ
キスト情報を含む検索情報を入力部１を介して入力する
ようユーザとの対話形式にてユーザに促すようになって
いる。

【００５９】質問式処理部２で抽出された、検索条件と
してのテキスト情報はキーワード切り出し部３、続いて
部分文字列切り出し部４に入力され、情報記憶時の場合
と同様、キーワードの切り出し、部分文字列の切り出し
が行われる。

【００６０】シグネチャ作成部９では、情報記憶時の場
合に用いたのと同じシグネチャ作成用データベース６を
用いて、与えられた検索条件としてのテキスト情報中の
キーワードの部分文字列に対するシグネチャの作成を行
う。

【００６１】次に、シグネチャ比較装置１０では、シグ
ネチャ作成部９で作成された検索条件のシグネチャとシ
グネチャ格納データベース８に格納されているシグネチ
ャとを比較し、双方の一致するレコードが存在する場合
は、そのレコードの識別子を読み出して、２次検索部１
２に転送する。

【００６２】２次検索部１２は、レコードの識別子をキ
ーとしてマスターデータベース５からレコードの実デー
タを取り出し、フォルスドロップ除去を行った後、出力
部１３を介して出力する。

【００６３】出力部１３は、例えば、プリンタ装置、デ
ィスプレイ装置、スピーカ装置等から構成されている。
以上説明したように、上記実施形態によれば、部分文字
列切り出し部４で入力された情報（レコード）中のキー
ワードを部分文字列に分割し、その際、その部分文字列
のキーワード中での出現頻度を計数して統計情報データ
ベース７に格納しておく。シグネチャ作成部７におい
て、シグネチャ作成用データベースに格納されている該
部分文字列に割り当てられたビット列（部分文字列のシ
グネチャ）に基づき前記入力された情報に対するビット
列（シグネチャ）を生成したら、そのビット列を前記入
力された情報に対応付けて、それぞれシグネチャ格納デ
ータベース８、マスターデータベース５に記憶する。情
報検索の際には、シグネチャ作成部９で、入力部１を介
して入力された検索情報に対するビット列を生成して、
それとシグネチャ格納データベース８に記憶されたビッ
ト列とを照合して情報を検索する。シグネチャ作成用デ
ータベース更新部１１は、統計情報データベース７に格
納されている前記部分文字列のキーワード中での出現頻
度に基づき該部分文字列に予め定められた長さのビット
列を割り当て、それに伴いシグネチャ格納データベース
８に格納されているシグネチャを更新することにより、
一般的なキーワード出現頻度とは異なる特殊なキーワー
ド出現頻度を持つテキストデータベースに対しても、テ
キスト中に現れるキーワード数、各キーワードの出現頻
度のばらつきに応じてフォルスドロップの発生を抑制で
きる。また、キーワード中の部分文字列（例えば２文
字）とそのキーワード中の出現位置との組み合わせに対
し、シグネチャを割り当てるので前方一致検索を行う際
には記憶領域のオーバーヘッドを押さえることができ、
高速な情報検索が行える。

【００６４】なお、上記実施形態で説明した質問式処理
部２、キーワード切り出し部３、部分文字列切り出し部
４、シグネチャ作成部９、シグネチャ比較部１０、シグ
ネチャ作成用データベース更新部１１、２次検索部１２
の処理動作は、コンピュータに実行させることのできる
プログラムとして磁気ディスク（フロッピーディスク、
ハードディスク等）、光ディスク（ＣＤ−ＲＯＭ、ＤＶ
Ｄ等）、半導体メモリなどの記録媒体に格納して頒布す
ることもできる。

【００６５】

【発明の効果】以上説明したように、本発明によれば、
テキスト中のキーワードの出現頻度に応じて、シグネチ
ャを用いた情報検索を行う際のフォルスドロップの発生
を抑制でき、記憶領域のオーバーヘッドを抑え、高速に
前方一致検索が行える。

【図面の簡単な説明】

【図１】情報検索にシグネチャについて説明するための
図。

【図２】シグネチャを用いた情報検索方法について説明
するための図。

【図３】本発明の実施形態に係る情報検索装置の構成例
を示した図。

【図４】レコードデータの一具体例を示した図。

【図５】図４のレコードから切り出されたキーワードの
一例を示した図。

【図６】図５のキーワードから切り出された部分文字列
の一例を示した図。

【図７】図３の部分文字切り出し部の処理動作について
説明するためのフローチャート。

【図８】図３のシグネチャ作成部でキーワードのシグネ
チャを作成する手順を説明するための図。

【図９】図３のシグネチャ作成用データベース更新部の
処理動作を説明するためのフローチャート。

【符号の説明】

１…入力部 ２…質問式処理部 ３…キーワード切り出し部 ４…部分文字列切り出し部 ５…マスターデータベース ６…シグネチャ作成用データベース ７…統計情報データベース ８…シグネチャ格納データベース ９…シグネチャ作成部 １０…シグネチャ比較部 １１…シグネチャ作成用データベース更新部 １２…２次検索部 １３…出力部

Claims (6)

【特許請求の範囲】
1. 【請求項１】 入力された情報中のキーワードから部分
   文字列を切り出し、この切り出された部分文字列のキー
   ワード中での出現頻度に基づき前記部分文字列に割り当
   てられた予め定められた長さのビット列を用いて前記入
   力された情報に対する第１のシグネチャを生成し、前記
   入力された情報を前記生成された第１のシグネチャと対
   応付けて記憶してデータベースを作成することを特徴と
   するデータベース作成方法。
2. 【請求項２】 情報とそれに対応する第１のシグネチャ
   とが対応付けられて記憶されたデータベースの検索方法
   であって、 入力された検索情報中のキーワードから部分文字列を切
   り出し、この切り出された各部分文字列についてその部
   分文字列のキーワード中での出現頻度に基づいて予め割
   り当てられたビット列を用いて前記検索情報に対応する
   第２のシグネチャを生成し、この生成された第２のシグ
   ネチャと前記データベース内の第１のシグネチャとを照
   合することにより、前記検索情報に関連する情報を前記
   データベースから検索することを特徴とする情報検索方
   法。
3. 【請求項３】 入力された情報中のキーワードから部分
   文字列を切り出し、この切り出された部分文字列のキー
   ワード中での出現頻度に基づき前記部分文字列に割り当
   てられた予め定められた長さのビット列を用いて前記入
   力された情報に対する第１のシグネチャを生成し、前記
   入力された情報を前記生成された第１のシグネチャと対
   応付けて記憶してデータベースを作成し、情報検索の際
   には、入力された検索情報中のキーワードから部分文字
   列を切り出し、この切り出された各部分文字列について
   その部分文字列のキーワード中での出現頻度に基づいて
   予め割り当てられたビット列を用いて前記検索情報に対
   応する第２のシグネチャを生成し、この生成された第２
   のシグネチャと前記データベース内の第１のシグネチャ
   とを照合することにより、前記検索情報に関連する情報
   を前記データベースから検索することを特徴とする情報
   検索方法。
4. 【請求項４】 入力された情報中のキーワードから部分
   文字列を切り出す切出手段と、 この切り出し手段で切り出された部分文字列の出現頻度
   に基づき前記部分文字列に予め定められた長さのビット
   列を割り当てる割当手段と、 前記部分文字列に割り当てられたビット列を用いて前記
   入力された情報に対する第１のシグネチャを生成する生
   成手段と、 前記入力された情報を前記生成手段で生成された第１の
   シグネチャと対応付けて記憶してデータベースを作成す
   る手段と、 入力された検索情報中のキーワードから部分文字列を切
   り出し、この切り出された各部分文字列について前記生
   成手段で生成されたビット列を用いて、該検索情報に対
   応する第２のシグネチャを生成し、この生成された第２
   のシグネチャと前記データベース内の第１のシグネチャ
   とを照合することにより、前記検索情報に関連する情報
   を前記データベースから検索する検索手段と、 を具備したことを特徴とする情報検索装置。
5. 【請求項５】 入力された情報中のキーワードから部分
   文字列を切り出す切出手段と、 この切り出し手段で切り出された部分文字列の出現頻度
   に基づき前記部分文字列に予め定められた長さのビット
   列を割り当てる割当手段と、 前記部分文字列に割り当てられたビット列を用いて前記
   入力された情報に対する第１のシグネチャを生成する生
   成手段と、 前記入力された情報を前記生成手段で生成された第１の
   シグネチャと対応付けて記憶してデータベースを作成す
   る手段と、 を実行するプログラムを記録した機械読み取り可能な記
   録媒体。
6. 【請求項６】 入力された情報中のキーワードから部分
   文字列を切り出す切出手段と、 この切り出し手段で切り出された部分文字列の出現頻度
   に基づき前記部分文字列に予め定められた長さのビット
   列を割り当てる割当手段と、 前記部分文字列に割り当てられたビット列を用いて前記
   入力された情報に対する第１のシグネチャを生成する生
   成手段と、 前記入力された情報を前記生成手段で生成された第１の
   シグネチャと対応付けて記憶してデータベースを作成す
   る手段と、 入力された検索情報中のキーワードから部分文字列を切
   り出し、この切り出された各部分文字列について前記生
   成手段で生成されたビット列を用いて、該検索情報に対
   応する第２のシグネチャを生成し、この生成された第２
   のシグネチャと前記データベース内の第１のシグネチャ
   とを照合することにより、前記検索情報に関連する情報
   を前記データベースから検索する検索手段と、 を実行するプログラムを記録した機械読み取り可能な記
   録媒体。