JPH064585A - 構造化データベースにおけるポインター圧縮の改良された方法及び装置 - Google Patents

Abstract

(57)【要約】 （修正有） 【目的】ポインター圧縮を通して不経済な空ポインター
を除去し、かつ高速論理物理インデックス変換を可能に
する方法及び装置を提供する。 【構成】データベース構造内の圧縮されたノードに対す
る方法及び装置が開示される。各圧縮されたノードは特
定の写像機能と関連し、ノード内の各要素が特定の識別
コードが割り当てられ、検査されるべき文字は第１の部
分及び第２の部分を有する物理的アドレスへ変換され、
この第１の部分は圧縮ノード内の特定の要素にインデッ
クスを付加するのに使用され、第２の部分は、選択され
た要素が検索文字に対応することを確認するのに使用さ
れる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、構造化されたポインタ
ー圧縮を達成する改良された方法及び装置に関する。

【０００２】

【従来の技術】Ｉ．データベース構造 計算機化データベースは、検索が容易な様に編成された
情報の収集である。この様なデータベースは一般に構造
化パターンで編成されている。この様な構造の一つがＴ
ＲＩＥ構造として知られている。

【０００３】伝統的なＴＲくた構造化されたデータベー
スにおいて、情報の位置はＴＲＩＥノードを採用する検
索をとおして突き止められる。この様なＴＲＩＥノード
はメモリーによって支援され、各ノードは１６個の要素
のリストを含む。各要素は１６の可能な文字の一つに対
応する。この様なＴＲＩＥ構造は使用すると、任意の長
さの文字列ワードを検索することができる。第１に、検
索される文字列ワードは数個の文字に分割される。各々
は上記の例（即ち１６要素ノード）に対しては４ビット
長である。次に検索される第１の文字が第１のＴＲＩＥ
ノードのインデックスとして使用される。

【０００４】検索される文字に対応する要素は３つの形
態の一つとすることができる。 (1) 要素は別のＴＲＩＥノードを指し示すノード（ＮＯ
ＤＥ）ポインターとすることができる。ノードポインタ
ーは、検索される文字に関して、データベース内のエン
トリが検索されているストリングワードと一致すること
を示す。ノードポインターが第１の文字を第１のノード
内へのインデックスとして使用されていると、次に文字
列内の第２の文字がノードポインターによって参照され
るノード内へのインデックスとして使用される。別のノ
ードポインターが見出される場合、この繰り返され、今
度は文字列ワードの第３の文字をインデックスとして使
用する。

【０００５】(2) ノード内で参照することのできる要素
の第２の形態は空（ＮＩＬ）ポインターである。空ポイ
ンターは、データベースが、この点を越えて検索されて
いるストリングと一致するエントリを保有しないことを
示す。空ポインターが見出された時、検索が停止する。 (3) ノード内の第３の可能な要素はリーフ（ＬＥＡＦ）
ポインターである。リープポインターはデータベース内
の要素で一致が見出されたことを示す。リーフポインイ
ターは連続する検索の端部を書き印し、或る別のプロセ
スの開始を指示することができる。

【０００６】伝統的なＴＲＥＩ構造化されたデータベー
スを使用する検索の例が図１に与えれている。図１は伝
統的なＴＲＥＩ構造データベース（１０）を図示してい
る。ＴＲＥＩ構造はＡ（１１）、Ｂ（１３）、Ｃ（１
５）及びＤ（１７）を含む。文字列（００）が検索され
るべき例示的なワードとして図示されている。理解でき
る様に、文字列ワード（００）は、それぞれ４ビット長
の４つの文字（０１、０２、０３、０４）に分割され
る。

【０００７】第１の文字（０１）は第１のノード、ノー
ドＡ（１１）へのインデックスとして使用される。第１
の文字は１１１０、又は１６進（以下Ｅｈ）のＥである
ので、１５番目の要素（１２）が検査される。この例で
は、Ｅｈ（１２）に対応する要素がノードＢ（１３）を
指し示すノードポインターを含む。従って、検索はノー
ドＢで続く。

【０００８】文字ワード（０２）の第２の文字、Ａｈ
は、別のノードポインターが見出される場所であるノー
ドＢ（１３）へのインデックスとして使用される。この
ポインターはノードＣを指し示し、従って検索は検索語
の第３の文字（０３）、８ｈを使用するノードＣで続行
する。ノードＣにおいて、８ｈに対応する要素はノード
Ｄへのポインターである。

【０００９】このプロセスは、ノードＤ（１７）でリー
フポインターが第４の文字（０４）、３ｈに対応する要
素で見出される。この点で、検索が完了し、ポインター
によって参照されるプロセスが開始される。文字列ワー
ドの第４の特徴が０ｈであると、０ｈ（１８）に対応す
る要素が選択される。空ポインターがこの要素に位置す
るので、文字列ワード等と一致する要素がデータベース
内にないから検索が終了する。 II. ポインター圧縮 例示のＴＲＩＥ構造が図示する様に、各ノードはその１
６の要素をサポートするためにある程度のメモリーを必
要とする。これらの要素の多くは使用価値のない情報
（即ち、空ポインター）を本質的に含むので、メモリー
空間の大部分が浪費される。機能及び経済性の理由のた
め、ＴＲＩＥノードを支持するために必要とされるメモ
リーの量を最小化することが望まれる。

【００１０】浪費されるメモリーの或る部分を除去する
ためには、従来の技術のデータベースは「ポインター圧
縮」として知られる方法を使用している。伝統的なポイ
ンター圧縮において、特定のノードの空ポインターは、
このノードの非空ポインターを連続するリスト、即ち圧
縮されたノードへ圧縮することにより除去される。この
様なポインター圧縮の例が図２に与えられている。そこ
では、４つの非空要素を有するノード（２０）が４つの
みの、連続する、非空要素を有するノード（２２）へ圧
縮される。この方法を使用することにより、１６の要素
ノードが１及び１５の非空要素からなるノードへ圧縮す
ることができる。理解できる様に、完全ノードからのポ
インターは完全ノード内で見出される様に圧縮ノード内
にコピーされる。

【００１１】ノードが一旦圧縮されると、ノード内の要
素は検索文字によって直接イッデックを付けることが最
早出来なくなる。検索文字は今「論理」アドレス（即
ち、圧縮がない場合に、要素があるべき位置）を表す。
実際の要素は「物理」アドレス（要素がメモリ内に位置
される場所）に存在する。ポインター圧縮をサポートす
るために、論理物理インデックス変換を与える或る手段
が必要とされる。過去において、１６ビット「ビットマ
スク」がこの様な遷移を達成するために使用された。

【００１２】ビットマスク１６ビットコードであり、圧
縮の前にノードの特徴を記述する情報を提供する。完全
なノードが一度形成されると、ノード内の各要素が検査
される。ノード内の全ての非空ポインターがビットマス
ク内の対応するビットを１に設定させる。図２の例示ノ
ード（２０）に対しては、要素１ｈ、３ｈ、７ｈ及びＢ
ｈは全て１に設定されるであろう。これは非空ポインタ
ーがこれらインデンクスに対応するからである。この様
なビットマスクがヒットマスク（２５）として図説され
ている。

【００１３】検索がこの様な圧縮データベース上でなさ
れる時、文字例の検索文字はノードへでは無く、ビット
マスクへのインデンクスとして機能する。ビットマスク
内の対応する要素が次に検査される。このノードが０で
ある場合、対応するポインターは空である（即ち、存在
しない）。ビットが１の場合、そのノードにある非空ポ
インターは存在する文字に対応する。

【００１４】正しいポインターに近づくために、２つの
方法の一方が使用できる。第１の方法においては、関心
のあるビットよりも低位のインデックスで設定された１
の全ての計数がなされる。この計数値は、関心のあるポ
インターよりも前にリストされたノードに物理的に存在
するポインターの数を与える。この方法において、この
計数値は圧縮ノードへのインデックスを提供する。

【００１５】第２の方法において、１６ビットマスクが
４ビット検索文字と結合される。そしてこの２０ビット
コードはルックアップテーブル内の要素のアドレスを指
定するために使用される。この形態のポインター圧縮は
図２を参照してより良く説明される。例えば、圧縮ノー
ド（２２）で検索されるべき文字がＢｈである場合、Ｂ
ｈに対応するビットはビットマスク（２５）内で検査さ
れる。ビットが１であるのて、非空ポインターが第１の
方法に従って存在し、計数値がＢｈ未満のインデックス
を有する全てのビットから構成される。（別法として、
ルックアップテーブルを使用することができる。）この
計数値、３は、１４ポインター（要素３）が位置するノ
ード内へのインデックスとして使用される。この方法に
おいて、論理アドレスを物理アドレスへ変換することが
できる。

【００１６】ポインター圧縮のこの方法は、種々の欠点
を有している。第１に、この計数を実行するために必要
とされるハードウエアー又はソフトウエアーはしばしば
高速用途に対して遅すぎる。逆に、より高速のルックア
ップテーブルは大量のメモリー（２＊＊２０又は１メ
ガ）を必要とする。（ビットマスクを支援するための）
この追加のメモリーはポインター圧縮を使用することに
より実現するメモリー増加と匹敵する。

【００１７】本発明は、ポインター圧縮を通して不経済
な空ポインターを除去し、且つ高速論理物理インデック
ス変換を提供する方法及び装置を提供することにある。
本発明はより高速でこの様な変換を達成し、従来のシス
テムよりメモリーを要しない。１６ビットビットマスク
と対比して、本発明は４ビットノード形態及び２つのビ
ットポインターＩＤを利用して論理−物理変換を達成す
る。

【００１８】全ての空ポインターが本発明で除かれるの
ではなく、それらの大部分が除去される。完全なポイン
ター圧縮が部分圧縮と比較して何らかの利点を必ず与え
るものではないことが判った。特に、ノードを２の冪乗
以外のあるサイズに圧縮する点出ないことが論証され
た。（これらの議論を支持する詳細な計算は付録Ｉに見
出される。）全圧縮が必要とされないので、本発明は２
つのみの形態のノード、即ち、１６要素有するノード
（完全ノード）及び４つの要素を有するノード（圧縮ノ
ード）を使用する。従って、５以上の非空ポインターを
もともと有する如何なるノードも、完全なノードとして
残される。４以下の非空ポインターを有するノードは４
要素圧縮ノードへ変換される。

【００１９】完全ノードの要素は、ポインター圧縮がな
いようにインデックス付けされる。各圧縮ノードは１５
のノード形態の一つと関連する。各ノード形態は４ビッ
トから構成され、特定のハードウエアー（又はソフトウ
エアー）構成と関連される。特定のノードが（前のノー
ドに於けるノードポインターによって）選択される時、
対応するノード形態も選択される。

【００２０】このノード形態は特定のハードウエアーを
選択及び／又は制御するのに使用される。そのノードで
検索されるべき文字からなるビットは、選択されたハー
ドウエアーへの入力として使用される。（ソフトウエア
ーで実行することのできる）ハードウエアーは４ビット
信号を生成する。この信号の一部は圧縮ノード内のポイ
ンターのインデックスとして使用される。

【００２１】ハードウエアー（又はソフトウエアー）で
生成された信号は入力検索文字に対応する物理的インデ
ックスを表している。この物理的インデックスは、変換
マトリックスとして表現できるマッピング関数の使用を
とおして入力検索からえることができる。ポインターノ
ード内の各ポインターはポインターＩＤと関連してい
る。ポインターＩＤはポインターが関連する文字値を特
定する２ビットコードである。

【００２２】圧縮ノードで検索を達成するために、４ビ
ットノード形態は特定のハードウエアを選択又は制御す
るのに使用される。この構成は、検索文字のビットを入
力として使用して、４ビット出力信号を発生する。２つ
の出力ビットはノードに含まれるポインターへのインデ
ックスとして使用される。或るポインターが一度選択さ
れると、そのポインターに関連するポインターＩＤは出
力信号の他の２ビットと比較され、検索されている文字
がそのポインターによって表される文字と一致するか否
かを決定する。一致が見出されると、検索が続行する。
一致が見出されないと、検索されているワードがデータ
ベース内になく、検索が終了する。

【００２３】別の実施例においては、論理物理変換は、
ハードウエアでなく、ソフトウエアーを介して達成され
る。更に別の実施例においては、４ビットノード形態は
４ビット文字コードと結合されてルックアップテーブル
のアドレスを指定する。本発明の論理物理変換を実行す
るのに必要とされるハードウエアは、十分に簡単であ
り、従来の技術と比較して速度の点で大きな利益を与え
る。

【００２４】更に、本発明で採用される簡単な記述子
（ノード形態及びポインターＩＤ）は従来の技術と比較
してメモリーを節約する。例えば、ルックアップテーブ
ルが使用される場合、従来の装置は２＊＊２０（即ち
１，０４８，５７６）のエントリー（ビットマスクに対
して１６ビット且つ文字に対して４ビット）を有するル
ックアップテーブルを必要とする。本発明は２＊＊８又
は２５６エントリー（ノード形態に対して４ビット、文
字に対して４ビット）を有するテーブルを必要とする。

【００２５】作用的観点から本発明の実施例を要約する
と、アドレス指定されるノードが先ず検査され、このノ
ードが圧縮されたノード又は１６要素ノードであるかを
調べる。ノードが完全なノードである場合、検索文字は
ノード内への直接インデクスとして使用される。検索さ
れるべきノードが圧縮ノードである場合、検索文字が、
変換マトリックスによって表すことができるマッピング
関数を達成することにより物理アドレスへ変換される。
この変換されたアドレスからなるビットは、検索文字が
見出される変換マトリックスの行及び列の値を表してい
る。

【００２６】出力物理アドレスからの行の値は、圧縮ノ
ード内のポインターのアドレス値として使用される。各
この様なポインターは、ポインターが関連される変換マ
トリックスの列を示すポインターＩＤを含む。適当なポ
インターが（出力行ビットの使用を通して）一度設置さ
れると、出力列ビットが比較されて、位置されるポイン
ターが検索されている特定の文字に対応するか否かを決
定する。

【００２７】列ビットが一致する場合、検索は設置され
たポインター内で結合されたアドレスを使用し続ける。
列ビットが一致しないと、空ポインターは、関連する１
６要素ノード内の検索文字位置内にあることを示し、検
索は終了しなければならないことを示す。

【００２８】

【実施例】上述された様に、本発明においては、完全な
ノード（１６要素を有するノード）がポインター圧縮が
無い如くインデックス付けされる。この様にして、ＴＲ
ＩＥノードの全ての参照が圧縮ノード（４つの要素を有
するノード）に向けられるが、これ以外の場合は特別な
ものとされる。ポインター圧縮に加えて、「パス圧縮」
がを同様に採用される。パス圧縮は、一つのみの非空要
素を有する全ノードを除去する。パス圧縮を達成するた
めの方法又は装置がCOMPRESSED PREFIXMATCHING DATABA
SE と題される１９８９年１２月７日に出願された米国
特許出願第３７８，７１８に記述される。 Ｉ．ノード形態及び関連するハードウエアー 各圧縮されたノードは４つの要素を有しており、各要素
は１６の可能な文字の一つに対応し、或る与えられた圧
縮ノードに対応し得る４つの文字の１８２０〔即ち、１
６個から４個を取り出す組み合わせの数１６！／〔１２
！＊４！〕〕の可能な組み合わせが存在する。本発明は
１４の４ビットノード形態及び４つの２ビットポインタ
ーＩＤを利用して、全ての可能な要素の組み合わせを、
従って、全ての可能な圧縮ノードを記述する。

【００２９】上述した様に、本発明においては、各圧縮
ノードは４ビットノード形態と関連しており、各ノード
形態は、特定の論理物理インデックス変換を達成する能
力がある特定のハードウエアーと関連している。これら
のノード形態は、各ノード形態と関連するハードウエア
ーによって変換できる論理インデックスの可能な組み合
わせを表している。１５の可能なノード形態があり、４
つのビットか選択された適当なノード形態を示すのに要
求される。

【００３０】各ノード形態と関連するハードウエアーは
そのノードで検索される文字に応答して動作する。上述
された様に、検索文字は検索される文字列の部分であ
り、通常４ビット長である。４ビット長であると、各検
索文字は１６進と均等なものにより呼び出すことができ
る。例えば、検索文字１１１１はＦｈと等しく、１００
１は９ｈと等しい。他の場合で特定されない場合は、検
索文字は１６進の形態で参照される。

【００３１】各ノード形態及び対応する変換マトリック
スが図３〜５に図示される。変換マトリックスは１５の
ハードウエアー構成の各々によって変換するこのできる
文字（論理インデックス）の可能な組み合わせを表示す
る。図示される１５の変換マトリックスは１５の内の一
つのみの可能な組みである。図示されたものと機能的に
等しい１５の変換マトリックスの多くの他の組みが存在
する。各均等なマトリックスは説明されたマトリックス
から容易に引き出すことができる。

【００３２】ハードウエアー（又はソフトウエアー）を
実行すると、文字の組み合わせを論理インデックスから
物理インデックスへ変換することができる。各ハードウ
エアー（又はソフトウエアー）構成によって達成される
変換は関連するマトリックスによって表示される。完全
ノードが圧縮ノードに圧縮されるか（又は圧縮ノードが
構成される）時、どの４つの文字が圧縮ノードと関連す
るかが一般的に判る。先に議論された圧縮されたノード
に対して、文字１ｈ、３ｈ、７ｈ及びＢｈに対応するこ
とが判る。或る圧縮ノード及び対応する文字が与えられ
ると、変換マトリックスを適切なノード形態を選択する
ために使用できる。

【００３３】これらの変換マトリックスは以下の様にし
て解釈することができる。各ノード形態と関連するハー
ドウエアー又はソフトウエアーを論理インデックスから
物理インデックスへ変換するのに使用することができ
る。１要素を有する如何なるノードに対する文字コード
が行０からの要素に対応し、他の１の要素は行１からの
要素に対応する。他の２つの要素は行２及び３の各々か
らの文字に対応する。各組み合わせからなる文字は、各
行から選択される一つのみの要素が存在する限り、如何
なる列からも選択することができる。

【００３４】例えば、ノード形態０００１と関連するハ
ードウエアーは文字３ｈ、６ｈ、８ｈ、Ｅｈに対応する
圧縮ノードの変換を達成することができる。これは、各
文字が変換マトリックスの別の行に設定されるからであ
る。同じハードウエアーは文字０ｈ、５ｈ、Ｆｈ及びＤ
ｈ又は文字３ｈ、１ｈ、８ｈ、Ａｈに対応する要素を有
するノードに対する変換を達成することができる。これ
は、これらの文字の各々が変換マトリックスの別の行内
に或るからである。

【００３５】しかしながら、同じハードウエアー（ノー
ド形態０００１）を使用すると、文字Ｂｈ及びＣｈの文
字が変換行の同じ行（行２）内に設置されるので、文字
６ｈ、Ｂｈ、Ｃｈ及びＤｈの組み合わせを変換すること
が出来ない。この様な組み合わせに対して、ノード形態
１００１によって表される組み合わせの様な他のハード
ウエアーの組み合わせが必要となる。ノード形態１００
１は行２内に６ｈを有しており、行３にＢｈを有してお
り、行０にＣｈを有しており、且つ行２にＤｈを有して
いる。

【００３６】この実施例が説明する様に、文字は完全ノ
ード内にあるので、文字が変換マトリックス内と同じ順
序で見出される必要はない。４文字の所与の組み合わせ
から、所定のノード形態を選択するためのみに必要なこ
とは、各文字が変換マトリックスの異なる行で見出され
ることにある。この方法だと、所与のノードに対する４
つの文字が一度知られると、適当なノード形態及びその
関連する変換ハードウエアー又はソフトウエアーを選択
することが可能となる。例えば、図２の対応するノード
が本発明で変換されると１１１１のノード形態が選択さ
れるであろう。このノードは、このノードに対応する４
つの文字の各々がノード形態１１１１に関連する変換マ
トリックスの異なる行で見出されるので、選択される。

【００３７】固有のノード形態が一度選択されと、ノー
ド形態１１１１と関連するハードウエアー又はソフトウ
エアーが適当な論理物理変換を１ｈ、３ｈ、７ｈ及びＢ
ｈに対応する文字を有するノードに対して達成すること
ができる。特定のノードに対するノード形態が、そのノ
ードと関連する特定のメモリー空間に記憶することがで
きる。或る実施例において、各ノードに対するノード形
態が、ノードを指し示すポインターと共に記憶される。
この実施例においては、各ノードポインターは次のノー
ドの位置を示すポインターアドレスだけでなく、次のノ
ードで実行される変換マトリックスを示すノード形態を
含む。

【００３８】１５のみのノード形態が存在するので、１
つの４ビットの組み合わせ（００００）は使用されな
い。従って、００００のノード形態は次のノードか完全
（１６要素）ノードであることを示すのに使用できる。 ＩＩ． ポインターＩＤ ノード形態に加えて、本発明はポインターＩＤとして知
られる２つのコードを利用して、圧縮ノードに対する論
理物理インデックス変換を実行する。各ポインターＩＤ
は、圧縮ノード内に各ポインターが位置する文字を表す
２ビットコードである。各ノードは１５のノード形態の
一つと関連しており、ノード内の各要素が４つのポイン
ターＩＤの一つと関連している。ポインターＩＤは、所
定のノードに対するノード形態が知られる後だけでポイ
ンターＩＤを選択することができる。

【００３９】ポインターＩＤはノード内の特定の要素に
どの文字が対応するかを示す。上述した様に、各変換マ
トリックスは、各ノード形態と関連するハードウエアー
又はソフトウエアーによって達成される特定の変換をす
る４×４の表記である。ノード形態のみが、特定のノー
ドが２５６の可能な組み合わせの何れか一つ（例えば、
行０からの４要素から一つ、行１からの４要素から一
つ）を表現することができることを示す。ポインターＩ
Ｄは、所与の圧縮ノードにどの特定の文字が対応すかを
示すのに使用することができる。ポインターＩＤは、圧
縮ノード内の特定の要素が対応する変換マトリックス内
の特定の列の２進表現として解釈できる。

【００４０】例えば、所与のノードが文字３ｈ、２ｈ、
Ｃｈ及びＤｈに対応することが分かると、（各文字が異
なる行内に存在するので）ノード形態０００１を選択す
ることができる。ノード形態は０００１は、しかしなが
ら、所与のノードを一義的には記述しない。例えば、ノ
ード形態０００１はまた７ｈ、５ｈ、Ｆｈ及びＤｈに対
応するノードを同様に表現している。

【００４１】ノードを完全に記述するために、ポインタ
ーが必要とされる。上述されたように、ポインターＩＤ
は圧縮された各要素に関連する。上述した例（ノードが
３ｈ、２ｈ、Ｃｈ及びＤｈに対応している）において、
第１の要素のポインターＩＤは０１であろう。これは文
字３が変換マトリックスの列１内にあるからである。第
２の要素は文字２ｈに対応するので、変換マトリックス
の列０内の２ｈとしてポインターＩＤ００と関連され
る。同様にして、第３及び第４の要素に対するポインタ
ーＩＤが決定される。第３の要素のポインターＩＤは１
０であり（Ｃｈは第２列になあるので（２進１０＝
２））、第４の要素のポインターＩＤは１１（列３に対
する）である。

【００４２】図６は、ノード形態及びポインターＩＤの
両方を使用するノード圧縮の例を示している。この例に
おいては、完全なノード、ノード（６０）が先ず４つの
要素（６２）を有する圧縮ノード、ノードＣ’に圧縮さ
れる。完全ノードが３ｈ、６ｈ、８ｈ及びＥｈに対応す
る非空ポインターを有していたので、上記の文字の各々
か別の行に存在する変換マトリックスが選択される必要
がある。ノード形態０００１に対応する変換マトリック
スがこの行に対する要求を満足すのので、これが選択さ
れる。

【００４３】検索中、ノードＣ’に対するノード形態
が、ノードＣ’に対するポインターが参照されると同時
に指定される。完全ノードからのポインターは次に圧縮
ノード内の位置に移動することができる。この順序はノ
ード０００１に対する変換マトリックス内の順序に従う
必要がある（即ち、ポインターは文字３ｈに最初に、６
ｈに次に対応する。）。

【００４４】ポインター値に加えて、ポインターＩＤは
圧縮ノード内の各要素とともに記憶される。ポインター
ＩＤは、このポインターに対応する文字が選択された変
換マトリックス内に存在する場所である列に対応する。
この例において、文字３ｈがノード形態０００１に対応
する変換マトリックスの第１の列内に存在するので、第
１の要素に対するポインターＩＤが０１となる。

【００４５】同様にして、文字６ｈが第２の列にあるの
で、第２の要素に対するポインターＩＤは１０である。
第３及び第４の要素に対するポインターＩＤはそれぞれ
００及び１０である。上記の手続きに従って、圧縮され
たＴＲＩＥ構造を形成できる。各圧縮されたノードに対
して、好適なノード形態が選択される。選択されたノー
ド形態及びその関連変換マトリックスが与えられると、
好適なポインターＩＤが選択できノード内に入ることが
できる。 III.圧縮ＴＲＩＥデータベースの構築 スクラッチから開始すると、圧縮されたＴＲＩＥデータ
ベースを構築するための少なくとも２つの方法が存在す
る。第１の方法は帰納的方法として知られ第２の方法は
並列的方法として知られる。

【００４６】Ａ．帰納的構築 機能的方法において、ＴＲＩＥ構造へ導入されるべきエ
ントリーが順次導入される。第１のエントリーが導入さ
れる時、根ノードが作り出される。そこから、次のノー
ドが発生されて、導入されるべき文字列の各文字に対応
される。（ノード発生原因の文字以外の）新たに発生さ
れたノードの各ポインターが空ポインターに設定され
る。次のエントリーは先ず存在するＴＲＩＥに対して対
抗される。新たなエントリーは複製ではない場合、新た
な分岐が構成されて、新たなエントリーが保持される。

【００４７】図７はこの様な帰納的構築の様な例を与え
ている。先ず、文字列０００１ １１０１ １０１１
０１１０がＴＲＩＥに導入される。これは第１のエント
リであるが、４つのノードが生成される。第２のエント
リ０００１ １１０１ １１１１ ０００１は第１の２
つのノードを介して第１のＴＲＩＥと対抗する。１１１
１に対応する要素がないので、新たな分岐が生成される
ことが必要とされる。この様な分岐は第３のノードで形
成されるべきことが要求されるので、或る付加ノードが
加えられる。分岐は空ポインターを非空ポインターに変
更することにより形成され、別のノードを指し示した
り、一致するエントリーが見出されたこと（即ち、リー
フノード）を示す。

【００４８】新たなノードを形成する時にとれだけ多く
のポインターがノードに設置されるかを決めることが出
来ないので、新たなノードの全てを完全なノード（１６
ポインター）として生成することが好ましい。一度ＴＲ
ＩＥが形成されると、４つ又はそれ以下の非空ポインタ
ーを有する完全なノードが圧縮されたノードに変換され
る。

【００４９】Ｂ．並列構築 並列構築を達成するためには、データベース内で置かさ
れるべき全てのエントリーが同時検査に対して利用でき
る必要がある。各エントリーの第１の文字のコピーをと
り、これを「バケット」に投げ込むことにより構築が開
始する。全ての複製文字は廃棄され、残る物は、第１の
ノード内の対応するポインターを有することを必要とす
る文字である。新たなエントリがこのノードに設置され
ることを必要とするのて、圧縮されたノードは、必要な
場合生成することができる。

【００５０】第１のノードが一度形成されると、第１の
根ノード文字に対応する出口ポインターが選択される。
この第１の根ノード文字に対応する文字と一致する第１
の文字を有する各エントリーの第２の文字が、新たなバ
ケットに投入される。複製を廃棄し、新たなノードを形
成するこのプロセスは繰り返えされる。この形態の構築
は、２つのやり方の一方で続行することができる。幅最
初方法だと、各ノードが如何なる以下のノードの構成に
も先立って充填される。深さ最初構成においては、デー
タベースエントリーの各選択された部分集合は、前のノ
ードの次のポインターに移動する以前に充填される。

【００５１】Ｃ．ノード形態の選択 ＴＲＩＥ構造が一度構成されると、５個の非空ポインタ
ーよりも少ないノードも圧縮ノード内に圧縮することが
できる。圧縮されたノードが（並列又は帰納的構築によ
り）構成される時、ノード形態は先ず各圧縮されたノー
ドと関係づけられる。

【００５２】適当なノード形態を選択するための或る可
能な方法は、４つのノード要素に対応する文字を図３か
ら５の種々のマトリックスと組織的に比較する。４文字
が異なる行に存在するマトリックスで見出される時、一
致が生じる。変換マトリックスに対応するノード形態は
次に圧縮ノードと関係される。要素は次に、一致するマ
トリックスによって指示される順番で圧縮ノード内に設
置される。

【００５３】４未満の文字がノードに対応する場合、或
るダミー文字（例えば０）は、ノード形態を選択する
時、使用することができる。これらの文字を保持するノ
ードが構築される時、ダミー文字に対応するノードに空
ポインターが与えられる。速度の観点で、別の方法が使
用され、如何なる所与の圧縮ノードに対しても適当なノ
ード形態を選択することができる。この方法において、
ルックアップテーブルが採用される。このルックアップ
テーブルを使用するために、非空要素と関連する４つの
所与の文字が１６ビットコードに結合される。このコー
ドは、適当なノード形態を報告する６４Ｋのエントリー
ルックアップテーブルのアドレス決めを行うために使用
される。ルックアップテーブルはまた４文字がノードに
割り当てられるべき順番に関する幾つかの指示を同様に
報告することができる。

【００５４】ルックアップテーブルの構成は６４Ｋの各
エントリーを使用して、どの４文字がそのエントリーの
アドレスを指定するかを決めることにより達成すること
ができる。変換マトリックスは次に、適当なマトリック
スが見出されるまで線形的に検索することができる。こ
のマトリックスに対応するノード形態は次にルックアッ
プテーブル内に記憶することができる。

【００５５】所与のノードに対するノード形態が一度選
択されると、完全ノードからのポインターは圧縮ノード
の対応する要素内に輻射することができる。ポインター
が圧縮ノードに移動する時、関連する文字のポインター
ＩＤは各ポインターに割り当てられ、圧縮ノード内のポ
インターと共に記憶される。或る実施例において、指し
示されているノードに対するノード形態はポインター及
びポインターＩＤに記憶することができる。

【００５６】図８は完全ノードから圧縮ノードへ圧縮す
る２つの例を提供しており、ここで、ポインターＩＤ及
びノード形態がポインター要素と共に記憶される。 Ｄ．データベース補修 偶然的に新たなエントリーが加えられ又は古いエントリ
ーが除去される時、データベースを修正することが必要
となる場合がある。これは、ＴＲＩＥ構造を再構築する
のではなくＴＲＩＥ構造を調整することによって達成す
ることができる。

【００５７】新たなエントリー量を、ＴＲＩＥ構造を工
業的に構築する時に、同じ物に加える。ここで、存在す
るノードを、圧縮ノードから完全ノードに成長し、４未
満の非空ポインターを有する圧縮ノードから空ポインタ
ーを有さない圧縮ノードに成長することができる。圧縮
ノードが空ポインターを有するノードから空ポインター
を有さない（又はより少ないポインターを有する）ノー
ドへ成長する場合、この新たなノード形態が選択される
ことが必要とされる。これは、ダミー文字を使用して選
択されたノード形態が、新たに加えられた文字を含む組
み合わせを変換することが出来ない場合に発生する場合
がある。この様な状況では、新たなノード形態を新たな
ポインターＩＤと共に選択される必要がある。

【００５８】或る状況では、この再選択プロセスがノー
ドを完全に再構成することを含む。この様にして、バッ
クポインターのテーブルを含み、親ノードが設置され、
適当に変更する様にすることが一般的に望ましい。デー
タベースエントリの削除は削除されるべきエントリーの
位置を探り、リーフポインターを空ポインターに設定す
ることにより簡単に達成される。若し、リーフポインタ
ーが空ポインターへ変更する結果として、リーフポイン
ターを一度含むノードが全ての空ポインターを有するノ
ードへ還元されると、このノードは除去することがで
き、（このノードを指し示す）その親ノードは空に設定
される。このノードにおいて非空ポインター又はその親
ノードの数を５未満に減少することが可能であり、この
場合、適当なノードを圧縮することができる。

【００５９】データベース補修が古いノードを利用可能
なフリーメモリーのリストへ戻し、新たなノードを利用
可能なノードメモリのリストから取り出すことは明らか
である。２つ異なるサイズのノードが存在するので、利
用可能な及び使用されたメモリーのトラックの追跡は困
難になる。利用可能なノードメモリーを維持するための
或る可能な方法は、完全ノードに対するものと、圧縮ノ
ードに対するものとの２つの別のメモリースタックを保
持することにある。

【００６０】ノードメモリーを補修する別の方法は、フ
リーメモリーの単一のリストを使用することである。こ
の様な構成が図９に図示されている。このリスト（７
０）は２つの端部（７２，７４）及び各端部を示す分離
ポインターＰ１６（７６）及びＰ４（７８）を有してい
る。ＴＲＩＥ構造が空の時、フリーリストは一杯であ
り、ポインターＰ１６（７６）はＮ個のフリー完全ノー
ドを指し示す。同時にポインターＰ４（７８）は４＊Ｎ
個のフリー圧縮ノードを指し示す。

【００６１】ＴＲＩＥ構造が構築される時、圧縮された
ノードがリストの一端から取得され、完全ノードが他の
端部から取得される。一つのノードキュー及び２つのポ
インターを利用するための方法は２つの別のメモリース
タックの使用と比較してメモリーを節約する。メモリー
が短縮された連続の形態で使用されることを補償するた
めに、除去された古いノードはリストに戻される。これ
らのノードは、リストの適当な終わりで使用されたノー
ドと取り替えられる。このポインターは次に一つ位置を
ずらす。これは、ポインターの衝突及びノードメモリス
タックの使用下となることを防ぐために必要とされる。
この様な方法で、古いノードで使用されるメモリーがフ
リーリスト内に設置され、利用可能なメモリーの短縮使
用を推進する。

【００６２】この様なノード取り替えの例が図１０及び
図１１に図示されている。図１１において、Ｐ１６ポイ
ンターは、最終使用ノードであるノードＸを指し示す。
この例では、ノードＹは除去される。ノード取り替えが
採用されないと、ノードＹはその対応するメモリー位置
に戻され、メモリーの分断化を結果する可能性がある。
この様な結果は図１０に図示される。

【００６３】図１１はノード取り替えを通して得ること
のできる利益を図示している。この例においては、ノー
ドＹはメモリースタックには戻されず、ノードＸによっ
て取り替えられる。このノードＸはＰ１６によって最終
ノードが指し示めした。図１１は、どの様にして取り替
えが、使用された及びフリーメモリーの両方が連続する
ことを可能として、利用可能なメモリーの効率的な使用
を促進しているのかを図示している。 IV. 圧縮ＴＲＩＥデータベースの検索 圧縮されたＴＲＩＥデータベースが一度構成されると、
検索は以下の方法で達成することができる。

【００６４】検索は先ず、検査されるべき第１のノード
（根ノード）に対するポインターを保持するレジスタの
位置を探ることにより開始される。この「ポインター」
はノード内の要素の形式と等しい。この様にして、根ノ
ードに対するポインターは、根ノードが圧縮ノードであ
ること、及びその場合のノード形態を示すことができ
る。根ルートに対するポインターはレジスタである必要
はなく、或る特定の位置が根ノードに対するポインター
を含むことのみが必要である。

【００６５】第１に、検索されるべきノードが完全ノー
ドである場合、検索は、ポインター圧縮がない如くに実
行される（即ち、検索されるべき文字がそのノードに対
する直接インデックスとして使用される）。検索される
べきノードが圧縮ノードである場合、文字値（論理値）
が物理アドレスへ交換されて、修正ポインターの位置を
探る必要がある。

【００６６】上述した様に、この変換は１５のノード形
態の各々と関連する特定のハードウエアー又はソフトウ
エアーを介して達成される。このハードウエアーは対応
する変換マトリックスで説明された変換手法を実行する
のに使用される。特定の圧縮ノードが選択されると、対
応するノード形態も選択される。図１２は本発明の１実
施例を示している。この実施例においては、ブロック８
０はノード形態に対応する種々の変換機能を達成する能
力のあるハードウエアーを表している。検索されている
文字の４ビット表示はハードウエアーブロック（８０）
への入力として使用されている。また、４ビットノード
形態も入力として使用される。

【００６７】これらの２つの信号に応答し、変換ハード
ウエアー（８０）が４ビット出力を発生する。この出力
は、検索されるべき文字によって参照される論理アドレ
スと関連する物理アドレスに対応する。この物理アドレ
スの最初の２ビットは、圧縮されたノード内の４つのポ
インターの一つを選択するのに使用される。第２の２ビ
ットは次にこのポインターと関連するポインターＩＤと
比較される。ポインターＩＤが物理アドレスの第２の２
ビットと一致する場合、この一致が見つけられ、この検
索がポインターアドレスによって参照されるノードで続
行する。ポインターＩＤが物理アドレスビットと一致し
ない場合、一致がなく、検索は終了する（即ち、空ポイ
ンターに到達する。）変換ハードウエア又はソフトウエ
アーによって達成される変換は以下の通りである。ノー
ド形態が一度選択されると、特定のハードウエアー及び
ソフトウエアー及び特定の変換マトリックスも選択され
る。このハードウエアーが関連する変換マトリックスに
よって図示される機能を達成する様に構成されている。
例えば、０００１のノード入力及び０１００又は４ｈの
文字入力を使用して、変換ハードウエアー又はソフトウ
エアーが００１０の出力信号を発生する。出力の最初の
２ビットは変換マトリックスの対応する行（即ち、この
例においては、第１の行（行０）を表している。出力の
第２のビットが対応する変換マトリックスの列を表して
いる。この例において、入力文字（４ｈ）が第２の列に
あるので、列の値は１０（２進２）である。

【００６８】変換マトリックスに対するのに加え、変換
ハードウエアーからの出力は又圧縮ノード内の物理ポイ
ンターのアドレス指定及び検査に使用される。以上の例
において、行の値が００であるので、第１の要素（行
０）内のポインターが選択される。特定のポインターに
関連するポインターＩＤは次に１０、出力信号の最終の
２ビットと比較される。一致は、第１のポインターが文
字４ｈに対応することを示し、検索が続行する。ビット
及びポインターＩＤが一致しない場合、選択されたノー
ドの文字４ｈと関連するポインターが存在しないので、
検索は終了する。

【００６９】この方法により、上述の方法で構成された
ノードは４ビットノード形態及び２ビットポインターＩ
Ｄのみを使用して検索することができる。これらの２つ
のコードの使用は各ポインター要素に対して６（４＋
２）だけの付加ビットを必要とする。これでインデック
ス変換に対する１６ビットビットマスクを使用する装置
と比較してかなりメモリーを節約することになる。

【００７０】Ｖ．変換ハードウエアーの実現 Ａ．ハードウエアー 変換機能を有する実際のハードウエアーの構成を助ける
ために、図１３、１４、１５は各ノード形態、その関連
する変換マトリックス及び第３のマトリックスを図示す
る。この第３のマトリックスは「ハッシング」マトリッ
クスとして知られている。

【００７１】各ノード形態に対するハードウエアーの構
成は以下の通りである。第１に、関連するノード形態が
図１３、１４、１５に配置される。次に、対応するハッ
シングマトリックスが得られる。各ハッシングマトック
スは、論理インデックス（即ち、検索文字）を、ハッシ
ングマトリックスと関連するノード形態を有する圧縮さ
れたノード内の対応する要素のアドレス指定を行うのに
使用される物理アドレスへ写像するハードウエアー又は
ソフトウエアーを介して実行される線形関数を表してい
る。

【００７２】上述した様に、各ハッシュは特定の線形写
像関数の表示である。この議論の目的から、線形関数は
本質的に以下の通りである。Ａが（ａ１及びａ２を含
む）文字集合であり、＃が（ａ１＃ａ２）の結果が同様
にＡ内の文字である様に選ばれた非トリビアル２進オペ
レータである場合において、集合Ａから異なる集合Ｂの
要素に写像する関数Ｈ（）が定義される。集合Ｂがま
た、（ｂ１＠ｂ２）がＢの要素である様な非トリビアル
オペレータ＠を含む場合、オペレータ＃及び＠が、全て
の可能な要素ａ１及びａ２に対して、Ｈ（ａ１）＠Ｈ
（ａ２）＝Ｈ（ａ１＃ａ２）であることが見出される場
合及びその場合のみにおいて、関数Ｈ（）は線形であ
る。

【００７３】ハッシングマトリックスによって表される
線形関数に対して、集合Ａは全ての可能な検索文字（文
字インデックス）の集合に対応し、集合Ａは固有のノー
ド要素をアドレス指定するのに使用される物理インデッ
クスに対応する。従って、各パッシングマトリックスは
写像関数Ｈ（）に対応し、論理インデックスから物理イ
ンデックスへ写像する。

【００７４】変換マトリックスによって表される写像関
数及び関連するハッシングマトリックスは線形であるの
で、単純なハードウエア構成が各関数（又は各ノード形
態が１５の可能な写像関数の一つと関連するのでノード
形態）に対して導かれる。２進オペレータ＃及び＠に対
して数種の可能なハードウエア構成が存在するが、排他
的論理和（ＸＯＲ）オペレータを利用するハードウエア
のみが記述される。

【００７５】排他的論理和ハードウエアーは、その２つ
入力の何れかが１である場合は常に論理１信号を発生す
る。両入力が１又は両入力が０の場合、出力は零とな
る。図１６は排他的ハードウエアーに対する通常のシン
ボルを図示している。３入力以上の排他的論理和は入力
信号を２つづつのグループに分けることにより説明でき
る。４入力の排他的論理和の例が図１７に与えられてい
る。

【００７６】図１８はハッシング関数の一つの可能なハ
ードウエアーの実行を図示している。ノード形態（９
０）が一度（例えば、親ノード内のポインターから）得
られると、これは１６（２＊＊４）エントリーを有する
ルックアップテーブル（９２）内に入力される。ルック
アップテーブル内の各エントリーはハッシングマトリッ
クスの１６のマトリックス係数を表す１６のビットから
なる。従って、ルックアップテーブルは、入力ノード形
態と関連するハッシングマトリックスの係数を表す１６
ビット出力（Ｈ０−ＨＦ）を発生する。ルックアップテ
ーブル及びハッシュテーブルマトリックス間の相関がマ
トリックス（９６）内に図示されている。

【００７７】マトリックス係数がルックアップテーブル
（９２）から一度出力されると、これらは図１８に図示
されるハッシングハードウエアーへ入力される。各マト
リックス係数は１６ＡＮＤゲート（９８Ａ−９８Ｐ）の
一つへの１入力として機能する。最上位ビットであるＣ
０を有する検索文字（Ｃ０−Ｃ３）に対する文字ビット
はまたハッシングハードウエアーへの入力である。各文
字入力ビットは１６ＡＮＤゲートの４入力とされる。

【００７８】１６ＡＮＤゲートからの出力は４つのグル
ープに分けられ、入力は４つの４入力ＸＯＲゲート（９
９Ａ）にグループ分けされる。これらのゲートの動作は
図１７に図示されるものと同じである。最上位ビット０
０を有する４つのＸＯＲゲート（００−０３）は入力検
索文字に対応するハッシュされた（又は物理）インデッ
クスを表示する。

【００７９】図示されたハードウエアーはハッシングマ
トリックスを直接実行するものと考えることができる。
各々４つのＡＮＤゲートの集合である（各ＸＯＲ）ゲー
トはハッシングマトリックスの別の行と考えることがで
きる。従って、各ＸＯＲゲートの出力は、関連するハッ
シングビットによって表される行と、列化された形態で
検索文字ビットによって表される列との２進値マトリッ
クスの積に等しい。

【００８０】例えば、検索文字７ｈ（０１１１）及びノ
ード形態００１０が与えられると、ハードウエアーは以
下の様に作動する。先ず、ノード形態００１０はルック
アップテーブル（９２）へ入力される。ルックアップテ
ーブルは（例えば、１０１００００１０１００００１０
の）関連するマトリックス係数を発生する。これらのマ
トリックスは入力文字ビットとの論理和が取られ、ＸＯ
Ｒゲートに対する入力を発生する。この例では、ＸＯＲ
（９９Ａ）に対する入力は００１０であり、ＸＯＲ（９
９Ｂ）に対する入力は０００１であり、ＸＯＲ（９９
Ｃ）に対する入力は０１００であり、ＸＯＲ（９９Ｄ）
に対する入力は００１０である。

【００８１】従って、ハードウエアーからの出力は１１
１１又は行３、列３である。図１３を参照し直すと、ノ
ード形態００１０に関連する変換マトリックスに対する
行３、列３に対応する文字は７ｈ（これは入力文字であ
った）であることに気付く。従って、各ノード形態に対
するハッシングマトリックスが与えられると、ハードウ
エアーの実現が極めて容易になる。

【００８２】Ｂ．ソフトウエアーの実現 論理物理アドレス変換がハードウエアーでなく、ソフト
ウエアーの使用を通して生じる別の実施例が考えられ
る。これを実行することできる少なくとも２つの方法が
存在する。 １．マトリックス乗算 論理物理変換は、ノード形態と関連するハッシングマト
リックスを列形態の入力検索文字の４つのビットと乗算
することにより達成することができる。この様な乗算は
公知のブログラム技法をとして達成することができ、変
換された（物理）アドレスを発生することができる。

【００８３】例えば、検索文字７ｈ（０１１１）及びノ
ード形態００１０が与えられると、変換アドレスは以下
の様にして決定することができる。ソフトウエアーを
（伝統的な方法を使用して）発展させ、図１９に示され
るマトリックス乗算を達成することができる。この様な
乗算は、上述のハードウエアーを使用して得られるもの
と等しい４ビット出力を発生する。

【００８４】同様の方法で、マトリックス乗算を達成す
るためのプログラムが１５のノード形態の各々に対して
発展することができる。 ２．ルックアップテーブル 乗算プログラムを使用する代わりに、高速ルックアップ
テーブルを採用することができる。変化されたアドレス
を得るために、４ビット検索文字を４ビットノード形態
と結合して、８ビットアドレスを発生することができ
る。この様なアドレスは２５６（２＊＊８）エントリー
を有する変換テーブルのアドレス決めに使用することが
できる。この様な変換テーブルは、ノード形態を文字コ
ードと組織的に結合し、これがどのアドレスにアクセス
するかを決め、そしてそのアドレスに特定のノード形態
及び文字の結合に対応する変換アドレスを記憶すること
により達成できる。 ＶＩ．実施例 図２０−２１は８エントリーを有するＴＲＩＥ構造化さ
れたデータベースの構築を図示している。図２１におい
て、このエントリーは圧縮されたノードを使用するＴＲ
ＩＥ構造へ設置される。図２２は、上述の方法を使用し
て圧縮されるＴＲＩＥ構造を図示している。この例で
は、現在のノードに対する次のノード及びポインターＩ
Ｄに対するノード形態が各ノードの各要素に記憶され
る。また、この例では、リーフノードが０、１又は２に
等しい如何なるエントリーに対しても与えられる。完全
ノードに対して、ポインターＩＤビットが不適切であ
る。

【００８５】図２３は検索ワード６Ｄ５に対する例示的
なデータベースで行うことのできる検索を図示してい
る。一致がこの検索ワードに対して見出されると、検索
はリーフノードで終了する。図２４Ｂにおいて、同じデ
ータベースが、異なる検索項ＥＡ９を使用して検索され
る。ここで、対応するエントリーが見出されず、検索は
ノードＤで終了する。ここで、ポインターＩＤが発生さ
れた変換アドレスと一致しないことか分かる。 VII. 特別な実行 以下に記述のおいて、上で参照された出願による通路圧
縮が採用されると考える。

【００８６】図２５−３３は本発明の特定の実施例を図
示している。図示された実施例は少なくとも３０Ｋのエ
ントリーを保有する能力がある。３２Ｋの末端ノード及
び３０Ｋの末端ノードが存在する。２Ｋの変換ノードが
写像されて、特別な実行（例えば、ＩＳＯ ８３４８／
ＳＤ２ フォーマットネットワートアドレッシング）に
対する固有の解析を指示するための付加的なメモリーが
提供される。写像されたノードのアドレス指定の試み
は、空ノードとして解釈される。この実施例において、
通路圧縮がポインター圧縮と共に実行される。

【００８７】図２５は本発明において利用されるメモリ
ー構成を図示する。７個の１メガＳＲＡＭが以下の様に
構成される。６個の２４５＊４のチップが２５６Ｋ＊２
４メモリーバンクとして構成されている。７番目のＳＲ
ＡＭが１２８Ｋ＊８メモリーバンクとして採用される。
２５６Ｋ＊２４メモリーバンクが文字列／ポインターメ
モリーとして知られる。この１２８Ｋ＊８メモリーバン
クは制御／拡張ワードメモリーとして知られる。

【００８８】文字列／ポインターメモリーは１２８Ｋ＊
２４の２つのバンクに分割される。上方のバンクは「ポ
インターバンク」と呼ばれ、３２Ｋの圧縮ノードの一連
の領域と考えることが出来る。この領域は１５ノードア
ドレスビットのアドレスによってアドレス可能である。
１６のアドレスビットは、ノードが遷移ノード（別のノ
ードを指し示すノード）であるか、末端ノード（検索の
端部を指し示すノード）であるかを示すのに使用され
る。この１６ビットはアドレス可能な圧縮された６４Ｋ
のノード全てに作用する。

【００８９】文字例／ホインターバンク内の下方のバン
クは「文字列バンク」として知られる。このバンクは６
４Ｋの二重ワードに分割される。各二重ワードは６４Ｋ
のアドレス可能なノードの一つと関連する。各２重ワー
ドが第１の文字例及び第２の文字ワードからなる。文字
ワードの使用はCOMPRESSED PREFIX MATCHIN DATABASESE
ARCHINGと題される出願に議論されており、ここでは議
論されない。

【００９０】１２８Ｋ＊８メモリーバンクが制御／拡張
ワードメモリーとして知られる。このメモリーバンクは
６４Ｋの二重ワードに分解される。各二重ワードはアド
レス可能な圧縮ノードの一つと関連する。制御／拡張ワ
ードは通路圧縮で使用され、上記特許出願で議論され
る。図２６は文字列／ポインターメモリーに記憶される
２４ビットポインターの分割を図示している。各４ノー
ドはこの様な４ポインターを含んでいる。第１の２ビッ
トＰ及びＳはパリティービット及び文字列ビットであ
る。このパリティービットはポインターが正しく記憶さ
れていることを補償するのに使用され、文字列ビット
が、通路圧縮文字列が次のノードに記憶されることを示
す。この説明の目的として、文字列ビットが設定され
ず、即ち、通路圧縮文字列が次のノードに記憶されない
と仮定する。文字列ビットが設定される時の固有の操作
が上記出願に含まれる。

【００９１】Ｐ及びＳビットの後に、２ビットポインタ
ーＩＤが配置される。ポインターＩＤに次のノードに対
するポインターが続く。このポインターは１６ビットか
らなる。第１の（最上位）ビットがＴＮとして知られ
る。このビットが設定される場合、これは、次のノード
が末端ノードであることを示す。ＴＮビットに続く１５
ビットは次のノードの最下位ビットからなる。上述した
様に、２Ｋの遷移ノードが分析のために写像することが
できる。これが行われる場合、００００ｈから０７ＦＦ
ｈ迄のアドレスは空ノードと解釈され、この範囲内の値
を有するポインターは空ポインターである。１６要素ノ
ード（完全ノード）がアドレスされるべき場合、ポイン
ターの最後の２つの最下位ビットが零に設定されるべき
である。

【００９２】ポインターに続いて、次のノードに対する
４ビットノード形態が続く。００００のノード形態が、
次のノードが完全ノードであることを示す。ポインター
が、次のノードが端子ノード又は空であることを示す場
合、そのノードビットは不適切である。図２７−２９は
制御／拡張ワード及び文字列ワードに対するビット表現
を記述する。

【００９３】図３０は本発明の実施例を表示する図。計
数器／拡張ワードメモリー（１００）、レジスタ（１０
１）、文字列圧縮論理（１０２）、及びＡＮＤゲート
（１０３）は全て通路圧縮で利用される。上述の様に、
この説明の為に、各ノードは２以上の非空ノード要素を
有する完全ノード又は圧縮ノードであると考える。この
様にして、ＡＮＤゲート（１０３）は常に０を発生し
て、（文字ワードと対比される）ポインターがフェッチ
されるべきことを示す。

【００９４】レジスタ（１０４）及び（１０５）は次の
ポインター及び検索されるべき次の文字の開始を記録す
るのに使用される。検索文字（１０６）は検索されてい
るデータ文字列の４ビット部分からなる。上述の様に、
各ポインターは文字列／ポインターメモリー（１０８）
に記憶される２４ビットエントリーである。レジスタ
（１０５）は、検索文字の開始しと同時に各ポインター
の開始を記録するのに使用される。

【００９５】２４ビットポインター信号は文字列圧縮論
理（１０２）及びホールディングレジスタ（１０９）に
与えられる。ホールディングレジスタは、フェッチされ
たエントリーがポインターか文字列であるかを示す信号
（１１０）によってイネーブルになる。このために、ホ
ールディングレジスタは常にイネーブル状態となる。ノ
ード形態を表すポインター信号の４ビットは、零検出器
（１１２）及びノード形態ルックアップ（１１３）の両
方に与えられる。零検出器（１１２）は、ノード形態入
力が００００に等しい時常に１を発生する。従って、完
全ノードがアドレス指定された時（即ち、ノード形態＝
００００）、零検出器（１１２）からの信号は１であろ
う。０信号は、アドレスされるべき次のノードが圧縮さ
れたノードであることを示す。零検出器（１１２）から
の出力はレジスタ（１３０）への入力として加えられ、
次のクロックサイクル（ブロックＢ）に対する入力とし
て機能する。

【００９６】ノード形態ルックアップ（１１３）通常論
理を採用して、４ビット形態を、ノード形態と関連する
変換マトリックスを示す１６ビット信号へ変換する。ハ
ッシュ論理（１１４）は４ビット検索文字入力にハッシ
ング動作を達成する。ハッシュ論理（１１４）からの出
力は２つの列ビット（１１５ａ）及び２つの行ビット
（１１５ｂ）を含む。理解される様に、ハッシュ列ビッ
トがレジスタ（１３０）に与えられ、次のクロックサイ
クルに対する入力として機能する。（ブロックＡを見
よ）２つの行ビット（１１５ｂ）は、ポインターアドレ
スの２最下位ビットと結合されて、乗算器１１６へ４ビ
ット入力を発生する。乗算器（１１６）への第２の入力
が入力検索文字のハッシュされないビットからなる。

【００９７】乗算器（１１６）は零検出器（１１２）に
よって発生される信号に応答する。零検出器（１１２）
からの１は、ハッシュされない文字ビットを乗算器（１
１６）に通させる。これは、完全ノードがアドレス指定
される場合である。ゼロ検出器（１１２）からの０は、
ポインターアドレスの２最下位ビットと共に２行ビット
を選択する。これは、次のノードが圧縮ノードである場
合である。

【００９８】乗算器（１１６）からの出力は第２の乗算
器（１１７）へ送られる。この乗算器は、ポインター、
圧縮文字のいずれが次に選択されるべきかを選択するの
に使用される。ＡＮＤゲート（１０３）からの出力は乗
算器（１１７）に対する選択された信号として使用され
る。上述の様に、この例ではポインターのみがアドレス
指定されると仮定される。この様にして、乗算器（１１
７）に対する選択入力は０であり、乗算器（１１６）か
らの出力が選択される。

【００９９】接続（１１８）において、最後の２最下位
ポインターアドレスビットが（ＴＮビット及びフェッチ
ストリングワードビットと共に）、ポインターアドレス
のＴＮビットに続く最初の１３アドレスビットと再結合
される。また、この点において、ＴＮビットが（通路圧
縮と関連する他のビットと共に）、１７ビット信号（１
１９）と再結合さる。この信号の部分は端末／ＮＬ検出
論理（１２０）に加えられる。

【０１００】末端／空検出器論理は、次のノードが末端
ノード（即ち、ＴＮ＝１）であることを決める。次のノ
ードが末端ノードである場合、１は、検索が完了される
ことを示す出力（１２０ａ）で発生される。末端ノード
はリーフポインターによって指示されるノードである。
ポインターアドレスが写像された範囲（即ち、００００
−０７ＦＦ）内にある場合、末端論理（１２０）は出力
（１２０ｂ）に出力を発生し、データベースに一致がな
く、検索が完了すべきことを示す。

【０１０１】１７ビット信号が同様に、本例で利用され
ない制御／拡張メモリー（１００）に加えられる。（ブ
ロックＤを見よ）乗算器（１１７）からの出力はポイン
ターアドレスのＴＮビットに続く第１の１３アドレス
（即ち、「中間」の１３ビット）と結合される。上述の
様に、乗算器（１１７）の出力は （ａ）４つ文字ビット〔次の完全ノード〕又は （ｂ）２行ビット及び最後の２最下位アドレスビット
〔次の圧縮されたノード〕からなる。

【０１０２】この１７ビット信号はＡＮＤゲート（１０
３）からの出力と結合され、１８ビット信号（１２２）
を発生する。ゲート（１０３）からの出力は、次のアド
レスがポインターアドレス又は文字列アドレスであるか
を示す。議論した様に、この例では、ゲート（１０３）
は常に０を出力する。この１８ビット信号（１２２）は
文字列／ポインターメモリー（１０８）に加えられる。
この信号は文字列／ポインターメモリー（１０８）内の
次のポインター素子をアドレスするのに使用される。
（ブロックＣを見よ）ハッシュ論理（１１５）からのこ
の２つの列ビット（１１５ａ）は零検出器（１１２）か
らの信号と結合される。そして、ゲート（１０３）は４
ビット信号（１２３）を発生する（ブロックＤ、Ａ、
Ｂ）。この４ビット信号は (1)次のポインターに対する
ハッシュされた列の値、(2) 次のアドレスがポインター
又はストリング（本場合は常にポインター）に対するか
否か、及び(3) 次のノードが１６要素又は４要素を含む
か否かを示す。この信号（１２３）はレジスタ（１２
５）に与えられる。

【０１０３】制御レジスタ（１２５）にクロック信号が
与えられる時、４ビット信号（１２３）はレジスタ（１
２５）を通過すことが許される。ハッシュされる列ビッ
トは、要素（１２５）でレジスタ（１０５）を介してク
ロック入力されるポインターのポインターＩＤビットと
比較される。ビットが一致しない場合、空ポインターが
示され、他の制御ゲートビットが、圧縮されたノードが
アドレス指定されていることを示すと場合に（即ち、信
号が４ノード及びポインターを示す場合）、ＳＴＯＰ信
号がＡＮＤゲート（１２７）で発生される。

【０１０４】図３１−３２が上述の回路の動作を説明し
ている。説明を容易にするため、検索が既に進行してお
り、図３１の時間に文字Ｘ（文字Ｘ）がレジスタ（１０
４）の電流出力であると仮定される。レジスタ（１０
５）の出力、ポインターＸ−１は、文字Ｘがインデック
ス付けされるノードに対するポインターである。このポ
インターは、前の文字及び親ノードによって事前に選択
されており、Ｘ−１とラベルされる。この実施例に対し
ては、ポインターＸ−１は完全ノード内に存在する。レ
ジスタ（１３０）の出力は、ポインターＸ−１が完全ノ
ード内に存在することを示す完全／圧縮されたビット
（Ｆ／ＣＢ．Ｘ−１）及び文字Ｘ−１に対するハッシュ
列ビットを示すハッシュ列ビット（ＨＣＢ．Ｘ−１）を
含む４ビット及びフェッチされたエントリーが文字列又
は列であるか否かを示す文字列／ポインタービットを含
む。

【０１０５】レジスタ（１０４）への入力、文字Ｘ＋１
への入力は、文字Ｘによってインデックス付けされた要
素によって指示されるノードへのインデックスとして使
用される検索文字を表している。レジスタ（１０５）へ
の入力は、文字Ｘ（電流検索文字）及びポインターＸ−
１（文字Ｘによってインデックス付けされるべきノード
を指し示すポインター）に応答して上述の論理によって
発生される。この様にして、レジスタ（１０５）への入
力は文字Ｘ＋１によってインデックス付けされるべきノ
ードのアドレスを表している。

【０１０６】レジスタ（１３０）への入力は、次のポイ
ンター（ポインターＸ）が完全又は圧縮されたノードを
示すか否かを示す完全／圧縮されたビット、Ｆ／ＣＢ．
Ｘを含む４ビットからなる。レジスタへの別の入力は文
字Ｘ、ＨＣＢ．Ｘのハッシュされた列ビットの２ビット
表現である。説明のために、ポインターＸ−１はアドレ
ス付けされる次のノードは圧縮されたノードであること
を示していると仮定する。この様にして、Ｆ／ＣＢ．Ｘ
は、０であり、次のノードが圧縮されたノードであるこ
とを示す。上述された様に、ポインターＸ−１は文字Ｘ
によって検査されるべきノードのノード形態を示す４ビ
ットを含む。この信号に応答して、ノード形態ルックア
ッフ（１１３）及びハッシュ論理（１１４）は、次のサ
イクル内での圧縮に対するレジスタ（１３０）に入力さ
れる文字Ｘのハッシュされた列ビットを発生する。

【０１０７】３つのレジスタがクロック駆動される時、
信号は図１５Ｆに図示される様になる。レジスタ（１０
４）はシステム内へ文字Ｘ＋１をクロック信号と同期し
て入力する。文字Ｘ＋２は次の位置まで移動する。レジ
スタ（１０５）は文字Ｘによってアドレス付けされるポ
インター要素をクック信号と同期して入力する。このポ
インターはラベル付けされたポインターＸである。レジ
スタ（１３０）は文字Ｘのハッシュされた列ビット及び
ポインターＸが圧縮されたノード（Ｆ／ＣＢ．Ｘ）内に
位置することの指示をクロック信号と同期して入力す
る。

【０１０８】レジスタ（１０５）にクロック入力された
ポインターＸは特定の要素に対するポインターＩＤを含
む。同じクロックサイクルにおいて、文字Ｘのハッシュ
された列がレジスタ（１３０）を通してクロック入力さ
れる。この様なビットは比較器（１６０）で比較でき
る。ビットが一致しない場合、検索が終了すべき信号が
発生される。

【０１０９】理解できる様に、ポインターＸは文字Ｘ＋
１よってインデックス付けされるべきノードに対するア
ドレスを、そのノードに対するノード形態とともに、含
む。従って、ハッシング論理を、次のサイクルで圧縮す
るための適当な列ビットを発生するために採用すること
ができる。図３０−３３の回路に周期的にクロック入力
することにより、データベースの検索を実行することが
できる。この検索は、末端／空検出器が末端点を検出す
るまで続行し、ポインターＩＤ／列比較器が一致せず、
パリティーエラーが発生し、検索対象の文字が使い切ら
れるか、文字列不一致が発生する。

【０１１０】図３３は結合された出力入力ブロックを伴
う本発明の上述の実施例を図示している。本発明は４ビ
ット文字及び４要素のみからなる圧縮ノードに分けられ
た検索ワードと関係する間、説明された方法及び装置は
異なる長さの文字列及び異なるサイズの圧縮ノードに作
用する様に適用することができる。

【０１１１】この変換を促進するために、圧縮されたノ
ードサイズは２の冪乗である必要がある。例えば、８つ
の要素の圧縮ノードが必要な場合は、変換マトリックス
は、８行２列である。従って、ポインターＩＤは（列０
又は例１を示す）１ビットに減少されるべきである。２
要素の圧縮されたノードに対する、変換マトリックスは
２行８列である。この様にして、３ビットポインターＩ
Ｄが必要とされる。

【０１１２】変換マトリックスが発展されて、ノード形
態が指定されて、２又は８文字の全ての可能な構成が記
述されることが可能とされるべきである。例えば、２要
素ノードをサポートするためには、４のみの新たな変換
マトリックスが必要とされる。これは、２ビットのみノ
ード形態を有する。各変換マトリックスは、２ノードで
文字の８＊８＝６４の可能な対をカバーする。１２０の
みの可能な２文字の組み合わせ（１６から２の選択、１
６！／（１４！＊２！））があるが、４つの変換マトリ
ックスが、必然的な高い重なりを補償するために必要と
される。

【０１１３】８要素をサポートするために、ノードはよ
り多くの変換マトリックスを必要とする。８要素に対し
て、１２、８７０の可能な文字の組み合わせ（１６から
８の選択、１６！／（８！＊８！））がある。８×２の
変換マトリックスの各々が２＊＊８＝２５６の可能な組
み合わせをカバーする。従って、８つの要素変換表に対
する下限は１２７８０／２５６又は５１である。しかし
ながら、真に直交するマトリックスを発生するが不可能
であるので、７ビットのノード形態に対して必要となる
実際の数は６０−８０の範囲になる。

【０１１４】ハードウエアー又はソフトウエアーの構成
は次に上述の方法を使用して各変換マトリックスに対し
て展開することができる。２つの要素ノード及び８つの
要素ノードは、４ノード及び１６ノードを有する構造へ
の拡張としてのみとして実現できる（即ち、２及び８要
素ノードは１６及び４要素ノードと関連してのみ使用さ
れるべきである）。２及び８要素ノードは一緒に使用さ
れるべきである。８つの要素ノードを２つの要素ノード
なしに使用すること（又これの逆）が、最悪の場合には
何の利益も与えない。

【図面の簡単な説明】

【図１】伝統的なＴＲＩＥ構造化データベースを使用す
るデータベース検索の説明図

【図２】ポインター圧縮を達成するための１６ビットビ
ットマスクを採用するデータベース検索の説明図

【図３】本発明で利用されるノード形態及び関連する変
換マトリックスのリスト

【図４】本発明で利用されるノード形態及び関連する変
換マトリックスのリスト

【図５】本発明で利用されるノード形態及び関連する変
換マトリックスのリスト

【図６】ポインター圧縮のための改良された方法の説明
図

【図７】ＴＲＩＥ構造化されたデータベースを構築する
帰納的方法の説明図

【図８】ノード形態及びポインターＩＤを使用するポイ
ンター圧縮の２つの例を示す図

【図９】ノードメモリを補修する一方法の説明図

【図１０】フリーメモリーの単一リストを使用するノー
ド置き換えの説明図

【図１１】フリーメモリーの単一リストを使用するノー
ド置き換えの説明図

【図１２】本発明の一実施例のブロック図

【図１３】ノード形態、その関連する変換マトリックス
及び各ノード形態に対するハッシングマトリックス

【図１４】ノード形態、その関連する変換マトリックス
及び各ノード形態に対するハッシングマトリックス

【図１５】ノード形態、その関連する変換マトリックス
及び各ノード形態に対するハッシングマトリックス

【図１６】排他的論理和操作及び記号の説明図

【図１７】排他的論理和操作及び記号の説明図

【図１８】ハッシングマトリックスの一つの可能な実施
形態の説明図

【図１９】ハッシングマトリックスの一つの可能な実施
形態の説明図

【図２０】例示的データベースの構築の説明図

【図２１】充填された、未圧縮データベースの説明図

【図２２】ノード形態及びポインターＩＤを使用する圧
縮データベースの説明図

【図２３】例示データベースで達成される例示的検索の
説明図

【図２４】例示データベースで達成される例示的検索の
説明図

【図２５】本発明の一つの可能な実施例のメモリー構成
の説明図

【図２６】実施例で利用されるノードポインターのビッ
ト破壊の説明図

【図２７】実施例で利用されるノードポインターのビッ
ト破壊の説明図

【図２８】実施例で利用されるノードポインターのビッ
ト破壊の説明図

【図２９】実施例で利用されるノードポインターのビッ
ト破壊の説明図

【図３０】本発明の或る実施例のブロック図

【図３１】実施例を通しての信号の流れの説明図

【図３２】実施例を通しての信号の流れの説明図

【図３３】実施例を通しての信号の流れの説明図

─────────────────────────────────────────────────────

【手続補正書】

【提出日】平成５年６月１０日

【手続補正１】

【補正対象書類名】図面

【補正対象項目名】図１

【補正方法】変更

【補正内容】

【図１】

【手続補正２】

【補正対象書類名】図面

【補正対象項目名】図２

【補正方法】変更

【補正内容】

【図２】

【手続補正３】

【補正対象書類名】図面

【補正対象項目名】図３

【補正方法】変更

【補正内容】

【図３】

【手続補正４】

【補正対象書類名】図面

【補正対象項目名】図４

【補正方法】変更

【補正内容】

【図４】

【手続補正５】

【補正対象書類名】図面

【補正対象項目名】図５

【補正方法】変更

【補正内容】

【図５】

【手続補正６】

【補正対象書類名】図面

【補正対象項目名】図６

【補正方法】変更

【補正内容】

【図６】

【手続補正７】

【補正対象書類名】図面

【補正対象項目名】図７

【補正方法】変更

【補正内容】

【図７】

【手続補正８】

【補正対象書類名】図面

【補正対象項目名】図８

【補正方法】変更

【補正内容】

【図８】

【手続補正９】

【補正対象書類名】図面

【補正対象項目名】図９

【補正方法】変更

【補正内容】

【図９】

【手続補正１０】

【補正対象書類名】図面

【補正対象項目名】図１０

【補正方法】変更

【補正内容】

【図１０】

【手続補正１１】

【補正対象書類名】図面

【補正対象項目名】図１１

【補正方法】変更

【補正内容】

【図１１】

【手続補正１２】

【補正対象書類名】図面

【補正対象項目名】図１２

【補正方法】変更

【補正内容】

【図１２】

【手続補正１３】

【補正対象書類名】図面

【補正対象項目名】図１３

【補正方法】変更

【補正内容】

【図１３】

【手続補正１４】

【補正対象書類名】図面

【補正対象項目名】図１４

【補正方法】変更

【補正内容】

【図１４】

【手続補正１５】

【補正対象書類名】図面

【補正対象項目名】図１５

【補正方法】変更

【補正内容】

【図１５】

【手続補正１６】

【補正対象書類名】図面

【補正対象項目名】図１６

【補正方法】変更

【補正内容】

【図１６】

【手続補正１７】

【補正対象書類名】図面

【補正対象項目名】図１８

【補正方法】変更

【補正内容】

【図１８】

【手続補正１８】

【補正対象書類名】図面

【補正対象項目名】図１９

【補正方法】変更

【補正内容】

【図１９】

【手続補正１９】

【補正対象書類名】図面

【補正対象項目名】図２０

【補正方法】変更

【補正内容】

【図２０】

【手続補正２０】

【補正対象書類名】図面

【補正対象項目名】図２１

【補正方法】変更

【補正内容】

【図２１】

【手続補正２１】

【補正対象書類名】図面

【補正対象項目名】図２２

【補正方法】変更

【補正内容】

【図２２】

【手続補正２２】

【補正対象書類名】図面

【補正対象項目名】図２３

【補正方法】変更

【補正内容】

【図２３】

【手続補正２３】

【補正対象書類名】図面

【補正対象項目名】図２４

【補正方法】変更

【補正内容】

【図２４】

【手続補正２４】

【補正対象書類名】図面

【補正対象項目名】図２５

【補正方法】変更

【補正内容】

【図２５】

【手続補正２５】

【補正対象書類名】図面

【補正対象項目名】図３０

【補正方法】変更

【補正内容】

【図３０】

【手続補正２６】

【補正対象書類名】図面

【補正対象項目名】図３１

【補正方法】変更

【補正内容】

【図３１】

【手続補正２７】

【補正対象書類名】図面

【補正対象項目名】図３２

【補正方法】変更

【補正内容】

【図３２】

【手続補正２８】

【補正対象書類名】図面

【補正対象項目名】図３３

【補正方法】変更

【補正内容】

【図３３】

Claims (20)

【特許請求の範囲】
1. 【請求項１】アドレス指定インデックスが検索文字であ
   り、データベース構造に２以上の要素を有する圧縮ノー
   ドをアドレス指定する方法が、 第１の識別コードを圧縮ノードに割り当て、 第２の識別コードをノード内の各要素への割り当て、 第３の識別コードを検索文字へ割り当て、 第４の第１、第２及び第３の識別コードを比較して、ア
   ドレスの一致が見出されたことを知る工程からなる方
   法。
2. 【請求項２】５未満の要素が非空ポインター要素である
   １６のポインター要素を有するＴＲＩＥノードから得ら
   れるデータを記憶する方法が、（ａ） 各ポインター要
   素を一義的な文字と関係付け、（ｂ） 第１の２ビット
   及び第２の２ビットから構成され、各この様なコード内
   の最小の４ビットがビットの一義的な組み合わせである
   別の一義的４ビットコードを各非空ポインター要素と関
   連する文字に割り当て、（ｃ） 非空ポインター要素及
   び４ビットコードの関連する第２のビットをプログラム
   記憶式プロセッサに記憶することからなる方法。
3. 【請求項３】各非空ポインターと関連する文字が異なる
   行に存在する様に構成された１６文字である要素を有す
   る４×４の変換マトリックスを発生する工程を更に含
   み、各４ビットコード内の第１の２ビットが４ビットコ
   ードと関連する文字が表れるマトリックス内の行と対応
   し、最後の２ビットが同じ文字がマトリックス内に表れ
   る列に対応することを特徴とする請求項２記載の方法。
4. 【請求項４】５未満の要素が非空ポインター要素である
   １６のポインター要素を有するＴＲＩＥノードからな
   り、（ａ）各非空ポインター要素を１６の１６進文字と
   関連し、（ｂ）一義的な４ビットコードを各関連する文
   字に割り当て、２つの４ビットコードが同じ第１の２ビ
   ット組み合わせを共有するようにし、（ｃ）非空ポイン
   ター要素を、各４ビットコードの第１の２ビットの２進
   値に従って順序づけ、（ｄ）各非空ポインター要素を、
   関連する１６進文字に割り当てられた４ビットコードの
   第２の２ビットと結合して、圧縮されたポインター要素
   を発生し、（ｅ）工程（ｃ）で達成された順序で圧縮さ
   れたノードに圧縮されたポインター要素を記憶する工程
   からなる方法。
5. 【請求項５】工程（ｂ）が、（ｂ１）各変換マトリック
   スが１６の１６進文字の全てを含む要素を含む４×４マ
   トリックスである様に、一つ以上の変換マトリックスを
   発生し、（ｂ２）非空ポインター要素に割り当てられた
   各１６進文字が異なる行に或る様に発生された変換マト
   リックスの一つを選択し、（ｂ３）４ビットコードを、
   第１の２ビットが行の２進値を表し、第２の２ビットが
   列の２進値を表す様な、１６進文字が見出される選択さ
   れた変換マトリックス内の位置の非空ポインターに割り
   当てられた各１６進文字に４ビットを割り当てる工程か
   らなることを特徴とする請求項４記載の方法。
6. 【請求項６】一義的な識別子が発生された変換マトリッ
   クスの各々に割り当てられ、工程（ｅ）が、（ｅ１）９
   を選択された変換マトリックスに割り当てられる識別子
   と関連付ける工程を含むことを特徴とする請求項５記載
   の方法。
7. 【請求項７】工程（ｂ１）が図３Ａ−３Ｃに図示される
   形態の変換マトリックスを発生することを含む請求項６
   記載の発明。
8. 【請求項８】１５の変換マトリックスが発生されること
   を特徴とする請求項５記載の発明。
9. 【請求項９】発生された変換マトリックスが線形である
   ことを特徴とする請求項５記載の発明。
10. 【請求項１０】（ａ） 各々が、１６の一義的な文字に
    一義的に対応する４つのポインター要素、（ｂ） ４つ
    のポインター要素の一つに各々割り当てられる４つのポ
    インターＩＤを含む圧縮されたＴＲＩＥノードからなる
    メモリーシステム。
11. 【請求項１１】圧縮されたノードが、１６の一義的な文
    字からなる要素を有する４×４の変換マトリックスと関
    連し、（ａ） 圧縮ノード内の各ポインター要素の位置
    が、対応する文字が見出される変換マトリックス内の行
    と関係し、そして、（ｂ） 各ポインターＩＤが、割り
    当てられた要素に対応する文字が見出される列と関係す
    ることを特徴とする請求項１０記載のメモリーシステ
    ム。
12. 【請求項１２】検索文字を使用する請求項１０のメモリ
    ーシステム内の圧縮ノードを検索するための方法であ
    り、この方法が、（ａ） 第１の部分及び第２の部分を
    有する変換アドレスを各検索文字に関連し、（ｂ） 変
    換アドレスの第１の部分を使用して、圧縮ノード内のポ
    インター要素の一つのアドレスを指定し、（ｃ） 変換
    アドレスの第２の位置をアドレスされた要素に割り当て
    られるポインターＩＤと比較し、（ｄ） 変換アドレス
    の第２の部分及びアドレス指定された変換ポインター要
    素に割り当てられたポインターＩＤが一致しない場合検
    索を停止することを含む請求項１０記載の方法。
13. 【請求項１３】検索文字を使用する請求項１０のメモリ
    ーシステム内の圧縮ノードを検索する方法であり、検索
    文字が請求項１０記載の１６の一義的な文字の一つであ
    り、この方法が、（ａ） 検索文字が見出される関連す
    る変換マトリックスの行の２進値を決め、（ｂ） 検索
    文字が見出される関連する変換マトリックスの列の２進
    値を決め、（ｃ） 行の２進値及び列の２進値を結合し
    て、変換アドレスを生成し、変換アドレスの第１部分
    が、行値からなり、第２の部分が列値からなり、（ｄ）
    変換アドレスを検索文字と関連し、（ｅ） 変換アド
    レスの第１の部分を使用して圧縮ノード内のポインター
    要素の一つのアドレス指定を行い、（ｆ） 変換アドレ
    スの第２の部分を、アドレス指定されたポインター要素
    に割り当てられたポインターＩＤと比較し、（ｇ） 変
    換アドレスの第２の部分及びアドレス指定されたポイン
    ター要素に割り当てられたポインターＩＤが一致しない
    場合検索を停止することからなる方法。
14. 【請求項１４】（ａ） 検索されるべき次のノードのア
    ドレスを示す第１の部分、次に検索されるべきノードの
    形態を示す第２の部分、及びポインター識別子からなる
    第３の部分からなるポインタービットフィールドを、ア
    ドレスビットフィールドに応答して発生するためのメモ
    リー手段、（ｂ） ポインターフィールドの第２の部分
    及び検索文字ビットフィールドに応答して、第１及び第
    ２の部分を有する変換アドレスを発生するためのメモリ
    ー手段に結合される論理手段、（ｃ） メモリー手段及
    び論理手段と論理的に結合され、ポインタービットフィ
    ールドの第３の部分及び変換アドレスの第２の部分を比
    較する比較手段からなる計算機化されたデータベース操
    作を達成するための装置。
15. 【請求項１５】入力検索文字及び検索文字を使用して検
    索されるべきノードを表す値を有するビットフィールド
    が与えられたＴＲＩＥ構造化されたデータベース内の圧
    縮されるノードあり、ポインター及びポインター識別子
    を有するノード要素を含む圧縮されるノードを検索する
    ための装置であり、この装置が、（ａ） 検索すべきノ
    ードを表示するビットフィールドに応答して、このノー
    ドに対する変換ビットフィールドを表す第１の論理手
    段、（ｂ） 論理的に第１の論理手段に結合され、変換
    ビットフィールド及び入力検索文字に応答して、検索さ
    れるべきノードの要素のアドレスを示す第１の部分及び
    検索文字に対応する第２の部分からなる変換されたアド
    レスを発生する第２の論理手段、（ｃ） 第２の論理手
    段に論理的に接続され、変換されたアドレスを受信し、
    変換されたアドレスの第１の部分によって示されるノー
    ド要素をアドレス指定を行うアドレス手段、（ｄ） 第
    ２の論理手段及びアドレス手段に論理的に接続され、変
    換されたアドレスを、アドレス指定する手段によってア
    ドレスされるノード要素のポインター識別手段と比較す
    る比較手段からなる装置。
16. 【請求項１６】検索文字及びノードアドレスが与えられ
    た一つ以上の、要素識別子を各々含む要素を有する圧縮
    されたＴＲＩＥノードを有する計算機化されたデータベ
    ースを検索する方法であり、各ＴＲＩＥノードは種々の
    ノード形態の一つである方法が、（ａ） 検索されるべ
    きノード及び検索されるべきノードのノード形態を示す
    ノードアドレスを受信し、（ｂ） このノードアドレス
    で参照されるノードで検索されるべき検索文字を受信
    し、（ｃ） 検索文字及び検索されるべきノードのノー
    ド形態に応答して、第１の部分及び第２の部分からなる
    ハッシュされた値を発生し、（ｄ） 検索されるべきノ
    ードのアドレス及びハッシュされた値の第１の部分も基
    づいて要素アドレスを生成し、（ｅ） 要素アドレスに
    応答してポインター要素を選択し、（ｆ） 選択された
    要素の要素識別子をハッシュされた値の第２の部分と比
    較することからなる方法。
17. 【請求項１７】部分が一致しない場合検索を停止する工
    程（ｇ）を更に含む請求項１６記載の方法。
18. 【請求項１８】特定の検索文字と各々関連する１つ以上
    の要素を有するＴＲＩＥ構造化データベース内の圧縮さ
    れたノードであり、このノードが、（ａ） 圧縮された
    ノードに位置され、その位置が要素と関連する検索文字
    を部分的に決める様にする第１の要素、（ｂ） 要素位
    置と組み合わせ、２進コードが第１の要素に関連する検
    索文字を完全に決める様に第１の要素と関連する２進コ
    ードからなる圧縮されたノード。
19. 【請求項１９】第１の要素が、他のノードに対するポイ
    ンターから成り、２進コードが第１の要素と同じメモリ
    ー位置に記憶される２ビットポインターＩＤからなる請
    求項１８記載の圧縮されたノード。
20. 【請求項２０】５未満の要素が非空ポインター要素であ
    る１６のポインイター要素を有するＴＲＩＥノードを圧
    縮する方法であり、この方法が、（ａ） 各非空ポイン
    ター要素を１６の１６進文字の一つと関連し、（ｂ）
    各変換マトリックスが、要素が１６の１６進文字の全て
    を含む４行４列のマトリックスである様に、１５の線形
    変換マトリックスを発生し、（ｃ） 非空ポインターに
    割り付けられる各１６進文字が異なる行にある様に発生
    された変換マトリックスの一つを選択し、（ｄ） 第１
    の２つのビットが行の２進値を表し、第２の２ビットが
    列の２進値を表す様に、１６進文字が見出される場所の
    選択された変換マトリックス内の位置の非空ポインター
    要素に割り当てる各１６進文字に４ビットコードを割り
    当て、（ｅ） 各４ビットコードの第１の２ビットの２
    進値に従って非空ポインター要素の順番を決め、（ｆ）
    関連される１６進文字に割り当てられる４ビットコー
    ドの第２の２ビットを有する各非空ポインターを関連す
    る１６進文字と結合し、圧縮されたポインター要素を結
    合し、（ｇ） 工程（ｅ）で達成される順番で圧縮され
    たノード内の圧縮されたポインター要素を記憶し、
    （ｈ） 一義的な識別子を発生された変換マトリックス
    の各々に割り当て、選択された変換マトリックスに割り
    当てられる識別子と圧縮されたノードを関連することか
    らなる方法。