JPH0573618A - 構造体の検索方法 - Google Patents

Abstract

(57)【要約】 【構成】 検索項の集合から、少なくとも一つの質問項
に対して単一化する検索項を検索する場合、先ず、検索
項および質問項に対して、そのアルゴリズムで生成した
符号語に２ビット以上からなる最小要素を設定し、かつ
符号語生成の際、最小要素以下には分割せず、また、分
割された各要素の符号語を定める。次に、検索項および
質問項の最小要素同士の符号語の論理演算で、単一化の
候補を選択する。 【効果】 識別できる関数子の種類が広がり、フェイル
ス・ドロップの確率を削減することができる。その結
果、単一化可能な候補に単一化不可能な項が入る率を減
少させることができる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、構造を持ったデータを
対象とした情報検索を行う構造体の検索方法に関する。

【０００２】

【従来の技術】人工知能等、知識を利用した計算機処理
などでは、構造を持ったデータがその知識やデータの表
現の基本要素として多く用いられている。大量の知識や
データを必要とする、より高度で大規模な知識処理の応
用を考えた場合、構造を持ったデータの高速な検索方法
が重要である。

【０００３】演繹データベース、知識データベース等の
システムでは、通常、変数を含む項が知識表現の基本要
素として用いられることが多く、それらの演算として単
一化演算が基本演算として必須である。知識の規模が大
きくなるにつれ、大量の項に対する単一化可能な項の高
速演算（検索機構）が必須である。そこで、何等かの高
速化手法が必要であるが、項は定数と異なり、構造を持
ち、しかもその構造が可変であるため、Ｂ−treeやハッ
シュ法等の従来の高速技法を適用することができない。

【０００４】そこで、各項に対し符号語を割り当て、そ
の符号語に対して簡単な演算を施すことにより、予め単
一化可能な候補を選択する手法が提案されている。その
一つとして、例えば、Wise, M. J. & Poerts, D. M. W.
“Indexing Prolog via Superimposed Code Word and F
ield Encoded Words”.International Conference on L
ogic Programming, IEEE Computer Society Press, pp2
03-210, Feb, 1984 に記載されたＦＥＷ（フィールド・
エンコーデッド・ワード：Field Encorded Word ）法が
知られている。

【０００５】以下、上記のＦＥＷ法について説明する。
先ず、最初に、項を定義する。項は、以下のように再帰
的に定義される。 (1) 変数及び０引数関数子は項である（０引数関数子は
定数）。 (2) ｎ引数関数子（項１、項２、…、項ｎ）は項であ
る。 そして、この項に対して、変数に適当な項を割り当てた
場合、同一の項となる（単一化可能な）項を検索する。
例えば、以下、大文字を変数として、ｆ（Ｘ，ｂ，ｇ
（Ｘ））とｆ（ａ，Ｙ，ｇ（ａ））は、Ｘにａを、Ｙに
ｂを代入することにより、どちらもｆ（ａ，ｂ，ｇ
（ａ））となるため、単一化可能である。逆に、ｆ
（Ｘ，ｂ，ｇ（Ｘ））とｆ（ａ，Ｙ，ｇ（ｂ））は、単
一化不可能である。また、単一化はＰｒｏｌｏｇ等で用
いられ、論理型言語を中心とした知識表現で多く用いら
れる。

【０００６】しかし、変数の代入操作が含まれるため、
例えば、想定される質問（項）に対して、該当するデー
タ（単一化可能な項）を全て連続したように予め並べる
連続可能性のような性質すらなく、大量のデータに対し
て、従来の索引付けの方法、即ち、非構造体に関する方
法の適用が困難である。

【０００７】ＦＥＷ法の処理方法は以下のように行われ
る。検索対象となる項集合中の全ての項および問い合わ
せである項に対して符号語を生成する。即ち、ｎ−ビッ
トの符号語に対して、項が、 (1) ０−引数関数子（定数）である場合、ハッシュ関数
を用いてｎビットの符号を生成する。 (2) ｍ−引数関数子である場合、符号語をｍ＋１個の部
分に分割し、最初の部分語にｍ−引数関数子のハッシュ
値を、残りのｍ個に各引数の項の分割された符号語に対
する符号を生成する。 (3) 変数の場合、格納される項に対しては、全てのビッ
トが１である符号を、また、問い合わせの項に対して
は、全てのビットが０である符号を生成する。

【０００８】そして、検索対象となる項集合中の全ての
項の符号語と問い合わせである項の符号語を比較するこ
とで、単一化可能な候補項を抽出する。即ち、検索対象
となる項の符号語をＳ、問い合わせの項の符号語をＱと
すると、Ｑ∧Ｓ＝Ｑを満足する項が候補項である。但し
∧はビット毎の論理積を表す。次いで、候補項に関して
問い合わせの項と単一化可能かどうかを調べる。

【０００９】図２に項集合の例を、図３に符号化の例を
示す。例えば、検索対象となる項を図２の(1) 〜(5) 、
問い合わせの項を図２の（ａ）として与えた場合の検索
処理は以下のようになる。先ず、検索対象の項集合の各
項に対して、図３の例のように符号語を割り当てる。符
号語は、上述した規則に従い、定数や変数の場合は、そ
の符号をハッシュ関数ψによって求める。ｍ−引数関数
の場合は、適当な関数を用いて符号語をｍ＋１個の符号
語に分割し、最初の符号語に関数子のハッシュ値を、残
りのｍ個には各引数の符号を同様に与える。引数がまた
ｍ−引数であった場合には、更に分割が行われる。これ
以上分割ができない（割り当てられた符号語が短過ぎ
る）場合分割を行わず、例えば関数子のハッシュ値をそ
の符号とする。但し、検索対象となる項に存在する変数
については、全ビット１を与える。また、問い合わせで
ある項についても、同様に符号語を作成する。但し、問
い合わせの項に存在する変数については、全ビット０を
与える。

【００１０】図４に、検索候補の選定処理の説明図を示
す。ここで、図４（ａ）は、質問項とその符号語を示
し、図４（ｂ）は検索処理を示している。図４（ａ）に
示すように、問い合わせである項（質問項）にも符号語
Ｑが与えられる。そして、検索対象の符号語をＳ、問い
合わせの符号語Ｑにおいて、Ｑ∧Ｓ＝Ｑを満足する項が
検索候補であり、この場合は検索候補として項(1) およ
び(4) が挙げられ（図４（ｂ）参照）、そのうち項(4)
が単一化可能な項である。しかしながら、Ｑ∧Ｓ＝Ｑを
満足しても、単一化可能でない場合がある。これをfail
s drop（フェイルス・ドロップ）と呼び、図４（ｂ）に
おける(1) がこれに相当する。また、この場合、Ｑ∧Ｓ
＝Ｑを満たさない項については単一化できないことが知
られているので、単一化を試みる必要がなくその分の検
索時間の短縮が図れる。

【００１１】一方、上記のＦＥＷ法と同種の方法として
知られるＣＣＷ（Concatinated Code Word）法では、予
め定められた構造に従って、項の内部の各関数子および
変数の符号化したもの（要素符号語）を結合したものを
符号語として用いる。この場合、ハッシュ値の比較に
は、各（要素）符号語が等しいかどちらかが変数である
かを調べ、全てそうであれば、候補とする方式をとる。

【００１２】

【発明が解決しようとする課題】しかしながら、上記の
ＦＥＷ法では、比較演算として、いわゆる重ね合わせ符
号（ＳＣＷ）の方式を踏襲しているため、ｎビットの符
号語で高々Ｃｏｍ（ｎ，ｎ／２）種類の関数子しか識別
できず、分解能（符号語により識別可能なデータの種
類）が低下するという問題点を有していた。尚、ここ
で、Ｃｏｍ（ｎ，ｎ／２）とは、ｎ個の中からｎ／２個
取出す組合せの数を示す。一方、上記のＣＣＷ法は、各
ｎビットの要素符号語に対して２ｎ−１種類の識別が行
えるが、構造を予め定める必要があり、構造に合わない
場合は、その符号語が無駄になるといる問題点を有して
いた。本発明は、上記従来の問題点を解決するためにな
されたもので、符号化の分解能（精度）を向上させるこ
とのできる構造体の検索方法を提供することを目的とす
る。

【００１３】

【課題を解決するための手段】本発明の構造体の検索方
法は、項を用いたデータ表現を行う計算機システムにお
いて、検索項の集合から、少なくとも一つの質問項に対
し、該質問項と単一化する検索項を検索する構造体の検
索方法において、前記検索項および質問項に対して、該
項内の各関数子および変数に対し、そのアルゴリズムで
該項の符号語を生成する符号語生成手段と、前記符号語
生成手段で生成された質問項の符号語と、前記検索項の
符号語との論理演算結果により、単一化の可能性のある
項を判定する判定手段とを備え、前記符号語生成手段
は、符号語に２ビット以上からなる最小要素を設定し、
前記符号語の生成の際、該最小要素以下には分割せず、
かつ分割された各符号語の符号を定め、前記判定手段
は、前記検索項および質問項の最小要素同士の符号語の
論理演算に基づき単一化の候補を選択することを特徴と
するものである。

【００１４】

【作用】本発明の構造体の検索方法においては、検索項
の集合から、少なくとも一つの質問項に対して単一化す
る検索項を検索する場合、先ず、検索項および質問項に
対して、そのアルゴリズムで生成した符号語に２ビット
以上からなる最小要素を設定し、かつ符号語生成の際、
最小要素以下には分割せず、また、分割された各符号語
の符号を定める。次に、検索項および質問項の最小要素
同士の符号の論理演算で、単一化の候補を選択する。従
って、識別できる関数子の種類が広がり、フェイルス・
ドロップの確率を削減することができる。その結果、単
一化可能な候補に単一化不可能な項が入る率を減少させ
ることができる。

【００１５】

【実施例】以下、本発明の実施例を図面を用いて詳細に
説明する。先ず、本発明では、検索対象となる項の集合
（データベース）から、各項の特徴を抽出した符号語を
予め用意する。また、検索の問い合わせに対しても、そ
の質問項もしくは、質問項の集合に対して符号語を同様
に作成し、符号語の比較により検索対象の絞り込みを行
い、絞り込まれた検索対象の項とだけ質問項との単一化
処理を行う。単一化の処理に比べ、符号語の比較演算は
極めて高速に行えるため、全ての検索対象に対して単一
化処理を行った場合と比較して高速な処理が期待でき
る。

【００１６】即ち、本発明の単一化検索の処理概要は、
以下のように構成されている。 (1) 検索対象となる項の集合の各項に対して、符号語を
作成する（尚、この符号語は通常索引ファイルと呼ばれ
るファイルに格納される）。 (2) 検索対象に対する検索指示が与えられたら、その検
索条件を表現する項である質問項もしくは、その項集合
に対しても、各項に対する符号語を作成する。 (3) 検索対象の符号語と質問項の符号語により、単一化
の可能性のある組合せを抽出する。 (4) 上記(3) で絞り込まれた組合せに対して単一化処理
を行う。 更に、検索対象に対する問い合わせがある場合は、(2)
から(4) を繰り返す。これにより、前処理として、(1)
のオーバヘッドを削減することができる。

【００１７】本発明の特徴は、上記(1) および(2) にお
ける索引化の方法にある。このような索引方法では、短
い符号語を用いていかに検索対象の語の情報を表現する
かが問題となり、その結果が(3) における絞り込みの率
となり、全体の処理時間に影響を与える。単一化検索の
ための索引法であるＦＥＷでは、符号語の対する符号化
の方式として重ね合わせ符号による符号化を用いてい
る。これは、オア演算を行うために符号語を２進語で表
現した時の１の現れるビット数と０の現れるビット数が
等しくなるように符号化した時に最も選択効率が良くな
ることが知られている。

【００１８】本発明では、符号語は、２ビット以上の分
割単位を持っていると考える。符号語の分割では、分割
単位を単位として行い、分割単位を更に分割することは
できない。本発明では、符号語の与え方として以下の方
法を用いる。 (1) 与えられた項が定数のとき、その符号語に対するハ
ッシュ値を演算し、その符号語の符号とする。 (2) 与えられた項が変数であるとき、その符号語に対す
る値は０とする。 (3) 与えられた項が、ｍ−引数関数で表現されていると
きは、符号語をｍ＋１個に分割して、各分割された符号
語に対して、 最初の分割された符号語には、関数名のハッシュ値を
符号とし、 残りの符号語には各引数の項に対する符号語を本アル
ゴリズムを再帰的に適用することにより計算する。 この時、分割できなければ、関数名のハッシュ値を符号
語全体の符号語とする。

【００１９】図１に、従来技術の項で説明したＦＥＷ法
の例と同様の項に対する符号語の構成を示す。この実施
例では、最小分割単位を４ビットにとっており、一つの
符号語は８個の分割要素からなっている。尚、符号化を
行う項は、ｆ（ａ，ｈ（Ｘ，ｃ））である。

【００２０】ここで、この項のトップレベルは、２引数
ｆであるので、この符号語を３つに分割する。この場
合、最初の２要素を関数記号ｆに割り当て、残りの３要
素ずつを２つの引数に割り当てる。即ち、最初の２要素
は、ｆの８ビットへのハッシュ関数値を用いて、「０１
０１０１０１」となる。その後の３要素については、第
１引数であるａによって決定されるが、これは定数であ
るため、その１２ビットへのハッシュ値を計算して、
「１００１１０１００１０１」となる。最後の３要素に
ついては、第２引数のｈ（Ｘ，ｃ）の符号語を計算する
が、これは２引数関数ｈであるので、更に分割し、最初
の要素がｈの４ビットへのハッシュ値で「００１０」、
２番目は変数のため「０００」、最後がｃで「１００
０」となる。この場合、最小要素より細かくなるような
分割は行わない。例えば、ｆの第２引数が３引数関数で
あった場合には、分割をせずにその関数記号のハッシュ
値とするか、最初の２引数と関数記号を用いたハッシュ
値を用いるかなどの方法を取る。これらは、対象となる
項の集合や質問の特性から決定することができる。

【００２１】一方、上記の符号語に対する検索は、以下
のようになる。全ての最小要素に対して、「その最小要
素に対して符号語が全く同じであるか、どちらかが０で
ある」という条件が成立すれば候補である。即ち、各符
号語の最小要素毎に、その値が０であれば、それを変数
として扱う。変数が現れる場所には、どのような値がき
ても候補となる。図５に、符号語の比較を示す。例え
ば、図５（ａ）に示す場合は、比較する符号語の２要素
目がどちらも０でなく、かつ等しくないため、候補には
ならない。反対に、図５（ｂ）に示す場合では、全ての
要素が等しいか、どちらかが０になっているため、候補
として残ることになる。

【００２２】この際、従来のＦＥＷ法のように、Ｓ∧Ｑ
＝Ｑのような判定ではなく、比較は通常の比較であるた
め、最小要素のビット幅をｍビットとすると、ｎビット
の符号語に対して変数の符号を除いた図５（ｃ）中の式
(1) の種類の記号を識別することができる。例えば、最
小要素が４ビットの場合、８ビットの符号語に対して、
従来のＦＥＷ法では、Ｃｏｍ（８，４）＝７０通りの符
号が用いられるが、本実施例では式(2) に示すように、
２２５通りの符号を用いることができる。

【００２３】尚、上記実施例では、符号語による候補の
選定をプログラムで構成するようにしたが、これは、ハ
ードウェアで構成することも可能である。図６に、ハー
ドウェアで構成した判定手段の例を示す。ここで、図６
（ａ）は判定手段の全体回路図、図６（ｂ）は各判定回
路Ａ、Ｂの内部回路図である。このように、判定回路Ａ
と判定回路Ｂには、それぞれ符号語の各１ビットずつが
入力されるよう構成されており、また、各判定回路Ａ、
Ｂ、…、の出力がアンド回路に入力され、その論理積を
演算するようになっている。また、各判定回路Ａ、Ｂ
は、符号語同士の各ビットをそれぞれ入力するエクスク
ルーシブ−ノア（ＥX −ＮＯＲ）回路１、２、３、４
と、それぞれの符号語の各ビットを入力するノア回路
５、６と、各エクスクルーシブ−ノア回路１、２、３、
４の出力を入力するアンド回路７と、アンド回路７の出
力とノア回路５、６の出力を入力するオア回路８とから
構成されている。

【００２４】また、上記実施例では、構造体として項の
場合を例にとって説明したが、一般の、プログラム言語
等で用いられる構造体は、通常、その構造定義とデータ
が分離されているが、このような構造体を項の形で表現
することも可能であり、従って、そのような構造体にお
いても項表現に変換することで、本発明を適用すること
が可能である。更に、上記実施例では、最小分割単位を
４ビットで構成したが、これに限定されるものではな
く、２ビット以上であれば、上記実施例と同様の効果を
奏する。

【００２５】

【発明の効果】以上説明したように、本発明の構造体の
検索方法によれば、検索による候補項の選定を、検索項
および質問項の２ビット以上からなる最小要素同士の論
理演算により行うようにしたので、例えば、ｍビットの
最小要素を有するｎビットの符号語に対して識別できる
関数子の種類が、Ｃｏｍ（ｎ，ｎ／２）から図５（ｃ）
の式(1) にまで広がり、単一化の候補の選択により、フ
ェイルス・ドロップの確率を削減することができる。従
って、単一化可能な候補に単一化不可能な項の入る率を
減少させることができ、その結果、項の数を増加させ、
項の単一化による高速な検索が可能となる。

【図面の簡単な説明】

【図１】本発明の構造体の検索方法の説明図である。

【図２】項集合の説明図である。

【図３】従来の構造体の検索方法における符号化の一例
を示す説明図である。

【図４】従来の構造体の検索方法における検索候補の選
定処理の説明図である。

【図５】本発明の構造体の検索方法における符号語の比
較処理の説明図である。

【図６】本発明の構造体の検索方法における判定手段の
他の実施例を示す構成図である。

Claims (1)

【特許請求の範囲】
1. 【請求項１】 項を用いたデータ表現を行う計算機シス
   テムにおいて、検索項の集合から、少なくとも一つの質
   問項に対し、該質問項と単一化する検索項を検索する構
   造体の検索方法において、 前記検索項および質問項に対して、該項内の各関数子お
   よび変数に対し、そのアルゴリズムで該項の符号語を生
   成する符号語生成手段と、 前記符号語生成手段で生成された質問項の符号語と、前
   記検索項の符号語との論理演算結果により、単一化の可
   能性のある項を判定する判定手段とを備え、 前記符号語生成手段は、符号語に２ビット以上からなる
   最小要素を設定し、前記符号語の生成の際、該最小要素
   以下には分割せず、かつ分割された各符号語の符号を定
   め、 前記判定手段は、前記検索項および質問項の最小要素同
   士の符号語の論理演算に基づき単一化の候補を選択する
   ことを特徴とする構造体の検索方法。