JPH05225238A

JPH05225238A - データベース検索システム

Info

Publication number: JPH05225238A
Application number: JP4056965A
Authority: JP
Inventors: Hiroshi Takada; 寛高田
Original assignee: Nippon Steel Corp
Current assignee: Nippon Steel Corp
Priority date: 1992-02-07
Filing date: 1992-02-07
Publication date: 1993-09-03
Anticipated expiration: 2017-02-18
Also published as: JP3258063B2

Abstract

(57)【要約】【目的】複雑な条件式によるデータベース検索システ
ムにおいて、検索を高速化し、検索結果の再利用を図
る。【構成】検索部１２において所定の条件Ａ、Ｂ等によ
る検索を行い、その結果を検索結果リスト格納部１４に
格納する。ＡorＢ、Ａand Ｂ等の複雑な条件による検索
の場合には、物件リスト条件検索部１６は検索結果リス
ト格納部１４に格納された条件Ａ、Ｂによる検索結果を
用いて検索を行う。複雑な条件によってデータベースを
直接検索しないため、検索時間を短縮できる。また、よ
り簡単な条件によって検索された結果を再利用するから
検索効率がよい。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、データベース検索シス
テムに関し、特に複数の条件によりデータベースから必
要な情報を取り出すためのデータベース検索システムに
関する。

【０００２】

【従来の技術】全物件検索によるデータベース検索にお
いて条件検索を行う場合には、所定の検索キーが設定さ
れ、この検索キーを全物件に適用して検索を行う。たと
えば各物件が検索キーを含むか否かを調べ、検索キーを
含む物件が検索結果としてリストアップされる。

【０００３】このような検索において、複数の検索キー
からなる条件式（検索式）を用いて検索を行う場合に
は、複数の検索キーによって条件式を立式し、これを用
いて検索することが従来行われている。たとえばキー
Ａ、Ｂ、Ｃ、Ｄによって、（Ａ or Ｂ or Ｃ）and
Ｄのような条件式を作成し、この式を用いて全物件に対
する検索を行う。

【０００４】

【発明が解決しようとする課題】しかしながら、このよ
うな検索は複数のキーから構成される条件式を用いてい
るため、検索時間が非常に長く、条件不成立時のコスト
パフォーマンスが低い。また、類似する条件式、たとえ
ば上記の条件式に類似する（Ａ or Ｂ or Ｃ）and
Ｅのような条件式による検索を行う場合に、すでに行っ
た検索の部分的な論理条件（Ａ or Ｂ or Ｃ）の再
利用ができないため、効率が低いという欠点がある。

【０００５】本発明は、上記のような従来の欠点を解消
し、複数の条件による検索において、条件式の複雑さに
かかわらず、高速な条件検索が可能であり、検索結果の
再利用が可能なデータベース検索システムを提供するこ
とを目的とする。

【０００６】

【課題を解決するための手段】本発明のデータベース検
索システムは、所定の条件により全物件検索を行う検索
手段と、検索手段による検索結果を記憶する検索結果記
憶手段と、検索結果記憶手段に記憶された検索結果を用
いて条件検索を行う条件検索手段とを具備する。

【０００７】

【作用】本発明によれば、複数の条件によって全物件検
索を行う場合に、複数の条件のうちの所定の条件によっ
て検索手段が検索を行い、検索の結果は検索結果記憶手
段に記憶される。次にこの検索結果を用いて条件検索手
段が複雑な条件の検索を行う。したがって、所定の条件
による検索結果が記憶されており、これを用いてより複
雑な条件の検索を行うから、部分的な検索結果を再利用
することができ、高速の条件検索が可能となる。

【０００８】

【実施例】図１には、本発明によるシステムの一実施例
が示されている。同図に示すように、本システムは、検
索部１２、検索結果リスト格納部１４、物件リスト条件
検索部１６を有する。検索部１２は検索キー入力部１８
から入力された所定の検索キーからなる条件式によって
データベースたる検索対象１０について全物件検索を行
う検索部である。

【０００９】たとえば検索キー入力部１８から入力され
るキーが同図に示すようにＡ、Ｂである場合に、検索部
１２は条件式Ａ、Ｂによってそれぞれ検索を行い、その
結果が検索結果リスト格納部１４に格納される。同図に
示す例では条件式Ａによって検索された物件の番号リス
トが３、５、１０、２０であり、条件式Ｂによって検索
された物件の番号リストが５、１０、３０である。これ
らの物件番号リストが検索結果として検索結果リスト格
納部１４に格納される。

【００１０】物件リスト条件検索部１６は、検索結果リ
スト格納部１４に格納された結果を用いてさらに複雑な
条件式による検索を行う検索部である。たとえば条件式
Ａ、Ｂによる前記の検索結果を用いて、条件式（Ａ or
Ｂ）や（Ａ and Ｂ）による検索を行う場合には、物
件リスト条件検索部１６は検索結果リスト格納部１４か
らから条件式Ａおよび条件式Ｂによる検索結果を読み出
し、これらを用いて条件式（Ａ or Ｂ）または（Ａ
and Ｂ）による検索を行う。

【００１１】本実施例の場合には、検索結果リスト格納
部１４に格納されている結果は前述のように、条件式Ａ
によって検索された物件の番号リストが３、５、１０、
２０であり、条件式Ｂによって検索された物件の番号リ
ストが５、１０、３０であるから、条件式（Ａ or
Ｂ）の検索の場合にはこれらの物件番号リストのＯＲを
求めることにより、物件番号リスト３、５、１０、２
０、３０が得られる。同様に、、条件式（Ａ and Ｂ）
の検索の場合にはこれらの物件番号リストのＡＮＤを求
めることにより、物件番号リスト５、１０が得られる。
これらの得られた物件番号リストの結果は再び検索結果
リスト格納部１４に送られ、格納される。

【００１２】したがって、これらのリストを用いて、物
件リスト条件検索部１６はさらに（Ａ or Ｂ or
Ｃ）や（Ａ or Ｂ or Ｃ）and Ｅのような条件式を
用いた検索を同様に行うことができる。

【００１３】本実施例によれば、上記のように所定の検
索キーからなる条件式によって検索した結果を物件番号
リストとして検索結果リスト格納部１４に格納してお
き、これらのキーを組み合わせた複雑な条件式による検
索を行う場合に、格納された物件番号リストを用いて条
件検索を行う。

【００１４】したがって、複雑な条件式による検索の場
合に、全物件に対してそれぞれ複雑な条件による検索を
行う必要がないため、検索時間を短縮することができ
る。また、部分的な条件検索の結果を再利用して検索を
行うから検索効率がよい。

【００１５】本発明による検索システムは、各種のデー
タベースの検索に適用できる。たとえば次のようなデー
タ検索システムにおける条件式の検索に適用できる。

【００１６】図２は、本発明が適用される一実施例を示
す近傍特徴量によるパターン検索システムのデータフロ
ー図である。この検索システムでは、予め全対象物件か
ら事象（情報）の位相情報を全て捨象した近傍特徴量を
作成し、そのデータ群に対して全物件検索を行なう。検
索のアルゴリズムは、学習ステップと検索ステップとか
らなる。学習ステップでは、物件毎に近傍特徴量行列が
作成される。検索ステップでは、検索キーと近傍特徴量
行列とのマッチング演算が行なわれ、物件ごとにマッチ
ング度（類似度）を示す評価結果を得る。以下、各ステ
ップについて説明する。

【００１７】（１）、学習ステップ図２に於いて、検索対象１０は、例えば日本語、英語、
ドイツ語、フランス語、ヘブライ語、ロシア語などの文
書データ、或いは量子化された波形数値データ、化学構
造式、遺伝子情報などである。このような検索対象に対
して、まず正規化手段Ｓ１により正規化の処理を行な
う。一般に検索対象は、情報の最小単位（文書であれば
アルファベットなどの文字、数値チャートであれば、あ
る時刻における実数値など）の列で表現されている。そ
れをなんらかの方法でｎ階調の整数列に変換する。これ
をデータの正規化と呼ぶ。

【００１８】例えば、英文書データの場合、ＡＳＣＩＩ
コード表をそのまま用いることにより、次のような２５
６階調の数値表現として実現される。 …… This is a pen. …… 84｜104 ｜105 ｜115 ｜32｜105 ｜115 ｜32｜97｜32｜112 ｜101 ｜110 ｜46｜

【００１９】上記のコードにおいては、Ｔが84、ｈが10
4 ．．と対応している。

【００２０】正規化されたデータ２０は、次に学習手段
Ｓ２により近傍特徴量行列３０の形式に畳込まれる。こ
こで近傍特徴量をとる演算式は種々考えられる。この演
算式は検索の鋭さ（過検出の少なさ）にも影響を与え
る。

【００２１】今、ｉ番目の物件（文書）のｊ番目のデー
タ（文字）をＣ_i,jとし、Ｃ_i,jに関する量子化量ｘと
Ｃ_i,jの前方ｋ近傍に関する量子化量ｙを次のようにし
て求める。ここでは、検索される対象物件（文書）がｎ
個あるとし、そのうちのｉ番目の物件の量子化について
説明する。ｉ番目の物件において、図３に示すように正
規化された数値列135,64,37,71,101,...が並んでいると
すると、Ｃ_i,jに関する量子化量ｘは、ｘ＝f(Ｃ_i,j）Ｃ_i,jの前方ｋ近傍に関する量子化量ｙはｙ＝g(Ｃ_i,j, Ｃ_i,j+1,Ｃ_i,j+2,....,Ｃ_i,j+k) で求められる。

【００２２】ここで、f(Ｃ_i,j）はＣ_i,jに関するｎ段
階量子化関数である。すなわち、ｉ番目の物件のｊ番目
のデータＣ_i,jについて所定の演算を行って得られる値
であり、１〜ｎのいずれかの整数で表される。したがっ
て、得られたｘの値によって図４に示す行列（座標）に
おいてｘ軸方向の位置が１〜ｎの範囲で定まる。

【００２３】また、g(Ｃ_i,j, Ｃ_i,j+1,Ｃ_i,j+2,....,
Ｃ_i,j+k) は、Ｃ_i,jの前方ｋ近傍に関するｍ段階量子
化関数である。すなわち、ｉ番目の物件のｊ番目のデー
タＣ_i,jとそのデータの近傍の所定の数のデータについ
て所定の演算を行って得られる値であり、１〜ｍのいず
れかの整数で表される。たとえば図３に示すようにｊ番
目のデータＣ_i,jが１３５であり、ｋが３の場合には、
Ｃ_i,j+1,Ｃ_i,j+2,Ｃ_i,j+3としてデータ１３５に続くデ
ータ６４、３７、７１を抽出し、これらのデータとデー
タ１３５との相関について所定の演算を行う。ｊ番目の
データＣ_i,jが次の６４の場合には、Ｃ_i,j+1,Ｃ_i,j+2,
Ｃ_i,j+3としてデータ６４に続くデータ３７、７１、１
０１を抽出し、これらのデータとデータ６４との相関に
ついて所定の演算を行う。

【００２４】このようにして得られたｙの値によって、
図４に示す行列（座標）におけるｙ軸方向の位置が１〜
ｍの範囲で定まる。したがって、上記のようにｘ、ｙを
求めることによって図４に示す行列（座標）における位
置が定まる。

【００２５】本システムでは、各物件情報は、上記のよ
うにして求めたｘ、ｙに対して物件の通番ｉと重みｗ
（x,y,i)の組として記憶される。重みｗ（x,y,i)は、デ
ータｘ、ｙ、ｉから所定の演算によって求められるが、
通常は重みｗ（x,y,i)の値は１に固定される。

【００２６】上記のようにして求められたデータＣ_i,j
ごとにｘ、ｙの値に基づき図４に棒によって示されるよ
うに、データを記憶する。すなわち、データＣ_i,jの
ｘ、ｙの値によって定められる座標の位置に、その物件
の通番ｉとその重みｗ（x,y,i)を組みとしたデータを記
憶する。同図ではこのようなデータが記憶されるごとに
棒の長さが延びるように表されている。通常は重みｗ
（x,y,i)は１とされるから、物件の通番ｉのデータのみ
がｘ、ｙの値によって定められる座標の位置に記憶され
てゆく。

【００２７】この様にして作成された近傍特徴量行列に
物件の識別番号を付加して構造ファイル４０として保存
する。

【００２８】（２）、検索ステップまず検索キー５０を入力する。例えば、"This is a pe
n."を検索キーとする。この検索キー５０に対して学習
ステップと同一の正規化方法に基づく正規化手段Ｓ３に
よりキー情報を整数列に正規化する。 84｜104 ｜105 ｜115 ｜32｜105 ｜115 ｜32｜97｜32｜112 ｜101 ｜110 ｜46｜

【００２９】次に、検索手段Ｓ４において、学習ステッ
プと同一の近傍特徴量抽出式f() 、g() を用いて各物件
に対応する正規化された数値列の先頭からｘ、ｙの組の
系列を作成する。次に、このｘ、ｙの組の系列に基づい
て、物件ｋに対する検索キーの含有度数ω_kとして、Ｖ
（ｘ_j,ｙ_j,ｋ）をｊ＝１〜ｍについて合計することによ
り算出する。

【００３０】ただし、Ｖ（ｘ_j,ｙ_j,ｋ）は、物件情報リ
ストが物件ｉについての重みを持つ場合、はその重みに
等しく、持たない場合には０と定める。

【００３１】したがって、検索すべき数値列のｘ、ｙの
組に対応する図４のｘ、ｙの位置にデータがある場合
（棒がある場合）には、別に設けられた記憶手段のその
データに示される物件の通番ｉの格納箇所にその重みの
値を記憶させる。

【００３２】次に、評価結果出力手段Ｓ５において、物
件毎に得られた構造評価値score （合致度）を完全一致
の場合の評価値（この場合は、検索キー情報の文字数−
ｋ）で割って、検索キーの含有確率を求め、評価結果の
リスト７０を得る。更にソート手段Ｓ６において、この
リスト７０を含有確率の降順にソートしソート済みリス
ト８０を得る。

【００３３】このソート済みリスト８０が検索結果であ
り、その上位物件を参照することにより、検索キーが物
件中に含まれている確率が高い物件名を知ることができ
る。含有確率は、完全一致及び不完全一致の全てについ
て求まるから、あいまい一致検索を行なうことができ
る。

【００３４】また、検索キーの全情報についての全物件
探索であるから、検索もれが発生する確率は、本質的に
零であると言う特徴がある。

【００３５】また、１つの物件に対する検索キーの評価
時間は、キーの文字数のみに依存し、物件の大きさには
依存しない。従って、非常に高速に検索を行なうことが
できる。

【００３６】上記のようなデータ検索の結果、ソート済
みリスト８０においてスコア（キーの含有確率）が所定
のしきい値よりも高い物件を抽出し、これを前述の条件
式ＡまたはＢによる検索結果とする。これらの物件の番
号リストは図１の検索結果リスト格納部１４に格納さ
れ、これを基にして前述のように物件リスト条件検索部
１６において条件検索が行われる。

【００３７】上記のようなデータ検索においては、検索
の結果がソート済みリスト８０として得られるからこれ
を検索結果リスト格納部１４に格納し、格納されたデー
タに基づいて条件検索を行うことにより、複雑な条件式
の場合にも高速で検索を行うことができる。

【００３８】式（１）の近傍特徴量抽出式は上述の例の
他に種々考えることができる。例えば、 f: x→x g: (x,y)→x-y （または｜x-y ｜）とすれば、隣接文字及び一つ置きの文字の差分（または
差分の絶対値）を近傍特徴量として近傍特徴量行列を作
ることができる。また幾つかの文字列の個々の文字整数
値に対し四則演算を施すことにより近傍特徴量を取り出
してもよい。

【００３９】近傍特徴量は、各物件の全データを対象と
し取り出さなくてもよい。例えば、物件データ中の特定
の一つまたは一つ以上の整数値、特定の範囲の整数値、
或いはデータ列を構成する各バイト中の特定の１つまた
は一つ以上のビットを除外して近傍特徴量を作成（抽
出）してもよい。また日本語文書のように２バイト文字
で構成されている場合には、例えば上位バイトを除外し
て下位バイトを対象として近傍特徴量を取り出してもよ
い。

【００４０】上述の例では、近傍特徴量行列は、２５６
次のビット行列であり、これは８Kバイトに相当する。
従って、１物件のデータが１K バイト程度であるデータ
ベースでは、効率のよいシステムであるとは言えない。
そこでデータ圧縮手段Ｓ７を設けてデータ圧縮を行なっ
て構造ファイル４０の容量を減らすのがよい。

【００４１】図５にデータ圧縮法の一例を示す。この例
では、２５６次の近傍特徴量行列の各要素毎に要素値が
１である物件名４０ａ（識別コード）を１バイト／件の
データ列として蓄積する。従って、要素値が０である物
件名は不要データとして除外する。

【００４２】物件数が２５５個以上ある場合には、物件
名４０ａは１バイトで表せないので、下位の１バイトの
みを蓄積する。例えば、物件数が１万件の場合、物件名
は２バイトで表されるが、そのうちの下位１バイトを使
用する。そして物件名コードが２５５を越える毎にデー
タ列にマーカ４０ｂを挿入する。

【００４３】検索時には、検索キーの近傍特徴量の各々
に該当する構造ファイルのデータ列を取り出し、物件名
毎の出現度数テーブルを作成する。この際、マーカ４０
ｂを越える毎に物件名コードに２５５を加える。このよ
うにして作成した出現度数テーブルに基づいて図２の評
価結果リスト７０が得られる。

【００４４】なお物件名コードのデータ列が例えば全物
件中の半分以上ある場合には、その近傍特徴量行列要素
は各物件について共通であると見なして、その要素を削
除してもよい。

【００４５】上述の実施例において，正規化手段Ｓ１、
学習手段Ｓ２、正規化手段Ｓ３、検索手段Ｓ４、評価結
果出力手段Ｓ５、ソート手段Ｓ６、データ圧縮手段Ｓ７
は、コンピュータプログラムによって構成することがで
きるが、論理回路素子を用いて専用のハードウエアを構
成してもよい。

【００４６】

【発明の効果】本発明のシステムによれば、所定の条件
による検索の結果を記憶しておくので、複雑な条件によ
る検索を高速で行うことができる。また、部分的な検索
結果を再利用できるので無駄がなく、検索効率が高い。

【図面の簡単な説明】

【図１】本発明によるデータベース検索システムの一実
施例のデータフロー図である。

【図２】本発明による検索システムを適用するデータベ
ース検索システムのデータフロー図である。

【図３】近傍情報の量子化を示す図である。

【図４】記憶される情報構造を示す図である。

【図５】圧縮された近傍特徴量のデータ構成図である。

【符号の説明】

１０検索対象１２検索部１４検索結果リスト格納部１６物件リスト条件検索部１８検索キー入力部２０正規化データ３０近傍特徴量行列４０構造ファイル５０検索キー６０正規化キー７０評価結果リスト８０ソート済みリストＳ１正規化手段Ｓ２学習手段Ｓ３正規化手段Ｓ４検索手段Ｓ５評価結果出力手段Ｓ６ソート手段Ｓ７データ圧縮手段

Claims

【特許請求の範囲】

【請求項１】所定の条件により全物件検索を行う検索
手段と、前記検索手段による検索結果を記憶する検索結果記憶手
段と、前記検索結果記憶手段に記憶された検索結果を用いて条
件検索を行う条件検索手段とを具備し、前記条件検索手段は、前記検索手段による検索において
用いられた前記条件を組み合わせた条件による検索を、
前記検索結果記憶手段に記憶された検索結果を基にして
行うことを特徴とするデータベース検索システム。
【請求項２】前記システムはさらに、前記条件が入力
される入力手段を具備することを特徴とする請求項１の
データベース検索システム。
【請求項３】検索対象の物件毎にその近傍特徴量を記
憶した記憶手段と、検索キーの近傍特徴量と検索対象の上記近傍特徴量との
合致度を物件毎に求め、物件番号を合致度の降順に出力
する検索手段とを具備するデータベース検索に用いられ
ることを特徴とする請求項１のデータベース検索システ
ム。
【請求項４】検索対象のｉ番目の物件のｊ番目のデー
タ列Ｃ_i,jに関する量子化量ｘとその近傍のｋ個のデー
タ列Ｃ_i,j+1,Ｃ_i,j+2,....,Ｃ_i,j+kに関する量子化量
ｙとをｘ＝f(Ｃ_i,j）ｙ＝g(Ｃ_i,j, Ｃ_i,j+1,Ｃ_i,j+2,....,Ｃ_i,j+k) によって求め、得られたｘ、ｙの値に基づいて定められ
る記憶手段の位置にその物件の通番ｉを記憶するデータ
ベース検索に用いられることを特徴とする請求項３のデ
ータベース検索システム。