JPH0581321A

JPH0581321A - フルテキストサーチの方法

Info

Publication number: JPH0581321A
Application number: JP3237805A
Authority: JP
Inventors: Yasushi Tomita; 泰志冨田; Hidekazu Matsumoto; 秀和松本; Shiro Nonaka; 士郎野中
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1991-09-18
Filing date: 1991-09-18
Publication date: 1993-04-02

Abstract

(57)【要約】【目的】文書データベースに蓄積されている文書の中か
ら、与えられた任意の文字列を含む文書を見つけるフル
テキストサーチにおいて、絞り込み率が高く、絞り込み
速度の大きい絞り込み方法を用いることによってフルテ
キストサーチを高速化することを目的とする。【構成】絞り込み処理部は、図１に示すように、文字列
の２字文字列への分解部，２字文字列の分類部，インデ
ックステーブル問い合わせ部，インデックステーブル，
統合部とから成り、与えられた検索語に対して、検索語
に含まれる２字文字列の全てを含むと思われる文書に絞
り込み、得られた候補の文書に対して、検索語との逐次
文字照合を行うことによってフルテキストサーチを行
う。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、大量に蓄えられた文書
の中から、調査したい事柄に関する書物等の希望する文
書を探し出す文書検索装置に係わり、与えられた任意の
文字列を含む文書を見つけるフルテキストサーチの方法
に関するものである。

【０００２】

【従来の技術】一般に、フルテキストサーチを高速に行
うには、与えられた文字列と各文書のテキストとを高速
なアルゴリズムで逐次照合する方法と、予め各文書がど
のような文字列で構成されているかという情報を高速に
アクセスできる形式で持っておく方法とが考えられる。

【０００３】後者によるフルテキストサーチの高速化に
ついては、「大規模文書情報システム用テキストサーチ
マシンの研究」（加藤寛次他４名，情報処理学会情報
学基礎研究会報告，Ｎｏ．１４−６（１９８９．７．２
７））に示されているように、各文書の構成文字を示す
文字成分表と、テキストを文字種で区切り助詞や接続詞
等の付属語を削除し重複を取り除いた凝縮本文との２つ
をインデックステーブルとして持ち、与えられた文字列
に対して、まず、文字成分表によって構成文字全てを含
む文書に絞り込み、次に、凝縮本文によって、与えられ
た文字列に含まれる同一文字種文字列を全て含む文書に
絞り込み、最後に候補となった文書のテキストと与えら
れた文字列とを逐次照合することによって、文字列全体
を含む文書を見つける方法が知られている。

【０００４】

【発明が解決しようとする課題】しかし、与えられた文
字列の構成文字を全て含んでいても、文字列としては含
んでいないことが多いため、文字成分表では十分な絞り
込み率が得られない。また、凝縮本文による絞り込み率
は高いが、凝縮本文では逐次照合を行うため、スピード
が遅い。

【０００５】そこで、本発明の目的は、フルテキストサ
ーチを高速化する、絞り込み率の高い絞り込み方法を得
るための１つの手段を提供し、幾つかの具体的な例を与
えることである。

【０００６】

【課題を解決するための手段】前述の課題を解決するた
め、本発明では、２字文字列を分類する手段と、分類に
よって得られた集合とこの集合に属する２字文字列を少
なくとも１つは含む文書名の集合とを対応させる手段と
を持つ絞り込み方法を与える。さらに、２字文字列分類
手段の具体例を幾つか挙げる。

【０００７】

【作用】２字文字列の分類手段と、分類によって得られ
た集合とこの集合に属する２字文字列を少なくとも１つ
は含む文書名の集合との対応を与える手段とによって、
与えられた文字列に含まれる２字文字列全てを含むと考
えられる文書を簡単に求めることができ、このことによ
って、絞り込みを実行する。

【０００８】

【実施例】

実施例１図２を用いて、実施例の構成と全体の処理の流れについ
て説明する。本実施例は、入出力部１，対話制御部２，
絞り込み処理部３，インデックステーブル４，逐次照合
処理部５，文書データベース６とから構成されている。
入出力部１より入力された文字列（以後、検索語とい
う）は、対話制御部２を介して絞り込み処理部３へ送ら
れる。絞り込み処理部３は、検索語を構成する２字文字
列全てを含む可能性のある文書へ、インデックステーブ
ル４を用いて絞り込み、結果を逐次照合処理部５へ送
る。逐次照合処理部５は、絞り込み処理部４で得られた
各文書を文書データベース６から取り出し、検索語と各
文書のテキストとを逐次文字照合することで、検索語を
含む文書のみに確定させて、その文書の名前等の検索結
果を対話制御部２へ送る。対話制御部２は、得られた文
書名等の検索結果を入出力部１へ出力する。逐次照合の
方法については、多くの公知の技術がある。

【０００９】次に、絞り込み処理部３について詳細に説
明する。

【００１０】絞り込み処理部３は、図１に示すように、
２字文字列への分解部３１，２字文字列分類部３２，イ
ンデックステーブル問い合わせ部３３，インデックステ
ーブル４，統合部３４より構成される。このうち、分類
部３２は、図３に示すように、２字文字列を分類する手
段、即ち、２字文字列全体の集合Σから有限集合Ｓへの
写像ｆを持つ。

【００１１】インデックステーブル４を説明する為に、
まず記号の説明を述べる。文書データベース６に蓄積さ
れている文書の名前（文書名）全体の集合をＢとおき、
Ｂの部分集合の族をＰ(Ｂ)で表す。文書名ｂ∈Ｂに対応
しているテキストに含まれる２字文字列全ての集合をΣ
(b)で表す。また、Ｋ(s)＝{σ∈Σ;f(σ)＝s} とおく。

【００１２】インデックステーブル４は、ＳからＰ(Ｂ)
への写像で、ｓ∈Ｓに対して文書名の集合Ｉ(s)＝{b∈
Ｂ;Σ(b)∩Ｋ(s)≠φ} を対応させる写像を表す手段で
あり、例えば、図５のようにＳの元を見出しとし、I
(ｓ) をこれに対応させた対応表が考えられる。Ｋ(s)
は、ｆによってｓに移される２字文字列の集合である。

【００１３】以上のような構成を持つ絞り込み処理部３
の処理について詳細に説明する。与えられた検索語は、
まず、分解部３１でこれを構成する２字文字列へ分解さ
れる。次に、得られた各２字文字列に対して、次の
(１)，(２)の処理によって、ある文書名の集合が対応付
けられる。

【００１４】（１）分類部３２が、写像ｆによって、２
字文字列に対応するＳの元ｓを求める。

【００１５】（２）インデックステーブル問い合わせ部
３３が、インデックステーブル４によって，(１)におい
て得られたｓに対応する文書名の集合Ｉ(s) を求める。

【００１６】このようにして得られた文書名の集合Ｉ
(s) の共通集合を、統合部３４が求めて、絞り込み結果
として逐次照合処理部５へ送る。

【００１７】このようにして得られた絞り込み結果は、
検索語を構成する各２字文字列に対して、その２字文字
列の属するＩ(s) の元を少なくとも１つは含む文書の名
前の集合である。また、以上述べたように、本実施例の
具体的な実現は、分類部３２の持つ２字文字列の分類写
像ｆを具体的に定義することで得ることができる。従っ
て、本発明は、フルテキストサーチ高速化のためのイン
デックステーブルを考える場合の１つの手段を提供す
る。

【００１８】そこで、次に、２字文字列の分類写像の具
体例を述べることで、本実施例の具体例を幾つか与え
る。

【００１９】（１）modulo u による分類ｕは任意の自然数とする。２字文字列ａｂに対して、第
１文字ａ，第２文字ｂの文字コードをそれぞれ再びａ，
ｂで表すとき、ｆ(ａｂ)＝ｕ＊（ａをｕで割った余り）
＋（ｂをｕで割った余り）で定義される分類。

【００２０】（２）差分による分類 (１)と同様に、ｆ(ａｂ)＝ｂ−ａで定義される分類。

【００２１】ここで、２字文字列は、各構成文字の文字
コ−ドを２つの成分とする平面上の点と見做すことがで
きる。そこで、(１)，(２)の分類について平面上の点と
いう観点から説明する。Ｓは、(１)の場合はＳ＝｛０，
１，２，３，…,ｕ²−１｝、(２)の場合はＳは絶対値が
文字コ−ドの最大値以下の整数全体の集合である。１つ
のｓに対応する２字文字列の集合Ｉ(s) 、即ち、分類に
よって１つにまとめられる２字文字列の集合は、図６に
大まかに表すと(１)のｕ＝２００の場合は＊印全ての集
合で、(２)は直線b−a＝s 上にある２字文字列全ての集
合になる。

【００２２】この２つの例では、分類方法ｆが高速計算
可能な数式で与えられているため、絞り込み率が良けれ
ば、フルテキストサーチを高速化できる。実際、(１)に
おいてｕ＝２００としてみると、文字成分表に比べて、
高い絞り込み率が得られることが実験によって示され
る。

【００２３】２字文字列の分類について、さらに具体的
に説明するため、図４を用いて、(１)の具体例を１つ説
明する。ｕ＝２００の場合の分類、即ち、ｆ(ａｂ)＝20
0・（ａを２００で割った余り）＋（ｂを２００で割った
余り）について述べる。幾つかの文字の文字コ−ドを例
えば、図４(ａ)のようであると仮定する。これをもと
に、幾つかの２字文字列のｆによる値と、その値によっ
て分類される２字文字列の集合を図４(ｂ）に図示し
た。例えば、ｆ（２字）＝２１５０,ｆ（文の）＝２１
５０，ｆ（文い）＝２１５０，ｆ（に字）＝３３５０，
ｆ（にい）＝3350，ｆ（字類）＝３０２０、等であり、
Ｋ（２１５０）＝｛２字，文の,文い，…｝，Ｋ（３３
５０）＝｛に字，にい，…｝，Ｋ（３０２０）＝｛字
類，…｝等である。

【００２４】実施例２本実施例は、図７に示すように、ネットワーク上に接続
された、入出力部１と対話処理部２とを持つワークステ
−ション７複数個と、絞り込み処理部３と逐次照合部４
とを持つ文書データベース６を管理するサーバ８とから
構成されており、ネットワーク上の任意の端末７を通し
て、文書データベース８に蓄積されている文書に対しフ
ルテキストサーチによる文書検索を行うことができる。

【００２５】

【発明の効果】高速な２字文字列の分類方法を具体的に
与えることで、絞り込み率の高い絞り込み方法を実現
し、高速フルテキストサーチ方法を実現することができ
る。

【図面の簡単な説明】

【図１】本発明の実施例の構成を示した図である。

【図２】本発明の絞り込み処理を示した図である。

【図３】絞り込み処理における２字文字列の分類手段ｆ
について説明した図である。

【図４】分類手段ｆの具体例について説明した図であ
る。

【図５】絞り込み処理におけるインデックステーブルを
説明した図である。

【図６】本発明で具体的に与えた２字文字列の分類方法
を大まかに説明した図である。

【図７】本発明の絞り込み方法を用いたフルテキストサ
ーチによる文書検索のシステムの構成を示した図であ
る。

【符号の説明】

１…入出力部、２…対話制御部、３…絞り込み処理部、
４…インデックステーブル、５…逐次照合処理部、６…
文書データベース、７…ワークステ−ション、８…サー
バ、３１…２字文字列への分解部、３２…２字文字列の
分類部、３３…インデックステーブル問い合わせ部、３
４…統合部。

Claims

【特許請求の範囲】

【請求項１】文書データベースに蓄積されている文書の
中から、与えられた任意の文字列を含む文書を探しだす
フルテキストサーチにおいて、予め各２字文字列に対し
てそれを含む文書の名前をある有限集合を介して対応さ
せる手段を持ち、与えられた文字列からそれに含まれる
２字文字列全てを抽出するステップと、前述の対応手段
を用いて各２字文字列を含む文書の名前を求めるステッ
プとによって、与えられた文字列を構成する２字文字列
を全て含むと考えられる文書に絞り込むことを特徴とす
るフルテキストサーチの方法。
【請求項２】検索語の入力や検索結果の出力をする入出
力部と、入出力部の制御を行う対話処理部と、検索語を
含む可能性のある文書に絞り込む絞り込み処理部と、絞
り込み処理部によって得られた文書と検索語とを逐次照
合する逐次照合処理部と、文書データベースとから成る
文書検索装置で、２字文字列全体から成る集合の分類手
段と、その分類手段によって分類された２字文字列の集
合にそのうち少なくとも１つの２字文字列を含むような
文書の名前の集合を対応させる手段とを持って、与えら
れた文字列に含まれる２字文字列をすべて含むと考えら
れる文書に絞り込むことを特徴とする文書検索装置。
【請求項３】請求項２において、入出力部と対話処理部
とを含む端末を複数個と、絞り込み処理部と逐次照合部
とを含むサーバと、文書データベースとをネットワーク
上に接続したことを特徴とする文書検索システム。
【請求項４】請求項１における２字文字列の分類手段と
して、２字文字列ａｂに対して、第１文字ａ，第２文字
ｂの文字コ−ドをそれぞれ再びａ，ｂで表すとき、ｆ
(ａｂ)＝ｕ・（ａをｕで割った余り）＋（ｂをｕで割っ
た余り）（ただし、ｕは自然数とする）で定義される分
類手段をとることを特徴とするフルテキストサーチ高速
化の方法。
【請求項５】請求項１における２字文字列の分類手段と
して、２字文字列ａｂに対して、第１文字ａ，第２文字
ｂの文字コ−ドをそれぞれ再びａ，ｂで表すとき、ｆ
(ａｂ)＝ｂ−ａで定義される分類手段をとることを特徴
とするフルテキストサーチ高速化の方法。