JPH01276237A - 単一化候補項の選択装置 - Google Patents
単一化候補項の選択装置Info
- Publication number
- JPH01276237A JPH01276237A JP63102609A JP10260988A JPH01276237A JP H01276237 A JPH01276237 A JP H01276237A JP 63102609 A JP63102609 A JP 63102609A JP 10260988 A JP10260988 A JP 10260988A JP H01276237 A JPH01276237 A JP H01276237A
- Authority
- JP
- Japan
- Prior art keywords
- characteristic value
- term
- value
- bits
- bit
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000006243 chemical reaction Methods 0.000 claims description 5
- 238000000034 method Methods 0.000 description 21
- 238000010586 diagram Methods 0.000 description 4
- 230000000694 effects Effects 0.000 description 3
- 230000000873 masking effect Effects 0.000 description 2
- 239000000284 extract Substances 0.000 description 1
Landscapes
- Devices For Executing Special Programs (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
め集合から単一化候補項を選択する技術に関わり、特に
検索項及び条件項を所定ビットの特性値に変−換して単
一化可能性を検証する単一化候補項の選択装置に関する
。
検索項及び条件項を所定ビットの特性値に変−換して単
一化可能性を検証する単一化候補項の選択装置に関する
。
（従来の技術）
知識ベースシステム、ファイルシステム等においては、
変数を含む項データの単一化を伴う検索に際し、検索対
象を絞り込んで検索効率の向上を図るため、予め検索対
象となる項データの集合から検索項データと単一化可能
性のある単一化候補項を選択することが行われる。この
種の選択処理は、高速に行われることが前提条件となる
ため、従来より検索項データを高速演算処理に適した形
態に変換することが種々行われている。その一つにＦ
Ｅ Ｗ （ｆ’１ｅｌｄ ｅｎｃｏｄｅ ｗｏｒｄ ）
法が知られている（Ｗｌｓｅ、Ｍ、Ｊ、、Ｐｏｗｅｒｓ
、Ｄ、ＭＪ、、−Ｉｎｄｅｘｉｎｇ ＰＲＯＬＯＧＣｌ
ａｕｓｅｓ ｖｉａ Ｓｕｐｅｒｉｍｐｏｓｅｄ Ｃｏ
ｄｅ ｗｏｒｄ ａｎｄＦｉｅｌｄ Ｅｎｃｏｄｅ Ｗ
ｏｒｄｓ’、Ｉｎ Ｐｒｏｃｅｅｄｉｎｇ ｏｆ ｔｈ
ｅＩＥＥＥ Ｃ０ｎｒｅｒｅｎＣｅ Ｏｒｌ Ｌｏｇｉ
ｃ ＰｒＯｇｒａｏ＋Ｉｎｇ、ＡｔｒａｎｔｉＣ索項と
して、 ｆ （ａ） ｆ （ａ、Ｘ） ｆ （ａ、 ｇ （ｂ） ） の３つの項が知識ベースに格納され、条件項として、 ｆ （Ｙ、ｂ） が与えられたとする。なお、ここで各項を構成する要素
のうち、小文字で記述されたｆ、ａ、ｂは定数、大文字
で記述されたＸ、Ｙは変数であり、カッコ内の要素は、
左括弧の左に付された要素の引数である。
変数を含む項データの単一化を伴う検索に際し、検索対
象を絞り込んで検索効率の向上を図るため、予め検索対
象となる項データの集合から検索項データと単一化可能
性のある単一化候補項を選択することが行われる。この
種の選択処理は、高速に行われることが前提条件となる
ため、従来より検索項データを高速演算処理に適した形
態に変換することが種々行われている。その一つにＦ
Ｅ Ｗ （ｆ’１ｅｌｄ ｅｎｃｏｄｅ ｗｏｒｄ ）
法が知られている（Ｗｌｓｅ、Ｍ、Ｊ、、Ｐｏｗｅｒｓ
、Ｄ、ＭＪ、、−Ｉｎｄｅｘｉｎｇ ＰＲＯＬＯＧＣｌ
ａｕｓｅｓ ｖｉａ Ｓｕｐｅｒｉｍｐｏｓｅｄ Ｃｏ
ｄｅ ｗｏｒｄ ａｎｄＦｉｅｌｄ Ｅｎｃｏｄｅ Ｗ
ｏｒｄｓ’、Ｉｎ Ｐｒｏｃｅｅｄｉｎｇ ｏｆ ｔｈ
ｅＩＥＥＥ Ｃ０ｎｒｅｒｅｎＣｅ Ｏｒｌ Ｌｏｇｉ
ｃ ＰｒＯｇｒａｏ＋Ｉｎｇ、ＡｔｒａｎｔｉＣ索項と
して、 ｆ （ａ） ｆ （ａ、Ｘ） ｆ （ａ、 ｇ （ｂ） ） の３つの項が知識ベースに格納され、条件項として、 ｆ （Ｙ、ｂ） が与えられたとする。なお、ここで各項を構成する要素
のうち、小文字で記述されたｆ、ａ、ｂは定数、大文字
で記述されたＸ、Ｙは変数であり、カッコ内の要素は、
左括弧の左に付された要素の引数である。
まず、これら検索項及び条件項は、それぞれ適当なビッ
ト数の特性値に変換される。これら特性値が例えば１６
ビツトであるとすると、まず、検索項ｆ （ａ）は、引
数が１つの関数ｆと定数ａとから構成されるので、第３
図（ａ）に示すように、１６ビツトのフィールドを例え
ば１０ビツトと ６ビツトとに分割し、上位１０ビツト
に関数ｆのアスキーコード６６Ｈ（１６進゛数表示）を
割当て、下位６ビー数Ｘとから構成されるので、第３図
（ｂ）に示すよ□うに、１６ビツトのフィールドを例え
ば ８ビツト、４ビツト及び ４ビツトに分割し、上位
８ビツトに一関数ｆのアスキーコード６６Ｈを割当て
、真中の４ビツトに定数ａのアスキーコード６、ＩＨの
下位４ビツトであるＩＨを割当て、更に変数Ｘに対応す
る下位４ビツトには全て１を割当てる。同様に、検索項
ｆ （ａ、 ｇ （ｂ） ）は、引数が２つの関数ｆ
、定数ａ、引数が１つの定数ｇ１及び定数すより構成さ
れるので、第３図（Ｃ）に示すように、１６ビツトのフ
ィールドを例えば８ビツト、 ４ビツト、 ２ビツト及
び ２ビツトに分割し、上位 ８ビツトに関数ｆのアス
キーコード６６Ｈを割当て、次の４ビツトに定数ａのア
スキーコード６１Ｈの下位４ビツトであるＩＨを割当て
、以下、それに続く ２ビツト、２ビツトに、それぞれ
定数ｇ、ｂのアスキーコードの下位２ビット３Ｈ，２Ｈ
をそれぞれ割当てる。これにより、各検索項の特性値１
゜２．３を得る。
ト数の特性値に変換される。これら特性値が例えば１６
ビツトであるとすると、まず、検索項ｆ （ａ）は、引
数が１つの関数ｆと定数ａとから構成されるので、第３
図（ａ）に示すように、１６ビツトのフィールドを例え
ば１０ビツトと ６ビツトとに分割し、上位１０ビツト
に関数ｆのアスキーコード６６Ｈ（１６進゛数表示）を
割当て、下位６ビー数Ｘとから構成されるので、第３図
（ｂ）に示すよ□うに、１６ビツトのフィールドを例え
ば ８ビツト、４ビツト及び ４ビツトに分割し、上位
８ビツトに一関数ｆのアスキーコード６６Ｈを割当て
、真中の４ビツトに定数ａのアスキーコード６、ＩＨの
下位４ビツトであるＩＨを割当て、更に変数Ｘに対応す
る下位４ビツトには全て１を割当てる。同様に、検索項
ｆ （ａ、 ｇ （ｂ） ）は、引数が２つの関数ｆ
、定数ａ、引数が１つの定数ｇ１及び定数すより構成さ
れるので、第３図（Ｃ）に示すように、１６ビツトのフ
ィールドを例えば８ビツト、 ４ビツト、 ２ビツト及
び ２ビツトに分割し、上位 ８ビツトに関数ｆのアス
キーコード６６Ｈを割当て、次の４ビツトに定数ａのア
スキーコード６１Ｈの下位４ビツトであるＩＨを割当て
、以下、それに続く ２ビツト、２ビツトに、それぞれ
定数ｇ、ｂのアスキーコードの下位２ビット３Ｈ，２Ｈ
をそれぞれ割当てる。これにより、各検索項の特性値１
゜２．３を得る。
一方、条件項ｆ （Ｙ、ｂ）は、引数が２つの関６６
Ｈを割当て、変数Ｙに対応する真中の４ビツトには全て
０を割当て、下位４ビツトには定数ｂに対応するコード
２Ｈを割当てる。これにより条件項の特性値４を得る。
Ｈを割当て、変数Ｙに対応する真中の４ビツトには全て
０を割当て、下位４ビツトには定数ｂに対応するコード
２Ｈを割当てる。これにより条件項の特性値４を得る。
このように各検索類及び条件項の特性値１〜４が得られ
たら、検索類の特性値をＤ１条件項の特性値をＱとして
、ＤとＱのビット毎の論理積結果とＱとを比較する。こ
れにより、ＤＡＱ≠Ｑであれば、検索類と条件項とは単
一化可能性がないと判定する。たとえば、ｆ （ａ）と
ｆ （Ｙ、ｂ）とは、 ００口１１００１１０１００００１ （Ｄ ）Ａ
０１１００１１０００００００１０ （Ｑ ）０
００（１００００００（１０００（１０≠Ｑであるから
単一化可能性はないと判定される。また、検索類ｆ （
ａ、Ｘ）と条件項ｆ （Ｙ、ｂ）とは、 ０１１００１１００００１１１１１ （Ｄ ）公′ｂ
′）とは１ 、 ０１１００１１００００１１１１０ （Ｄ
）Ａ （Ｈ１００Ｉ１００ＯＯＯＯ口１０
（Ｑ）１１ｉｌ １・ ０１１００１１００００００
０１０− Ｑ−−１〜１．。
たら、検索類の特性値をＤ１条件項の特性値をＱとして
、ＤとＱのビット毎の論理積結果とＱとを比較する。こ
れにより、ＤＡＱ≠Ｑであれば、検索類と条件項とは単
一化可能性がないと判定する。たとえば、ｆ （ａ）と
ｆ （Ｙ、ｂ）とは、 ００口１１００１１０１００００１ （Ｄ ）Ａ
０１１００１１０００００００１０ （Ｑ ）０
００（１００００００（１０００（１０≠Ｑであるから
単一化可能性はないと判定される。また、検索類ｆ （
ａ、Ｘ）と条件項ｆ （Ｙ、ｂ）とは、 ０１１００１１００００１１１１１ （Ｄ ）公′ｂ
′）とは１ 、 ０１１００１１００００１１１１０ （Ｄ
）Ａ （Ｈ１００Ｉ１００ＯＯＯＯ口１０
（Ｑ）１１ｉｌ １・ ０１１００１１００００００
０１０− Ｑ−−１〜１．。
となるから単一化可能性があると判定される。
しかしながら、最後の例についてみると、検索類ｆ （
ａ、 ｇ （ｂ） ）と条件項ｆ （Ｙ、ｂ）とは、
それぞれの第２引数が明らかに異なるので、実際には、
単一化が不可能であるにも拘らず、単一化が可能である
と判定している。つまり、ＦＥＷ法では、条件項の各要
素に対する特性値の計算において、要素が変数であって
対応するビットに０がセットされる場合と、要素が変数
でなく特性値の計算でたまたまビットに０がセットされ
る場合とが全く同一に取扱われるため、実際には、単一
化できないにも拘らず特性値による判定では単一化可能
であると判定されてしまうことが高い確率で発生する。
ａ、 ｇ （ｂ） ）と条件項ｆ （Ｙ、ｂ）とは、
それぞれの第２引数が明らかに異なるので、実際には、
単一化が不可能であるにも拘らず、単一化が可能である
と判定している。つまり、ＦＥＷ法では、条件項の各要
素に対する特性値の計算において、要素が変数であって
対応するビットに０がセットされる場合と、要素が変数
でなく特性値の計算でたまたまビットに０がセットされ
る場合とが全く同一に取扱われるため、実際には、単一
化できないにも拘らず特性値による判定では単一化可能
であると判定されてしまうことが高い確率で発生する。
このため、単一化候補の絞り込み効果が低く、項検索の
十分な高速化を図ることができないという問題があった
。
十分な高速化を図ることができないという問題があった
。
（発明が解決しようとする課題）
でも単一化可能性を判定できる点で優れた方式であるが
、実際には単一化不可能なものまでを単一化可能である
と判定してしまう確率が高く、項検索を十分に高速化す
ることができないという問題があった。一方、検索の対
象となる検索類については変数が含まれない場合も実際
には多くある。
、実際には単一化不可能なものまでを単一化可能である
と判定してしまう確率が高く、項検索を十分に高速化す
ることができないという問題があった。一方、検索の対
象となる検索類については変数が含まれない場合も実際
には多くある。
そこで、本発明は、このような検索類に変数が含まれな
い場合において、単一化候補項の十分な絞り込み効果が
期待できる単一化候補項の選択装置を提供することを目
的とする。
い場合において、単一化候補項の十分な絞り込み効果が
期待できる単一化候補項の選択装置を提供することを目
的とする。
［発明の構成〕
（課題を解決するための手段）
本発明の単一化候補項の選択装置は、定数のみから構成
される検索類から所定ビットの第１の特性値りを求める
第１の特性値算出手段と、定数及び／又は変数から構成
される条件項から前記第１の特性値りと同一ビットの第
２の特性値Ｑを求める第２の特性値算出手段と、前記条
件項から前記第１の特性値りと同一ビットの第３の特性
値Ｍを求める第３の特性値算出手段と、前記第１の特−
性がないと判定する判定手段とを具備している。
される検索類から所定ビットの第１の特性値りを求める
第１の特性値算出手段と、定数及び／又は変数から構成
される条件項から前記第１の特性値りと同一ビットの第
２の特性値Ｑを求める第２の特性値算出手段と、前記条
件項から前記第１の特性値りと同一ビットの第３の特性
値Ｍを求める第３の特性値算出手段と、前記第１の特−
性がないと判定する判定手段とを具備している。
：ここで、前記第１の特性値りは、前記検索類の □
構造に応じてビットフィールドを分割し、各分割−，フ
ィールドに当該検索項の各要素の数値変換値を対応させ
た値であり、前記第２の特性値Ｑは、前記条件項の構造
に応じてビットフィールドを分割し、定数要素が対応す
る分割フィールドに当該定数要素の数値変換値を対応さ
せ、変数要素が対応する分割フィールドの全ビットに０
を対応させた値であり、前記第３の特性値Ｍは、前記検
索類の構造に応じてビットフィールドを分割し、定数要
素が対応する分割フィールドの全ビットに１を対応させ
、変数要素が対応する分割フィールドの全ビットにＯを
対応させた値である。
構造に応じてビットフィールドを分割し、各分割−，フ
ィールドに当該検索項の各要素の数値変換値を対応させ
た値であり、前記第２の特性値Ｑは、前記条件項の構造
に応じてビットフィールドを分割し、定数要素が対応す
る分割フィールドに当該定数要素の数値変換値を対応さ
せ、変数要素が対応する分割フィールドの全ビットに０
を対応させた値であり、前記第３の特性値Ｍは、前記検
索類の構造に応じてビットフィールドを分割し、定数要
素が対応する分割フィールドの全ビットに１を対応させ
、変数要素が対応する分割フィールドの全ビットにＯを
対応させた値である。
毎の論理積のかわりにビット毎の論理和を使用するよう
にしても良い。
にしても良い。
を論理積することで、検索類の特性値りに対し、条件項
の変数部分に対応する部分のみを０に置換１．二えた値
が得られる。従って、検索類の特性値りに含まれる定数
部分の値はそのまま情報として残り、条件項の特性値Ｑ
との比較において、異なる定数についてはその違いを検
出することが可能となる。
の変数部分に対応する部分のみを０に置換１．二えた値
が得られる。従って、検索類の特性値りに含まれる定数
部分の値はそのまま情報として残り、条件項の特性値Ｑ
との比較において、異なる定数についてはその違いを検
出することが可能となる。
よって、本発明によれば、実際には単一化可能性のない
項が誤って単一化可能性があると判定される確率を大幅
に低減することができ、順検索の高速化を図ることがで
きる。
項が誤って単一化可能性があると判定される確率を大幅
に低減することができ、順検索の高速化を図ることがで
きる。
また、特性値Ｑは、変数要素が対応する分割フット毎の
論理積のかわりにビット毎の論理和を使用する場合も同
様の作用が得られる。
論理積のかわりにビット毎の論理和を使用する場合も同
様の作用が得られる。
（実施例）
以下、図面を参照しながら本発明の一実施例について説
明する。
明する。
とｉ、条件項を入力して第２の特性値Ｑ及び第３の′
１ 特性値Ｍをそれぞれ算出する特性値Ｑの算出手段、１；
２及び特性値Ｍの算出手段１３と、これら計算手段１１
〜１３で算出された特性値り、Ｑ、Ｍから（ＤＡＭ）と
Ｑとを比較して検索類についての単一化可能性を判定結
果として出力する判定手段１４とにより構成されている
。
１ 特性値Ｍをそれぞれ算出する特性値Ｑの算出手段、１；
２及び特性値Ｍの算出手段１３と、これら計算手段１１
〜１３で算出された特性値り、Ｑ、Ｍから（ＤＡＭ）と
Ｑとを比較して検索類についての単一化可能性を判定結
果として出力する判定手段１４とにより構成されている
。
以上の構成において、いま、検索類として、ｆ （ａ）
ｆ （ａ、 ｇ （ｂ） ）
条件項として、
ｆ （Ｙ、ｂ）
が与えられるとする。特性値り、Ｑ、Ｍを１８ビツトに
設定すると、計算手段１１．１２は検索類及び条件項を
従来のＦＥＷ法と全く同様の方法で特性値り及び特性値
Ｑにそれぞれ変換する。
設定すると、計算手段１１．１２は検索類及び条件項を
従来のＦＥＷ法と全く同様の方法で特性値り及び特性値
Ｑにそれぞれ変換する。
即ち、検索類ｆ （ａ）は、引数が１つの定数ｆと定数
ａとで構成されているので、計算手段１１は、第２図（
ａ）に示すように、１６ビツトのピッ”＝−一 当てる。これにより、検索類ｆ （ａ）の特性値Ｄ？ は第２図（ａ）に２１で示す値になる。また、検索類ｆ
（ａ、 ｇ （ｂ） ）については、引数が２つの
関数ｆ、定数ａ、引数が１つの定数ｇ１及び定数すより
構成されるので、計算手段１１は、第２図（ｂ）に示す
ように、１６ビツトのフィールドを例えば ８ビツト、
４ビツト、 ２ビツト及び ２ビツトに分割し、上位
８ビツトに関数ｆのアスキーコード６６Ｈを割当て、次
の４ビツトに定数ａのアスキーコード６１Ｈの下位４ビ
ツトであるＩＨを割当て、以下、それに続く ２ビツト
、２ビツトに、それぞれ定数ｇ、ｂのアスキーコードの
下位２ビット３Ｈ，２Ｈをそれぞれ割当てる。これによ
り、検索類ｆ （ａ、 ｇ （ｂ） ）の特性値りは
、第２図（ｂ）に２２で示す値になる。
ａとで構成されているので、計算手段１１は、第２図（
ａ）に示すように、１６ビツトのピッ”＝−一 当てる。これにより、検索類ｆ （ａ）の特性値Ｄ？ は第２図（ａ）に２１で示す値になる。また、検索類ｆ
（ａ、 ｇ （ｂ） ）については、引数が２つの
関数ｆ、定数ａ、引数が１つの定数ｇ１及び定数すより
構成されるので、計算手段１１は、第２図（ｂ）に示す
ように、１６ビツトのフィールドを例えば ８ビツト、
４ビツト、 ２ビツト及び ２ビツトに分割し、上位
８ビツトに関数ｆのアスキーコード６６Ｈを割当て、次
の４ビツトに定数ａのアスキーコード６１Ｈの下位４ビ
ツトであるＩＨを割当て、以下、それに続く ２ビツト
、２ビツトに、それぞれ定数ｇ、ｂのアスキーコードの
下位２ビット３Ｈ，２Ｈをそれぞれ割当てる。これによ
り、検索類ｆ （ａ、 ｇ （ｂ） ）の特性値りは
、第２図（ｂ）に２２で示す値になる。
また、条件項ｆ （Ｙ、ｂ）については、引数が２つの
関数ｆと変数Ｙと定数すとから構成されるので、計算手
段１１は、第２図（ｃ）に２３で示すように、１６ビツ
トのフィールドを例えば８ビツト、 ４ビツト及び ４
ビツトに分割し、上位 ８ビツ２Ｈを割当てる。これに
より、条件項の特性値Ｑは、第２図（Ｃ）の２３で示す
値となる。
関数ｆと変数Ｙと定数すとから構成されるので、計算手
段１１は、第２図（ｃ）に２３で示すように、１６ビツ
トのフィールドを例えば８ビツト、 ４ビツト及び ４
ビツトに分割し、上位 ８ビツ２Ｈを割当てる。これに
より、条件項の特性値Ｑは、第２図（Ｃ）の２３で示す
値となる。
一方、特性値Ｍの計算手段１３は、上記条件項ｆ （
Ｙ、ｂ）の特性値の１６ビツトのフィールドを第２図（
Ｃ）の２４に示すように、８ビツト、４ビツト及び４ビ
ツトに分割し、定数ｆ、ｂに対応する上位８ビツトと下
位４ビツトのフィールドの図（ｃ）の２４で示すような
定数部分のみを抽出するマスクパターンとなる。
Ｙ、ｂ）の特性値の１６ビツトのフィールドを第２図（
Ｃ）の２４に示すように、８ビツト、４ビツト及び４ビ
ツトに分割し、定数ｆ、ｂに対応する上位８ビツトと下
位４ビツトのフィールドの図（ｃ）の２４で示すような
定数部分のみを抽出するマスクパターンとなる。
次に、判定手段１４は、上記の各特性値り、Ｑ。
Ｍを入力して検索項と条件項との単一化可能性を判定す
る。即ち、先ず検索項ｆ （ａ）と条件項ｆ（ｙ、ｂ）
については、 ０００１１００１１０１００００１ （Ｄ ）Ａ
１１１１１１１１００００１１１１ （Ｍ ）≠０１
１００１１０００００００１０ （Ｑ ）ヤあるから
単一化可能性はないと判定される。また、検索項ｆ （
ａ、 ｇ （ｂ） ）と条件項ｆ （Ｙ。
る。即ち、先ず検索項ｆ （ａ）と条件項ｆ（ｙ、ｂ）
については、 ０００１１００１１０１００００１ （Ｄ ）Ａ
１１１１１１１１００００１１１１ （Ｍ ）≠０１
１００１１０００００００１０ （Ｑ ）ヤあるから
単一化可能性はないと判定される。また、検索項ｆ （
ａ、 ｇ （ｂ） ）と条件項ｆ （Ｙ。
ｂ）とは、
０１１００１１００００１１１１０ （Ｄ ）Δ １
１１１１１１１００００１１１１ （Ｑ ）≠０１１
００１１０００００００１０ （Ｑ ）となるから、
この場合も単一化可能性がないと判定される。
１１１１１１１００００１１１１ （Ｑ ）≠０１１
００１１０００００００１０ （Ｑ ）となるから、
この場合も単一化可能性がないと判定される。
この例から分るように、従来のＦＥＷ法では、条件項の
特性値において、ビット０が存在すると、検索項の特性
値の対応するビットの値がＯと１のいずれであっても、
そのビットに関する限り単一化可能でないと判定できな
かったが、本実施例に係る単一化候補項の選択装置では
、条件項に対する特性値Ｑの変数部分のマスク作用を、
第３の特性値Ｍによって得、検索項の特性値り内の重要
な情報が失われないようにしたので、その判定の精度を
飛躍的に向上させることができる。しかも、従来のＦＥ
Ｗ法に比べて検索項に対する特性値のを適用することは
可能である。
特性値において、ビット０が存在すると、検索項の特性
値の対応するビットの値がＯと１のいずれであっても、
そのビットに関する限り単一化可能でないと判定できな
かったが、本実施例に係る単一化候補項の選択装置では
、条件項に対する特性値Ｑの変数部分のマスク作用を、
第３の特性値Ｍによって得、検索項の特性値り内の重要
な情報が失われないようにしたので、その判定の精度を
飛躍的に向上させることができる。しかも、従来のＦＥ
Ｗ法に比べて検索項に対する特性値のを適用することは
可能である。
第１の方法は、検索項のうち、変数を含まない項につい
ては、上記実施例による方法を適用し、変数を含む項に
ついてはＦＥＷ法を適用する方式である。この方法によ
れば、ＦＥＷ法のみの場合より優れた検索方法となる。
ては、上記実施例による方法を適用し、変数を含む項に
ついてはＦＥＷ法を適用する方式である。この方法によ
れば、ＦＥＷ法のみの場合より優れた検索方法となる。
−例を挙げると、検索項に対する特性値の大きさを１ビ
ツトだけ大きくし、そこにその項が変数を含むか否かを
示すフラグをセットする。そして、実際に項を検索する
際に、そのフラグビットをまず参照して変数を含まない
場合には、本方式を適用し、変数を含む場合にはＦＥＷ
法を適用する。
ツトだけ大きくし、そこにその項が変数を含むか否かを
示すフラグをセットする。そして、実際に項を検索する
際に、そのフラグビットをまず参照して変数を含まない
場合には、本方式を適用し、変数を含む場合にはＦＥＷ
法を適用する。
また、第２の方法は、検索項についても条件項と同様に
特性値を２つ用意する方法である。即ち、特性値りを条
件項の特性値Ｑと同様の方法で求める。また、新たな特
性値りを導入し、それを条件項の特性値Ｍと同様の方法
で求める。このようにすると、特性値による単一化可能
性の判定には次の式を使用すれば良い。
特性値を２つ用意する方法である。即ち、特性値りを条
件項の特性値Ｑと同様の方法で求める。また、新たな特
性値りを導入し、それを条件項の特性値Ｍと同様の方法
で求める。このようにすると、特性値による単一化可能
性の判定には次の式を使用すれば良い。
することにより、両者ともに変数でない部分についての
比較を行なう。この方法も、ＦＥＷ法よりも優れた判定
結果を与える。しかし、各検索項に対して２つの特性値
を格納している必要があるので、ＦＥＷ法よりも多くの
格納領域を必要とする。
比較を行なう。この方法も、ＦＥＷ法よりも優れた判定
結果を与える。しかし、各検索項に対して２つの特性値
を格納している必要があるので、ＦＥＷ法よりも多くの
格納領域を必要とする。
また、本発明は、条件項の特性値として、定数及び関数
子に対応する特性値Ｑと、変数の位置を示す特性値Ｍの
２つを用意し、検索項の定数及び関数子に対する特性値
りを条件項の変数の位置を示す特性値Ｍでマスクするこ
とにより、定数及び関数値に対応する特性値同士の比較
を正確に行ない、判定の精度を向上させた点が特徴であ
る。従って、特性値Ｑは、変数である部分に１を対応さ
せ、特性値Ｍは、変数でない部分にＯを対応させ、変数
である部分に１をたて、単一化可能性の判定にはビット
毎の論理積のかわりにビット毎の論理和を使用するよう
にしても良い。また、別の実施例として特性値Ｍを使用
する代わりに、変数の出現位置を記憶し、特性値りと特
性値Ｍのビット毎の論理積に相当する演算を別事段で行
なうこともまない検索項の集合から条件項と単一化可能
な項を正確に検出できるので、項検索の高速化に大いに
寄与することが可能である。
子に対応する特性値Ｑと、変数の位置を示す特性値Ｍの
２つを用意し、検索項の定数及び関数子に対する特性値
りを条件項の変数の位置を示す特性値Ｍでマスクするこ
とにより、定数及び関数値に対応する特性値同士の比較
を正確に行ない、判定の精度を向上させた点が特徴であ
る。従って、特性値Ｑは、変数である部分に１を対応さ
せ、特性値Ｍは、変数でない部分にＯを対応させ、変数
である部分に１をたて、単一化可能性の判定にはビット
毎の論理積のかわりにビット毎の論理和を使用するよう
にしても良い。また、別の実施例として特性値Ｍを使用
する代わりに、変数の出現位置を記憶し、特性値りと特
性値Ｍのビット毎の論理積に相当する演算を別事段で行
なうこともまない検索項の集合から条件項と単一化可能
な項を正確に検出できるので、項検索の高速化に大いに
寄与することが可能である。
第１図は本発明の一実施例に係る単一化候補項の選択装
置のブロック図、第２図は同装置にて得られる各特性値
を示す図、第３図は従来のＦＥＷ法で使用される各特性
値を示す図である。 １１・・・特性値りの計算手段、１２・・・特性値Ｑの
計算手段、１３・・・特性値Ｍの計算手段、１４・・・
判定手段。 出願人 工業技術院長 飯塚 幸三 第１図 （ａ） （ｂ）第２図 （ａ） （ｂ）第 ３
区
置のブロック図、第２図は同装置にて得られる各特性値
を示す図、第３図は従来のＦＥＷ法で使用される各特性
値を示す図である。 １１・・・特性値りの計算手段、１２・・・特性値Ｑの
計算手段、１３・・・特性値Ｍの計算手段、１４・・・
判定手段。 出願人 工業技術院長 飯塚 幸三 第１図 （ａ） （ｂ）第２図 （ａ） （ｂ）第 ３
区
Claims (2)
- （１）定数のみから構成される検索項から所定ビットの
第１の特性値を求める第１の特性値算出手段と、定数及
び／又は変数から構成される条件項から前記第１の特性
値と同一ビットの第２の特性値を求める第２の特性値算
出手段と、前記条件項から前記第１の特性値と同一ビッ
トの第３の特性値を求める第３の特性値算出手段と、前
記第１の特性値と前記第３の特性値との論理積の結果と
前記第２の特性値とを比較して、両者が同一でなければ
、前記検索項は前記条件項と単一化可能性がないと判定
する判定手段とを具備し、前記第１の特性値は、前記検
索項の構造に応じてビットフィールドを分割し、各分割
フィールドに当該検索項の各要素の数値変換値を対応さ
せた値であり、前記第２の特性値は、前記条件項の構造
に応じてビットフィールドを分割し、定数要素が対応す
る分割フィールドに当該定数要素の数値変換値を対応さ
せ、変数要素が対応する分割フィールドの全ビットに１
を対応させた値であり、前記第３の特性値は、前記検索
項の構造に応じてビットフィールドを分割し、定数要素
が対応する分割フィールドの全ビットに１を対応させ、
変数要素が対応する分割フィールドの全ビットに０を対
応させた値であることを特徴とする単一化候補項の選択
装置。 - （２）前記第２の特性値は、前記条件項の構造に応じて
ビットフィールドを分割し、定数要素が対応する分割フ
ィールドに当該定数要素の数値変換値を対応させ、変数
要素が対応する分割フィールドの全ビットに０を対応さ
せた値であり、前記第３の特性値は、前記検索項の構造
に応じてビットフィールドを分割し、定数要素が対応す
る分割フィールドの全ビットに０を対応させ、変数要素
が対応する分割フィールドの全ビットに１を対応させた
値であり、前記判定手段は、前記第１の特性値と前記第
３の特性値との論理和の結果と前記第２の特性値とを比
較して、両者が同一でなければ、前記検索項は前記条件
項と単一化可能性がないと判定することを特徴とする請
求項１に記載の単一化候補項の選択装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63102609A JPH0664534B2 (ja) | 1988-04-27 | 1988-04-27 | 単一化候補項の選択装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63102609A JPH0664534B2 (ja) | 1988-04-27 | 1988-04-27 | 単一化候補項の選択装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH01276237A true JPH01276237A (ja) | 1989-11-06 |
| JPH0664534B2 JPH0664534B2 (ja) | 1994-08-22 |
Family
ID=14331983
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP63102609A Expired - Lifetime JPH0664534B2 (ja) | 1988-04-27 | 1988-04-27 | 単一化候補項の選択装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0664534B2 (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0573618A (ja) * | 1991-09-11 | 1993-03-26 | Agency Of Ind Science & Technol | 構造体の検索方法 |
| JPH06124304A (ja) * | 1991-02-05 | 1994-05-06 | Agency Of Ind Science & Technol | 拡張項のための重ね合わせ符号を用いた検索方法 |
| WO1996010227A1 (en) * | 1994-09-28 | 1996-04-04 | Hideki Iwanishi | Method of selecting rule used in bottom-up reasoning in system based on knowledge base |
-
1988
- 1988-04-27 JP JP63102609A patent/JPH0664534B2/ja not_active Expired - Lifetime
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06124304A (ja) * | 1991-02-05 | 1994-05-06 | Agency Of Ind Science & Technol | 拡張項のための重ね合わせ符号を用いた検索方法 |
| JPH0573618A (ja) * | 1991-09-11 | 1993-03-26 | Agency Of Ind Science & Technol | 構造体の検索方法 |
| WO1996010227A1 (en) * | 1994-09-28 | 1996-04-04 | Hideki Iwanishi | Method of selecting rule used in bottom-up reasoning in system based on knowledge base |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH0664534B2 (ja) | 1994-08-22 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6564206B1 (en) | Information search apparatus and method, and storage medium | |
| JP2790466B2 (ja) | 文字列検索方法及び装置 | |
| US5835635A (en) | Method for the recognition and completion of characters in handwriting, and computer system | |
| JPH11212980A (ja) | インデクス作成方法および検索方法 | |
| JPH08255176A (ja) | データベースのテーブルを比較する方法及びシステム | |
| GB2580559A (en) | Inclusion dependency determination in a large database for establishing primary key-foreign key relationships | |
| JPH01276237A (ja) | 単一化候補項の選択装置 | |
| JP2720590B2 (ja) | パターン認識装置 | |
| GB2515867A (en) | Searching apparatus utilizing sub-word finite state machines | |
| US5894427A (en) | Technique for concurrent detection of bit patterns | |
| JPH087670B2 (ja) | 加算回路 | |
| US6172623B1 (en) | Efficient bit scan mechanism | |
| JP2590698B2 (ja) | 文字列データ検索装置 | |
| JP2724235B2 (ja) | 変数名称推論装置 | |
| JP2722684B2 (ja) | ファイルシステムの検索装置 | |
| JP2000090110A (ja) | 全文検索方法、装置、および全文検索プログラムを記録した記録媒体 | |
| JPH0423167A (ja) | コマンド検索方式 | |
| JP3018579B2 (ja) | 名前検索処理装置 | |
| JPH03108063A (ja) | 後方一致検索方法および装置 | |
| JPH04279973A (ja) | 文字列比較方式 | |
| JPH04241672A (ja) | 文字列検索方式 | |
| JPH06162096A (ja) | レコード検索方法 | |
| JPH05225248A (ja) | データベース検索システム | |
| JPH09204490A (ja) | 文字列入力手段選択方法 | |
| JPH0675746A (ja) | １位置検出方法及び演算器 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EXPY | Cancellation because of completion of term |