JPH06124304A - 拡張項のための重ね合わせ符号を用いた検索方法 - Google Patents

Abstract

(57)【要約】 ［目的］ 拡張項に対して符号化の手段を導入し、パタ
ーン照合による索引検索として、ワイルドカードまたは
変数に適当な拡張項をあてはめた際に、一致するものを
求めることにより、高速な検索を可能とする。 ［構成］ 索引作成処理１０により、拡張項の各属性名
と属性値の組及び関数子に対してハッシュ値を求め、そ
れらのハッシュ値の論理和演算により、検索対象となる
集合の索引値と問い合わせの索引値とを予め作成してお
く。索引作成処理１０で作成された集合の索引値と問い
合わせの索引値との論理演算結果により、パターン照合
の可能性のある拡張項を判定する拡張項判定処理２０を
行った後、パターン照合処理３０を行う。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、構造をもったデータを
対象とした情報検索を高速処理する拡張項のための重ね
合わせ符号を用いた検索方法に関するものである。

【０００２】

【従来の技術】従来、このような分野の技術としては、
例えば次のような文献に記載されるものがあった。

【０００３】文献１；情報処理学会第３５回（昭和６２
年後期）全国大会予稿集、森田他「ＭＰＰＭを用いた知
識ベースマシン（３）」２Ｃ−７ 文献２；情報処理学会第３６回（昭和６３年前期）全国
大会予稿集、仲瀬等「知識ベースマシンＭｕ−Ｘ
（４）」５Ｅ−７ 文献３；情報処理学会第７８回データベース・システム
研究会誌（１９９０−７−２０）横田「演繹・オブジェ
クト指向データベース言語 Ｊｕａｎの概要（Ｔｈｅ
Ｏｕｔｌｉｎｅ ｏｆ ａ Ｄｅｄｕｃｔｉｖｅ ａｎ
ｄ Ｏｂｊｅｃｔ−Ｏｒｉｅｎｔｅｄ Ｄａｔａｂａｓ
ｅ Ｌａｎｇｕａｇｅ Ｊｕａｎ）」 一般に、演繹データベース、知識ベース等のシステムで
は、通常、変数を含む項を知識表現の基本要素として用
いている。

【０００４】近年、Ｐｒｏｌｏｇ等で用いられている単
純な項だけでなく、ψ項、素性構造、拡張項等、引数を
その位置ではなく、属性名等を用いて順不同で不定数個
記述できるように拡張された項が広く用いられるように
なってきた。この拡張項を要素とする集合から、パター
ン照合する拡張項を検索する処理は、演繹データベー
ス、知識ベース等のシステムにおいて基本処理として頻
繁に用いられる。しかし、この拡張項に対して、検索処
理の高速化を行う技法は知られていない。

【０００５】もっとも近いものとして、従来、前記文献
に記載されているように、項の単一化検索における高速
化技法がある。この単一化検索とは、知識の中にある項
集合から単一化可能である項を検索することであるが、
知識の規模が大きくなるにつれ、その単一化をすべての
知識に対して行うのではなく、予め単一化の可能性のあ
る検索候補を選択することが行われる。この項の単一化
検索で扱う項は、通常の定数と異なり、構造を持ち、し
かもその構造が可変である。このため、構造体内の各デ
ータのハッシュ値（符号）を構造に従って重ね合わせた
符号（ＳＳＣＷ；Ｓｔｒｕｃｔｕｒａｌ Ｓｕｐｅｒｉ
ｍｐｏｓｅｄ Ｃｏｄｅ Ｗｏｒｄ）や、符号に位置情
報を加えて重ね合わせる符号等の符号化を行い、符号の
上で予め単一化の可能性を検査することにより、高速に
単一化処理を行う方法が知られている。以下、その方法
を図２及び図３を参照しつつ説明する。

【０００６】図２は従来の索引（索引値集合）の作成を
説明する図、及び図３は従来の検索処理を説明する図で
ある。

【０００７】まず始めに、項を定義する。項は、次のよ
うに定義される。

【０００８】項：＝関数子（項１，項２，…，項ｎ） 但し、０引数の場合、項は関数子（定数）のみとなる
が、この場合も関数子（定数）は項である。

【０００９】この項に対して、変数に適当な項を割り当
てた場合、同一となる項（単一化可能な項）を検索す
る。処理方法は、以下のようである。

【００１０】検索対象となる項集合中のすべての項及び
被検索対象となる項（問い合わせである項）に対して索
引値を生成する。項の索引値は、関数子のハッシュ値の
ビットフィールドで、項１，項２，…，項ｎのＳＳＣＷ
によるビットフィールドを覆うように配置して、両者を
論理和演算（ＯＲ演算）することにより生成する。ここ
で、検索対象となる項及び問い合わせである項の索引値
を求める際、検索対象となる項に出現する変数について
は全ビット“１”、問い合わせである項に現れる変数に
ついては全ビット“０”のハッシュ値を与える。

【００１１】検索対象となる項集合中のすべての項の索
引値と、問い合わせである項の索引値とを比較すること
で、単一化可能な候補項を抽出する。検索対象となる項
の索引値をＳ、問い合わせの索引値をＱとすると、Ｑ∧
Ｓ＝Ｑを満足する項が候補項である。候補項に関して、
問い合わせの項と単一化可能かどうか調べる。

【００１２】例えば、検索対象となる項を図２の（ａ）
の（１）〜（５）、問い合わせの項を図３の（ａ）とし
て与えた場合の検索処理は次のようになる。

【００１３】項の関数子及び引数１，引数２をそれぞれ
８ビット，４ビット，４ビットでハッシュ化（符号化）
する。ハッシュした結果は、図１の（ｂ）のようにな
る。但し、検索対象となる項の引数に存在する変数につ
いては、全ビット“１”のハッシュ値を与える。引数１
と引数２のハッシュ値の並び（８ビット）を関数子のハ
ッシュ値（８ビット）にＯＲ演算することで、項の索引
値を生成する。図２（ａ）の検索対象となる項（１）〜
（５）に関して各項の索引値は図２の（ｃ）となる。

【００１４】次に、問い合わせである項について索引値
を作成する。結果は、図３の（ｂ）となる。但し、問い
合わせの引数に存在する変数については、全ビット
“０”のハッシュ値を与える。検索対象の索引値Ｓ、及
び問い合わせの索引値Ｑにおいて、Ｑ∧Ｓ＝Ｑを満足す
る項が検索候補であり、この場合、図３の（ｃ）に示す
ように、検索候補として項（２），（４）が挙げられ、
その内、項（２）が単一化可能な項である。

【００１５】このように、比較的、単純（高速）な論理
演算で候補を絞り込むことにより、高速な検索が行え
る。

【００１６】

【発明が解決しようとする課題】しかしながら、従来の
方法では、次のような課題があった。

【００１７】近年、Ｐｒｏｌｏｇ等で用いられている単
純な項だけでなく、ψ項、素性構造、拡張項等、引数を
その位置ではなく、属性名等を用いて順不同で不定数個
記述できるように拡張された項が、広く用いられるよう
になってきた。これら、拡張項を要素とする集合から、
同一である拡張項を検索する処理は重要である。ところ
が、従来、この拡張項に対しては、検索の高速化を行う
技法が知られていない。

【００１８】構造体の検索方法としては、前述の項に対
する単一化検索用のＳＳＣＷを用いた方法が知られてい
る。しかし、ＳＳＣＷを用いた方法では、対象とするも
のが、Ｐｒｏｌｏｇでいう項であり、引数の数及び位置
が固定されており、拡張項等に適用できないため、技術
的に充分満足のゆく検索方法を得ることが困難であっ
た。

【００１９】本発明は前記従来技術が持っていた課題と
して、拡張項に対して検索の高速化を行うことが困難な
点について解決した拡張項のための重ね合わせ符号を用
いた検索方法を提供するものである。

【００２０】

【課題を解決するための手段】本発明は前記課題を解決
するために、データ／知識を構造体である拡張項で表現
するシステムにおける該拡張項は、任意の個数からなる
属性名、及び属性値の組を含み、該属性名及び属性値の
部分に該拡張項を記述したネスト構造が扱え、検索条件
としては、前記属性名、属性値及び関数子に対してワイ
ルドカードまたは変数を与え、その属性名、属性値及び
関数子と照合する拡張項の項集合を検索する検索方法に
おいて、索引値を次のように構成する。

【００２１】即ち、前記関数子、属性名及び属性値のビ
ットフィールドを定め、該属性名と属性値のビットフィ
ールドの並びを該関数子のビットフィールドで覆うよう
に配置してそれぞれのビットフィールド中へのハッシュ
を行い、該属性名または属性値が拡張項でかつそのビッ
トフィールドが十分な大きさである場合には、該属性名
または属性値のビットフィールドを、該属性名または属
性値の関数子と属性名と属性値とのビットフィールドに
より索引値を構成する。

【００２２】そして、索引作成処理により、前記拡張項
の各属性名と属性値の組及び関数子に対してハッシュ値
を求め、それらのハッシュ値の論理和演算により、検索
対象となる集合に対する前記構成の索引値と問い合わせ
に対する前記構成の索引値とを予め作成しておく。次
に、前記索引作成処理で作成された集合の索引値と問い
合わせの索引値との論理演算結果により、パターン照合
の可能性のある前記拡張項を判定する拡張項判定処理を
行った後、パターン照合を行うようにしている。

【００２３】

【作用】本発明によれば、以上のように検索方法を構成
したので、索引作成処理により、予め集合の索引値と問
い合わせの索引値を作成しておき、その作成結果を拡張
項判定処理へ与える。拡張項判定処理では、パターン照
合の可能性のある拡張項を判定して該拡張項の個数を絞
り込んだ後、パターン照合を行わせる。

【００２４】つまり、拡張項に対して符号化の手段を導
入し、パターン照合による索引検索として、ワイルドカ
ードまたは変数に適当な拡張項をあてはめた際に、一致
するものを求めることにより、検索の高速化を図る。従
って、前記課題を解決できるのである。

【００２５】

【実施例】図１は、本発明の実施例を示すもので、拡張
項のための重ね合わせ符号を用いた検索方法の概略のフ
ローチャートである。

【００２６】まず、本実施例で扱う拡張項のシンタック
ス（Ｓｙｎｔａｘ）を示す。拡張項は、引数をその位置
でなく、属性名等を用いて、順不同、複数個記述できる
ように拡張された項であり、拡張項を次のシンタックス
として定義する。

【００２７】＜拡張項＞：：＝ ＜関数子＞［“［”＜
属性＞リスト“］”］ ＜属性＞：：＝ ＜属性名＞“＝”＜属性値＞ ＜属性名＞：：＝ ＜拡張項＞ ＜属性値＞：：＝ ＜拡張項＞ ｜“｛”＜属性値＞リスト“｝” 但し、＜拡張項＞において、＜属性＞リストがない場合
（０引数の場合）、＜関数子＞のみとなるが、この＜関
数子＞は定数を含む。

【００２８】このシンタックスからわかるように、本拡
張項では、次の特徴がある。

【００２９】（１） ＜属性＞リストにより、順不同、
不定数個の引数の記述が可能である。 （２） 属性の属性名及び属性値の部分に拡張項が記述
できるので、拡張項をネスト（ｎｅｓｔ，組込み）した
構造が扱える。 （３） 拡張項を用いてルール等を記述する場合、関数
子、属性名、及び属性値として変数が用いられる。

【００３０】本実施例では、図１に示すように、索引作
成処理１０により、予め検索対象となる拡張項の集合及
びその拡張項の属性名、属性値、及び関数子の部分にワ
イルドカードまたは変数を与えた問い合わせに対して索
引を作成する。そして、拡張項判定処理２０により、索
引同士がパターン照合する拡張項を検索した後、パター
ン照合処理３０を行う。

【００３１】索引作成処理１０では、ステップ１１で、
関数子、属性名、及び属性値のビットフィールドの割り
当てを行い、各属性名のハッシュ値の計算（ステップ１
２−１）、各属性値のハッシュ値の計算（ステップ１２
−２）、及び関数子のハッシュ値の計算（ステップ１２
−３）を行う。

【００３２】各属性名のハッシュ値の計算を行った後、
ステップ１３−１において、属性名が拡張項か否かの判
定を行う（ステップ１３ａ）。拡張項ならば、属性名の
ビットフィールドに対する索引値の計算を行い（ステッ
プ１３ｂ）、拡張項でないならば、属性名のハッシュを
行う（ステップ１３ｃ）。各属性値のハッシュ値の計算
後の処理は、ステップ１３−１の属性名と同じ処理を行
う。

【００３３】ステップ１２−３，１３−１，１３−２の
各処理結果は、ステップ１４で、論理和演算が行われ、
集合の索引値（ステップ１５−１）と、問い合わせの索
引値（ステップ１５−２）とが求められる。

【００３４】このような索引作成処理１０の処理結果に
基づき、拡張項判定処理２０をした後、パターン照合処
理３０による索引検索を行うことにより、高速な検索が
可能となる。

【００３５】以下、図４〜図１２を参照しつつ、図１に
おける各処理１０，２０，３０の内容を詳細に説明す
る。

【００３６】例えば、検索対象及び問い合わせの拡張項
を示す図４において、（１）〜（８）の検索対象となる
拡張項に対して、（９）に示す問い合わせである拡張項
とパターン照合する拡張項を検索する処理は、以下のよ
うになる。

【００３７】まず、図４に示す検索対象である拡張項
（１）〜（８）について、各々の索引値を求める。ある
拡張項が、前記のシンタックスに従い、 拡張項：＝関数子（属性名１＝属性値１，属性名２＝属
性値２，…，属性名ｎ＝属性値ｎ） で定義されているとする。この索引値は、図５の索引値
の構成に示すように、関数子及び各引数の属性名、及び
属性値（属性名１，属性値１，属性名２，属性値２，
…，属性名ｎ，属性値ｎ）をその索引値のビットフィー
ルド中にハッシュし、そのハッシュ値をＯＲ演算するこ
とで、求められる。

【００３８】図４に示す（１）〜（８）の索引値の構成
については、関数子、属性名、及び属性値のビットフィ
ールドをそれぞれ１８ビット、８ビット、８ビットのハ
ッシュ値とし、属性名と属性値のビットフィールドの並
びを関数子のビットフィールドで覆うように配置する。

【００３９】属性名（属性値）は、拡張項のシンタック
スで示したように、次の２つの形式、（ａ）値が唯一で
ある属性名（属性値）、及び（ｂ）値が拡張項である属
性名（属性値）が存在し、さらに属性値についてのみ、
（ｃ）値が属性値リスト（集合）である属性値、が存在
するため、それぞれ次のようにハッシュする。

【００４０】（ａ） 値が唯一である場合には、その値
を８ビットでハッシュし、そのハッシュ値を属性名（属
性値）のビットフィールドへ割り当てる。

【００４１】（ｂ） 値が拡張項である場合は、その属
性名（属性値）のビットフィールドとして、さらにその
属性名（属性値）の関数子、属性名と属性値のビットフ
ィールドを割り当てる。例えば、図４の（１）の属性ｗ
ｏｒｋｓ＝ｃｓ［ｄｎａｍｅ＝“ＣＳ”，ｍａｎａｇｅ
ｒ＝ｐｈｉｌ］中の属性値ｃｓ［ｄｎａｍｅ＝“Ｃ
Ｓ”，ｍａｎａｇｅｒ＝ｐｈｉｌ］については、ｃｓの
ビットフィールドを８ビット、ｄｎａｍｅ，“ＣＳ”，
ｍａｎａｇｅｒ，ｐｈｉｌのビットフィールドをそれぞ
れ３ビットとし、それぞれをハッシュする。

【００４２】（ｃ） 値が属性値リスト（集合）である
場合には、各属性値の要素を８ビットでハッシュし、各
要素のハッシュ値のＯＲ演算の結果を属性値のビットフ
ィールドへ割り当てる。例えば、図４の（１）の属性ｈ
ｏｂｂｙ＝｛ｍｕｓｉｃ，ｓｐｏｒｔ｝のハッシュ値ｈ
（ｈｏｂｂｙ＝｛ｍｕｓｉｃ，ｓｐｏｒｔ｝）は、ｈ
（ｍｕｓｉｃ）とｈ（ｓｐｏｒｔ）のＯＲ演算の結果で
ある。

【００４３】検索対象である拡張項の関数子、属性名、
属性値に存在する変数のハッシュ値については、それぞ
れのビットフィールドの長さを持つ、全ビット“１”の
ビット列を与える。

【００４４】図６に、拡張項（１）〜（８）に存在する
関数子のハッシュ値を示す。図７に、拡張項（１）〜
（８）に存在する属性名のハッシュ値を（ａ）値が唯一
である属性名と、（ｂ）値が拡張項である属性名の２つ
に場合分けして求めた結果を示す。図８に、拡張項
（１）〜（８）に存在する属性値のハッシュ値を（ａ）
値が唯一である属性値、（ｂ）値が拡張項である属性
値、及び（ｃ）値が属性値リスト（集合）である属性
値、の３つに場合分けして求めた結果を示す。図９及び
図１０に、図６〜図８を用いて求めた拡張項（１）〜
（８）についての索引値を示す。

【００４５】次に、問い合わせである拡張項について索
引値を作成する。

【００４６】図４の（９）に示すように、問い合わせに
存在する関数子を１８ビット、属性名及び属性値を８ビ
ットでハッシュした値を求める。その結果を図１１の
（ａ）に示す。但し、問い合わせである拡張項の関数
子、属性名及び属性値に存在する変数のハッシュ値につ
いては、それぞれのビットフィールドの長さを持つ、全
ビット“０”のビット列を与える。問い合わせである拡
張項の索引値を求める。その結果を図１１の（ｂ）に示
す。

【００４７】検索対象の索引値Ｓ、問い合わせの索引値
Ｑにおいて、Ｑ∧Ｓ＝Ｑを満足する項がパターン照合の
可能性のある（検索候補である）項である。この場合、
図１２の検索処理に示すように、この検索候補として、
（１），（８）が挙げられ、その内、（１）がパターン
照合可能な項である。Ｑ∧Ｓ≠Ｑを満たす項について
は、パターン照合できないとしてパターン照合を試みな
いので、その分の検索時間の短縮が図れ、高速な検索が
可能となる。

【００４８】なお、本発明は図示の実施例に限定され
ず、例えば図１の索引作成処理１０を他のステップで実
行したり、図４〜図１２に示す拡張項を他の内容にする
等、種々の変形が可能である。

【００４９】

【発明の効果】以上詳細に説明したように、本発明によ
れば、索引作成処理により、予め集合の索引値及び問い
合わせの索引値を作成しておき、拡張項判定処理を行っ
た後にパターン照合を行う。このように、索引を用いる
ことで、パターン照合の可能性のある拡張項の個数を絞
り込むことができるため、絞り込まれない項については
パターン照合可能かどうかの試みを行わない。従って、
その分の検索時間の短縮が図れ、高速な検索が可能とな
る。

【図面の簡単な説明】

【図１】本発明の実施例の検索方法を示す概略のフロー
チャートである。

【図２】従来の索引（索引値集合）の作成を説明する図
である。

【図３】従来の検索処理を説明する図である。

【図４】本実施例の検索対象及び問い合わせの拡張項を
示す図である。

【図５】本実施例の索引値の構成を説明する図である。

【図６】本実施例の関数子のハッシュ値を示す図であ
る。

【図７】本実施例の属性名のハッシュ値を説明する図で
ある。

【図８】本実施例の属性値のハッシュ値を説明する図で
ある。

【図９】本実施例の各拡張項（１）〜（６）の索引値を
説明する図である。

【図１０】本実施例の各拡張項（７）〜（８）の索引値
を説明する図である。

【図１１】本実施例の問い合わせである拡張項の索引値
を説明する図である。

【図１２】本実施例の検索処理を説明する図である。

【符号の説明】

１０ 索引作成処理 １１ 関数子、属性名及び属性値のビットフィール
ドの割り当て １２−１ 各属性名のハッシュ値の計算 １２−２ 各属性値のハッシュ値の計算 １２−３ 関数子のハッシュ値の計算 １４ 論理和演算 １５−１ 集合の索引値 １５−２ 問い合わせの索引値 ２０ 拡張項判定処理 ３０ パターン照合処理

【手続補正書】

【提出日】平成４年７月８日

【手続補正３】

【補正対象書類名】明細書

【補正対象項目名】００３５

【補正方法】変更

【補正内容】

【００３５】以下、図４〜図１３を参照しつつ、図１に
おける各処理１０，２０，３０の内容を詳細に説明す
る。

【手続補正４】

【補正対象書類名】明細書

【補正対象項目名】００４４

【補正方法】変更

【補正内容】

【００４４】図６に、拡張項（１）〜（８）に存在する
関数子のハッシュ値を示す。図７に、拡張項（１）〜
（８）に存在する属性名のハッシュ値を（ａ）値が唯一
である属性名と、（ｂ）値が拡張項である属性名の２つ
に場合分けして求めた結果を示す。図８に、拡張項
（１）〜（８）に存在する属性値のハッシュ値を（ａ）
値が唯一である属性値、（ｂ）値が拡張項である属性
値、及び（ｃ）値が属性値リスト（集合）である属性
値、の３つに場合分けして求めた結果を示す。図９及び
図１１に、図６〜図８を用いて求めた拡張項（１）〜
（８）についての索引値を示す。

【手続補正５】

【補正対象書類名】明細書

【補正対象項目名】００４６

【補正方法】変更

【補正内容】

【００４６】図４の（９）に示すように、問い合わせに
存在する関数子を１８ビット、属性名及び属性値を８ビ
ットでハッシュした値を求める。その結果を図１２の
（ａ）に示す。但し、問い合わせである拡張項の関数
子、属性名及び属性値に存在する変数のハッシュ値につ
いては、それぞれのビットフィールドの長さを持つ、全
ビット“０”のビット列を与える。問い合わせである拡
張項の索引値を求める。その結果を図１２の（ｂ）に示
す。

【手続補正６】

【補正対象書類名】明細書

【補正対象項目名】００４７

【補正方法】変更

【補正内容】

【００４７】検索対象の索引値Ｓ、問い合わせの索引値
Ｑにおいて、Ｑ∧Ｓ＝Ｑを満足する項がパターン照合の
可能性のある（検索候補である）項である。この場合、
図１３の検索処理に示すように、この検索候補として、
（１），（８）が挙げられ、その内、（１）がパターン
照合可能な項である。Ｑ∧Ｓ≠Ｑを満たす項について
は、パターン照合できないとしてパターン照合を試みな
いので、その分の検索時間の短縮が図れ、高速な検索が
可能となる。

【手続補正７】

【補正対象書類名】明細書

【補正対象項目名】００４８

【補正方法】変更

【補正内容】

【００４８】なお、本発明は図示の実施例に限定され
ず、例えば図１の索引作成処理１０を他のステップで実
行したり、図４〜図１３に示す拡張項を他の内容にする
等、種々の変形が可能である。

【手続補正８】

【補正対象書類名】明細書

【補正対象項目名】図面の簡単な説明

【補正方法】変更

【補正内容】

【図面の簡単な説明】

【図１】本発明の実施例の検索方法を示す概略のフロー
チャートである。

【図２】従来の索引（索引値集合）の作成を説明する図
である。

【図３】従来の検索処理を説明する図である。

【図４】本実施例の検索対象及び問い合わせの拡張項を
示す図である。

【図５】本実施例の索引値の構成を説明する図である。

【図６】本実施例の関数子のハッシュ値を示す図であ
る。

【図７】本実施例の属性名のハッシュ値を説明する図で
ある。

【図８】本実施例の属性値のハッシュ値を説明する図で
ある。

【図９】本実施例の各拡張項（１）〜（３）の索引値を
説明する図である。

【図１０】本実施例の各拡張項（４）〜（６）の索引値
を説明する図である。

【図１１】本実施例の各拡張項（７）〜（８）の索引値
を説明する図である。

【図１２】本実施例の問い合わせである拡張項の索引値
を説明する図である。

【図１３】本実施例の検索処理を説明する図である。

【符号の説明】 １０ 索引作成処理 １１ 関数子、属性名及び属性値のビットフィール
ドの割り当て １２−１ 各属性名のハッシュ値の計算 １２−２ 各属性値のハッシュ値の計算 １２−３ 関数子のハッシュ値の計算 １４ 論理和演算 １５−１ 集合の索引値 １５−２ 問い合わせの索引値 ２０ 拡張項判定処理 ３０ パターン照合処理

【手続補正９】

【補正対象書類名】図面

【補正対象項目名】図９

【補正方法】変更

【補正内容】

【図９】

【手続補正１０】

【補正対象書類名】図面

【補正対象項目名】図１０

【補正方法】変更

【補正内容】

【図１０】

【手続補正１１】

【補正対象書類名】図面

【補正対象項目名】図１１

【補正方法】変更

【補正内容】

【図１１】

【手続補正１２】

【補正対象書類名】図面

【補正対象項目名】図１２

【補正方法】変更

【補正内容】

【図１２】

【手続補正１３】

【補正対象書類名】図面

【補正対象項目名】図１３

【補正方法】追加

【補正内容】

【図１３】

Claims (1)

【特許請求の範囲】
1. 【請求項１】 データ／知識を構造体である拡張項で表
   現するシステムにおける該拡張項は、任意の個数からな
   る属性名、及び属性値の組を含み、該属性名及び属性値
   の部分に該拡張項を記述したネスト構造が扱え、検索条
   件としては、前記属性名、属性値及び関数子に対してワ
   イルドカードまたは変数を与え、その属性名、属性値及
   び関数子と照合する拡張項の項集合を検索する検索方法
   において、 前記関数子、属性名及び属性値のビットフィールドを定
   め、該属性名と属性値のビットフィールドの並びを該関
   数子のビットフィールドで覆うように配置してそれぞれ
   のビットフィールド中へのハッシュを行い、該属性名ま
   たは属性値が拡張項でかつそのビットフィールドが十分
   な大きさである場合には、該属性名または属性値のビッ
   トフィールドを、該属性名または属性値の関数子と属性
   名と属性値とのビットフィールドにより索引値を構成
   し、 索引作成処理により、前記拡張項の各属性名と属性値の
   組及び関数子に対してハッシュ値を求め、それらのハッ
   シュ値の論理和演算により、検索対象となる集合に対す
   る前記構成の索引値と問い合わせに対する前記構成の索
   引値とを予め作成しておき、 前記索引作成処理で作成された集合の索引値と問い合わ
   せの索引値との論理演算結果により、パターン照合の可
   能性のある前記拡張項を判定する拡張項判定処理を行っ
   た後、 パターン照合を行うことを特徴とする拡張項のための重
   ね合わせ符号を用いた検索方法。