JPS583035A - 木構造情報探索制御方式 - Google Patents
木構造情報探索制御方式Info
- Publication number
- JPS583035A JPS583035A JP56101507A JP10150781A JPS583035A JP S583035 A JPS583035 A JP S583035A JP 56101507 A JP56101507 A JP 56101507A JP 10150781 A JP10150781 A JP 10150781A JP S583035 A JPS583035 A JP S583035A
- Authority
- JP
- Japan
- Prior art keywords
- pointer
- information
- register
- tree structure
- node
- 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
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9027—Trees
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
本発明は、木構造情報探索制御方式、４！に木構造に展
開されて格納部れている末端ノードの出力情報を抽出し
た後に、隣接する末端ノードの出力情報を高速度でアク
セスできるように、少表くとも最も近い時点において選
択されなかったパスに関するポインタの値を残しておき
、当該値を利用して他の出力情報探索を行なわせるよう
にした木構造情報探索制御方式に関するものである。
開されて格納部れている末端ノードの出力情報を抽出し
た後に、隣接する末端ノードの出力情報を高速度でアク
セスできるように、少表くとも最も近い時点において選
択されなかったパスに関するポインタの値を残しておき
、当該値を利用して他の出力情報探索を行なわせるよう
にした木構造情報探索制御方式に関するものである。
従来から１例えば英語辞書の場合のように複数側のキー
情報あ列に対応して出力情−が対応づけられている如き
、木構造に展開される対応関係を情報格納部に格納して
おき、検索に当って入力され九検索コード列に本とづい
て上記情報格納部をアクセスし、上記キー情報と上記検
索コード列上のブードとを対比しつつ出力情報を抽出す
ることが行表われている。
情報あ列に対応して出力情−が対応づけられている如き
、木構造に展開される対応関係を情報格納部に格納して
おき、検索に当って入力され九検索コード列に本とづい
て上記情報格納部をアクセスし、上記キー情報と上記検
索コード列上のブードとを対比しつつ出力情報を抽出す
ることが行表われている。
このような木構造検索処理装置において１例えば第１図
図示の如き゛木構造上で末端ノードＮ５に対応する出力
情報を抽出した段階で、あわせて末端ノードＮ５１１Ｃ
＠接する末端ノードＮ４やＮａｋ対応している出力情報
を抽出したい場合が生じる。
図示の如き゛木構造上で末端ノードＮ５に対応する出力
情報を抽出した段階で、あわせて末端ノードＮ５１１Ｃ
＠接する末端ノードＮ４やＮａｋ対応している出力情報
を抽出したい場合が生じる。
このような場合におけるアクセスを有効に行なわせる方
式として、従来、（１）第１図を参照して後述される逆
ポインタを用いる方式、 （Ｉｆ）第２図を参照して後
述される水平ポインタを用いる方式、（１）第３図を参
照して後述されるスタックを用いる方式、←）上記第１
図図示の末端ノード例えばＮ５を探索する処理の間にポ
インタを逆向きｋしておいてこれを利用する方式などが
知られている。
式として、従来、（１）第１図を参照して後述される逆
ポインタを用いる方式、 （Ｉｆ）第２図を参照して後
述される水平ポインタを用いる方式、（１）第３図を参
照して後述されるスタックを用いる方式、←）上記第１
図図示の末端ノード例えばＮ５を探索する処理の間にポ
インタを逆向きｋしておいてこれを利用する方式などが
知られている。
しかし、これら各方式においても夫々難点が存在する。
以下この点について先に簡単に述べておく。
（１）上記第（１）の方式。
一般に木構造を格納するＫｍつては、第１図図示のノー
ドＡＯ，Ａ１．・・・・・・Ｎ１２ を木の根から末
端に向う方向にポインタｐＯ，νｌ・・・・・・を社る
ようＫされ、末端ノード例えばＮ５を探索するに当って
は、各ノードに対応するキー情報を調べつつポインタ９
０． ｐＬ ｐＬ ｔｓの如く選択してノードＮ５に到
達する。峡第（１）の方式においては。
ドＡＯ，Ａ１．・・・・・・Ｎ１２ を木の根から末
端に向う方向にポインタｐＯ，νｌ・・・・・・を社る
ようＫされ、末端ノード例えばＮ５を探索するに当って
は、各ノードに対応するキー情報を調べつつポインタ９
０． ｐＬ ｐＬ ｔｓの如く選択してノードＮ５に到
達する。峡第（１）の方式においては。
末端ノードＮ５に達した後に、隣接する。末端ノードＮ
４やＮ６を効率よく調べ得るようにする九めに、上記ポ
インタνＯ，ｊ１１．・・・・・・ｋ対応して逆方向の
ポインタｐＯニジｌ；・・・・・・を木構造に附加して
おくようＫする。そして、末端ノードＮ５から末端ノー
ドＮ６を探す場合には、末端ノードＮ５“から逆ポイン
タｔ３′・・・・・・と遍ってゆき、１つのノード（例
えば図示Ａ６）Ｋ違したときに。
４やＮ６を効率よく調べ得るようにする九めに、上記ポ
インタνＯ，ｊ１１．・・・・・・ｋ対応して逆方向の
ポインタｐＯニジｌ；・・・・・・を木構造に附加して
おくようＫする。そして、末端ノードＮ５から末端ノー
ドＮ６を探す場合には、末端ノードＮ５“から逆ポイン
タｔ３′・・・・・・と遍ってゆき、１つのノード（例
えば図示Ａ６）Ｋ違したときに。
下向きのポインタであって遡ってきた方向でなくかつ最
も左側に向うポインタ（図示の場合ｐ４）ｅｌＫ無を調
べ、存在すればそのノード（図示Ａ６）からいわば左へ
左へたどってゆくようＫされる。
も左側に向うポインタ（図示の場合ｐ４）ｅｌＫ無を調
べ、存在すればそのノード（図示Ａ６）からいわば左へ
左へたどってゆくようＫされる。
この方式の場合には、木構造内に逆ポインタを附加して
いるために、木構造を格納する丸めの記憶容量が大と表
る。ｔたこのために、木構造が複数のページＫｔたがっ
て格納されることが生じ易くなり、 ｓ際のアクセス処
理Ｋｍつていわゆるページ・フォールトが生じ易くなる
。
いるために、木構造を格納する丸めの記憶容量が大と表
る。ｔたこのために、木構造が複数のページＫｔたがっ
て格納されることが生じ易くなり、 ｓ際のアクセス処
理Ｋｍつていわゆるページ・フォールトが生じ易くなる
。
〔璽〕上記第（１）の方式。
この方式の場合には、第２図図示の如く、末端ノードＮ
Ｏ，Ｎｌ、・・・・・・間に水平方向ポインタ（図示点
ｍ＞をはっておくようにする。そして、今。
Ｏ，Ｎｌ、・・・・・・間に水平方向ポインタ（図示点
ｍ＞をはっておくようにする。そして、今。
１つの末端ノードＮ５に到達した状態で、隣接するノー
ドＮ４を調べたい場合には、上記水平方向ポインタの内
容にもとづいて即ノードＮ４をアクセスできるようにす
る。勿論図示における水平方向ポインタは一方向のみで
あって本よ＜、また両方向ある場合にはノードＮ８とＮ
Ｏとを結ぶポインタは必らずしも必要としない。
ドＮ４を調べたい場合には、上記水平方向ポインタの内
容にもとづいて即ノードＮ４をアクセスできるようにす
る。勿論図示における水平方向ポインタは一方向のみで
あって本よ＜、また両方向ある場合にはノードＮ８とＮ
Ｏとを結ぶポインタは必らずしも必要としない。
この方式の場合にも、木構造内に水平方向ポインタを附
加するものであシ、記憶容量の増大とページ・フォルト
発生頻度の増大をまねく。
加するものであシ、記憶容量の増大とページ・フォルト
発生頻度の増大をまねく。
〔厘〕上記館（―）の方式。
第３図（Ａにおいて根のノードＡＯから末端ノードＮ４
に向って探索した際に、その間に通過し九ノードから出
ているどのポインタを選択したかを、第３図ω）図示の
スタックＳＴＫ内ＫＪ［に格納してゆく。蚊スタックＳ
ＴＫ内にはポインタν１とｍｌポインタの方向とが格納
される。
に向って探索した際に、その間に通過し九ノードから出
ているどのポインタを選択したかを、第３図ω）図示の
スタックＳＴＫ内ＫＪ［に格納してゆく。蚊スタックＳ
ＴＫ内にはポインタν１とｍｌポインタの方向とが格納
される。
なお１例えばポインタｐ０は蟲レボインタによって指示
されるノードＡ１が格納されている記憶アドレスそのも
のであり、方向「１０」は左、方向「１１」は中、方向
「０１」は右を示している。
されるノードＡ１が格納されている記憶アドレスそのも
のであり、方向「１０」は左、方向「１１」は中、方向
「０１」は右を示している。
第３図（Ａ）（Ｂ）図示の場合に末端ノードＮ４に至る
過＠において、ノードＡＯにおいて左方向ポインタνＯ
が選択づれたためにこの旨をスタックＳＴＫ上に格納し
９次いでノードＡＩにおいて右方向ポインタｐ３が選択
されたためにこの旨を格納し９次いでノードＡ２におい
て右方向ポインタｔ−が選択されえ九めにこの旨を格納
している。そして例えば末端ノードＮ３を調べるＫは、
上記スタックの内容を利用し、１つ上のノードにおいて
ポインタの存在方向を調べてノードＮ３に向うようにす
る。図示の場合には。
過＠において、ノードＡＯにおいて左方向ポインタνＯ
が選択づれたためにこの旨をスタックＳＴＫ上に格納し
９次いでノードＡＩにおいて右方向ポインタｐ３が選択
されたためにこの旨を格納し９次いでノードＡ２におい
て右方向ポインタｔ−が選択されえ九めにこの旨を格納
している。そして例えば末端ノードＮ３を調べるＫは、
上記スタックの内容を利用し、１つ上のノードにおいて
ポインタの存在方向を調べてノードＮ３に向うようにす
る。図示の場合には。
ノードＮ４． ノードＡ２． ノードＮ３と向うよ
うにする。な−お図示スタックＳＴＫ中の矢印Ｘの情報
は必らずしもスタック中に必要としない。
うにする。な−お図示スタックＳＴＫ中の矢印Ｘの情報
は必らずしもスタック中に必要としない。
この方式の場合には、木構造とは別個にスタックを４う
けている九め１／Ｃ（ｌ＃にこれがハードウェアスタッ
クであれば）上述のページ・フォールトなどの発生頻度
は少ないが、木構造の段数が大になるＫつれて、スタッ
ク８７ＫＫ要する段数が大となる。
けている九め１／Ｃ（ｌ＃にこれがハードウェアスタッ
クであれば）上述のページ・フォールトなどの発生頻度
は少ないが、木構造の段数が大になるＫつれて、スタッ
ク８７ＫＫ要する段数が大となる。
（Ｗ）上記第←）の方式。
この方式の場合には１例えば第ｉｌ１図示において末端
ノードＮ５を探索する処理の関に通過してきたポインタ
９０．シ１，９鵞、 ｔＳの方向を夫々逆方向に変更せ
しめるようＫする（逆方向ポインタ９０−ν１′・・・
は用いない）。そして、当該逆方向に向きを変えたポイ
ンタをちょうど逆方向ポインタと同じように利用してゆ
くようにする。
ノードＮ５を探索する処理の関に通過してきたポインタ
９０．シ１，９鵞、 ｔＳの方向を夫々逆方向に変更せ
しめるようＫする（逆方向ポインタ９０−ν１′・・・
は用いない）。そして、当該逆方向に向きを変えたポイ
ンタをちょうど逆方向ポインタと同じように利用してゆ
くようにする。
この方式の場合には、上述の逆方向ポインタを附−加し
な匹ので、上述の記憶容量増大なくの難点は存在し危い
、しかし、上述の如く逆方向にはシ直したポインタを元
通りに戻す必要があり、この処理の際に非所望にページ
・７オ一ル本発明は、上記の点を考慮してなされたもの
であシ、上述の問題点を解決した木構造情報探索制御方
式を提供することを目的としている。そしてそのため９
本発明の木構造情報探索制御方丈は。
な匹ので、上述の記憶容量増大なくの難点は存在し危い
、しかし、上述の如く逆方向にはシ直したポインタを元
通りに戻す必要があり、この処理の際に非所望にページ
・７オ一ル本発明は、上記の点を考慮してなされたもの
であシ、上述の問題点を解決した木構造情報探索制御方
式を提供することを目的としている。そしてそのため９
本発明の木構造情報探索制御方丈は。
ノードに対応したキー情報と１つま九は複数のポインタ
とが設定された木構造をもって出力情報が格納されてな
り、複数のキー・コードにもとづく；−ド列の各コード
を上記ノードに対応して設定されているキー情報と対比
しつつ上記出力情報を抽出すみ木構造検索処理装置にお
いて、上記木構造にもとづいて上記キー情報と上記ポイ
ンタとを格納した木構造格納情報格納部をそなえると共
に。
とが設定された木構造をもって出力情報が格納されてな
り、複数のキー・コードにもとづく；−ド列の各コード
を上記ノードに対応して設定されているキー情報と対比
しつつ上記出力情報を抽出すみ木構造検索処理装置にお
いて、上記木構造にもとづいて上記キー情報と上記ポイ
ンタとを格納した木構造格納情報格納部をそなえると共
に。
該木構造格納情報格納部を探索するｉｌｌの関に選択さ
れなかったポインタを格納する左非選択レジスタおよび
／または右非選択レジスタをもうけ。
れなかったポインタを格納する左非選択レジスタおよび
／または右非選択レジスタをもうけ。
抽出され九１つの出力情報ｋｌｉ＊する他の出力情報を
抽出するに幽って、上記左非選択レジスタおよび／ま丸
線右非選択レジスタの内容にもとづいて上記本構造格納
情報格納部をアクセスしめ１他の出力情報を探索する処
理を行なうようＫしたことを特徴としている。以下図面
を参照しつつ説明する。
抽出するに幽って、上記左非選択レジスタおよび／ま丸
線右非選択レジスタの内容にもとづいて上記本構造格納
情報格納部をアクセスしめ１他の出力情報を探索する処
理を行なうようＫしたことを特徴としている。以下図面
を参照しつつ説明する。
第４図は本発明の一集施例制御方式の概念を説明する説
明図、第５図は本発明の一実施例構成を示す。
明図、第５図は本発明の一実施例構成を示す。
本発明の場合９例えば第４図において、ノードＡＯから
末端ノードＮ５に至る探索の間に次のような処理を行な
う。即ち （１） ノードＡＯにおいて左ポインタ１０が選択さ
れたとき１図示レジスタＲ（右非選択レジスタ）Ｋ選択
されなかつ九右ポインタｐ１Ｂをセットする。
末端ノードＮ５に至る探索の間に次のような処理を行な
う。即ち （１） ノードＡＯにおいて左ポインタ１０が選択さ
れたとき１図示レジスタＲ（右非選択レジスタ）Ｋ選択
されなかつ九右ポインタｐ１Ｂをセットする。
（２） ノードＡｌｊおいて右ポインタｊ６が選択さ
れたとき１図示レジスタＬ（左非選択レジスタ）Ｋ選択
されなかった左ポインタ１４１をセットする。
れたとき１図示レジスタＬ（左非選択レジスタ）Ｋ選択
されなかった左ポインタ１４１をセットする。
（３） ノードＡ４において、右ポインタを口が選択
され九ことから１図示レジスタＬｍ左ポインタｐフをオ
ーバ・ライトする。
され九ことから１図示レジスタＬｍ左ポインタｐフをオ
ーバ・ライトする。
（４） ノードＡ５において、右ポインタｐ１０が選
択されたことから９図示レジスタＬＫ左ボ・ｆンタｐ會
をオーバ・ライトする。
択されたことから９図示レジスタＬＫ左ボ・ｆンタｐ會
をオーバ・ライトする。
（ｊｌ） ノードＡ６において、左ポインタ９１１が
選択されたことから１図示レジスタＲＫ右ポインタｔｔ
Ｓをオーバ・ライトする。
選択されたことから１図示レジスタＲＫ右ポインタｔｔ
Ｓをオーバ・ライトする。
このようｋして、末端ノードＮ５に達し九とき。
図示レジスタＬＫはポインタシ会がセットされ。
かつレジスタＲＫはポインタｐｌｓがセットされている
形となる。こめ状１１において９例えば左ＩＩりのノー
ドＮ４を調べるｋはレジスタＬの内容ｌＩＣ４とづ−て
（当該内容はポインタｐ９が指しているノードの格納ア
ドレスである）、ノードＮ４に至シ、ノードＮ４から更
に右方向に下るポイントが存在するか否かを調べ、最後
的に左隣シのノードＮ４に至る。
形となる。こめ状１１において９例えば左ＩＩりのノー
ドＮ４を調べるｋはレジスタＬの内容ｌＩＣ４とづ−て
（当該内容はポインタｐ９が指しているノードの格納ア
ドレスである）、ノードＮ４に至シ、ノードＮ４から更
に右方向に下るポイントが存在するか否かを調べ、最後
的に左隣シのノードＮ４に至る。
このようにするととｋよって、木構造を格納する記憶容
量の増大に関して社問題がなく、ま九必要とするものと
しては例えば左右隣績のものを調べる場合には２伽程度
のレジスタを用意すれば足シる。勿論、レジスタＬとし
て２個のレジスタを用意し、レジスタＲとして２個のレ
ジスタを用意することｋよって、左隣接、その左隣接、
右隣接。
量の増大に関して社問題がなく、ま九必要とするものと
しては例えば左右隣績のものを調べる場合には２伽程度
のレジスタを用意すれば足シる。勿論、レジスタＬとし
て２個のレジスタを用意し、レジスタＲとして２個のレ
ジスタを用意することｋよって、左隣接、その左隣接、
右隣接。
その右隣接の各末端ノードを調べることも容易となる。
この場合Ｋｄ、例えば第４図図示のレジスタＬそのもの
をレジスタＬ１とし、＃レジスタＬ１の元の内容が転送
されるレジスタＬ２を用意し。
をレジスタＬ１とし、＃レジスタＬ１の元の内容が転送
されるレジスタＬ２を用意し。
スタＬ２に移せばよい。
第５図は本発明の一実施例構成を示す０図中の符号１は
木構造格納情報格納部 、２けアドレス・レジスタ、３
はデータ・レジスタ、４は分岐判定回路部、５は制御回
路部であってマルチプレクサ（ＭＰＸ）を制御するもの
、６ないし９は夫々！ルチプレクサ、１０は左非選択レ
ジスタであって第４図図示の「レジスタＬ」に相轟する
亀の、１１紘右非選択レジスタであって第４図図示の「
レジスタＲＪＫ相当するもの、１２．１３は夫々ゲート
を表わしている。
木構造格納情報格納部 、２けアドレス・レジスタ、３
はデータ・レジスタ、４は分岐判定回路部、５は制御回
路部であってマルチプレクサ（ＭＰＸ）を制御するもの
、６ないし９は夫々！ルチプレクサ、１０は左非選択レ
ジスタであって第４図図示の「レジスタＬ」に相轟する
亀の、１１紘右非選択レジスタであって第４図図示の「
レジスタＲＪＫ相当するもの、１２．１３は夫々ゲート
を表わしている。
舷情報等゛を含む情報Ｆと左ポインタＬＰＴと右ポイン
タＲＰＴとが格納されている。以下、末端ノードＮ５に
至る探索処理について説明する。
タＲＰＴとが格納されている。以下、末端ノードＮ５に
至る探索処理について説明する。
（６） 最初アドレス・レジスタ２に木の機のアドレ
ススＡＯがセットされる。これによって、情報格納部ｌ
内の番地ＡＯの内容がデータ・レジスタ３に読出される
。
ススＡＯがセットされる。これによって、情報格納部ｌ
内の番地ＡＯの内容がデータ・レジスタ３に読出される
。
（７）分岐判定回路部４Ｆｉ、読出された情報ＦＯのう
ちのキー情報と検索コード列の上位部分とを比較する。
ちのキー情報と検索コード列の上位部分とを比較する。
この場合には一致しておシ、制御回路部５は、情報ＦＯ
中の分岐情報から左ポインタ１０をマルチプレクサ６に
おいて選択し、かつ右ポインタν１３をマルチプレクサ
７において選択する。
中の分岐情報から左ポインタ１０をマルチプレクサ６に
おいて選択し、かつ右ポインタν１３をマルチプレクサ
７において選択する。
（８）そして今の場合には探索モードであることから、
上記左ポインタｙｏＦｉマルチプレクサ８を介してレジ
スタ２にセットされる。一方左ポインタが選択されたこ
とからゲート１３をオンしてレジスタｌｌｋ右ポインタ
Ｐ１３をセットする。
上記左ポインタｙｏＦｉマルチプレクサ８を介してレジ
スタ２にセットされる。一方左ポインタが選択されたこ
とからゲート１３をオンしてレジスタｌｌｋ右ポインタ
Ｐ１３をセットする。
（・）次いで情報格納部１の゛番地Ａ１の内容が読出さ
れる。
れる。
１０） このとき分岐判定回路４は、読出されたキー
情報と検索コード列の１つ上位のノードで比較した部分
（１次いで比較すべき部分とを比較する。
情報と検索コード列の１つ上位のノードで比較した部分
（１次いで比較すべき部分とを比較する。
この場合にも一致であり、情報Ｆｌ中の分岐情報に基づ
いてマルチプレクサ６は右ポインタＰ６を選択しかつマ
ルチプレクサ７は左ポインタｔ１を選択するようｋされ
る。そして右ポインタ？−はマルチプレクサ８を介して
レジスタ２にセット嘔れ、左ポインタ２１はゲー）１２
を介してレジスタＩＯＫセットされる。
いてマルチプレクサ６は右ポインタＰ６を選択しかつマ
ルチプレクサ７は左ポインタｔ１を選択するようｋされ
る。そして右ポインタ？−はマルチプレクサ８を介して
レジスタ２にセット嘔れ、左ポインタ２１はゲー）１２
を介してレジスタＩＯＫセットされる。
い）次いで情報格納部１の番地Ａ４の内容が読出される
。
。
（ロ） このときも一致であることから、情報Ｆ４中の
分岐情報に基づいて右ポインタシ専がアドレス・レジス
タ２にセットされ、かつ左ポインタｇ７がレジスタＩＯ
Ｋオーバ・ライトされる。
分岐情報に基づいて右ポインタシ専がアドレス・レジス
タ２にセットされ、かつ左ポインタｇ７がレジスタＩＯ
Ｋオーバ・ライトされる。
（ロ） 次いで情報格納部１０番地Ａ５の内容が読出さ
れる。
れる。
Ｑ４ このときも一致であることから、情報Ｆ５中の
分岐情報に基づいて右ポインタｐ１Ｇがアドレス・レジ
スタ２にセットされ、かつ左ポインタＰ９がレジスタＩ
ＯＫオーバ・ライトされる。
分岐情報に基づいて右ポインタｐ１Ｇがアドレス・レジ
スタ２にセットされ、かつ左ポインタＰ９がレジスタＩ
ＯＫオーバ・ライトされる。
θ呻 次いで情報格納部１の番地Ａ６の内容が読出きれ
る。
る。
（ロ） このときに屯一致であることから、情報Ｆ６中
の分岐情報に基づき左ポインタｐｉｍがアドレス・レジ
スタ２にセットされ、かつ右ポインタｔｌ！がレジスタ
１１上にオーバ・ライト、される。
の分岐情報に基づき左ポインタｐｉｍがアドレス・レジ
スタ２にセットされ、かつ右ポインタｔｌ！がレジスタ
１１上にオーバ・ライト、される。
Ｑｆ）そして９次に出方情報抽出モードに入り番地Ｎ５
の内容ＤＮＳが出方情報として読出される。しかし、こ
のモードについては第５図上から省略されている。この
とき、レジスタ１０上にはポインタν・が残シ、レジス
タ１１上にはポインタｔ１！が残っている。
の内容ＤＮＳが出方情報として読出される。しかし、こ
のモードについては第５図上から省略されている。この
とき、レジスタ１０上にはポインタν・が残シ、レジス
タ１１上にはポインタｔ１！が残っている。
（ロ）次ｋ例えば左ｌＩシの末端ノードＮ４を調べる場
合Ｋａ、 レジスタ１ｏの内容ν・がアドレス・レジ
スタ２にセットされ、情報格納部１０番地Ｎ４の内容を
読出す。
合Ｋａ、 レジスタ１ｏの内容ν・がアドレス・レジ
スタ２にセットされ、情報格納部１０番地Ｎ４の内容を
読出す。
以上説明した如く１本発明によれば、記憶容量の増大を
きたすことなく、シかも簡単なレジスタをもうけるとと
Ｋよって隣接する末端ノードに関する情報を保持してお
くことができる。
きたすことなく、シかも簡単なレジスタをもうけるとと
Ｋよって隣接する末端ノードに関する情報を保持してお
くことができる。
第１図ないし第３図は本発明の前提問題を説明する説明
図、第４図は本発明の一実施例制御方式の概念を説明す
る説明図、第５図は本発明の一笑施例構成を示す。 図中、１は木構造格納情報格納部、２はアドレス・レジ
スタ、３はデータ・レジスタ、４は分岐判定回路部、５
は制御回路部、６ないし９は！ルチプレクサ、１０は左
非選択レジスタ、１１は右非選択レジスタを表わす。 特許出願人 富士通株式会社 代理人弁理士 森 １） 寛 −ｊｒ２闇 す３図 （Ｂ）
図、第４図は本発明の一実施例制御方式の概念を説明す
る説明図、第５図は本発明の一笑施例構成を示す。 図中、１は木構造格納情報格納部、２はアドレス・レジ
スタ、３はデータ・レジスタ、４は分岐判定回路部、５
は制御回路部、６ないし９は！ルチプレクサ、１０は左
非選択レジスタ、１１は右非選択レジスタを表わす。 特許出願人 富士通株式会社 代理人弁理士 森 １） 寛 −ｊｒ２闇 す３図 （Ｂ）
Claims (1)
- ノードに対応したキー情報と１つまたは複数のポインタ
とが設定された木構造をもって出力情報が格納きれてな
り、複数のキー・コードにもとづくコード列の各コード
を上記ノードに対応して設定されているキー情報と対比
しつつ上記出力情報を抽出する木構造検索処理装置にお
いて、上記木構造にもとづいて上記キー情報と上記ポイ
ンタとを格納した木構造格納情報格納部をそなえると共
に、該木構造格納情報格納部を探索する処理の間に選択
されなかったポインタを格納する左非選択レジスタおよ
び／ｌたは右非選択レジスタを４うけ、抽出された１つ
の出力情報にｉｅ＊する他の出力情報を抽出するに当っ
て、上記左非選択レジスタおよび／ｌたは右非選択レジ
スタの内容にもとづいて上記木構造格納情報格納部をア
クセスし当骸他の出力情報を探索する処理を行なうよう
Ｋしたことを特徴とする木構造情報探索制御方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP56101507A JPS583035A (ja) | 1981-06-30 | 1981-06-30 | 木構造情報探索制御方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP56101507A JPS583035A (ja) | 1981-06-30 | 1981-06-30 | 木構造情報探索制御方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS583035A true JPS583035A (ja) | 1983-01-08 |
| JPS6326411B2 JPS6326411B2 (ja) | 1988-05-30 |
Family
ID=14302502
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP56101507A Granted JPS583035A (ja) | 1981-06-30 | 1981-06-30 | 木構造情報探索制御方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS583035A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS61141035A (ja) * | 1984-12-14 | 1986-06-28 | Hitachi Ltd | デ−タ検索方式 |
| JPH02112067A (ja) * | 1988-10-21 | 1990-04-24 | Nec Corp | テーブル間整合性チェック方式 |
-
1981
- 1981-06-30 JP JP56101507A patent/JPS583035A/ja active Granted
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS61141035A (ja) * | 1984-12-14 | 1986-06-28 | Hitachi Ltd | デ−タ検索方式 |
| JPH02112067A (ja) * | 1988-10-21 | 1990-04-24 | Nec Corp | テーブル間整合性チェック方式 |
Also Published As
| Publication number | Publication date |
|---|---|
| JPS6326411B2 (ja) | 1988-05-30 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Rosenfeld | Isotonic grammars, parallel grammars, and picture grammars | |
| Grefenstette | Tokenization | |
| CA1288871C (en) | Method for verifying spelling of compound words | |
| US6671856B1 (en) | Method, system, and program for determining boundaries in a string using a dictionary | |
| US4701851A (en) | Compound word spelling verification | |
| US5323310A (en) | Analyzing textual documents | |
| JPS63254559A (ja) | 複合ワードのためのスペリング援助方法 | |
| US5268840A (en) | Method and system for morphologizing text | |
| US20230124402A1 (en) | Inference Methods For Word Or Wordpiece Tokenization | |
| Apostolico et al. | Structural properties of the string statistics problem | |
| US7933885B1 (en) | Longest matching prefix search engine with hierarchical decoders | |
| JPS583035A (ja) | 木構造情報探索制御方式 | |
| Milintsevich et al. | Enhancing sequence-to-sequence neural lemmatization with external resources | |
| JPH0869476A (ja) | 検索システム | |
| US4524427A (en) | Method for making comparisons between reference logical entities and logical entities proceeding from a file | |
| CN115455948A (zh) | 一种拼写纠错模型训练方法、拼写纠错方法及存储介质 | |
| King | Table Look-up Procedures in Language Processing—Part I: The Raw Text | |
| EP0145202B1 (en) | Word spelling checking system | |
| JP2729491B2 (ja) | 可変長文字列検出装置 | |
| JPH03116375A (ja) | 情報検索装置 | |
| CN116910182B (zh) | 一种跨语言代码搜索方法及装置 | |
| CN118333053B (zh) | 语言数据处理方法、装置、计算机设备及存储介质 | |
| JPH0746362B2 (ja) | 文字列照合方法 | |
| EP0178651B1 (en) | Data retrieving apparatus | |
| AU659639B2 (en) | Analysing textual documents |