JPH01156826A - 単一化候補項の選択装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 知識ベース処理における、単一化処理または単一化検索
に使用される単一化候補項の選択装置に関する。

（従来の技術） 知識情報処理言語の一つであるＰｒｏｌｏｇでは、「項
」と呼ぶ形式を用いて表した述語の集合（項集合）から
なるプログラムに対し、目標となる項（目標類）が与え
られ、この目標類がプログラム中の項集合で満足させら
れるかどうかを調べて行くことを処理の基本にしている
が、この過程の中で、項と項との単一化（Ｕｎｉｆｉｃ
ａｔｉｏｎ）が重要な役゛　割を果たす（Ｖ、Ｐ、ＣＩ
ｏｃｋｓｉｎ／Ｃ，Ｓ、Ｍｅｌｌｉｓｈ著、中村克彦訳
ｒ　Ｐｒｏｌｏｇプログラミング」マイクロソフトウェ
ア刊：参照）。

二つの項ｔｌとｔ２の単一化の成功・失敗は、■ｔｉと
ｔ２が全く同じであれば単一化成功、■１１またはｔ２
に変数があるとき、（同一変数には同じ項を代入すると
して）その変数に適当な項を代入することによって、他
方と一致させることができれば単一化成功、これら■と
■とによって単一化成功でく方法を採ることが多い。し
かし、この方法では、項集合の中で目標類との単一化に
成功する項が少数であるのにも拘らず、処理として意味
のあるこれら少数の項との単一化を行うために、より多
くの失敗可能性のある単一化作業を行わねばならないと
いう欠点があった。その結果、従来、単一化の処理は時
間のかかるものであり％　Ｐｒｏｌｏｇのプログラムは
実行速度の点で、他の言語のプログラムより遅くなるこ
とが多かった。

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

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

合の全ての項と単一化を試みるかわりに、単一化可能な
項が必ず含まれている部分類集合の各項とのみ単一化を
試みるようにしたものであり、換言すれば、単一化に失
敗する項のうちの大部分の項とは始めから単一化を試み
ないようにすることにより、全体の処理時間を短縮し、
実行速度を上げようとするものである。

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

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

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

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

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

登録手段は、前記項集合記憶手段から任意の項が与えら
れることにより、前記汎項アドレス生成手段が生成した
アドレスで指示される前記索引記憶手段の記憶場所に、
当該項の識別子を書込んで前記汎項索引を登録するとと
もに、前記項集合記憶手段から任意の項が与えられるこ
とにより、前記等項アドレス生成手段が生成したアドレ
スで指示される前記等項索引記憶手段の記憶場所に、当
生成手段が生成した各アドレスで前記索引記憶手段中の
前記等項索引を検索し、前記目標項入力手段から目標項
が与えられることにより、前記等項アドレス生成手段が
１成したアドレスで前記汎項索引を検索し、さらに前記
目標項入力手段から目標項が与えられることにより、前
記等項アドレス生成手段が生成したアドレスで前記等項
索引を検索し、登録されている項の識別子があった場合
にこれを単一化候補項として読み出すものである。

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

「項」の表現は数学で用いる関数の表現と同様テアッテ
、例エバ、ｆ’（ｇＧａ、ｂ）　５ｈ（Ｘ））などと表
現される。ここで、ｒやｇやｈなどは一種の関数記号で
あり、ｆとｇにはそれぞれ２個の項を代入できる場所が
あって、この場合には、ｆにはｇ、ｈなる項が、ｇには
ａ、ｂなる項がそれぞれ入っている。

数）に対して、定数と呼ぶことにする。

いま」−記の項の例をｔｌとすると（ｔｌ−ｆ’（ｇ（
ａ、ｂ）、ｈ（Ｘ））　）、ｔｌと単一化可能な項とし
ては、ｔ２−１’（ｇ（ａ、Ｙ）浦（ｇ（ｃ、ａ）））
などがある。この場合、単一化は、Ｘ−ｇ（Ｃ，ａ）ｌ
　　Ｙ−ｂとおけば、ｔｌもｔ２も、ともにｆ’（ｇ（
ａ、ｂ）、ｈ（ｇ（ｃ、ａ）））となるので、成功する
。このようにｔｌと単一化可能な項は他にも、ｒ（ｇ（
ａ、ｂ）、ｈ（１’（ｄ（ｂ、ｈ（ｃ）、ｋ）、Ｚ））
）、１’（ｇ（ａ、ｂ）。

ｈ（ｄ（ｙ、ｂ、ａ）））、　・・・・・−・・・・・
４（Ｘ、ｈ（ｇ（ａ、Ｙ）））、　−などと、無数に存
在する。単一化はこのように、変数を含む項では、無数
の相手と成功し得るので、単純な一致検索のように、あ
らかじめハツシング・テーブルに登録をしておくことに
より、検索を、ゴ連化するという手法を使うことができ
ない。

ところで、項の表現として、上記の表現以外に、各定数
にそのａｒｔｔｙを対にしたものを、括弧“０”を使わ
ずに、その出現順に書き並べた、「線形表現」がある。

この表現によると、上記のｔｌ、　ｔ２は ｔｌ−ｆ：２．　ｇ：２．　ａ：０．　ｂ：０．　ｈ：
１．　Ｘ：０閣と書かれる。このように（単一化によっ
て）変数に代入を行うと、線形表現では、その変数の位
置より左側だけが影響を受ける。

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

項　　　　　　核　　　　　　　　　　左定数長ｔｌ−
ｆ’：２．　ｇ：２．　ａ：０．　ｂ：ｏ、　ｈ：１　
　　　　　・＝−５ｔ２−ｆ’：２．　ｇ：２．　ａ：
０　　　　　　　　　　　・・・−・−３ｔ３・ｆ’：
２．　ｇ：２．　ａｇｏ、　ｂ：ｏ、　ｈ：ｌ、　ｇ：
２．　ｃ：０．　ａｇ。

・・・・・・８ ［１］ｔｌと１２が単一化できるためには、ｔｌとｔ２
の左定数長をそれぞれｎｌ、　ｎ２とすると、１１と１
２の線形表現を比較して、左端からｓｉｎ　ｌｎｌ、　
ｎ２１番目までの定数が完全に一致している必要がある
。

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

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

［２］ｔｌとｔ２が単一化できるためには、１１とｔ２
の左定数長をそれぞれｎｌ、　ｎ２とすると、 （ａ）ｎｌ＞ｎ２ならば・・・・・・左端からｎ２番目
まで一致していること。つまり、ｔｌの核のｎ２番目ま
での定数がｔ２の核と一致していること。

（ｂ）ｎｌ＜ｎ２ならば・・・・・・左端からｎ１番目
まで一致していること。つまり、ｔ２の核のｎ１番目ま
での定数がｔｌの核と一致していること。

（ｃ）ｎｌ−ｎ２ならば・・・・・・左端からｎｌ（ｏ
ｒｎ２）番目まで一致していること。つまり、Ｋ（ｔｌ
）とＫ（ｔ２）が完全に一致していること。

が必要である。

ここで、上記必要条件のうち（ａ）が成立しているとき
、「ｔ２は、ｔｌの「汎項」である。」と定義し、「ｔ
２は、１１より「−殺性」が高いＪと言うことにする。

また、（Ｃ）が成立している時、ｒｔ２は、【ｌのｒ等
項」である」と定義する。さらに、項ｔの汎項の全体を
、ｇ☆ｔと書くことにする。

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

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

さて、汎項アドレス生成手段は、ある項が与えられると
、その項の（全ての）汎項の核（Ｋ（ｇ☆ｔｌ））に対
して、その核から一定のアルゴリズムで索引記憶手段の
アドレスを出力する。

たとえば、前例のｔｉに対して、その汎項の核Ｋ（ｇ☆
ｔｌ）は、 ｋｌｌ：　　　　　　ｆ　二２．ｇ：２．ａ：０．ｂ：
０−ｋ１２：　　　ｆ：２．ｇ：２．ａ：０−ｋ１３：
　　　ｆ：２．ｇ：２− ｋ１４：　　　ｆ’：２− ｋ１５：　　　− の５個あるが、これらの各文字列を適当なハツシングに
よって、例えば０〜２５５の範囲のアドレＡ（ｋ１３）
−Ｘ’ＡＢ’ Ａ（ｋ１４）−Ｘ’６６゜ Ａ（ｋ１５）−Ｘ’００゜ 等類アドレス生成手段は、ある項を与えられると、その
項の核から一定のアルゴリズムで索引記憶手段のアドレ
スを出力する。この時に用いるアルゴリズムは、汎項ア
ドレス生成手段で用いるアルゴリズムと、同じ記憶手段
に対しては同じものを用いる。例えば、前例のｔｌに対
しては、その核Ｋ（ｔｌ）は ｋｌｏ：　　　ｆ’：２．ｇ：２．ａ：Ｏ，ｂ：Ｏ，ｈ
：１．−であり、前とおなじハツシングアルゴリズムで
は、索引記憶手段に対するアドレスとして、次の数を出
力する。

Ａ（ｋｌＯ）　−Ｘ’７４’ 本発明では、このようなアドレス生成手段を用いて任意
の項についての汎項索引と等項索引とを索引記憶手段に
登録しておき、目標項から求められる汎項アドレスと等
項アドレスとによって上記索引記憶手段を検索するよう
にしているので、単一の実施例について説明する。

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

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

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

憶手段５０のアドレスを出力する手段である。

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

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

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

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

名称記憶部１４は１語３２ビツトの記憶装置のＮ番地か
ら開始され、各シンボルの名称の綴りを格納する部分で
ある。１個のシンボルの名称の綴りは１個以上の文字か
らなるが、１語に４文字づつ区切って記憶する。１語の
なかでの余白には、綴りの終了または余白を表す記号（
１）で埋められと余白の“／ｌ”を合せた“Ｉｙ／／”
を格納している。

シンボル定義部１５はやはり１語３２ビツトの記憶装置
のＡ番地から開始され、項に使われる各シンボルのａｒ
ｌｔｙと、そのシンボルのシンボル定義子とを対にして
記憶しておく部分である。なお、ここで上記シンボル定
義子とは、名称記憶部１４中の当該シンボルが記憶され
ている記憶場所のＮからの相対アドレスを示している。

例えば、前述の例における項１１に現れる“ｆ″なるシ
ンボルは、Ａ＋６番地に定義されており、ａｒｌｔｙは
２、名称記憶部１４でのその名称（“ｆ”）の相対番地
は１１であることを示している。また、変数の場合はそ
のａｒｉｔｙは常に０であるので、ａｒｉｔｙのかわり
に、変数であるとを示すｘ’ｐｐ’を格納する。例えば
前記の例項１１における変数“Ｘ”を表すシンボルはＡ
　＋１００番地に定義されており、その内容は、変数を
示すＦＦと、名称記憶部において“Ｘ′が格納されてい
る記憶場所の相対番地１７とを示している。

分である。なお、ここで項要素定義子とは、シンボル定
義部１５中の当該シンボルについてのシンボル定義子が
格納されている記憶場所のＡからの相対アドレスを示し
ている。例えば、前記の例で項ｔｉはＴ＋２５番地から
格納されていて１１の線形表現： ｆ’：２．　ｇ：２．　ａ：０．　ｂ：０．　ｈ：ｌ、
　Ｘ：０を表している。

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

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

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

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

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

項集合記憶手段ｌＯは項識別子を１個読みだす毎に、そ
の項識別子をＰＮ端子から出力し、かつそのシンボル定
義子を、さらにそのシンボル定義子の指示する相対番地
を用いて、名称記憶部１４から名称の綴りを読みだして
、ＤＡＴＡ端子から順に出力する。例えば、第４図の１
６で示す項識別子が項集合指定部１３から読み出される
と、この項識別子をＰＮ端子から出力するとともに、こ
の項識別子が指示する項の項要素の数が６、項定義部１
２での項の格納開始番地が２５であるので、項定義部１
２内のアドレスＴ＋２５からＴ＋３０までの６個の項要
素定義子を読み出し、次にこれらの項要素定義子が指示
する相対番地がそれぞれ８．７．１．２．８．１００で
あるので、シンボル定義部１５内のＡ＋６．Ａ＋７．Ａ
＋１．Ａ＋２．Ａ＋８゜Ａ＋１００に格納されているシ
ンボル定義子を読み出し、続いてこれらのシンボル定義
子が指示する、名称記憶部１４の相対番地がそれぞれ１
１．１４，３．６゜１３．１７であるので、名称記憶部
１４から、Ｎｕｌｌ。

Ｎ＋１４．Ｎ＋３．Ｎ＋６．Ｎ＋１３．Ｎ＋１７に格納
されている名称の文字列、ｆ’、ｇ、ａ、ｂ、ｈ、Ｘを
読み出しテＤＡＴＡ端子から送り、モの項の汎項アドレ
スを生成することを要求する。

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

例えば、第５図の１６なる項識別子から前記のようにし
て読み出された項の線形表現での文字列：ｆ、ｇ、ａ、
ｂ、ｈ、ＸがＤＡＴＡ　１端子から入力されると、汎項
アドレス生成手段３０は最初に現れる変数（Ｘ）以下を
取除いてこの項の核：　ｆ、ｇ、ａ、ｂ、ｈ、−、を得
て、これからこの項の汎項の核：　ｆ’、ｇ、ａ、ｂ、
−；１’、ｇ、ａ、−；　ｆ’、ｇ、−；　ｒ、−；　
−：　　を求めて、この文字列からハツシング操作によ
って、Ｘ’ＯＥ゛、Ｘ’３６°。

Ｘ’ＡＢ’、Ｘ’６Ｂ’、Ｘ’００’なるアドレスを作
る。なお、このハツシングは、対象とする文字列の各文
字のＡＳＣＩＩ　ｃｏｄｅを、ａ（１）　、ａ（２）　
＝＝−、ａ（ｎ）　、−、ａ（Ｎ）としたとき、次の斬
化式を用いている。

の方法によると、ＩＩ（Ｎ−ｔ）、ｎ（ｔ）、・・・、
　ＩＩ　（０）はそれぞれ汎項の核に対するハツシング
結果になっている。

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

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

例えば、第５図の１６の処理の場合は、前記のように汎
項アドレス生成手段３０から、汎項アドレスとして、Ｘ
’ＯＥ”、Ｘ’３Ｂ’、Ｘ’ＡＢ’、Ｘ’８８°、ｘ’
ｏｏ°なルアドレスが次々に生成されるので、これらの
アドレ段１０に記憶されている項集合の全ての項に対し
て、その汎項の核（と同じ核を持つ項の核）からその項
の項識別子を直ちに検索するための索引表を、汎項索引
記憶手段５０の中に作り出す。

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

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

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

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

等類アドレス生成手段４０はＣ端子からこの要求を受け
ると、ＤＡＴＡＩ端子から人力される項自身から、その
項の核を抽出し、その核の文字列からハ項アドレス生成
手段４０は最初に現れる変数（Ｘ）以下を取除いてこの
項の核：　ｒ、ｇ、ａ、ｂ、ｈ、−、を得て、この文字
列からハツシング操作によって、Ｘ’７４’なるアドレ
スを作る。このときのハツシングは、前記（ａｔ）と同
じものを用いている。

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

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

例えば、第５図の１６の処理の場合は、前記のように等
類アドレス生成手段４０から、等類アドレスとして、ｘ
°７４°なるアドレスが生成されるので、このようにし
て、第１の等項登録部６２は項・集合記憶手段１０に記
憶されている項集合の全ての項に対して、その核（と同
じ核を持つ項の核）からその項の項識別子を直ちに検索
するための索引表を、等項索引記憶手段５２の中に作り
出す。

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

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

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

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

このときの等類アドレス生成手段４０の動作は（ｂｌ）
の場合と全く同じであるので、説明を省略計 べ 次に、第２の等Ｊ６登鏝部６３は、等項アドレス生生成
するたびに、ｄ端子から汎項索引記憶手段５０に制御信
号を送って、その等類アドレスの指す記憶場所に、項集
合記憶手段ＩＯのＰＮ端子から出力されている項識別子
を書込むよう要求する。

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

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

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

以上のようにして、登録手段６０の制御によって（ｂ２
）最初に、汎項検索・選択部７１の動作を説明する。

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

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

例えば、第６図中２１で示した目標項が入力されていた
とすると、目標項人力手段２０は、ｆ’、ｇ、ａ、Ｙ。

ｈ、ｐ、−なる文字列をＤＡＴＡ端子から送り出す。

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

汎項アドレス生成手段３０はに端子からこの要求を受け
ると、ＤＡＴＡ２端子から入力される項の文字あるが、
例えば、第６図の２１なる目標項が入力される前記の場
合には、目標項入力手段２０から送り出される目標項の
文字列がＤＡＴＡ２端子から入力されると、汎項アドレ
ス生成手段３０は最初に現れる変数（Ｙ）以下を取除い
てこの目標項の核：ｒ、ｇ、ａ、−を得て、これからこ
の目標項の汎項の核：ｒ、ｇ、−；　ｒ、−；−；を求
めて、この文字列からノ１ツシングニヨッテ、Ｘ’ＡＢ
’　、Ｘ’６６°、ｘ’ｏｏ°なるアドレスを生成し、
ＡＤＲ９端子から出力する。このとき用いるハツシング
は（ａｌ）でのものと同じである。

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

等項索引記憶手段５２はＲＣ端子からこの要求を受ける
と、ＭＤＩ端子から入力されるアドレスの指す記憶場所
の語を読み出し、もしその語が空で゛なくＸ°６６°、
ｘ’ｏｏ°なるアドレスを出力するので、等項索引記憶
手段５２はこれらのアドレスの指す記憶場所の語を読み
出す。第６図の場合にはこれらの語にはなにも登録され
て（書込まれて）いないので、単一化候補項は出力され
ない。

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

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

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

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

ら等類アドレス生成手段４０に制御信号を送って、目標
類入力手段２０から送り出された項の等類アドレスを生
成するよう要求する。

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

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

次に、第１の等順検索・選択部７２は、等類アドレス生
成手段４０が上記のようにして等項アドレス汎項索引記
憶手段５０はＲＣ端子からこの要求を受けると、ＡＤ２
端子から入力されるアドレスの指す記憶場所の語を読み
出し、もしその語が空でなく項識別子が記入されていた
ら、その項識別子を単−化候補項として、ＲＤ端子から
出力する。

例えば、第６図の２１なる目標類に対しては、前記の如
く等類アドレス生成手段４０は、ｘ°８６°なるアドレ
スを出力するので、汎項索引記憶手段５０はこれらのア
ドレスの指す記憶場所の語を読み出す。

第６図の場合にはこれらの語には２個の項識別子（２５
，８６）が登録されて（書込まれて）いるので、これら
の項識別子が単一化候補項として出力される。

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

以上詳述したように、本実施例では、登録手段ＢＯによ
り検索対象の項集合を汎項索引記憶手段５０可能として
いる。

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

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

すなわち、第７図に示すように第２の等項登録部６３の
動作を削除し、代わりに第２の等順検索・録された項集
合の項識別子を、第２の等順検索・選択部７３に゛よっ
て目標類の核から表引きにより検索することで行なう。

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

登録手段６５は、汎項登録部６１と第１の等項登録部６
２とからなり、これらの動作は前記の（ａｔ）　。

（ｂｌ）と同じである。

また、検索・選択手段７５は、汎項検索・選択部７１と
第１の等順検索・選択部７２の他に、′Ｍ２の等順検索
・選択部７３を含む。汎項検索・選択部７１の動作は前
記（ｂ２）と全く同じである。また、第１の等順検索・
選択部７２の動作は前記（ａｃ２）と同じではあるが、
その結果検索される項識別子は単一化の必要条件［３］
（ａ）に合致するものだけである。

例えば、第７図の２１なる目標類に対しては、等類アド
レス生成手段４０は、Ｘ’８Ｇ’なるアドレスを出力す
るので、汎項索引記憶手段５０はこのアドレスの指す記
憶場所の語を読み出し、単一化候補項とる。

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

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

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

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

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

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

以上の実施例において、索引記憶手段として、汎項索引
記憶手段５０と等項索引記憶手段５２の２種を設けてい
るのは、単一化の必要条件［３］の（ａ）と（ｂ）の「
混合」、すなわちこれらの必要条件に合致する項の表引
き型検索動作において、不要な組合わせ：　ＫＣｇ☆１
１）とＫ（ｇ＊ｔ２）　　：による表引き結果が混じり
込むことを避けるためである。

この問題には次に述べるような別の解決法がある。

それを第３の実施例として説明する。

第１０図は、第３の実施例の構成を示している。

この実施例では索引記憶手段が、１つの索引記憶手段５
８となっている。また、８０は登録手段、９０はからな
る。

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

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

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

また、等順検索・選択部９２が目標項に対する単−化候
補項を求める動作は、前記第１の実施例の（ａｃ２）と
全く同じであって、このときは読み出さ以上に詳述した
通り、本発明の単一化候補項の高速選択装置によれば、
多数の項を含む項集合の中から、目標項と単一化成功の
可能性のある単一化候補項を、極めて高速に選択するこ
とができる。

その結果、時間のかかる単一化操作を項集合の全ての項
との組合わせに対して行う場合に必要な時間の大部分を
節約することができる。

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

【図面の簡単な説明】

第１図〜第６図は本発明の第１の実施例に係る単一化候
補項の選択装置を説明するための図で、第１図は全体構
成図、第２図は項集合記憶手段の構成図、第３図は登録
手段の構成図、第４図は検索・選択手段の構成図、第５
図は項集合記憶手段図で、第７図は動作の説明図、第８
図は登録手段の構成図、第９図は検索・選択手段の構成
図、第１０図〜第１４図は本発明の第３の実施例に係る
単一化候補項の選択装置を説明するための図で、第１０
図は全体構成図、第１１図は登録手段の構成図、第１２
図は検索・選択手段の構成図、第１３図は動作の説明図
、第１４図は登録されたフラグと項識別子の形態を示す
図である。 ｌＯ・・・項集合記憶手段、２０・・・目標項入力手段
、３０・・・汎項アドレス゛生成手段、４０・・・等類
アドレス生成手段、５０・・・汎項索引記憶手段、５２
・・・等項索引記憶手段、５８・・・索引記憶手段、６
０．８０・・・登録手段、７０゜９０・・・検索・選択
手段。 出願人　工業技術院長　飯塚幸三 第１図 第２図 第８図　　　　　　第９図 項定義部１２　　　　　　シンボル定遷ｇｔｓ　　　　
名称記憶部鳳４第５図 第１０図 第１４図 第１１図　　　　　第１２図

Claims (4)

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