JPS6326411B2

JPS6326411B2 -

Info

Publication number: JPS6326411B2
Application number: JP56101507A
Authority: JP
Inventors: Akio Shinagawa
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1981-06-30
Filing date: 1981-06-30
Publication date: 1988-05-30
Also published as: JPS583035A

Description

【発明の詳細な説明】本発明は、木構造情報探索制御方式、特に木構
造に展開されて格納されている末端ノードの出力
情報を抽出した後に、隣接する末端ノードの出力
情報を高速度でアクセスできるように、少なくと
も最も近い時点において選択されなかつたパスに
関するポインタの値を残しておき、当該値を利用
して他の出力情報探索を行なわせるようにした木
構造情報探索制御方式に関するものである。

従来から、例えば英語辞書の場合のように複数
個のキー情報の列に対応して出力情報が対応づけ
られている如き、木構造に展開される対応関係を
情報格納部に格納しておき、検索に当つて入力さ
れた検索コード列にもとづいて上記情報格納部を
アクセスし、上記キー情報と上記検索コード列上
のコードとを対比しつつ出力情報を抽出すること
が行なわれている。

このような木構造検索処理装置において、例え
ば第１図図示の如き木構造上で末端ノードＮ５に
対応する出力情報を抽出した段階で、あわせて末
端ノードＮ５に隣接する末端ノードＮ４やＮ６に
対応している出力情報を抽出したい場合が生じ
る。

このような場合におけるアクセスを有効に行な
わせる方式として、従来、(i)第１図を参照して後
述される逆ポインタを用いる方式、(ii)第２図を参
照して後述される水平ポインタを用いる方式、(iii)
第３図を参照して後述されるスタツクを用いる方
式、(iv)上記第１図図示の末端ノード例えばＮ５を
探索する処理の間にポインタを逆向きにしておい
てこれを利用する方式などが知られている。

しかし、これらの方式においても夫々難点が存
在する。以下この点について先に簡単に述べてお
く。

〔〕上記第(i)の方式一般に木構造を格納するに当つては、第１図図
示のノードＡ０，Ａ１，……Ｎ１２を木の根から
末端に向う方向にポインタp₀，p₁……をはるよう
にされ、末端ノード例えばＮ５を探索するに当つ
ては、各ノードに対応するキー情報を調べつつポ
インタp₀，p₁，p₂，p₃の如く選択してノードＮ５
に到達する。該第(i)の方式においては、末端ノー
ドＮ５に達した後に、隣接する末端ノードＮ４や
Ｎ６を効率よく調べ得るようにするため、上記ポ
インタp₀，p₁，……に対応して逆方向のポインタ
p₀′，p₁′，……を木構造に附加しておくようにす
る。そして、末端ノードＮ５から末端ノードＮ６
を探す場合には、末端ノードＮ５から逆ポインタ
p₃′……と遡つてゆき、１つのノード（例えば図
示Ａ６）に達したときに、下向きのポインタであ
つて遡つてきた方向でなくかつ最も左側に向うポ
インタ（図示の場合p₄）の有無を調べ、存在すれ
ばそのノード（図示Ａ６）からいわば左へ左へた
どつてゆくようにされる。

この方式の場合には、木構造内に逆ポインタを
附加しているために、木構造を格納するための記
憶容量が大となる。またこのために、木構造が複
数のページにまたがつて格納されることが生じ易
くなり、実際のアクセス処理に当つていわゆるペ
ージ・フオールトが生じ易くなる。

〔〕上記第(ii)の方式この方式の場合には、第２図図示の如く、末端
ノードＮ０，Ｎ１，……間に水平方向ポインタ
（図示点線）をはつておくようにする。そして、
今、１つの末端ノードＮ５に到達した状態で、隣
接するノードＮ４を調べたい場合には、上記水平
方向ポインタの内容にもとづいて即ノードＮ４を
アクセスできるようにする。勿論図示における水
平方向ポインタは一方向のみであつてもよく、ま
た両方向ある場合にはノードＮ８とＮ０とを結ぶ
ポインタは必らずしも必要としない。

この方式の場合にも、木構造内に水平方向ポイ
ンタを附加するものであり、記憶容量の増大とペ
ージ・フオルト発生頻度の増大をまねく。

〔〕上記第(iii)の方式。

第３図Ａにおいて根のノードＡ０から末端ノー
ドＮ４に向つて探索した際に、その間に通過した
ノードから出ているどのポインタを選択したか
を、第３図Ｂ図示のスタツクSTK内に順に格納
してゆく。該スタツクSTK内にはポインタpiと
当該ポインタの方向とが格納される。なお、例え
ばポインタp₀は当該ポインタによつて指示される
ノードＡ１が格納されている記憶アドレスそのも
のであり、方向「１０」は左、方向「１１」は
中、方向「０１」は右を示している。

第３図Ａ，Ｂ図示の場合に末端ノードＮ４に至
る過程において、ノードＡ０において左方向ポイ
ンタp₀が選択されたためにこの旨をスタツク
STK上に格納し、次いでノードＡ１において右
方向ポインタp₃が選択されたためにこの旨を格納
し、次いでノードＡ２において右方向ポインタp₆
が選択されたためにこの旨を格納している。そし
て例えば末端ノードＮ３を調べるには、上記スタ
ツクの内容を利用し、１つ上のノードにおいてポ
インタの存在方向を調べてノードＮ３に向うよう
にする。図示の場合には、ノードＮ４、ノードＡ
２、ノードＮ３と向うようにする。なお図示スタ
ツクSTK中の矢印×の情報は必らずしもスタツ
ク中に必要としない。

この方式の場合には、木構造とは別個にスタツ
クをもうけているために（特にこれがハードウエ
アスタツクであれば）上述のページ・フオールト
などの発生頻度は少ないが、木構造の段数が大に
なるにつれて、スタツクSTKに要する段数が大
となる。

〔〕上記第(iv)の方式。

この方式の場合には、例えば第１図図示におい
て末端ノードＮ５を探索する処理の間に通過して
きたポインタp₀，p₁，p₂，p₃の方向を夫々逆方向
に変更せしめるようにする（逆方向ポインタp₀′，
p₁′…は用いない）。そして、当該逆方向に向きを
変えたポインタをちようど逆方向ポインタと同じ
ように利用してゆくようにする。

この方式の場合には、上述の逆方向ポインタを
附加しないので、上述の記憶容量増大などの難点
は存在しない。しかし、上述の如く逆方向にはり
直したポインタを元通りに戻す必要があり、この
処理の際に非所望にページ・フオールトが発生す
ることが生じる。

本発明は、上記の点を考慮してなされたもので
あり、上述の問題点を解決した木構造情報探索制
御方式を提供することを目的としている。そして
そのため、本発明の木構造情報探索制御方式は、
ノードに対応したキー情報と１つまたは複数のポ
インタとが設定された木構造をもつて出力情報が
格納されてなり、複数のキー・コードにもとづく
コード列の各コードを上記ノードに対応して設定
されているキー情報と対比しつつ上記出力情報を
抽出する木構造検索処理装置において、上記木構
造にもとづいて上記キー情報と上記ポインタとを
格納した木構造格納情報格納部をそなえると共
に、該木構造格納情報格納部を探索する処理の間
に選択されなかつたポインタを格納する左非選択
レジスタおよび／または右非選択レジスタをもう
け、抽出された１つの出力情報に隣接する他の出
力情報を抽出するに当つて、上記左非選択レジス
タおよび／または右非選択レジスタの内容にもと
づいて上記木構造格納情報格納部をアクセスし当
該他の出力情報を探索する処理を行なうようにし
たことを特徴としている。以下図面を参照しつつ
説明する。

第４図は本発明の一実施例制御方式の概念を説
明する説明図、第５図は本発明の一実施例構成を
示す。

本発明の場合、例えば第４図において、ノード
Ａ０から末端ノードＮ５に至る探索の間に次のよ
うな処理を行なう。即ち (1) ノードＡ０において左ポインタp₀が選択され
たとき、図示レジスタＲ（右非選択レジスタ）
に選択されなかつた右ポインタp₁₃をセツトす
る。

(2) ノードＡ１において右ポインタp₆が選択され
たとき、図示レジスタＬ（左非選択レジスタ）
に選択されなかつた左ポインタP₁をリセツト
する。

(3) ノードＡ４において、右ポインタp₈が選択さ
れたことから、図示レジスタＬに左ポインタp₇
をオーバ・ライトする。

(4) ノードＡ５において、右ポインタp₁₀が選択
されたことから、図示レジスタＬに左ポインタ
p₉をオーバ・ライトする。

(5) ノードＡ６において、左ポインタp₁₁が選択
されたことから、図示レジスタＲに右ポインタ
p₁₂をオーバ・ライトする。

このようにして、末端ノードＮ５に達したと
き、図示レジスタＬにはポインタp₉がセツトさ
れ、かつレジスタＲにはポインタp₁₂がセツト
されている形となる。この状態において、例え
ば左隣りのノードＮ４を調べるにはレジスタＬ
の内容にもとづいて（当該内容はポインタp₉が
指しているノードの格納アドレスである）、ノ
ードＮ４に至り、ノードＮ４から更に右方向に
下るポイントが存在するか否かを調べ、最後的
に左隣りのノードＮ４に至る。

このようにすることによつて、木構造を格納
する記憶容量の増大に関しては問題がなく、ま
た必要とするものとしては例えば左右隣接のも
のを調べる場合には２個程度のレジスタを用意
すれば足りる。勿論、レジスタＬとして２個の
レジスタを用意し、レジスタＲとして２個のレ
ジスタを用意することによつて、左隣接、その
左隣接、右隣接、その右隣接の各末端ノードを
調べることも容易となる。この場合には、例え
ば第４図図示のレジスタＬそのものをレジスタ
Ｌ１とし、該レジスタＬ１の元の内容が転送さ
れるレジスタＬ２を用意し、レジスタＬ１の内
容が第４図に関連して説明した如く更新される
ときに当該レジスタＬ１に入つていた内容をレ
ジスタＬ２に移せばよい。

第５図は本発明の一実施例構成を示す。図中
の符号１は木構造格納情報格納部、２はアドレ
ス・レジスタ、３はデータ・レジスタ、４は分
岐判定回路部、５は制御回路部であつてマルチ
プレクサ（MPX）を制御するもの、６ないし
９は夫々マルチプレクサ、１０は左非選択レジ
スタであつて第４図図示の「レジスタＬ」に相
当するもの、１１は右非選択レジスタであつて
第４図図示の「レジスタＲ」に相当するもの、
１２，１３は夫々ゲートを表わしている。

情報格納部１内の１つの番地には、キー情報
分岐情報等を含む情報Ｆと左ポインタLPTと
右ポインタRPTとが格納されている。以下、
末端ノードＮ５に至る探索処理について説明す
る。

(6) 最初アドレス・レジスタ２に木の根のアドレ
スＡ０がセツトされる。これによつて、情報格
納部１内の番地Ａ０の内容がデータ・レジスタ
３に読出される。

(7) 分岐判定回路４は、読出された情報Ｆ０のう
ちのキー情報と検索コード列の上位部分とを比
較する。この場合には一致しており、制御回路
部５は、情報Ｆ０中の分岐情報から左ポインタ
p₀をマルチプレクサ６において選択し、かつ右
ポインタp₁₃をマルチプレクサ７において選択
する。

(8) そして今の場合には探索モードであることか
ら、上記左ポインタp₀はマルチプレクサ８を介
してレジスタ２にセツトされる。一方左ポイン
タが選択されたことからゲート１３をオンして
レジスタ１１に右ポインタp₁₃をセツトする。

(9) 次いで情報格納部１の番地Ａ１の内容が読出
される。

(10) このとき分岐判定回路４は、読出されたキー
情報と検索コード列の１つ上位のノードで比較
した部分に次いで比較すべき部分とを比較す
る。この場合にも一致であり、情報Ｆ１中の分
岐情報に基づいてマルチプレクサ６は右ポイン
タp₆を選択しかつマルチプレクサ７は左ポイン
タp₁を選択するようにされる。そして右ポイン
タp₆はマルチプレクサ８を介してレジスタ２に
セツトされ、左ポインタp₁はゲート１２を介し
てレジスタ１０にセツトされる。

(11) 次いで情報格納部１の番地Ａ４の内容が読出
される。

(12) このときも一致であることから、情報Ｆ４中
の分岐情報に基づいて右ポインタp₈がアドレ
ス・レジスタ２にセツトされ、かつ左ポインタ
p₇がレジスタ１０にオーバ・ライトされる。

(13) 次いで情報格納部１の番地Ａ５の内容が読
出される。

(14) このときも一致であることから、情報Ｆ５
中の分岐情報に基づいて右ポインタp₁₀がアド
レス・レジスタ２にセツトされ、かつ左ポイン
タp₉がレジスタ１０にオーバ・ライトされる。

(15) 次いで情報格納部１の番地Ａ６の内容が読
出される。

(16) このときにも一致であることから、情報Ｆ
６中の分岐情報に基づき左ポインタp₁₁がアド
レス・レジスタ２にセツトされ、かつ右ポイン
タp₁₂がレジスタ１１上にオーバ・ライトされ
る。

(17) そして、次に出力情報抽出モードに入り、
番地Ｎ５の内容DN５が出力情報として読出さ
れる。しかし、このモードについては第５図上
から省略されている。このとき、レジスタ１０
上にはポインタp₉が残り、レジスタ１１上には
ポインタp₁₂が残つている。

(18) 次に例えば左隣りの末端ノードＮ４を調べ
る場合には、レジスタ１０の内容p₉がアドレ
ス・レジスタ２にセツトされ、情報格納部１の
番地Ｎ４の内容を読出す。

以上説明した如く、本発明によれば、記憶容量
の増大をきたすことなく、しかも簡単なレジスタ
をもうけることによつて隣接する末端ノードに関
する情報を保持しておくことができる。

【図面の簡単な説明】

第１図ないし第３図は本発明の前提問題を説明
する説明図、第４図は本発明の一実施例制御方式
の概念を説明する説明図、第５図は本発明の一実
施例構成を示す。図中、１は木構造格納情報格納部、２はアドレ
ス・レジスタ、３はデータ・レジスタ、４は分岐
判定回路部、５は制御回路部、６ないし９はマル
チプレクサ、１０は左非選択レジスタ、１１は右
非選択レジスタを表わす。

Claims

【特許請求の範囲】

１ノードに対応したキー情報と１つまたは複数
のポインタとが設定された木構造をもつて出力情
報が格納されてなり、複数のキー・コードにもと
づくコード列の各コードを上記ノードに対応して
設定されているキー情報と対比しつつ上記出力情
報を抽出する木構造検索処理装置において、上記
木構造にもとづいて上記キー情報と上記ポインタ
とを格納した木構造格納情報格納部をそなえると
共に、該木構造格納情報格納部を探索する処理の
間に選択されなかつたポインタを格納する左非選
択レジスタおよび／または右非選択レジスタをも
うけ、抽出された１つの出力情報に隣接する他の
出力情報を抽出するに当つて、上記左非選択レジ
スタおよび／または右非選択レジスタの内容にも
とづいて上記木構造格納情報格納部をアクセスし
当該他の出力情報を探索する処理を行なうように
したことを特徴とする木構造情報探索制御方式。