JPH03198155A - 入れ子型トークン列の検索装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は各種情報機器間で通信されるマルチメディア情
報または各種記憶媒体に記憶されつマルチメディア情報
を構成する入れ子型トークン列の検索を高速化する装置
に関するものである。

（従来の技術） 上記トークン（字句）列の検索装置は異機種情報機器間
のプロトコル（コード取り決め）変換や解析処理や、ハ
イパーテキストサーチやマルチメディアデータベース検
索に使われる。ネットワークを介した各種情報機器間の
マルチメディア情報の通信と検索に欠かせないものであ
る。ここ１こ、トークンが入れ子（ネスト）型であると
いう事は検索される情報が世界標準のＯ８Ｉ階層プロト
コルに基づいて表現されている事を意味する。

従来の入れ子型トークン列での特定トークンの検索はメ
ツセージを受信する情報機器に含まれるコンピュータに
よって、トークン列の順次読み出しとヘッダ部の解読の
済んだ後で行われた。すなわち、送られてきたメツセー
ジを一旦主記憶に格納し、トークン毎のヘッダ一部の解
読によってネストレベルの判別処理を行い、その後でホ
ストレベルの照合を行った。ここに、ホストレベルとは
メツセージに入れ子（ホストと呼ぶ）構造で含まれる多
数のトークンの入れ子の深さである。ソフトウェアによ
る処理ではホストレベルが深くなるにつれてホストレベ
ル判別までの処理時間が増加した。ホストレベルが判明
した後でないと、指定のホストレベルＮＬとＩＤコード
を持ったトークンのサーチを行えなかった。そのために
特定トークンのテキストデータの選択や特定トークンの
プロトコル変換処理に時間がかかった。この問題をもう
少し詳しく説明するために、始めに、ホストレベル検出
のプロセスを第２図を用いて説明する。

第２図はＯ８Ｉの階層プロトコルに従ってメツセージの
取扱方式（ＭＨ８）の構文規則によって作成されたトー
クン列の１例である。この図においては、トークン列２
５０の各トークンはヘッダ一部２４１とボディ一部２４
２から成る。ボディ一部２４２がさらにヘッダ一部２３
１とボディ一部２３２から成るトークン（入れ子なし）
とヘッダ一部２３３とボディ一部２３４からなるトーク
ン（入れ子あり）を含むことが出来る。

従って、ボディ一部２３４はヘッダ一部２２１．２２３
とボディ一部２２２．２２４を持つ入れ子なしトークン
列とヘッダ一部２２５とボディ一部２２６を持つ入れ子
ありトークンを含み、ボディ一部２２６はさらにヘッダ
ー部２１１とボディ一部２１２の入れ子なしトークンと
ヘッダ一部２１３とボディ一部２１４の入れ子ありトー
クンを持つ。

故に、ホストレベルＮＬ＝１のトークン２５０のボディ
一部２４２がホストレベルＮＬ＝２の２つのトークン列
を含み、第１のトークン（２３１，２３２）はＮＬ＝２
止まりであるが、第２トークンのボディ一部２３４がさ
らにＮＬ＝３のトークン（２２１，２２２Ｘ２２３．２
２４）（２２５，２２６）を含むと言う入れ子構造のト
ークン列が存在する。第２図の場合、さらに、トークン
（２２５，２２６）のボディ一部２２６がＮＬ＝４のト
ークン（２１１，２１２）（２１３，２１４）を含むこ
とまでが示されている。

入れ子でトークンを含むか否かは各トークンのヘッダ一
部のＩＤコードの６ビツト目（ホストビット）が１か０
で判定される。その事をこの図においてはＩＤコードの
＊印で示している。入れ子を含まないトークン列は先頭
位置が指定されると′各トークンのヘッド一部に含まれ
るＬＬコード（短形式）やＬコード（長形式）からボデ
ィ一部の長さと次のトークンの終わり位置あるいは始ま
り位置がわかる。トークンの終わりの後に次のトークン
のヘッダ一部があると約束されていることから、各トー
クンの先頭のＩＤコードを見つけることが簡単となる。

トークン毎のＩＤコードとホストレベルがわかった後で
はじめて、それらを使ったトークンの選択が可能になり
、選択されたトークンのプロトコル変換や内容検索が可
能になる。ホストレベルが常にトークンの先頭読みだし
位置でわかっている場合には、ＩＤコード読み出しと共
にそのトークンのヘッダ検索が可能になり、検索条件と
して与えられたホストレベルとＩＤコードと照合され、
マツチしたトークンは読みだしを続け、ミスマツチなら
、読み飛ばしを行えるが、これまでは、ホストレベルの
判定に時間が掛かって、トークンの選択処理も遅くなっ
ていた。

（発明が解決しようとする課題） 従って、本発明の目的はホストコンピュータの主記憶に
格納されたトークン列を先頭から読みだしする時に各ト
ークンの処理機能（ＩＤコード）とホストレベルの検出
と同時に検索条件にマツチしているか否かの判定を可能
にすることにある。

この検索処理の難しさは各トークンの始めと終わりが陽
に指示されていない事、ＩＤコードやＬＬコードがデー
タコードと区別できないコード（オクテツト）であるた
めに次のトークンの読みだし位置の計算抜きでは識別さ
れない事、また゛、各トークンの階層（ホスト）レベル
がビットパターンとして与えられていない事にある。

ソフトウェアによるトークン列の検索に際しては、トー
クン列をコンピュータの主記憶に格納してから、順に読
み出してヘッダー位置や処理機能やホストレベルを解読
した。ホストレベルの追跡を行う時にホストレベルの深
さが増すと共に処理付加が大きくなった。ソフトウェア
ではホストレベル毎のトークン長さの比較が並列でなく
順に行われるからである。トークンの検索はホストレベ
ルが判定した後で行われるために、ヘッダ検索処理速度
はホストレベル検索処理速度よりさらに遅くなった。本
発明はヘッダ検索処理速度をトークンの主記憶からの読
みだし速度以上にする。

（課題を解決するための手段） 従って、本発明は次のように構成される。第１の発明に
トークン列のヘッダ検索装置は、トークン列の記憶手段
と、検索条件保持手段と、前記記憶手段をアクセスする
ために開始アドレスにトークンの読み出し位置アドレス
を加算して出力する外部アドレス発生手段と、各トーク
ンの先頭のＩＤコードや長さコードを検出して保持する
ヘッダ保持手段と、ＩＤコードからのホストビット検出
手段と、ＩＤコードやホストレベルなどの属性照合手段
と、照合結果と長さコードと長さコード読みだし位置に
よって次に読み出されるトークンの読み出し位置を決め
、アドレス発生手段に与えるトークン列の読み出し位置
アドレス計算手段と、長さコードとそのコードの読み出
し位置を使って、各トークンのエンドアドレスを計算す
るエンドアドレス計算手段と、エンドアドレスをホスト
レベル別に記憶するエンドアドレス保持手段と、前記ト
ークン列の読み出し位置と前記エンドアドレスとアドレ
ス比較手段と、ホストビットによってシフトアップされ
、アドレス比較手段のマツチ出力によってリセットされ
、シフトダウンするフラグビット保持手段と、複数個の
フラグビット保持手段につながるホストレベルエンコー
ド手段とホストレベル出力レジスタとを備えることを特
徴とする。

第２の発明は、トークン列の記憶手段と、検索条件保持
手段と、前記記憶手段をアクセスするために開始アドレ
スにトークンの読み出し位置アドレスを加算して出力す
る外部アドレス発生手段と、各トークンの先頭のＩＤコ
ードや長さコードを検出して保持するヘッダ保持手段と
、ＩＤコードからのホストビット検出手段と、ＩＤコー
ドやホストレベルなどの属性照合手段と、長さコードと
長さコード読みだし位置の加算によってトークンのエン
ドアドレスを計算するエンドアドレス計算手段と、エン
ドアドレスをホストレベル別に記憶するエンドアドレス
保持手段と、前記トークン列の読み出し位置と前記エン
ドアドレスとアドレス比較手段と、ＩＤコードを受信し
たヘッダ保持手段の出力するホストビットによってシフ
トアップされ、アドレス比較手段の出力によってリセッ
トされ、シフトダウンするフラグビット保持手段と、複
数個のフラグビット保持手段につながるホストレベルエ
ンコード手段とホストレベル出力レジスタと、属性照合
手段がミスマツチを出し、ホストビットが０である時に
はエンドアドレスに１を加え、そうでないときは、現在
の読みだし位置アドレスに１を加えて、アドレス発生手
段に与えるトークン列の読みだしアドレス発生手段とを
備えることを特徴とする。

第３の発明は、第１の発明において、トークン列の読み
出し位置アドレス計算手段が現在の出力に１と長さコー
ドを加算する３入力加算器で実現され、属性照合手段の
出力がミスマツチでかつホストビットがＯの時以外は長
さコードの代わりにＯを与える事を特徴とする。

第４の発明は、第１の発明において、トークン列の読み
出し位置アドレス計算手段が、現在の出力に長さコード
を加算する加算器であって、キャリー信号によって１が
加算されることを特徴とする。

第５の発明は、トークン列の記憶手段と、前記記憶手段
をアクセスするために開始アドレスと相対的なトークン
読み出し位置アドレスを加算するアドレス発生手段と、
検索条件保持手段と、外部クロックに従ってタイミング
シーケンスを発生する順序制御手段と、前記タイミング
シーケンスによって各トークンの先頭のＩＤコードや長
さを検出して保持するヘッダ保持手段と、ＩＤコードか
らのホストビット判定手段と、前記検索条件保持手段の
内容に従って比較内容を限定するトークンの属性照合手
段と、長さコードと長さコードの読みだし位置の加算に
よってトークンのエンドアドレスを計算するエンドアド
レス計算手段と、エンドアドレスをホストレベル別に記
憶するエンドアドレス託憶手段と、全エンドアドレスと
現在のトークンの読み出し位置アドレスとの並列比較結
果とホストビットから次のトークンのホストレベルを判
定するホストレベル判定手段と、ホストレベル出力レジ
スタと、属性照合手段のミスマツチ信号と０のホストビ
ット信号の時にはトークン列の読みだし位置に１と長さ
コードを加算し、それ以外の時には１だけを加算するト
ークン列の読み出し位置アドレス手段とを備えることを
特徴とする。

第６の発明は、第１、第２、第５の発明において、検索
条件保持手段がＩＤコードとホストレベルとボディーサ
イズとトークン列記憶手段の検索開始アドレスと検索さ
れるトークン列のサイズと検索コマンドのいずれかを保
持するレジスタから成り、検索コマンドが比較の対象に
しない項目を指示するビットパターンである事を特徴と
する。

以下、図面を用いて本発明の更に詳細な説明を行う。

第１図（ａ）が請求項１に、第１図（ｂ）が請求項２に
対応する。第２図は入れ子型トークン列の説明図、第３
図はホストレベルの計算方法を、第４図はホストレベル
判別回路の構成図を、第５図は入れ子型トークン列の検
索例を、第６図は読み出し位置アドレス発生回路の説明
図であり、（ａ）が請求項３に、（ｂ）が請求項５に対
応する。第６図（ｅ）は請求項２に含まれる実施例であ
る。第７図は各トークンのオクテツトの順次見出しとス
キップのための順次制御回路の実施例であり、請求項５
に対応する。第８図は検索条件保持手段の実施例であり
、請求項６に相当する。

（実施例） 第１図（ａ）、　（ｂ）は本発明の第１の実施例である
。いずれもトークン列はトークン列メモリ１００から読
みだされる。外部アドレス発生手段１１０がトークンメ
モリ１００に格納されたトークン列の読み出し位置アド
レスを発生する。読みだし開始アドレスとサイズが検索
条件レジスタ１０５に格納されるため、アドレス発生手
段１１０から外部へ発生されるアドレスは開始アドレス
にトークンの先頭から数えたオクテツト数を示す相対ア
ドレスを加算したものである。

各トークンの先頭にあるヘッダ一部はボディー部（テキ
ストデータ）に対する処理機能を示すＩＤコードとボデ
ィ一部の長さを示すＬＬコードやＬコードからなる。こ
れらは順次に読みだされ、検出される都度、ヘッダー保
持手段１２０のＩＤコードレジスタ１２１と長さコード
レジスタ１２２に貯えられる。

ＩＤコードレジスタの６ビツト目はホストビットＮｂと
して次のトークンの始まりまで、ホストビットレジスタ
１２５に保持される。

長さコードについては、Ｏ８ＩのＭＨ８（メツセージハ
ンドリングシステム）では短形式と長形式があり、先頭
のＬＬコードの７ビツト目が０なら短形式、１なら長形
式であると定義されている。短形式の場合にはＬＬコー
ドがボディー長さを示すが、長形式の場合にはＬＬコー
ドがその後に続くＬコードの長さを示し、複数のＬコー
ドがボディー長さを示す。いずれにおいても、ボディー
長さコードがヘッダー保持手段１２０に格納される。

入れ子構造のトークン列は第２図に示したようにホスト
レベル１のトークン内にホストレベル２のトークンが含
まれ、ホストレベル２のトークンの中にまたもやホスト
レベル３のトークンが含まれる、と言つように、いくつ
ものホストレベルのトークンが内部に含まれる。入れ子
のトークンを含むが含まないかはＩＤコードの６ビツト
目（ホストビット）が１であるか０であるかに指示され
る。ホストビットレジスタ１２５から出力されるホスト
ビットが１であれば、現在のトークンの中に含まれるト
ークンのホストレベルが現在のトークンのネ゛ストレベ
ルより１ステップ高くなる。このホストレベルの高さは
、第１図では、ホストレベル数に比例した長さのフラグ
ピットレジスタ１６０とエンコーダ１７０を備えたホス
トレベル判別回路１９０で判定される。

上昇したホストレベルのトークンが元のホストレベルに
戻るのは読み取りアドレスがトークンの最終オクテツト
に達したときである。そこで、長さコードが判明した時
に、長さコードの読みだし位置と長さコードの和を求め
るトークンの最終オクテットの位置を示す。ＥＡ（エン
ドアドレス）の計算手段１３０を設けておき、ＥＡスイ
ッチ１４５を介してＥＡをホストレベル別のＥＡレジス
タ１４０に保持しておく事とした。そして、トークンの
読みだし位置アドレスＡと全ＥＡレジスタの内容をアド
レス比較器１５０で並列に比較し、アドレス比較器がマ
ツチ信号を発生する時に、フラグビットレジスタ１６０
の該当する位置のレジスタを０にリセットする。

このフラグピットレジスタ１６０の後にＡＮＤゲート１
６５を使うことで、１と０との境目が判別し、その位置
からホストレベルがどごまで下がるかをホストレベルエ
ンコーダ１７０で識別できる。その出力はＮＬ出力レジ
スタ１７５に保持され、デコーダ１４５の制御や属性照
合に使われる。

属性照合は要求ＩＤレジスタや要求ＮＬレジスタを含む
検索条件メモリ１０６ヘツダー保持手段１２０とＮＬ出
力レジスタ１７０に接続された属性比較器１３５で行わ
れる。この時にミスマツチトークンの読み飛ばしを行う
ことが出来る。

ミスマツチトークンのボディ部の読み飛ばしに際しては
２つのやり方がある。第１図（ａ）はミスマツチ検出時
に、長さコード読みだし位置Ａに長さコードＢと１を加
えて、次のトークンのヘッダアドレスを決定する内部ア
ドレス発生回路１３５を使う。ミスマツチでないときに
はＢを０とする。

第１図（ｂ）はミスマツチ検出時に、エンドアドレスＥ
ＡにＡを加算して次のトークンの読みだし位置アドレス
を発生し、マツチの時はＥＡの代わりに現在の読みだし
位置アドレスＡに１を加えてオクテツトの読みだし位置
アドレスを発生する読みだし位置アドレス発生回路を使
う。この場合しごは使用する加算器の数が少なくなる。

検索処理条件の指定は検索条件メモリ１０６の中の開始
アドレスレジスタ１０１やサイズレジスタ１０２や要求
ＩＤコードレジスタ１０３や要求ホストレベルレジタ１
０４やコマンドレジスタ１０５によって設定される。コ
マンドレジスタ１０５にビットパターンを設定する事に
よって検索結果の出力形式が決められる。たとえば、マ
ツチしたトークンのヘッダアドレスを出力するか、マツ
チしたトークンのボディ部を出力するか、トークンの検
索処理毎でスタートパルス待ちになって停止するか全ト
ークン列の終わりまで連続的にサーチを行うか、ＩＤマ
ツチを使うか、ホストレベルＮＬマツチを使うかなどの
検索条件をコマンドレジスタ１０５上のビットパターン
で記憶する。

以下では、第１図Ｃａ）、（ｂ）でのホストレベル判別
とヘッダ検索の動作をもう少し詳しく説明する。

まず始めに、トークンのホストレベルＮＬが１（“ＯＯ
”）とする。故に、フラグピットレジスタ１６０は左端
のレジスタ以外全て“０″にリセットされ、出力レジス
タ１７０は００″を示し、それによって制御されたＥＡ
スイッチ１４５はＥＡ計算手段１３０の出力を０番目の
ＥＡレジスタに接続している。

外部アドレス発生回路１１０が主記憶に格納されたトー
クン列を先頭から順に読みだすべくアドレスを発生する
と、トークン列が主記憶から送られて来る。その先頭を
見て、ホストビットＮｂを含むＩＤコードやボディーの
長さコードがヘッダ保持手段１２０とホストビットレジ
スタ１２５にラッチされる。

長さコードの示すボディー長さをＢ１とすると、トーク
ンのエンドアドレスＥＡは、 ＥＡ１＝Ａ＋Ｂ１　　　　　　　　　　　　　　（１）
から計算される。これがＥＡ計算回路１３０で求められ
る。トークンの読みだし位置アドレスＡは常にアドレス
比較器１５０にも送られる。

ヘッダ保持手段１２０においてホストビットＮｂが１な
らば、ヘッダ部の後にＮＬ＝２のトークンが続くので、
ＮＬ＝２を示すように、フラグビット（ＦＢ）レジスタ
１６０を上から２番目まで１にする。斜線の施された最
上段のフラグピットレジスタ１６０は常に“１″を保持
するとしている。次段のフラグピットレジスタ１６０が
“１”で、その下の段がすべて“Ｏ”となる。“１”と
“０”の境目をエンコーダ１７０とＡＮＤゲート１６５
が検出し、ホストレベルをコード“０１″として発生し
、出力レジスタ１７５に送る。

ＮＬ＝２のトークンのヘッダ一部保持手段１２０への設
定後、再び、そのトークンのボディーの長さＢＬ２とそ
の時の内部アドレスＡと１の加算結果ＥＡ２がＥＡレジ
スタ１４０の２番目に格納される。Ａはトークンのオク
テツトを１つ読み取る都度、１つづつ大きくなる。いま
、ＮＬ＝２のトークンのＮｂが０であると、そのトーク
ンはプリミティブと呼ばれ、ヘッダ一部の後にボディ一
部が続く。

アドレスＡとトークンの内容を順に読み取って行くにつ
れて増加し、比較器１５０で全てのＥＡレジスタの内容
と比較される。もしＡがＥＡ２に等しくなると、ＡがＮ
Ｌ＝２のトークンの終わりに到達したこと意味し、ＮＬ
を１に戻さなければならない。その事を実行するために
、比較器１５０の出力が１の時に上から２番目のフラグ
ビットレジスタ１６０をＯにリセットする。その結果、
フラグピットレジスタの１番目が１で、それ以下は０に
なる。エンコーダ１７０はこれを検出してホストレベル
ＮＬ＝１（’“ｏｏ”）を出力する。

このように、トークンの先頭読みだし位置でＩＤコード
とホストレベルＮＬコードが求まると、要求ＩＤと要求
ＮＬレジスタ１１５の内容の比較結果が属性比較器１３
５から直ちに求まる。これは現在のトークンが検索条件
にマツチしたか否かを示している。

マツチしていれば、読み出しアドレスＡに１を加えなが
ら、現在のトークンのボディ一部を順次読み出せばよい
。

ミスマツチならば現在のトークンのボディ一部を読み出
す必要が無い。その場合には、次のトークンのヘッダア
ドレスＨＡを計算して、その結果をアドレス発生手段１
１０に送る必要がある。ホストビットＮｂが“１′”の
時はすぐに入れ子のトークンのヘッダ部が続くので、長
さコード読み出し位置アドレスをＡとすると、次のトー
クンのヘッダアドレスは、ＨＡ＝Ａ＋１から計算される
。Ｎｂが０の時には、ミスマツチのトークンのボディ一
部の長さＢがわかった時点で次のトークンのヘッダアド
レスはＨＡ＝Ａ＋Ｂ＋１から計算される。これらが内部
アドレス計算回路１３５で求められ、その結果が外部ア
ドレス発生回路１１０に与えられる。

第３図はトークン列のホストレベル計算例を示している
。第３図（ａ）はトークン列の一例を、第３図（ｂ）は
これに対応したホストレベルの出力結果である。第３図
（ａ）は図面の関係で入れ子の深さが４までしか示して
いないが、数１０に及んでも同じ様な構造が繰り返され
るだけである。始めのトークンのホストレベルは常に１
番目である。

第３図（ａ）に示しトークンのヘッダ一部はＩＤコード
＊印の有無とＬＬコードの数字がそれぞれ、ホストビッ
トが“１′”であるか否かとそのトークンのボディ部の
長さを示しているとする。すなわち、第１のトークンは
コンストラクタであって、入れ子を持つこととボディー
長さが６４（オクテツト）であることがわかる。ヘッダ
ー長さを２とすると、このトークンの全長は６６となる
。すなわち、位置アドレスが６４に達するとホストレベ
ルが必ず１に戻ることを示す。トークンの下側の数字は
位置アドレスであり、まるで囲まれた数字はプリミティ
ブトークンのエンドアドレスである。ホストレベルは３
オクテツト目で１から２へ、１７オクテツト目で２から
３へ、２９オクテツト目で３から４へ変わる場合が示さ
れている。

第３図（ｂ）は横軸３０１でトークンのオクテツト数を
、縦軸３０２でホストレベルを示している。これが第３
図（ａ）のトークン列に対するホストレベル検出装置の
出力するホストレベルに該当する。第１番目のヘッダー
を読み取った第２オクテツト目でこのホストレベルのト
ークンの終わりが６６オクテツト目であることがわかる
。それをエンドアドレスレジスタに設定した後、ホスト
レベルを上げる。第２ネストレベルのプリミティブトー
クンが３オクテツト目から始まり、４オクテツト目でそ
のトークンが１４オクテツト目迄続くとわかる。それを
２番目のエンドアドレスレジスタに設定する。５オクテ
ツト目からは１４オクテツトまではトークンを順に読む
。オクテツト数が１４に達すると２番目のエンドアドレ
スレジスタをリセットする。それまでの間、ホストレベ
ルは２のままである。６６オクテツト目になるまでホス
トレベルは１に戻らをいためである。

１５オクテツト目で次の第２ネストレベルのトークンが
始まる。ＩＤコードに＊印がある。１６オクテツト目の
ＬＬコードの数字５０からこのホストレベルのトークン
の終わりが（１６＋　５０）＝　６６オクテツト目であ
ると計算され、２番目のエンドアドレスレジスタに設定
される。この後、ホストレベルが１つ増える。

１７オクテツト目のＩＤコードには托１が付いていない
ので、１８オクテツト目のＬＬはプリミティブトークン
のボディ一部の長さ８を示す。故に、１８＋８＝２６オ
クテツト目がエンドアドレスになる。オクテツト数が２
６に達すると、このトークンが終わるが、この後に、再
び第３ネストレベルのトークンが続く。すなわち、２７
オクテツト目はＩＤコードに＊印があるので、２８オク
テツト目のＬＬコードの数字３８から第３ネストレベル
のトークンの終わりを２８　＋　３８　＝６６オクテツ
ト目と計算し、３番目のエンドアドレスレジスタに設定
する。その後ホストレベルを３から４に上げる。２９オ
クテツト目に読むＩＤコードには＊印が無いので、３０
オクテツト目のＬＬコードはプリミティブトークンのボ
ディ一部の長さ３６を示す。故に、３１オクテツト目か
ら後は６６オクテツト目までホストレベル４のままとな
る。その後で、ホストレベルは１に戻る。

第４図はホストレベル検出回路の１構成例を示している
。この回路は第１図のホストレベル判別回路１９０の中
のフラグピットレジスタ１６０とエンコーダ１７０との
接続部に対応する。フラグピットレジスタＦＢＲを左側
からＦＢＲｌ、　ＦＢＲ２，ＦＢＲ３，・・・と呼ぶ。

ホストレベルが１の時はＦＢＲｌのみが“１″で、他は
“０″であるとする。本印付きＩＤコードを持つトーク
ンがくると、ホストビットが“１″であるから、ホスト
ビットレジスタ１２５からＮｂ＝１が端子４０１から与
えられる。

ＬＬコード読み出し時のタイミングで端子４０２からク
ロックＣＬＫが与えられる。それによって、ゲート１６
５を介してＦＢＲ２にも“１″が設定される。

その結果、ゲート１７５は左から２番目がホットになり
、エンコーダ１７０から出力されるネーストレベルが１
番目（”ｏｏ”）から２番目（“’０１”）に上がる。

これがホストビットの上昇のケースである。さらにホス
トビソト“１”のトークンが、くると、ホストレベルは
さらに高くなる。その時に、ＦＢＲｌ、　ＦＢＲ２，Ｆ
ＢＲ３が次々と“１”′になって行く。一般に、ＦＢＲ
，が“１”でＦＢＲ，＋１が“０″のときに、エンコー
ダはｉ番目のホストレベルを出力する。ただし、ｉは１
．２．３．−である。

ＦＢＲ，が“′１”の時に比較器１５０がエンドアドレ
スとトークン読みだし位置との比較結果（マツチ信号）
を出力した時に、“０″にもどる。その時にＦＢＲ，が
−１ “１″のままであれば、エンコーダの出力するホストレ
ベルはｉ−１番目となる。

同時に、ＦＢＲ，とＦＢＲｉ−０が比較器１５０の出力
するマツチ信号によって“０″になった場合には、ホス
トレベルはｉ−２番目まで下がる。ＦＢＲ，からＦＢＲ
２迄がすべて“′０″になった場合には、ホストレベル
は当然、１番目に戻る。なお、戻りのタイミングは、Ｉ
Ｄコードの直前のオクテツトの読み出し時とする。

入れ子ありトークンが連続する場合には、ホストレベル
が階段状に上昇し、上昇の都度、ホストレベル毎に割り
当てられたエンドアドレスレジスタ１４０にエンド、ア
ドレス（ＥＡ）が書き込まれる。そして、アドレス比較
器１５０がマツチ信号を発信するときは、入れ子なしト
ークンの最後のオクテツト入力時であって、その時にフ
ラグピットレジスタ１６０がリセットされる。

第５図は入れ子型トークン列の検索動作の説明図である
。第３図（ａ）のトークンの列の中の検索条件にあった
トークンを読み出す検索動作を示している。トークンを
読み出す場合の内部アドレス発生回路１３５の発生する
トークン読み出し位置アドレスＡが横軸５１０で示され
、検索条件にあったトークンの読み出しのためのアクセ
ス回数が縦軸５２０で示されている。いくつかの検索例
によって、トークンの属性比較でミスマツチのトークン
がヘッダ部以外で読み飛ばされ、アクセス回数が少なく
て、検索条件にマツチしたトークンだけが速く読み出さ
れることが示される。

第５図（ａ）は検索条件としてホストレベルＮＬ＝４と
ＩＤコートのＩＤ６が与えられた場合の検索動作を示し
ている。この図かられかるように、読み出しアドレスＡ
は１．２．３．４の後１５．１６．１７．１８．２７．
２８．２９．３０と変化し、Ａが２９の時に始めて、Ｉ
ＤとＮＬのマツチ信号が発生する。従って、Ａが３０か
ら６６まではマツチしたトークンの順次読み出しのため
に発生される。これに合わせ、出力端子５０１からバリ
ッド信号が出る。これを見て、主記憶１００から読み出
されるトークンが外部でプロトコル変換や内容検索にな
どに利用されてる。アクセス回数は４８回である。

全部読み出す場合（６６回）の約２／３である。不要な
トークンのボディ一部が短い時には読み飛ばしの効果が
少ないが、長くなるにつれ、効果が大きくなる。

第５図（ｂ）は第３図（ａ）のトークンの中のヘッダ部
のみのサーチの例である。検索条件としてヘッダ部のみ
の検索要求とＩＤコードのＩＤ６が与えられているとす
る。故に、Ａは１．２．３．４．１５．１６．１７．１
８．２７．２８゜２９、３０となる。Ａが２９の時に、
マツチ信号が出るが、Ａ＝３１の時には、出力端子５０
２からバリッド信号が出力される。この時のアドレス発
生手段１１ｏの出力かマツチトークンのボディ一部アド
レスを示すからである。これはプロトコル解析やコンフ
ォーマンステスト等に使われる。この時のトータルアク
セス回数は１２回であって、全体の約１１５となる。ボ
ディ一部の長いトークンの列の解析に有効となる。

第５図（ｅ）はえストレベルのみの指定によるトークン
列の検索例である。ホストレベルＮＬを３として検索す
る場合、ＮＬが１．２．４のトークンについてはヘッダ
一部しかサーチしない。すなわち、Ａは１．２．３．４
゜１５、１６．１７と進んだあとで、ＮＬマツチが発生
し、Ａが１８から２８までは１つづつ増加する。その後
はＡが３０まで進んで、検索が終了する。このような検
索はマルチメディア文書データの中のテキストデータの
みを抜き出して検索するときとが画像データのみを抜き
だして表示するときとが、数値データのみを抜き出して
ソートする時などに使われる。

トータルアクセス回数は２０回であって、全体の約４／
１３となる。

第５図（ｄ）はホストレベルのレンジ指定によるトーク
ン列の検索例である。ホストレベル２以下のトークンを
検索する場合は、ＮＬが１と２のトークンのヘッダ部を
サーチする。ＮＬが２の入れ子ありトークンについては
そのトークンのボディ部がホストレベル３以上になると
判断し、ミスマツチと判定し、そのトークンをスキップ
する。すなわち、Ａはｌ、２゜３．４から１５．１６ま
で進むと、Ａは１６に長さコードの値５０と１を加えた
６７ヘスキツプする。このような検索は文書情報の表題
名や出版社名などの上位概念で検索範囲を絞るときに使
える。この場合のトータルアクセス回数は１６回であり
、全体の約１１１１と小さくなる。これはハイパーテキ
ストサーチにも有効である。

第６図はトークンの列の読みだし位置アレス発生回路の
１構成例を示している。一般に、この部分はトークンを
構成するオクテツトを順次に読み取り相対アドレスを発
生するためだけであれば、クロック信号の計数器（カウ
ンタ）によって実現される。本発明では、トークンのヘ
ッダ部の解読でわかる属性を検索条件として指定された
属性と比較して、ミスマツチであればそのトークンのボ
ディ部をスキップするようにアドレスを発生する。すな
わち、長さコードが求まったときの読み出し位置アドレ
スＡに１と長さコードの示す値Ｂを加えて、次のトーク
ンの先頭アドレスを計算する。

第６図（ａ）は上記Ａと１とＢの加算を２個の２入力加
算器から成る３入力加算器で実現する場合を示している
。ホストビットＮｂ＝１とか属性比較結果のｚｂがマツ
チ（“１′”）の時にはＢ＝０とする。そのためにスイ
ッチ６０３が加算器６０１の入力側に入れられている。

加算器６０２は常に加算器６０１の出力に１を加算する
だけである。そのために＋１のホルダー回路が使われて
いる。加算結果はレジスタ６０４に保持され、加算器６
０１にフィードバックされると共に、端子６０８から出
力される。

このような計算は最も単純な方法であるが、アドレス信
号が３２ビット以上に及ぶと、加算器が５００ゲ一ト以
上となり、大きな面積を占めるだけでなく遅延時間も大
きくなるので、ＬＳＩチップとして実現するには最適と
言えない。外部アドレス発生器やエンドアドレス計算回
路の所でも同じ加算器を使うので、加算器の個数を減ら
した方が処理速度が上がり、チップコストが下がる。

第６図（ｂ）は加算器を１個だけで実現するトークン列
読みだし位置アドレス発生回路である。Ａ＋Ｂ＋１を計
算するに際し、１を端子６０９からキャリー信号として
受は付ける２入力加算器６０５を使う。前段のゲート６
０３は属性照合結果がマツチなら、Ｂを０とし、そうで
なければＢのままで受は付けるスイッチである。当然な
がら、加算器６０５の出力はレジスタ６０４にラッチさ
れ、加算器６０５の入力にフィードバックされ、端子６
０８から出力される。これによって属性マツチの時には
次のオクテツトがアクセスされ、ミスマツチの時には現
トークンのボディ部の後のトークンの先頭がアクセスさ
れる。

第６図（Ｃ）はエンドアドレス計算回路を利用したトー
クン列の読みだし位置アドレス発生回路例である。Ａ＋
Ｂはヘッダ部の読み取りが終わるときに別のＥＡ計算用
加算器６０７で必ず計算される。この加算器６０７の内
容がデコーダ１４５を介してＥＡレジスタに設定される
事に着目し、デコーダ１４５がＥＡレジスタへ加算器６
０７の内容を設定した後、端子６０９から与えられるキ
ャリー信号を使って加算器６０７の値をインクリメント
し、アドレスレジスタ６０４に設定する。それが次のオ
クテツトの読みだし位置アドレスになる。

すなわち、加算器６０７の出力をＥＡレジスタ１４０に
設定する期間には、加算器６０６の入力段のゲート６０
３はボディ長さレジスタの値Ｂとアドレスレジスタ６０
４の出力を加算器に伝達する。ＥＡレジスタへのＥＡの
設定後は、デコーダ１４５が切り替わり、スイッチ６０
３は、属性照合結果がミスマツチなら閉じられて、Ｂが
そのまま加算器６０７に入力される。

マツチの時にはスイッチ６０３がオープンとなり、Ｂ＝
０が加算器６０７に入力される。このスイッチと同じタ
イミングでキャリー信号１が加算器に入力され、加算器
６０７の出力は次のトークンの読みだし前にアドレスレ
ジスタ６０４に設定される。

結果としての回路構成は第６図（ｂ）と余り変わらない
が、エンドアドレス計算用の加算器°を使わない分、加
算器の使用数が１つ減る。第６図（ａ）ではアドレス発
生に関係して少なくとも４個の加算器を使うが、第６図
（ｂ）では３個、第６図（ｅ）では２個を使うだけで良
くなる。

第７図はトークン読みだしの順序制御回路の実施例の説
明である。第７図（ａ）が順序制御回路の状態遷移図を
示し、第７図（ｂ）がそれを実現する回路図を示す。

第７図（ａ）においては、トークンの読みだしに伴う状
態変化が示されている。丸７５０は状態ノードを示し、
それらを結ぶ矢印線７５５は状態遷移パスを示す。状態
ノード間の状態遷移は矢印線７５５に沿って記入された
条件式が満足されたときに、矢印の方向への状態遷移が
起こる。最初の状態はＳ０てある。この状態になるとト
ークンの先頭オクテツトの読みだし位置アドレスが発生
され、第１オクテツトのＩＤコードが読み出される。そ
れを読み取ると、状態はＳｌと８２の２通りがある。状
態８１はＩＤコードのホストビットＮｂが０の時であり
、Ｓ２はＮｂが１の時である。

次に、ＳｌまたはＳ２の状態ではトークンの第２オクテ
ツトを読み出すアドレスが発生され、ＬＬコードが読み
出される。ＬＬコードが読み出され、７ビツト目の短形
式か長形式を示すＬｂと属性照合結果のｚｂが受けられ
ると、状態はノード８１やＳ２からＳＯに戻る以外にＳ
３．８４．８５の３状・態への遷移が考えられる。

ＳｌからＳＯやＳ２からＳＯへの遷移はＬＬコード７ビ
ツト目が“０１１で短形式であり属性照合がミスマツチ
の時に起こり、Ｓｌから８３への状態遷移は短形式で属
性マツチの時に起こる。長形式のときには、Ｓｌから８
４への遷移と８２から８５への遷移が起こる。長形式の
後ＬコードがＤ個続くとき、（Ｄ−１）回のＬコード受
付が終わるまでＳ４やＳ５の状態はそこに留まる。Ｄ回
目のＬコード受付時に状態はＳ４から８６へ、Ｓ５から
はＳＯへ進む。状態Ｓ６はボディ部データ受付の状態で
あり、ボディ部の長さをＢとすると、（Ｂ−１）回のデ
ータ読み出し迄は状態が８６にとどめられる。Ｂ回目の
データ読み出しで、状態が８６からＳＯへ戻る。

状態Ｓ５ではデータが来ないので、長さＢが求まるとＳ
Ｏに戻ってしまう。

第７図（ｂ）はホストビット信号Ｎｂ、長さの形式信号
Ｌｂ、属性マツチ信号Ｚｂ（７）３１ｚジスタフ０１．
７０２．７０３と、状態ノードＳＯから遷移先状態ノー
ドまでの距離の計数器７０５と、状態ノードのデコーダ
７０７とデコーダ７０７の出力にしたがうクロック信号
の制御ゲート７０９とから構成される順序制御回路７１
０の説明図である。この中のゲート７０９の出力が第１
図で示した回路を含む被制御回路７３０に送られる。り
ロック信号は端子７２２から与えられるが、ＡＮＤゲー
ト７２５で制御される。すなわち、ビジーフラグレジス
タ７１２０が端子７２１から与えられたスタート信号に
よって１”にセットされていれば、クロック信号を通過
させるが、０”ヘリセットされた後では通過させない。

リセット信号は１連の検索動作が終わったときに、被制
御回路７３０から発せられる。エンドアドレスレジスタ
やアドレスレジスタの内容は保持したままで、状態をノ
ードＳＯに戻すことである。

このリセット信号はトークン毎に発生される場合もあり
得る。

被制御回路７３０の中のヘッダ保持手段１２０ではそこ
に含まれる各種レジスタへのデータの設定やＬコードや
ボディ長さのカウンタの更新タイミングパルスが順序制
御回路７１０から与えられる。

距離計数器７０５は被制御回路での１クロック分の動作
が終わると、終了の信号（状態遷移信号）をＯＲゲート
７０６を介して受付けて、計数値のカウントアツプを行
う。また、被制御回路７３０での一連の動作が終わると
、そこからリセット信号を受ける。

それによって初期状態に戻る。状態ノードの遷移信号を
ＯＲゲート７０６を介して受は付ける。ＯＲゲート７０
６の使用の理由は、状態ノードが分岐している事による
。

例えば、レジスタ７０１から７０３がすべてＯで、距離
計数器７０５も００の時は状態がＳＯであり、デコーダ
７０７が第１番がホットになる。したがって、クロック
信号はゲート７０９を通して第１番目から出力される。

それが被制御回路７３０とＯＲゲート７０６を介して距
離計数器７０５を０１に変化させる。これと共に、ＩＤ
コードから読み出されたＮｂが変わる。゛それにより選
択されたデコーダ７０７とゲート７０９から２番目のク
ロック信号が出力され、第２オクテツトのＬＬカウンタ
とＬコードレジスタへの設定を実行し、かつ、ＯＲゲー
ト７０６を介して距離計数器７０５をカウントアツプす
る。状態遷移図に従って、次々と、デコーダの入力と出
力が変化する。

第８図は属性照合手段の回路構成図の一例を示している
。属性照合手段は検索条件メモリ１０６から与えられる
検索要求とヘッダ保持手段１２０やＮＬ出力レジスタ１
７５から与えられる属性データとの比較を行う部分であ
って、第１図では属性比較器１１５によって実現される
と説明されたが、ここでは、もう少し詳細を説明する。

検索条件はＩＤコードやホストレベル（ＮＬコード）で
与えらるが、その他に、トークン列の検索がヘッダ部に
限られること示すヘッダ要求信号のレジスタ８０１で与
えられるとする。これは第５図（ｂ）に示されるような
トークン列検索で使われる。従って、属性データもＩＤ
レジスタ１２１やＮＬ出力レジスタ１７５から与えられ
る他に、読み出されているオクテツトがヘッダ部に属し
ている事を示すヘッダ信号の検出器８０２から与えられ
るとする。

故に、属性検出手段では、少なくとも３つの比較器８１
０が使われる。すなわち、第１がヘッダ要求信号とヘッ
ダ信号の比較器であり、第２が要求ＩＤコードとＩＤコ
ードの比較器であり、第３が要求ＮＬコードとＮＬ出力
コードの比較器である。

属性のマツチ信号ｚｂは常に３つの比較器の出力論理積
とは限らない。第５図で示したように、検索条としてＮ
Ｌコードのみとか、ＩＤコードのみを指定する。あるい
は、ＩＤやＮＬコードを指定しないで、ヘッダ部全ての
検索を指定する場合がある。そこで、マスクビットパタ
ーンを記憶するコマンドレジスタ１０５を使い、検索条
件に含めない比較器８１０の出力をマスクする。

いま、ｉ番目の比較器８１０の出力信号をｙ、とじ、コ
マンドレジスタ１０５から与えられるｉ番目のマスクビ
ットをｍ、とすると、属性のマツチ信号ｚｂは次式％式
％ （２） ここに、＋は論理和を表すとする。

従って、マツチ信号ｚｂは比較器８１０につながるＯＲ
ゲート８２０と全てのＯＲゲートの出力の論理積を求め
るＡＮＤゲート８２５から出力される。

この実施例の中では、ＮＬのレンジサーチの場合を示し
ていないが、要求ＮＬとＮＬの出力信号の比較器８１０
の出力を比較の完全一致の端子からでなく大小比較の端
子から切り替えるだけで、要求ＮＬ以下のＮＬを持つト
ークンを選択するように出来る。さらに、比較器８１０
を増やしても、もっと色々な属性の比較結果を出せるよ
うにすることも可能であり、以上の記述だけで検索条件
の設定範囲が制限されるものではない。

（発明の効果） 以上に説明したように、本発明は、主記憶に格納された
トークン列のホストレベルやＩＤコード等の属性をトー
クン毎に解読してから、属性を使ってトークン列を検索
する２重手間によってトークン列の検索処理速度の遅く
なる欠陥を容易に解決するとわかる。すなわち、トーク
ン列のヘッダ部の解読と検索を同時に行うことによって
、ヘッダ部でミスマツチとなったトークンのボディ部の
読み飛ばしを行え、検索条件にマツチするトークンの読
みだしのための主記憶アクセス回数が全トークン列読み
出しのアクセス回数の数分の１に減る。この事が検索時
間を短縮させる。

情報処理機器のホストコンピュータ側でのソフトウェア
でホストレベル検出を行わせる時には処理速度がＩＭＢ
／ｓｅｅであっても、ホストが６４レベルになると、ワ
ーストケースであるが、処理速度が１６ＫＢ／ｓｅｅに
下がる。しかし、ホストレベルを常に判別するハードウ
ェアを内蔵させたことで、ホストレベルが常に出力され
、それによって、トークンの検索がトークンの入力と同
時に達成される。

すなわち、ＩＭＢ／ｓｅｅの検索処理速度が確保される
。

それだけでなく、不要トークンの読み出しをスキップす
るために、実質の検索処理速度は数ＭＢ／ｓ以上に上が
る。しかも、この装置はホストレベルが３２から６４に
及んでも２万ゲート以下のゲートアレイで設計できるの
で、現在のＬＳＩ技術レベルでも、容易に１個のＬＳＩ
チップで実現される。

【図面の簡単な説明】

第１図（ａ）、（ｂ）は本発明の実施例の装置構成図、
第２図は入れ子（ホスト）構造のトークン列の説明図、
第３図はホストレベルの計算プロセスの説明図、第４図
はホストレベル判別回路の１実施例を示す図である。第
５図はトークン列の検索動作の説明図、第６図は読み出
し位置アドレス発生回路の１実施例を示す図、第７図（
ａ）、　（ｂ）は各々トークン読み出しの順序制御回路
の状態遷移図と、それを実現する回路図、第８図は属性
照合手段の１例を示す図である。 図において、１００・・・トークン列バッファメモリ、
１０１・・・開始アドレスレジスタ、１０２・・・サイ
ズレジスタ、１０３・・・要求ＩＤレジスタ、１０４・
・・要求ＮＬレジスタ、１０５・・・コマンドレジスタ
、１０６・・・検索条件メモリ、１１０・・・外部アド
レス発生器、１１５・・・属性比較器、１２０・・・ヘ
ッダ保持手段、１２１・・・ＩＤコードレジスタ、１２
２・・・長さコードレジスタ、１２５・・・ホストビッ
トレジスタ、１３０・・・エンドアドレス計算回路、１
３５・・・内部アドレス発生回路、１４０・・・エンド
アドレスレジスタ、１４５・・・デコーダ、１５０・・
・アドレス比較器、１６０・・・フラグピットレジスタ
、１６２．１６５・・・ＡＮＤゲート、１７０・・・エ
ンコーダ、１７５・・・ＮＬ出力レジスタ、１９０・・
・ホストレベル判別回路。

Claims (6)

【特許請求の範囲】
1. （１）トークン列の記憶手段と、検索条件保持手段と、
   前記記憶手段をアクセスするために初期アドレスにトー
   クンの読み出し位置アドレスを加算して出力する外部ア
   ドレス発生手段と、各トークンの先頭のＩＤコードや長
   さコードを検出して保持するヘッダ保持手段と、ＩＤコ
   ードからのネストビツト検出手段と、ＩＤコードやネス
   トレベルなどの属性照合手段と、照合結果と長さコード
   と長さコード読みだし位置によって次に読み出されるト
   ークンの読み出し位置を決め、アドレス発生手段に与え
   るトークン列の読み出し位置アドレス計算手段と、長さ
   コードとそのコードの読み出し位置を使って、各トーク
   ンのエンドアドレスを計算するエンドアドレス計算手段
   と、エンドアドレスをネストレベル別に記憶するエンド
   アドレス保持手段と、前記トークン列の読み出し位置と
   前記エンドアドレスとアドレス比較手段と、ネストビッ
   トによってシフトアップされ、アドレス比較手段のマッ
   チ出力によってリセットされ、シフトダウンするフラグ
   ビット保持手段と、複数個のフラグビット保持手段につ
   ながるネストレベルエンコード手段とネストレベル出力
   レジスタとを備えることを特徴とする入れ子型トークン
   列の検索装置。
2. （２）トークン列の記憶手段と、検索条件保持手段と、
   前記記憶手段をアクセスするために初期アドレスにトー
   クンの読み出し位置アドレスを加算して出力する外部ア
   ドレス発生手段と、各トークンの先頭のＩＤコードや長
   さコードを検出して保持するヘッダ保持手段と、ＩＤコ
   ードからのネストビット検出手段と、ＩＤコードやネス
   トレベルなどの属性照合手段と、長さコードと長さコー
   ド読みだし位置の加算によってトークンのエンドアドレ
   スを計算するエンドアドレス計算手段と、エンドアドレ
   スをネストレベル別に記憶するエンドアドレス保持手段
   と、前記トークン列の読み出し位置と前記エンドアドレ
   スとアドレス比較手段と、ＩＤコードを受信したヘッダ
   保持手段の出力するネストビットによってシフトアップ
   され、アドレス比較手段の出力によってリセットされ、
   シフトダウンするフラグビット保持手段と、複数個のフ
   ラグビット保持手段につながるネストレベルエンコード
   手段とネストレベル出力レジスタと、属性照合手段がミ
   スマッチを出し、ネストビットが０てある時にはエンド
   アドレスに１を加え、そうでないときは、現在の読みだ
   し位置アドレスに１を加えて、アドレス発生手段に与え
   るトークン列の読みだしアドレス発生手段とを備えるこ
   とを特徴とする入れ子型トークン列の検索装置。
3. （３）トークン列の読み出し位置アドレス計算手段が現
   在の出力に１と長さコードを加算する３入力加算器で実
   現され、属性照合手段の出力がミスマッチでかつネスト
   ビットが０の時以外は長さコードの代わりに０を与える
   事を特徴とする請求項１に記載の入れ子型トークン列の
   検索装置。
4. （４）トークン列の読み出し位置アドレス計算手段が、
   現在の出力に長さコードを加算する加算器であって、キ
   ャリー信号によって１が加算されることを特徴とする請
   求項１に記載の入れ子型トークン列の検索装置。
5. （５）トークン列の記憶手段と、前記記憶手段をアクセ
   スするために初期アドレスと相対的なトークン読み出し
   位置アドレスを加算するアドレス発生手段と、検索条件
   保持手段と、外部クロックに従ってタイミングシーケン
   スを発生する順序制御手段と、前記タイミングシーケン
   スによって各トークンの先頭のＩＤコードや長さを検出
   して保持するヘッダ保持手段と、ＩＤコードからのネス
   トビット判定手段と、前記検索条件保持手段の内容に従
   って比較内容を限定するトークンの属性照合手段と、長
   さコードと長さコードの読みだし位置の加算によってト
   ークンのエンドアドレスを計算するエンドアドレス計算
   手段と、エンドアドレスをネストレベル別に記憶するエ
   ンドアドレス記憶手段と、全エンドアドレスと現在のト
   ークンの読み出し位置アドレスとの並列比較結果とネス
   トビットから次のトークンのネストレベルを判定するネ
   ストレベル判定手段と、ネストレベル出力レジスタと、
   属性照合手段のミスマッチ信号と０のネストビット信号
   の時にはトークン列の読み出し位置に１と長さコードを
   加算し、それ以外の時には１だけを加算するトークン列
   の読みだし位置アドレス手段とを備えることを特徴とす
   る入れ子型トークン列の検索装置。
6. （６）検索条件保持手段がＩＤコードとネストレベルと
   ボディーサイズとトークン列記憶手段の検索開始アドレ
   スと検索されるトークン列のサイズと検索コマンドのい
   ずれかを保持するレジスタから成り、検索コマンドが比
   較の対象にしない項目を指示するビットパターンである
   事を特徴とする請求項１、２または５に記載の入れ子型
   トークン列の検索装置。