JPH0564809B2 - - Google Patents

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） この発明は、情報処理、特に知識情報処理や知
識ベース処理における、単一化処理または単一化
検索に使用される単一化候補項の選択装置に関す
る。

（従来の技術） 知識情報処理言語の一つであるPrologでは、
「項」と呼ぶ形式を用いて表した述語の集合（項
集合）からなるプログラムに対し、目標となる項
（目標項）が与えられ、この目標項がプログラム
中の項集合で満足させられるかどうかを調べて行
くことを処理の基本にしているが、この過程の中
で、項と項との単一化（Unification）が重要な
役割を果たす（W.F.Cloksin／C.S.Mellish著、中
村克彦訳「Prologプログラミング」マイクロソ
フトウエア刊：参照）。

二つの項t1とt2の単一化の成功・失敗は、t1
とt2が全く同じであれば単一化成功、t1または
t2に変数があるとき、（同一変数には同じ項を代
入するとして）その変数に適当な項を代入するこ
とによつて、他方と一致させることができれば単
一化成功、これらととによつて単一化成功で
ない場合は単一化失敗、として定義される。

この単一化に対する従来の処理方式では、目標
項と単一化すべき項の集まりである項集合中の一
つの項との間で、それらの表現を逐次調べていく
方法を採ることが多い。しかし、この方法では、
項集合の中で目標項との単一化に成功する項が少
数であるのにも拘らず、処理として意味のあるこ
れら少数の項との単一化を行うために、より多く
の失敗可能性のある単一化作業を行わねばならな
いという欠点があつた。その結果、従来、単一化
の処理は時間のかかるのもであり、Prologのプ
ログラムは実行速度の点で、他の言語のプログラ
ムより遅くなることが多かつた。

（発明が解決しようとする問題点） このように、従来の単一化候補項の選択装置に
おいては、単一化の失敗可能性のある多くの項と
目標項との単一化作業を行なわなくてはならず、
実行速度が遅くなるという問題があつた。

本発明は、このような問題点を解決すべくなさ
れたもので、複数の項を要素とする項集合の各項
と、目標項との間の単一化作業を高速に行ない得
る単一化候補項の選択装置を提供することを目的
とする。

［発明の構成］ （問題点を解決するための手段） 本発明は、複数の項を要素とする項集合の各項
と、目標項との間で単一化を試みる際に、項集合
の全ての項と単一化を試みるかわりに、単一化可
能な項がある場合に、その項が必ず含まれている
部分項集合の各項とのみ単一化を試みるようにし
たものであり、換言すれば、単一化に失敗する項
のうちの大部分の項とは始めから単一化を試みな
いようにすることにより、全体の処理時間を短縮
し、実行速度を上げようとするものである。

複数の項を要素とする項集合から、その部分項
集合として単一化候補項集合を、目標項と単一化
可能な項は必ず含まれているように選びだすた
め、本発明は、以下に述べる項集合記憶手段と、
目標項入力手段と、汎項アドレス生成手段と、等
項アドレス生成手段と、索引記憶手段と、登録手
段と、検索・選択手段とを備えたことを特徴とし
ている。

項集合記憶手段は、検索の対象となる複数の項
を要素とする項集合を記憶するものである。

目標項入力手段と、目標項を入力するものであ
る。

汎項アドレス生成手段は、前記項集合記憶手段
又は前記目標入力手段から任意の項が与えられる
と、その項の全ての汎項の核から、その核を特定
するアドレスを生成・出力するものである。

等項アドレス生成手段は、前記与えられた任意
の項の核から、その核を特定するアドレスを生
成・出力するものである。

索引記憶手段は、前記項集合記憶手段から任意
の項が与えられることにより、前記汎項アドレス
生成手段が生成したアドレスで指示される記憶場
所に当該汎項に係る項の識別子を汎項索引として
記憶するとともに、前記項集合記憶手段から任意
の項が与えられることにより、前記等項アドレス
生成手段が生成したアドレスで指示される記憶場
所に当該項の識別子を等項索引として記憶するも
のである。

登録手段は、前記項集合記憶手段から任意の項
が与えられることにより、前記汎項アドレス生成
手段が生成したアドレスで指示される前記索引記
憶手段の記憶場所に、当該項の識別子を書込んで
前記汎項索引を登録するとともに、前記項集合記
憶手段から任意の項が与えられることにより、前
記等項アドレス生成手段が生成したアドレスで指
示される前記等項索引記憶手段の記憶場所に、当
該項の識別子を書込んで前記等項索引を登録する
ものである。

検索・選択手段は、前記目標項入力手段から目
標項が与えられることにより、前記汎項アドレス
生成手段が生成した各アドレスで前記索引記憶手
段中の前記等項索引を検索し、前記目標項入力手
段から目標項が与えられることにより、前記等項
アドレス生成手段が生成したアドレスで前記汎項
索引を検索し、さらに前記目標項入力手段から目
標項が与えられることにより、前記等項アドレス
生成手段が生成したアドレスで前記等項索引を検
索し、登録されている項の識別子があつた場合に
これを単一化候補項として読み出すものである。

（作用） 本発明では、汎項アドレス生成手段が特に重要
であるので、その働きを説明するが、その準備と
して汎項について説明する。

「項」の表現は数学で用いる関数の表現と同様
であつて、例えば、ｆ（ｇ（ａ，ｂ），ｈ（Ｘ））な
どと表現される。ここで、ｆやｇやｈなどは一種
の関数記号であり、ｆとｇにはそれぞれ２個の項
を代入できる場所があつて、この場合には、ｆに
はｇ，ｈなる項が、ｇにはａ，ｂなる項がそれぞ
れ入つている。又、ｈは１個の項を代入できる場
所を持つていて、Ｘなる変数が入つている。この
場合、「ｆ，ｇのarityは２，ｈのarityは１，ａ，
ｂのarityは０である」などという。また、ｆ，
ｇ，ａ，ｂなどをＸ（変数）に対して、定数と呼
ぶことにする。

いま上記の項の例をt1とすると（t1＝ｆ（ｇ
（ａ，ｂ），ｈ（Ｘ）），t1と単一化可能な項として
は、t2＝ｆ（ｇ（ａ，Ｙ），ｈ（ｇ（ｃ，ａ）））など
がある。この場合、単一化は、Ｘ＝ｇ（ｃ，ａ），
Ｙ＝ｂとおけば、t1もt2も、ともにｆ（ｇ（ａ，
ｂ），ｈ（ｇ（ｃ，ａ）））となるので、成功する。
このようにt1と単一化可能な項は他にも、ｆ（ｇ
（ａ，ｂ），ｈ（ｆ（ｄ（ｂ，ｈ（ｃ），ｋ），Ｚ））
），
ｆ（ｇ（ａ，ｂ），ｈ（ｄ（ｙ，ｂ，ａ））），……ｆ
（Ｘ，ｈ（ｇ（ａ，Ｙ））），……などと、無数に存在
する。単一化はこのように、変数を含む項では、
無数の相手と成功し得るので、単純な一致検索の
ように、あらかじめハツシング・テーブルに登録
をしておくことにより、検索を高速化するという
手法を使うことができない。

ところで、項の表現として、上記の表現以外
に、各定数にそのarityを対にしたものを、括弧
“（ ）”を使わずに、その出現順に書き並べた、
「線形表現」がある。この表現によると、上記の
t1、t2は t1＝ｆ：２，ｇ：２，ａ：０，ｂ：０，ｈ：
１，Ｘ：０■ t2＝ｆ：２，ｇ：２，ａ：０，Ｙ：０，ｈ：
１，ｇ：２，ｃ：０，ａ：０■ と書かれる。またこれらを単一化した結果の項を
t3とすると、t3は、 t3＝ｆ：２，ｇ：２，ａ：０，ｂ：０，ｈ：
１，ｇ：２，ｃ：０，ａ：０■ と書かれる。このように（単一化によつて）変数
に代入を行うと、線形表現では、その変数の位置
より左側だけが影響を受ける。

いま線形表現で項ｔを表したとき、左端から見
て行つて初めて変数が現れるまでの定数の列、ま
たは変数が現れなければ項全体をその項の「核」
と定義し、Ｋ（ｔ）書く。また、項ｔの核に含ま
れる定数の個数を、その項の「左定数長」と定義
し、Ｌ（ｔ）と書く。上記の例では、各項の核と
左定数長は次の通りとなる。

項 核
左定数長 t1……ｆ：２，ｇ：２，ａ：０，ｂ：０，ｈ：
１ ……５ t2……ｆ：２，ｇ：２，ａ：０ ……３ t3……ｆ：２，ｇ：２，ａ：０，ｂ：０，ｈ：
１，ｇ：２，ｃ：０，ａ：０ ……８ これらの準備の下に、単一化の必要条件を考え
る。

t1とt2が単一化できるための必要条件として、
次の条件が考えられる。

［１］ t1とt2が単一化できるためには、 t1とt2の左定数長をそれぞれn1，n2とする
と、t1とt2の線形表現を比較して、左端から
min｛n1，n2｝番目までの定数が完全に一致し
ている必要がある。

何故ならば、これらの項の単一化において、 min｛n1，n2｝＋１番目以降に現れるどちらか、
あるいは両方の変数にどのように代入を行なつて
も、それによつて起きる項の変化は線形表現では
min｛n1，n2｝＋１番目以降のみに影響があらわ
れ、左端からmin｛n1，n2｝番目までは不変なの
で、この部分に不一致があると、どのように代入
を行なつても不一致が解消できず、単一化ができ
ない（失敗）からである。

この必要条件を書き直すと次のように書ける。

［２］ t1とt2が単一化できるためには、 t1とt2の左定数長をそれぞれn1，n2とする
と、 (a) n1＞n2ならば……左端からn2番目まで一
致していること。つまり、t1の核のn2番目ま
での定数がt2の核と一致していること。

(b) n1＜n2ならば……左端からn1番目まで一
致していること。つまり、t2の核のn1番目ま
での定数がt1の核と一致していること。

(c) n1＝n2ならば……左端からn1（or n2）番
目まで一致していること。つまり、Ｋ（t1）
とＫ（t2）が完全に一致していること。

が必要である。

ここで、上記必要条件のうち(a)が成立している
とき、「t2は、t1の『汎項』である。」と定義し、
「t2は、t1より『一般性』が高い」と言うことに
する。また、(c)が成立している時、「t2は、t1の
『等項』である」と定義する。さらに、項ｔの汎
項の全体を、ｇ☆ｔと書くことにする。

このように定義し、さらにt1とt2の単一化の必
要条件（上記［２］）を調べることを考えてみる
と、次の３種の場合を調べればよい。

［３］ (a) Ｋ（ｇ☆ｔ）のなかにＫ（t2）と同じ
ものがあるか？ (b) Ｋ（t1）と同じものがＫ（ｇ☆t2）のなかに
あるか？ (c) Ｋ（t1）とＫ（t2）とが同じか？ このチエツクは、すべて等しいかどうかのチエ
ツクであり、かつＫ（ｇ☆t1）とＫ（t1）は有限個
（Ｌ（t1）個）であつて、予め作ることができるの
で、ハツシングテーブルあるいは索引表に登録し
ておいて高速に見付け出す手法が使用できる。本
発明はこのような事実に基づいている。

さて、汎項アドレス生成手段は、ある項が与え
られると、その項の（全ての）汎項の核（Ｋ（ｇ
☆t1））に対して、その核から一定のアルゴリズ
ムで索引記憶手段のアドレスを出力する。たとえ
ば、前例のt1に対して、その汎項の核（Ｋ（ｇ☆
t1））は、 k11：ｆ：２，ｇ：２，ａ：０，ｂ：
０− k12：ｆ：２，ｇ：２，ａ：０− k13：ｆ：２，ｇ：２− k14：ｆ：２− k15：− の５個あるが、これらの各文字列を適当なハツシ
ングによつて、例えば０〜255の範囲のアドレス
に変換して次のようなアドレスを発生する。

（Ｘ“……”は16進数を表す） Ａ（k11）＝Ｘ“0E” Ａ（k12）＝Ｘ“36” Ａ（k13）＝Ｘ“AB” Ａ（k14）＝Ｘ“66” Ａ（k15）＝Ｘ“00” 等項アドレス生成手段は、ある項を与えられる
と、その項の核から一定のアルゴリズムで索引記
憶手段のアドレスを出力する。この時に用いるア
ルゴリズムは、汎項アドレス生成手段で用いるア
ルゴリズムと、同じ記憶手段に対しては同じもの
を用いる。例えば、前例のt1に対しては、その核
Ｋ（t1）は K10：ｆ：２，ｇ：２，ａ：０，ｂ：０，
ｈ：１，− であり、前とおなじハツシングアルゴリズムで
は、索引記憶手段に対するアドレスとして、次の
数を出力する。

Ａ（k10）＝Ｘ“74” 本発明では、このようなアドレス生成手段を用
いて任意の項についての汎項索引と等項索引とを
索引記憶手段に登録しておき、目標項から求める
られる汎項アドレスと等項アドレスとによつて上
記索引記憶手段を検索するようにしているので、
単一化候補項の検索を高速に行なうことができ
る。

（実施例） 以下、第１図〜第６図に基づいて本発明の第一
の実施例について説明する。

第１図は本実施例に係る単一化候補項の選択装
置の全体構成図である。同図に示すように、本装
置は、項集合記憶手段１０と、目標項入力手段２
０と、汎項アドレス生成手段３０と、等項アドレ
ス生成手段４０と、汎項索引記憶手段５０と、等
項索引記憶手段５２と、登録手段６０と、検索・
選択手段７０とから構成されている。

項集合記憶手段１０は、単一化の対象となる項
を記憶しておく手段であり、第２図に示すよう
に、項記憶部１１と項定義部１２と項集合指定部
１３とから構成されている。項記憶部１１は、項
を線形表現で表したときの各要素を記憶するもの
である。項定義部１２は、項記憶部１１中の各要
素を用いた各々の項の定義を記憶する。更に項集
合指定部１３は、項定義部１１中の複数の項定義
に対するポインタなどの項識別子の集合によつて
項集合を指定し記憶する。これらの具体的記憶形
態については後述する。

目標項入力手段２０は、単一化の目標となる項
を、この装置外から入力する手段である。

汎項アドレス生成手段３０は、ある項が与えら
れると、その項の全ての汎項の核に対して、その
核を構成する文字列をハツシングによつて、例え
ば０〜255の範囲のアドレスに変換して汎項索引
記憶手段５０のアドレスを出力する手段である。

等項アドレス生成手段４０は、ある項が与えら
れると、その項の核から上記汎項アドレス生成手
段３０と同様ハツシングによつて、等項索引記憶
手段５２のアドレスを出力する手段である。

また、本実施例では、索引記憶手段として、汎
項索引記憶手段５０と等項索引記憶手段５２の２
個の索引記憶手段を備えている。これら索引記憶
手段は、項集合の各項に対してその項やその汎項
の核に対する各々の特定の番地にその項へのポイ
ンターなどの項識別子を記憶する手段である。

登録手段６０は、第３図に示すように、汎項登
録部６１と第１の等項登録部６２と第２の等項登
録部６３とから構成されている。第１の等項登録
部６２は、項集合記憶手段１０に記憶されている
指定された項集合の各項に対して、等項アドレス
生成手段４０が生成するアドレスで指定された等
項索引記憶手段５２中の記憶場所に、項識別子を
書込む制御部である。また、第２の等項登録部６
１は、項集合記憶手段１０に記憶されている指定
された項集合の各項に対して、等項アドレス生成
手段４０が生成するアドレスで指定された汎項索
引記憶手段５０中の記憶場所に、項識別子を書込
む制御部である。

さらに、検索・選択手段７０は、第４図に示す
ように、汎項検索・選択部７１と第１の等項検
索・選択部７２とからなる。第１の等項検索・選
択部７２は、目標項入力手段２０から入力される
目標項に対して、等項アドレス生成手段４０が生
成するアドレスで指定された汎項索引記憶手段５
０中の記憶場所に記憶されている項または項識別
子を出力させる制御部である。

第５図は項集合記憶手段１０における項と項集
合の記憶方式を示た図である。項集合記憶手段１
０の中の項記憶部１１は項の要素である定数や変
数を定義・記憶するためであり、名称記憶部１４
とシンボル定義部１５とからなる。

名称記憶部１４は１語32ビツトの記憶装置のＮ
番地から開始され、各シンボルの名称の綴りを格
納する部分である。１個のシンボルの名称の綴り
は１個以上の文字からなるが、１語に４文字づつ
区切つて記憶する。１語のなかでの余白には、綴
りの終了または余白を表す記号（／）で埋められ
る。例えば、Ｎ＋15番地には“likely”というシ
ンボルの名称が格納されているが、この名称は６
文字からなるので、２語文の記憶場所を用い、１
語目に“like”までを、２語目に残りの“ly”と
余白の“／／”を合せた“ly／／”を格納してい
る。

シンボル定義部１５はやはり１語32ビツトの記
憶装置のＡ番地から開始され、項に使われる各シ
ンボルのarityと、そのシンボルのシンボル定義
子とを対にして記憶しておく部分である。なお、
ここで上記シンボル定義子とは、名称記憶部１４
中の当該シンボルが記憶されている記憶場所のＮ
からの相対アドレスを示している。例えば、前述
の例における項t1に現れる“ｆ”なるシンボル
は、Ａ＋６番地に定義されており、arityは２、
名称記憶部１４でその名称（“ｆ”）の相対番地は
11であることを示している。また、変数の場合は
そのarityは常に０であるので、arityのかわり
に、変数であることを示すＸ“FF”を格納する。
例えば前記の項t1における変数“Ｘ”を表すシン
ボルはＡ＋100番地に定義されており、その内容
は、定数を示すFFと、名称記憶部において“Ｘ”
が格納されている記憶場所の相対番地17とを示し
ている。

項定義部１２はやはり１語32ビツトの記憶装置
のＴ番地から開始される部分で、項を線形表現で
表した場合の各シンボルのarityと項要素定義子
とを対にして、線形表現での出現順に格納する部
分である。なお、ここで項要素定義子とは、シン
ボル定義部１５中の当該シンボルについてのシン
ボル定義子が格納されている記憶場所のＡからの
相対アドレスを示している。例えば、前記の例で
項t1はＴ＋25番地から格納されていてt1の線形表
現： ｆ：２，ｇ：２，ａ：０，ｂ：０，ｈ：１，
Ｘ：０ を表している。

なお、第５図では図示されていないが、項集合
指定部１３は、複数の項識別子を格納できる記憶
装置で構成されている。項識別子は第５図に示さ
れるように、その項に含まれるシンボルの個数と
項定義部１２中の当該項が定義されている記憶場
所のＴからの相対番地（その項へのポインター）
を含んでいる。例えば、前記の例t1の場合には、
項識別子は図中１６に示すように、t1のシンボル
の個数６と、t1の項定義部１２中での相対番地25
とを含んでいる。

第６図は本実施例での単一化候補項の選択の原
理と動作を示している。

本実施例では、前記（作用）で述べた単一化の
必要条件［３］(a)，(b)，(c)に合致する項を項集合
の中から高速に見つけだす動作を、登録手段６０
と検索・選択手段７０とによつて制御する。すな
わち、項集合の中の１つの項をt1、目標項をt2と
したとき、 汎項登録部６１と第１の等項検索・選択部７
２とによつて、必要条件(a)に、 第１の等項登録部６２と汎項検索・選択部７
１とによつて、必要条件(b)に、 第２の等項登録部６３と第１の等項検索・選
択部７２とによつて、必要条件(c)に、 それぞれ合致する項を、直ちに選択する。

（a1） まず、汎項登録部６１の動作を説明
する。

最初に、汎項登録部６１はａ端子から項集合記
憶手段１０に制御信号を送り、項集合指定部１３
に記憶されている項集合の項識別子を順に読み出
すよう要求する。

項集合記憶手段１０は項識別子を１個読みだす
毎に、その項識別子をPN端子から出力し、かつ
その項識別子の指示するシンボルの個数だけその
相対番地から項定義部１２中の項要素定義子を読
みだし、各項要素定義子に対して、その項要素定
義子の指示する相対番地を用いて、シンボル定義
部１５からシンボル定義子を、さらにそのシンボ
ル定義子の指示する相対番地を用いて、名称記憶
部１４から名称の綴りを読みだして、DATA端
子から順に出力する。例えば、第４図の16で示す
項識別子が項集合指定部１３から読み出される
と、この項識別子をPN端子から出力するととも
に、この項識別子が指示する項の項要素の数が
６、項定義部１２での項の格納開始番地が25であ
るので、項定義部１２内のアドレスＴ＋25からＴ
＋30までの６個の項要素定義子を読み出し、次に
これらの項要素定義子が指示する相対番地がそれ
ぞれ６，７，１，２，８，100であるので、シン
ボル定義部１５内のＡ＋６，Ａ＋７，Ａ＋１，Ａ
＋２，Ａ＋８，Ａ＋100に格納されているシンボ
ル定義子を読み出し、続いてこれらのシンボル定
義子が指示する、名称記憶部１４の相対番地がそ
れぞれ11，14，３，６，13，17であるので、名称
記憶部１４から、Ｎ＋11，Ｎ＋14，Ｎ＋３，Ｎ＋
６，Ｎ＋13，Ｎ＋17に格納されている名称の文字
列、ｆ，ｇ，ａ，ｂ，ｈ，Ｘを読み出して
DATA端子から送りだす。

次に汎項登録部６１は項集合記憶手段１０が上
記のようにして項集合の中から項を１個読み出す
度に、ｂ端子から汎項アドレス生成手段３０に制
御信号を送り、その項の汎項アドレスを生成する
ことを要求する。

汎項アドレス生成手段３０はＢ端子からこの要
求を受けると、DATA１端子から入力される項
自身から、その項の核を抽出し、その核の文字列
から汎項の核を生成し、各々の核の文字列からハ
ツシングによつて汎項アドレスを生成する。

例えば、第５図の16なる項識別子から前記のよ
うにして読み出された項の線形表現での文字列：
ｆ，ｇ，ａ，ｂ，ｈ，ＸがDATA１端子から入
力されると、汎項アドレス生成手段３０は最初に
現れる変数（Ｘ）以下を取除いてこの項の核：
ｆ，ｇ，ａ，ｂ，ｈ，−，を得て、これからこの
項の汎項の核：ｆ，ｇ，ａ，ｂ，−；ｆ，ｇ，ａ，
−；：ｆ，ｇ，ｆ，−；−；を求めて、この文字
列からハツシング操作によつて、Ｘ“0E”，Ｘ
“36”，Ｘ“AB”，Ｘ“66”，Ｘ“00”なるアドレス
を作る。なお、このハツシングは、対象とする文
字列の各文字のASC codeを、ａ（１），ａ
（２），……，ａ（ｎ），……，ａ（Ｎ）としたとき、
次の斬化式を用いている。

Ｈ（０）＝０， Ｈ（ｉ）＝ａ（ｉ）．eor.（left＊Ｈ（ｉ−１））…
…
ｉ＝１〜Ｎ 但し、「．eor.」はビツト毎の排他的論理和、
「left＊」は１ビツトの左ローテートを示す。こ
の方法によると、Ｈ（Ｎ−１），Ｈ（１），……，Ｈ
（０）はそれぞれ汎項の核に対するハツシング結
果になつている。

次に、汎項登録部６１は、汎項アドレス生成手
段３０が上記のようにして汎項アドレスを１個生
成するたびに、ｄ端子から汎項索引記憶手段５０
に制御信号を送つて、その汎項アドレスの指す記
憶場所に、項集合記憶手段１０のPN端子から出
力されている項識別子を書込むよう要求する。

汎項索引記憶手段５０はWC端子からこの要求
を受取ると、WD端子から入力される項識別子
を、AD１端子から入力されるアドレスの指す記
憶場所の語の空所に格納する。汎項索引記憶手段
５０の１語は16個の項識別子を記憶できるビツト
数を持つている。但し、第６図では、そのうちの
最初の４個のみを示している。

例えば、第５図の16の処理の場所は、前記のよ
うに汎項アドレス生成手段３０から、汎項アドレ
スとして、Ｘ“0E”，Ｘ“36”，Ｘ“AB”，Ｘ“66”，
Ｘ“00”なるアドレスが次々に生成されるので、
これらのアドレスに項識別子１６を書込む。ただ
し、第５図では項識別子１６を、その項識別子１
６に含まれる項定義部１２での相対番地：「25」
で示してある。

このようにして、汎項登録部６１は項集合記憶
手段１０に記憶されている項集合の全ての項に対
して、その汎項の核（と同じ核を持つ項の核）か
らその項の項識別子を直ちに検索するための索引
表を、汎項索引記憶手段５０の中に作り出す。

（b1） 次に、第１の等項登録部６２の動作
を説明する。

最初に、第１の等項登録部６２はａ端子から項
集合記憶手段１０に制御信号を送つて、項集合指
定部１１に記憶されている項集合の項識別子を順
に読み出すよう要求する。

このときの項集合記憶手段１０の動作は前記
（a1）の場合と全く同じであるので、説明を省略
する。

次に第１の等項登録部６２は項集合記憶手段１
０が上記のようにして項集合の中から項を１個読
み出す度に、ｃ端子から等項アドレス生成手段４
０に制御信号を送つて、その項の等項アドレスを
生成することを要求する。

等項アドレス生成手段４０はＣ端子からこの要
求を受けると、DATA１端子から入力される項
自身から、その項の核を抽出し、その核の文字列
からハツシングによつて等項アドレスを生成す
る。

例えば、第５図の16なる項識別子から前記のよ
うにして読み出された項の線形表現での文字列：
ｆ，ｇ，ａ，ｂ，ｈ，ＸがDATA１端子から入
力されると、等項アドレス生成手段４０は最初に
現れる変数（Ｘ）以下を取除いてこの項の核：
ｆ，ｇ，ａ，ｂ，ｈ，−，を得て、この文字列か
らハツシング操作によつて、Ｘ“74”なるアドレ
スを作る。このときのハツシングは、前記（a1）
と同じものを用いている。

次に、第１の等項登録部６２は、等項アドレス
生成手段４０が上記のようにして等項アドレスを
１個生成する度に、ｅ端子から等項索引記憶手段
５２に制御信号を送つて、その等項アドレスを指
す記憶場所に、項集合記憶手段１０のPN端子か
ら出力されている項識別子を書込むよう要求す
る。

等項索引記憶手段５２はWC端子からこの要求
を受取ると、WD端子から入力される項識別子
を、AD２端子から入力されるアドレスの指す記
憶場所の語の空所に格納する。

例えば、第５図の16の処理の場合は、前記のよ
うに等項アドレス生成手段４０から、等項アドレ
スとしてＸ“74”なるアドレスが生成されるので、
このアドレスの指す記憶場所の語の空所に項識別
子１６を書込む。ただし、第６図では項識別子１
６を、その項識別子１６に含まれる項定義部１２
での相対番地：「25」で示してある。

このようにして、第１の等項登録部６２の項集
合記憶手段１０に記憶されている項集合の全ての
項に対して、その核（と同じ核を持つ項の核）か
らその項の項識別子を直ちに検索するための索引
表を、等項索引記憶手段５２の中に作り出す。

（c1） 次に、第２の等項登録部６３の動作を
説明する。

最初に、第２の等項登録部６３はａ端子から項
集合記憶手段１０に制御信号を送つて、項集合指
定部１３に記憶されている項集合の項識別子を順
に読み出すように要求する。

このときの項集合記憶手段１０の動作は前記
（a1）の場合と全く同じであるので、説明を省略
する。

次に第２の等項登録部６３は項集合記憶手段１
０が上記のようにして項集合の中から項を１個読
み出す度に、ｃ端子から等項アドレス生成手段４
０に制御信号を送つて、その項の等項アドレスを
生成することを要求する。

このときの等項アドレス生成手段４０の動作は
（b1）の場合と全く同じであるので、説明を省略
する。

次に、第２の等項登録部６３は、等項アドレス
生成手段４０が上記のようにして等項アドレスを
１個生成するたびに、ｄ端子から汎項索引記憶手
段５０に制御信号を送つて、その等項アドレスの
指す記憶場所に、項集合記憶手段１０のPN端子
から出力されている項識別子を書込むよう要求す
る。

汎項索引記憶手段５０はWC端子からこの要求
を受取ると、WD端子から入力される項識別子
を、AD２端子から入力されるアドレスの指す記
憶場所の語の空所に格納する。

例えば、第５図の16の処理の場合は、前記のよ
うに等項アドレス生成手段４０から、等項アドレ
スとして、Ｘ“74”なるアドレスが生成されるの
で、このアドレスの指す記憶場所の子１６に含ま
れる項定義部１２での相対番地：「25」で示して
ある。

このようにして、第２の等項登録部６３は項集
合記憶手段１０に記憶されている項集合の全ての
項に対して、その核（と同じ核を持つ項の核）か
らその項の項識別子を直ちに検索するための索引
表を、汎項索引記憶手段５０に追加する。

以上のようにして、登録手段６０の制御によつ
て汎項索引記憶手段５０と等項索引記憶手段５２
の中に項集合に対する索引表を作つた上で、次の
ようにして、検索・選択手段７０の制御により目
標項に対する単一化候補項を、高速に検索する。

（b2） 最初に、汎項検索・選択部７１の動
作を説明する。

まず汎項検索・選択部７１は、ｊ端子から制御
信号を送つて、目標項入力手段２０に対して、入
力された目標項をDATA端子から送り出すよう
に、要求する。

目標項入力手段２０はIC端子からこの要求を
受取ると、この装置の外部（図示せず）から入力
された目標項から、その線形表現による項要素の
文字列を生成し、DATA端子から送り出す。

例えば、第６図中２１で示した目標項が入力さ
れていたとすると、目標項入力手段２０は、ｆ，
ｇ，ａ，Ｙ，ｈ，ｐ，−なる文字列をDATA端子
から送り出す。

次に、汎項検索・選択部７１は、ｋ端子から汎
項アドレス生成手段３０に制御信号を送つて、目
標項入力手段２０から送り出された項の汎項アド
レスを生成するよう要求する。

汎項アドレス生成手段３０はＫ端子からこの要
求を受けると、DATA２端子から入力される項
の文字列から、その項の核を抽出し、その文字列
から汎項の核を生成し、各々の核の文字列からハ
ツシングによつて汎項アドレスを生成する。

この動作は基本的に（a1）におけるものと同
じであるが、例えば、第６図の２１なる目標項が
入力される前記の場合には、目標項入力手段２０
から送り出される目標項の文字列がDATA２端
子から入力されると、汎項アドレス生成手段３０
は最初に現れる変数（Ｙ）以下を取除いてこの目
標項の核：ｆ，ｇ，ａ，−を得て、これからこの
目標項の汎項の核：ｆ，ｇ，−；ｆ，−；−；を求
めて、この文字列からハツシングによつて、Ｘ
“AB”，Ｘ“66”，Ｘ“00”なるアドレスを生成し、
ADRS端子から出力する。このとき用いるハツシ
ングは（a1）でのものと同じである。

次に、汎項検索・選択部７１は、汎項アドレス
生成手段３０が上記のようにした汎項アドレスを
１個生成するたびに、ｎ端子から等項索引記憶手
段５２に制御信号を送つて、その汎項アドレスの
指す記憶場所に格納されている項識別子を読み出
すように要求する。

等項索引記憶手段５２はRC端子からこの要求
を受けると、AD１端子から入力されるアドレス
の指す記憶場所の語を読み出し、もしその語が空
でなく項識別子が記入されていたら、その項識別
子を単一化候補項として、RD端子から出力す
る。

例えば、第６図の２１なる目標項に対しては、
前記の如く汎項アドレス生成手段３０は、Ｘ
“AB”，Ｘ“66”，Ｘ“00”なるアドレスを出力す
るので、等項索引記憶手段５２はこれらのアドレ
スを指す記憶場所の語を読み出す。第６図の場合
にはこれらの語にはなにも登録されて（書込まれ
て）いないので、単一化候補項は出力されない。

この動作は前記（作用）で述べたところの、目
標項に対して必要条件［３］の(b)に合致する項を
項集合の中から検索する結果になつている。

（ac2） 次に、第１の等項検索・選択部７
２の動作を説明する。

まず第１の等項検索・選択部７２は、ｊ端子か
ら制御信号を送つて、目標項入力手段２０に対し
て、入力された目標項をDATA端子から送り出
すように要求する。

目標項入力手段２０はIC端子からこの要求を
受取ると、この装置の外部（図示せず）から入力
された目標項から、その線形表現による項要素の
文字列を生成し、DATA端子から送り出す。

例えば、第６図の２１で示した目標項が入力さ
れていたとすると、目標項入力手段２０は、ｆ，
ｇ，ａ，Ｙ，ｈ，ｐ，−なる文字列をDATA端子
から送り出す。

次に、第１の等項検索・選択部７２は、１端子
から等項アドレス生成手段４０に制御信号を送つ
て、目標項入力手段２０から送り出された項の等
項アドレスを生成するよう要求する。

等項アドレス生成手段４０はＬ端子からこの要
求を受けると、DATA２端子から入力される項
の文字列から、その項の核を抽出し、その文字列
からハツシングによつて等項アドレスを生成す
る。

この動作は基本的に（b1）におけるものと同
じであるが、例えば、第６図の２１なる目標項が
入力される前記の場合には、目標項入力手段２０
から送り出される目標項の文字列が、DATA２
端子から入力されると、等項アドレス生成手段４
０は最初に現れる変数（Ｙ）以下を取除いてこの
目標項の核：ｆ，ｇ，ａ，−を得て、この文字列
からハツシングによつてＸ“36”なるアドレスを
生成し、ADRS端子から出力する。このとき用い
るハツシングは（a1）でのものと同じである。

次に、第１の等項検索・選択部７２は、等項ア
ドレス生成手段４０が上記のようにして等項アド
レスを生成すると、ｍ端子から汎項索引記憶手段
５０に制御信号を送つて、その等項アドレスの指
す記憶場所に格納されている項識別子を読み出す
ように要求する。

汎項索引記憶手段５０はRC端子からこの要求
を受けると、AD２端子から入力されるアドレス
の指す記憶場所の語を読み出し、もしその語が空
でなく項識別子が記入されていたら、その項識別
子を単一化候補項として、RD端子から出力す
る。

例えば、第６図の２１なる目標項に対しては、
前記の如く等項アドレス生成手段４０は、Ｘ“36”
なるアドレスを出力するので、汎項索引記憶手段
５０はこれらのアドレスの指す記憶場所の語を読
み出す。第６図の場合にはこれらの語には２個の
項識別子２５，８６が登録されて（書込まれて）
いるので、これらの項識別子が単一化候補項とし
て出力される。

この動作は前記（作用）で述べたところの、目
標項に対して必要条件［３］の(a)と(c)に合致する
項を項集合の中から検索する結果になつている。

以上詳述したように、本実施例では、登録手段
６０により検索対象の項集合を汎項索引記憶手段
５０と等項索引記憶手段５２に登録し、検索・選
択手段７０によつて目標項と単一化の必要条件
［３］(a)，(b)，(c)に合致する項を汎項索引記憶手
段５０と等項索引記憶手段５２を用いて高速に選
択することを可能としている。

なお、本実施例では（c1）で述べた如く、第２
の等項登録部６３によつて、自身の核から項識別
子を検索するための表を汎項索引記憶手段５０に
追加登録しているが、（a1）のステツプで、汎項
アドレス生成手段３０が、汎項の核に対するハツ
シング結果（Ｈ（０）〜Ｈ（Ｎ−１））の生成の最
後に、その項の核のハツシング結果（Ｈ（Ｎ））を
も容易に生成できるので、前記の追加登録を
（a1）で同時に行い、（c1）を、従つて第２の等
項登録部６３を省略することもできる。

なお、本発明は上述した実施例に限定されたも
のではない。例えば、上記実施例では単一化の必
要条件［３］の(c)に合う項を表引きで検索するた
め、第２の等項登録部６３と第１の等項検索・選
択部７２によつて行つているが、次のようにして
もよい。

すなわち、第７図に示すように第２の等項登録
部６３の動作を削除し、代わりに第２の等項検
索・選択部７３の動作を追加する。この場合、単
一化の必要条件［３］(c)に合う項の検索は、第１
の等項登録部６２によつて等項索引記憶手段５２
の中に登録された項集合の項識別子を、第２の等
項検索・選択部７３によつて目標項の核から表引
きにより検索することで行なう。

第８図は、この実施例における登録手段６５
を、また第９図に、この実施例における検索・選
択手段７５をそれぞれ示す。

登録手段６５は、汎項登録部６１と第１の等項
登録部６２とからなり、これらの動作は前記の
（a1），（b1）と同じである。

また、検索・選択手段７５は、汎項検索・選択
部７１と第１の等項検索・選択部７２の他に、第
２の等項検索・選択部７３を含む。汎項検索・選
択部７１の動作は前記（b2）と全く同じである。
また、第１の等項検索・選択部７２の動作は前記
（ac2）と同じではあるが、その結果検索される
項識別子は単一化の必要条件［３］(a)に合致する
ものだけである。例えば、第７図の２１なる目標
項に対しては、等項アドレス生成手段４０は、Ｘ
“36”なるアドレスを出力するので、汎項索引記
憶手段５０はこのアドレスの指す記憶場所の語を
読み出し、単一化候補項として25なる項識別子を
得る。ここでは、（ac2）の場合の86が登録され
ていないので、86は読み出されない。

（c2） 第２の等項検索・選択部７３の動作を
説明する。

まず第２の等項検索・選択部７３は、ｊ端子か
ら制御信号を送つて、目標項入力手段２０に対し
て、入力された目標項をDATA端子から送り出
すように、要求する。

目標項入力手段２０の動作は前記（ac2）にお
けるものと同様である。

次に、第２の等項検索・選択部７３は、１端子
から等項アドレス生成手段４０に制御信号を送つ
て、目標項入力手段２０から送り出された項の等
項アドレスを生成するよう要求する。この時の等
項アドレス生成手段４０の動作は（ac2）におけ
るのと同様である。

次に、第２の等項検索・選択部７３は、等項ア
ドレス生成手段４０が上記のようにして等項アド
レスを生成すると、ｎ端子から等項索引記憶手段
５２へ制御信号を送つて、その等項アドレスを指
す記憶場所に格納されている項識別子を読み出す
よう要求する。

この時の等項索引記憶手段５２の動作は前記
（b2）におけるものと同じであるが、その結果読
み出される項識別子は、単一化の必要条件［３］
(c)に合致したものとなつている。

例えば、第７図の２１なる目標項に対しては、
等項アドレス生成手段４０は、Ｘ“36”なるアド
レスを出力するので、等項索引記憶手段５２はこ
のアドレスの指す記憶場所の語を読み出す。第７
図の場合には項識別子として、86が読み出され
る。

なお、この第２の実施例において、第２の等項
検索・選択部７３の動作（c2）を、汎項検索・選
択部７１の動作（b2）と同時に行わせることも
できる。

以上の実施例において、索引記憶手段として、
汎項索引記憶手段５０と等項索引記憶手段５２の
２種を設けているのは、単一化の必要条件［３］
の(a)と(b)の「混合」、すなわちこれらの必要条件
に合致する項の表引き型検索動作において、不要
な組合わせ：Ｋ（ｇ☆t1）とＫ（ｇ☆t2）：による
表引き結果が混じり込むことを避けるためであ
る。この問題には次に述べるような別の解決法が
ある。それを第３の実施例として説明する。

第１０図は、第３の実施例の構成を示してい
る。この実施例では索引記憶手段が、１つの索引
記憶手段５８となつている。また、８０は登録手
段、９０は検索・選択手段であつて、それぞれ第
１１図及び第１２図に示す通り、汎項登録部８１
と等項登録部８２、汎項検索・選択部９１と等項
検索・選択部９２とからなる。

この第３の実施例の動作を第１３図に示す。こ
の実施例では、登録手段８０が索引記憶手段５８
に項識別子を登録する時に、それが汎項に対する
ものか、等項に対するものかを区別するために、
フラグを添えて登録する。

第１４図は、この登録の時のフラグと項識別子
を示している。先頭の１ビツトがフラグであつ
て、これが１なら汎項登録部８１によつて登録さ
れたことを、０なら等項登録部８２によつて登録
されたことを、表わしている。

汎項検索・選択部９１が目標項に対する単一化
候補項を求める動作は、前記第１の実施例の
（b2）とほとんど同じであるが、前記の「混合」
問題を避けるため、このとき読み出される項識別
子のうち、０なるフラグを持つものだけを単一化
候補項とする。

また、等項検索・選択部９２が目標項に対する
単一化候補項を求める動作は、前記第１の実施例
の（ac2）と全く同じであつて、このときは読み
出される項識別子はフラグの値によらず、全て単
一化候補項とする。

［発明の効果］ 以上に詳述した通り、本発明の単一化候補項の
高速選択装置によれば、多数の項を含む項集合の
中から、目標項と単一化成功の可能性のある単一
化候補項を、極めて高速に選択することができ
る。その結果、時間のかかる単一化操作を項集合
の全ての項との組合わせに対して行う場合に必要
な時間の大部分を節約することができる。

また、大部分の応用では、単一化の対象となる
項集合は固定的であるので、その索引記憶手段へ
の登録をあらかじめ行つておくことにより、単一
化候補項の選択時間を、考え得る方法のうちの最
も短いものとすることができる。しかもこの選択
時間は、項集合が含む項の数によらず、一定であ
るという、優れた性質がある。

【図面の簡単な説明】

第１図〜第６図は本発明の第１の実施例に係る
単一化候補項の選択装置を説明するための図で、
第１図は全体構成図、第２図は項集合記憶手段の
構成図、第３図は登録手段の構成図、第４図は検
索・選択手段の構成図、第５図は項集合記憶手段
における項の記憶形態を示す図、第６図は動作の
説明図、第７図〜第９図は本発明の第２の実施例
に係る単一化候補項の選択装置を説明するための
図で、第７図は動作の説明図、第８図は登録手段
の構成図、第９図は検索・選択手段の構成図、第
１０図〜第１４図は本発明の第３の実施例に係る
単一化候補項の選択装置を説明するための図で、
第１０図は全体構成図、第１１図は登録手段の構
成図、第１２図は検索・選択手段の構成図、第１
３図は動作の説明図、第１４図は登録されたフラ
グと項識別子の形態を示す図である。 １０……項集合記憶手段、２０……目標項入力
手段、３０……汎項アドレス生成手段、４０……
等項アドレス生成手段、５０……汎項索引記憶手
段、５２……等項索引記憶手段、５８……索引記
憶手段、６０，８０……登録手段、７０，９０…
…検索・選択手段。

Claims (1)

1. 【特許請求の範囲】 １ 検索の対象となる複数の項を要素とする項集
   合から、別に与えられた目標項と単一化可能な項
   がある場合に、その項が必ず含まれるように単一
   化候補項を選択する装置であつて、 前記項集合を記憶してなる項集合記憶手段と、 前記目標項を入力する目標入力手段と、 前記項集合記憶手段又は前記目標入力手段から
   任意の項が与えられると、その項の全ての汎項の
   核から、その核を特定するアドレスを生成・出力
   する汎項アドレス生成手段と、 前記与えられた任意の項の核から、その核を特
   定するアドレスを生成・出力する等項アドレス生
   成手段と、 前記項集合記憶手段から任意の項が与えられる
   ことにより、前記汎項アドレス生成手段が生成し
   たアドレスで指示される記憶場所に当該汎項に係
   る項の識別子を汎項索引として記憶するととも
   に、前記項集合記憶手段から任意の項が与えられ
   ることにより、前記等項アドレス生成手段が生成
   したアドレスで指示される記憶場所に当該項の識
   別子を等項索引として記憶する索引記憶手段と、 前記項集合記憶手段から任意の項が与えられる
   ことにより、前記汎項アドレス生成手段が生成し
   たアドレスで指示される前記索引記憶手段の記憶
   場所に、当該項の識別子を書込んで前記汎項索引
   を登録するとともに、前記項集合記憶手段から任
   意の項が与えられることにより、前記等項アドレ
   ス生成手段が生成したアドレスで指示される前記
   等項索引記憶手段の記憶場所に、当該項の識別子
   を書込んで前記等項索引を登録する登録手段と、 前記目標項入力手段から目標項が与えられるこ
   とにより、前記汎項アドレス生成手段が生成した
   各アドレスで前記索引記憶手段中の前記等項索引
   を検索し、前記目標項入力手段から目標項が与え
   られることにより、前記等項アドレス生成手段が
   生成したアドレスで前記汎項索引を検索し、さら
   に前記目標項入力手段から目標項が与えられるこ
   とにより、前記等項アドレス生成手段が生成した
   アドレスで前記等項索引を検索し、登録されてい
   る項の識別子があつた場合にこれを単一化候補項
   として読み出す検索・選択手段とを 具備したことを特徴とする単一化候補項の選択
   装置。 ２ 前記登録手段は、前記項集合記憶手段から任
   意の項が与えられることにより、前記等項アドレ
   ス生成手段が生成したアドレスで指示される前記
   索引記憶手段の記憶場所に当該項の識別子を書込
   んで前記等項索引を前記汎項索引に追加登録する
   ものであり、前記検索・選択手段は、前記目標項
   入力手段から目標項が与えられることにより、前
   記等項アドレス生成手段が生成したアドレスで前
   記汎項索引に追加登録された前記等項索引を検索
   するものであることを特徴とする特許請求の範囲
   第１項記載の単一化候補項の選択装置。 ３ 前記索引記憶手段は、前記汎項索引として登
   録された各項の識別子と、前記等項索引として登
   録された各項の識別子とを、区別可能な状態で同
   一の記憶場所に記憶したものであることを特徴と
   する特許請求の範囲第１項記載の単一化候補項の
   選択装置。 ４ 前記項の識別子は、項自体又は項のポインタ
   などの識別記号であることを特徴とする特許請求
   の範囲第１項記載の単一化候補項の選択装置。