(57)【特許請求の範囲】
【請求項１】
保管テーブルを備える木構造データベースにおける順次的プレフィックス検索により、および一定の長さの各検索キーの連続するセグメントを評価することにより、入力された検索キーに応答して出力情報を決定する検索方法であって、
ａ）検索キー・セグメントを評価する少なくとも１つのステップにおいて、前記セグメントの選択されたビットは、そのセグメントに関連した保管テスト値のテーブルにアクセスするための圧縮インデックスとして使用され、
ｂ）前記圧縮インデックスによってアクセスされた前記テスト値は、前記評価された検索キー・セグメントの少なくとも残りの部分と比較され、前記比較結果が肯定的である場合に前記検索方法を継続し、または、前記比較結果が否定的である場合に前記検索方法を終了し、
更に、評価された検索キー・セグメントから、圧縮インデックスを構成するビットを選択するインデックス・マスクを生成するために、
ｃ）個別検索キー・セグメントにおいて発生可能であり、前記指示されたテーブル内に保管された前記テスト値に対応し、そこからビットが選択される全ての有効な２つのインデックス値を対としてＸＯＲ積を生成するステップと、
ｄ）複数ビットからなる各暫定インデックス・マスクにおいて単一のビットが１であるビット列から始め、１のビットの数が増加するビット列に移り、そこからビットが選択される前記検索キー・セグメントにおけるビットの数と等しい総数のビットを各々含む暫定インデックス・マスクを順次的に作成するステップと、
ｅ）前記作成された暫定インデックス・マスクの各々に関して、前記個別暫定インデックス・マスクとステップ（ｃ）においてあらかじめ生成された前記ＸＯＲ積の全てとの間のビット単位ＡＮＤ積を連続して生成するステップと、
ｆ）暫定インデックス・マスクに関して生成された前記ＡＮＤ積の各々が、少なくとも１つの１ビットを含む場合には前記ステップ（ｃ）〜（ｅ）を終了し、前記個別検索キー・セグメントに対する最適のインデックス・マスクとして前記個別暫定インデックス・マスクを保管するステップとを含む検索方法。
【請求項２】
前記個別検索キー・セグメントにおいて発生可能であり、各々がｋビットを含む全ての有効な２つのインデックス値を対としてＸＯＲ積を生成する時に、ステップ（ａ）の間に、
前記可能なＸＯＲ積の１つへ各々割り当てられた２ｋビット位置を備えるＸＯＲ積ビット・ベクトルを与え、全ての生成されたＸＯＲ積がステップ（ｅ）における前記ＡＮＤ積の生成まで保存される必要があるわけではないように、１つのＸＯＲ積の生成の後に、前記ＸＯＲビット・ベクトルにおける前記個別ビット位置を１にセットする付加的なサブステップを含む請求項１に記載の方法。
【請求項３】
新しい有効なテスト値および対応するインデックス値を挿入する必要がある場合に、検索データ構造を更新するために、全ての有効なインデックス値に基づき、関連した各インデックス・マスクを新たに計算し、前記新しいインデックス・マスクを組み込むステップを含む請求項１に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＩＰアドレスのような一定の検索キーに応答して、その検索キーを有するアイテムの更なる処理または転送を判断するための保管テーブル（ｓｔｏｒｅｄ  ｔａｂｌｅ）内のエントリを検出する分野に関し、特に、本発明は、保管テーブルの圧縮と、一定の検索キーにマッチングするテーブル内のエントリに対する検索の最適化とに関する。
【０００２】
【従来の技術】
最長マッチング・プレフィックス（Ｌｏｎｇｅｓｔ  ｍａｔｃｈｉｎｇ  ｐｒｅｆｉｘ：ＬＰＭ）検索が広く用いられ、特に、割り当てられたＩＰアドレスに従ってインターネット内でパケットを経路指定するために用いられている。多くのソリューションが、保管プレフィックス（ｓｔｏｒｅｄ  ｐｒｅｆｉｘ）に対して先行検索キー・ビット（プレフィックス）を比較し、保管データ構造（ｓｔｏｒｅｄ  ｄａｔａ  ｓｔｒｕｃｔｕｒｅ）におけるその関連した出力ルート情報（またはネクスト・ホップ・ポインタ）と共に最長マッチング・プレフィックスを検出するために提案されてきた。特に、探索木は、最長マッチング・プレフィックス検索にアプリケーションを提供してきた。
【０００３】
非常に簡単なＬＰＭ検索スキームは、検索キーのあらゆる可能な値に関する検索結果を含むテーブルへのインデックスとして検索キーを用いることにより構成される。
【０００４】
図１は、そこにおいて検索キーが３２ビットＩＰ宛先アドレスより構成されるＩＰバージョン４転送に適用されたこの方法の例を説明する。この例において、ルーティング・テーブルは、以下のプレフィックスを含む。
【０００５】
【表１】
0003782950.tif 000002
【０００６】
このテーブルは、１つのエントリが３２ビットＩＰ宛先アドレスの各可能な値に割当てられた２32エントリを含む。全ての有効なエントリ（すなわち、有効な検索結果Ａ，Ｂ，ＣまたはＤに帰着し得るエントリ）が、図１に示される。全ての他のエントリが無効とみなされ、無効な検索結果に終わる。エントリは、例えばビット・フラグを用いて有効または無効であると識別され得る。
【０００７】
このＬＰＭスキームの主な不利な点は、大量の記憶域の非効率な使用である。図１が示すように、テーブルは、そこからほんの少数が保管プレフィックスに関連した実情報を有する有効なエントリであるにすぎない２32エントリを含む。他の不利な点は、短いプレフィックスに関連した情報が、複数のテーブル・エントリに保管され、そのプレフィックスの挿入および除去のために複数のメモリ・アクセスを必要とするということである。図１において２12＝４０９６テーブル・エントリ（ＡＢＣＤＥ０００ｈからＡＢＣＤＥＦＦＦｈまで）を範囲とする第４のプレフィックス（ＡＢＣＤＥｈ）がそうである。
【０００８】
これら２つの不利な点は、全体の検索キーによって指示される単一テーブルを、検索キーのより小さい部分によって指示される複数のリンク・テーブルの木のような構造に変換することにより削除可能である。このアプローチは、Ｇｕｐｔａら（“Ｒｏｕｔｉｎｇ  Ｌｏｏｋｕｐｓ  ｉｎ  Ｈａｒｄｗａｒｅ  ａｔ  Ｍｅｍｏｒｙ  Ａｃｃｅｓｓ  Ｓｐｅｅｄｓ．”，Ｐａｎｋａｊ  Ｇｕｐｔａ，Ｓｔｅｖｅｎ  Ｌｉｎ，ａｎｄ  Ｎｉｃｋ  ＭｃＫｅｏｗｎ，ＩＥＥＥ  Ｉｎｆｏｃｏｍ  Ａｐｒｉｌ  １９９８，Ｖｏｌ３，ｐｐ．１２４０−１２４７，ＳａｎＦｒａｎｃｉｓｃｏ）およびＶａｒｇｈｅｓｅら（“Ｆａｓｔ  ａｄｄｒｅｓｓ  ｌｏｏｋｕｐｓ  ｕｓｉｎｇ  ｃｏｎｔｒｏｌｌｅｄ  ｐｒｅｆｉｘ  ｅｘｐａｎｓｉｏｎ．”，Ｖ．Ｓｒｉｎｉｖａｓａｎ  ａｎｄ  Ｇ．Ｖａｒｇｈｅｓｅ，ＡＣＭ  Ｔｒａｎｓ．Ｃｏｍｐｕｔ．Ｓｙｓｔ．１７，１，Ｆｅｂ．１９９９，ｐｐ．１−４０）によって述べられてきた。
【０００９】
図２は、このような概念を図１のデータ構造に応用する例を説明する。図２において、検索キーは、図２に示される対応する３つのレベルでのテーブルを指示するために使用される１６，８および８ビットから構成される３つのセグメントに分けられる。これらのテーブルの各々は、有効および無効なエントリを含むことができ、有効なエントリは、次のレベルでのテーブルに対するポインタあるいは検索結果を含むことができ、無効なエントリは、無効な検索結果を指示する。
【００１０】
検索オペレーションは、レベル１でのテーブルへのインデックスとして第１のセグメントを用いることから開始する。指示されたエントリが次のレベルでのテーブルへのポインタを含む場合には、このテーブルは、次のセグメントを用いて指示され得る。検索オペレーションは、検索オペレーションの結果となり得る検索結果を含むエントリが指示される時、あるいは、その場合に検索オペレーションの結果が無効な結果となり得る無効なエントリが指示される時に終了する。
【００１１】
これを‘１２３４５６７８ｈ’に等しいＩＰ宛先アドレスに関して説明する。図２において、このＩＰ宛先アドレスの第１のセグメントは、レベル１でのテーブルへのインデックスとして使用される‘１２３４ｈ’に等しい。このエントリは、図２におけるレベル２での下位のテーブルをポイントし、下位のテーブルは、‘５６ｈ’に等しいＩＰ宛先アドレスの第２のセグメントによって指示される。このエントリは、図２におけるレベル３でのテーブルだけをポイントし、このテーブルは、‘７８ｈ’に等しいＩＰ宛先アドレスの第３のセグメントを用いて指示される。このエントリは、検索結果‘Ｂ’を与える。他のプレフィックスに関する検索結果は同様な方法で得られる。
【００１２】
図２におけるデータ構造は、レベル１での６５５３６テーブル・エントリ，レベル２での２＊２５６＝５１２テーブル・エントリ，およびレベル３での１＊２５６テーブル・エントリから構成され、図１のデータ構造の２32テーブル・エントリよりはるかに少ない総計６６３０４テーブル・エントリになる。両図におけるエントリは同一ではないかもしれない（例えば、図２におけるエントリは、ポインタまたは検索結果のいずれが保管されているかの指示と共にポインタを保管できることを必要とする）が、図２のデータ構造は、図１のデータ構造よりも明らかにはるかに少ないストレージ要件を有する。さらに、短いプレフィックスに関連した情報は、更新オペレーションのためのより少ないメモリ・アクセスをもたらすより少ないテーブル・エントリに保管される。例えば、ここでは、第４のプレフィックス（ＡＢＣＤＥｈ）は、図１のデータ構造における４０９６エントリに代わってほんの１７テーブル・エントリ（レベル１でのテーブルにおけるＡＢＣＤｈ、およびレベル２での上位のテーブルにおけるＥ０ｈからＥＦｈまで）を範囲とするにすぎない。
【００１３】
図２に示されるスキームは、図１に示されるスキームよりも、単一検索オペレーションのためにより多くのメモリ・アクセスを要求することが可能である。しかしながら、同一のレベルに属する全てのテーブルが、個別の独立してアクセス可能なメモリ・バンクに保管される場合には、パイプライン方式を適用して、時間単位ごとに図２に示されるスキームと同数のルックアップを得ることが可能である。
【００１４】
図２におけるデータ構造の実際のストレージ要件は、ＩＰ宛先アドレス内のセグメントの数およびサイズと、データ構造に保管されたプレフィックスとに依存している。ＭｃＫｅｏｗｎおよびＶａｒｇｈｅｓｅは、固定数の固定サイズ・セグメント（図２に示されるような）を有するスキーム、そして可変数の可変サイズ・セグメントを有するスキームを説明する。後者のタイプのスキームにおいては、セグメント・サイズ情報は、次のレベルでのテーブルへのポインタを含むテーブル・エントリ内部に組み込まれる。この点で、データ構造の異なるパスを選択する異なるＩＰ宛先アドレスのための検索オペレーションは、異なるサイズを有する異なる数のセグメントを含み得る。結果として、同一のレベルでのテーブルのサイズが異なり得る。
【００１５】
可変数の可変サイズ・セグメントを有するスキームは、データ構造のストレージ要件のよりよい最適化を可能にする。しかしながら、更新機能ははるかに複雑であり、特に、インクリメンタル更新のサポートは複雑であり、より多くの時間を消費する。様々なレベルでのテーブルが上述のパイプライン方式を可能にする個別のメモリ・バンクに保管される場合には、可変数の可変サイズ・セグメントを有するスキームのための更新オペレーションは、更新オペレーションがデータ構造の一定のパスに従ってセグメント・サイズを変更する際に、異なるバンク間のデータ移動を伴い得る。これは、現代の多くの検索エンジンにおいてクリティカル・リソースであるメモリ帯域幅のより低効率の使用をもたらし、結果として更新パフォーマンスの低下をもたらす。ストレージ要件を最適化するための他の方法は、米国特許第５７８１７７２号公報（Ｗｉｌｋｉｎｓｏｎら）で説明される。この特許は、ノード内の固定サイズ・セットのポインタに適用される、ポインタ圧縮と称されるメカニズムを説明する。このメカニズムは、‘無効な’ポインタ（ＮＩＬ−ポインタ）がノードから除去されるということ、および各ノードへ加えられかつどのポインタがノード内に存在する（すなわち、非ＮＩＬ−ポインタ）かを指示するビット・マスクを用いて、有効なポインタ（非ＮＩＬ−ポインタ）のロケーションが判断され得るということを含む。同一のメカニズムが、図２に示されるテーブルへ適用可能である。同種の方法が、米国特許第５８１３００１号公報（Ｂｅｎｎｅｔｔ）において説明される。
【００１６】
このタイプの圧縮は、少数のエントリを有するテーブルに対してよく機能し得る。より大きなテーブルは、より大きいストレージ要件と検索オペレーションの際のよりスローな処理時間とをもたらし得るより大きいビット・マスクを必要とする。他の不利な点は、結果テーブルは、２の累乗を必然としない、あらゆるサイズを有し得るということである。これは、バッファ管理をより複雑にし得る。というのは、２の累乗でないバッファ・サイズは、効率的に管理することがより困難だからである。
【００１７】
【発明が解決しようとする課題】
本発明の目的は、一定の検索キーに応答して、保管データ構造においてマッチングするエントリを検出する方法（およびデータ構造）を創出することであり、この方法は、実際に保管されたデータの分散に応答してデータ・テーブルを圧縮することによって改良検索を可能にし、そして、検索オペレーションのための最適化プロシージャを提供する。さらなる目的は、一定の検索キー・セグメントから個別的かつ最適に選択される、テーブル・アクセスのための可変長インデックス値の使用を可能にする検索方法を提供することである。
【００１８】
【課題を解決するための手段】
これらの目的を達成する本発明は、特許請求の範囲で定義される。本発明は、特に、一定の検索キー・セグメントと比較されるべきテスト値の最適に圧縮されたテーブルにアクセスするために、固定長検索キー・セグメントの選択されたあるいはマスクされたビットの使用を提供する。特定の実施の形態において、本発明は、検索キー・セグメントからのビットの選択のための最適のインデックス・マスクを生成する効率的なプロシージャを提供する。さらに特定の実施の形態において、付加的なプレフィックス・マスクが、一定の検索キー・セグメントとの比較のために実際に必要であるテスト値のビットだけを選択するために与えられる。
【００１９】
本発明の主な利点は、より短い検索時間およびストレージ・スペースに対する節約である。さらに、固定長検索キー・セグメントの使用に起因して（実際に使用される可変数の検索キー・ビットにもかかわらず）、保管テーブルの更新が単純化される。可能なインクリメンタル更新は、より低いストレージ要件を生じさせる。さらに、２の累乗のバッファ・サイズの使用に起因して、バッファ管理が単純化され、メモリがより効率的に使用される。
【００２０】
【発明の実施の形態】
以下において、本発明の実施の形態を、図面を参照して説明する。
【００２１】
テーブル圧縮の概念
本発明は、これらのデータ構造内部に生じるそれぞれの個々のテーブルに圧縮を適用することによって図２に示されるデータ構造と同種のデータ構造から派生可能なデータ構造に基づく最長マッチング・プレフィックス検索（ｌｏｎｇｅｓｔ  ｍａｔｃｈｉｎｇ  ｐｒｅｆｉｘ  ｓｅａｒｃｈ）方法を含む。
【００２２】
この圧縮の原理は、図３および図４において説明される。図３は、例証する目的のために１６進数の代わりに２進数インデックス表記を用いて、レベル３での図２に示されたテーブルを再度示す。テーブルを指示するために使用される検索キーの第３のセグメントは、図２および３に示されるように８ビットから構成されるので、個別テーブルは、２8＝２５６エントリを含む。これらのエントリから、ただ３つだけがインデックス‘３４ｈ’，‘７８ｈ’および‘ＣＤｈ’で有効であるにすぎない。図３は、また、図２におけるレベル２でのテーブル内のエントリを示し、エントリは示されるテーブルへのポインタを含み、ポインティング・エントリとして表示される。
【００２３】
図３に示されるテーブルは、図４に示されるようなより小さいテーブルへ圧縮可能であり、より小さいテーブルは、元のテーブルを指示するために使用された検索キー・セグメントを構成するビットのサブセットによって指示される。圧縮テーブルへのインデックスを圧縮インデックスと称する。図４において、圧縮インデックスは、検索キー・セグメント内部の位置０および２におけるビットから構成される。圧縮インデックスを構成するビットは、直前のレベルでのテーブル内のポインティング・エントリに（次のテーブルへのポインタと共に）保管されたいわゆるインデックス・マスクによって指示される。圧縮インデックスがｋビットから構成される場合には、圧縮テーブルは２kエントリを含み得る。その場合には、インデックス・マスクは、‘１’にセットされたｋビットを含み得る。圧縮インデックスは、元のテーブルにおける有効なエントリに対応するどの２つの検索キー・セグメント値（すなわち、元のテーブルにおける有効なエントリのどの２つのインデックス）も同一の圧縮インデックスを生じさせ得ないような方法で、検索キー・セグメントから選択される必要がある。
【００２４】
圧縮インデックスが単に検索キー・セグメントのサブセットである時に、同一の圧縮インデックスを生じる検索キー・セグメントの複数の値が存在する。こういう訳で、圧縮テーブル内の各エントリに保管され、圧縮インデックスの一部でない検索キー・セグメント・ビットの値を指定するテスト値に対するテスト・オペレーションがインデックス・オペレーションに続く。テスト結果が肯定的（すなわち、検索キー・セグメント・ビットがテスト値に等しい）である場合には、検索オペレーションは、指示されたエントリの内容に基づいて継続する。テスト結果が否定的である場合には、検索オペレーションは、まるで無効なエントリが指示されたように終了する。
【００２５】
実施の容易のために、このテスト値は、圧縮インデックス・ビットを含む全体の検索キー・セグメント値から構成されることもできる。図４に示されるテスト値は、そこにおいて圧縮インデックスの一部でなくそれゆえにテストされることが必要なビットがアンダーラインで示される全体の検索キー・セグメント値から構成される。
【００２６】
図５は、そこにおいて説明されたテーブル圧縮がレベル１でのテーブルを除く全てのテーブルに適用される図２のデータ構造を示す。典型的なシステムにおいて、レベル１でのテーブルを指示するために使用される第１のセグメントが、検索パフォーマンス上の理由のために、他のセグメントと比較すると相対的に大きいことがあるということが予期される。相対的に大きい第１のセグメント・サイズは、圧縮バージョンに対してよりスローな更新オペレーションをもたらし得る（更新オペレーションは、以下に述べる）ので、更新パフォーマンス上の理由のために、この第１のテーブルを圧縮されないままにしておくことがより望ましいであろう。
【００２７】
図５は、レベル２での下位のテーブルが、レベル１でのテーブル内の対応するポインティング・エントリにおける‘００ｈ’に等しいインデックス・マスクによって指示されるセグメント値から常に独立して指示され得る（アクセスされ得る）１つの単一エントリを有するテーブルに圧縮されるということを示す。図を分かりやすくしておくために、図５は、様々なテーブルを指示するために使用されるが、それからこれらの圧縮インデックスが構成される実ビットではない圧縮インデックスのサイズ（０ビット／４ビット）だけを示す（これらは、図５において１６進数表記で示されるインデックス・マスクから派生可能である）。
【００２８】
図６は、図５に示されるデータ構造に基づく検索オペレーションの際に実行されなければならない種々のステップを説明するフロー図を示す。
【００２９】
圧縮データ構造の構築および更新
圧縮データ構造を構築し更新する１つの方法は、圧縮されないデータ構造も保持することを伴う。この圧縮されないデータ構造は、従来の方法で構築され更新され得る。構築あるいは更新オペレーションの際に変化する全てのテーブルは、圧縮されない形式で最初に得られ、次に、圧縮データ構造に圧縮され更新され得る。この点で、データ構造の構築および更新の複雑さは、個々のテーブルの圧縮の複雑さに変えられる。
【００３０】
テーブルの圧縮は、以下の２つのステップからなる。
１）圧縮インデックスを引き出すために使用されるインデックス・マスクを決定するステップ。
２）インデックス・マスクおよび元のテーブル内容に基づいて圧縮テーブルを構築するステップ。
【００３１】
第１のステップを以下に説明する。第２のステップは簡単である。
【００３２】
最適のインデックス・マスク生成
最大圧縮は、元のテーブルにおけるどんな２つの有効なエントリも、同一の圧縮インデックス値にマップされないという条件を満たす最小圧縮インデックスで達成される。後者の条件は、２つの有効なインデックスの各可能な対に対して、圧縮インデックスが、そこにおいてこれらのインデックスが異なる検索キー・セグメントからの、少なくとも１つのビットを含む場合に満たされる。
【００３３】
ただ１つの有効なインデックス（テーブル・エントリ）だけが存在する場合に、最適のインデックス・マスクは、全てゼロから構成される（例えば、図５における第２のレベルでの下位のテーブルのために、第１のレベルでのテーブルにおけるポインティング・エントリが、全てゼロから構成されるインデックス・マスクを含む場合がそうである）。複数の有効なインデックス（テーブル・エントリ）の場合には、１にセットされた最小数のビットを有する最適のインデックス・マスクに対応する最小圧縮インデックスは、以下の方法で決定可能である。
【００３４】
１）２つの有効なインデックス（テーブル・エントリ）の各対に対して、そこにおいてそれらが異なるビット位置が決定される。これは、有効なインデックスの各対に対するビット単位ＸＯＲ積を決定することによってなし得る。これらのＸＯＲ積のそれぞれは、そこにおいて対応する２つのインデックスが異なるビット位置での‘１’ビットを含む。
【００３５】
２）次に、全ての可能な非ゼロ・インデックス・マスク（暫定インデックス・マスク）が生成され、１にセットされた増加する数のビットに従ってオーダされる。各可能な（暫定）インデックス・マスクに対して、ビット単位ＡＮＤ積が、第１のステップで決定されたＸＯＲ積のそれぞれを用いて決定される。それに対して全てのこれらのＡＮＤ積が非ゼロであり得る第１の暫定インデックス・マスクは、最適のインデックス・マスクとして選択され得る（インデックス・マスクが、各ＸＯＲ積との非ゼロＡＮＤ積を有する場合には、これは、対応する圧縮インデックスが、そこにおいて有効なインデックス（テーブル・エントリ）の各対が異なる少なくとも１つのビットを含み得るということ、すなわち、そこにおいて可能なインデックス・マスクが生成されるオーダに起因して、上述の条件を満たすことが理解された第１のインデックス・マスクは、最小数の‘１’ビットを含み得るということを意味する）。
【００３６】
この概念は、図３において示された例を用いて説明可能である。この例において、有効なインデックス（テーブル・エントリ）は、
【００３７】
【表２】
0003782950.tif 000003
【００３８】
これらのインデックスのうちの２つの各可能な組み合わせのＸＯＲ積は、
【００３９】
【表３】
0003782950.tif 000004
【００４０】
以下のテーブルは、続けて生成されたインデックス・マスクとこれらのインデックス・マスクのビット単位ＡＮＤ積と上述のＸＯＲ積とを説明する。インデックス・マスク‘０００００１０１ｂ’は、それに対して全てのＡＮＤ積が非ゼロである第１のインデックス・マスクである。このインデックス・マスクは、最適のインデックス・マスクとして選択される（これは、同様に、図４において使用されるインデックス・マスクである）。
【００４１】
【表４】
0003782950.tif 000005
【００４２】
ＸＯＲ積ビット・ベクトル
８ビットに等しいセグメント・サイズに対して、セグメント値（有効なインデックス）の対状ＸＯＲ組み合わせによって生成された異なるＸＯＲ積の最大数は、２５５に等しい（ゼロに等しいＸＯＲ積は不可能である。というのは、これは２つの同一のインデックス間のＸＯＲ積を指示するからである）。有効なインデックス（セグメント値）の数がｎに等しい場合、ＸＯＲ積の数は、（ｎ割る２）に等しくなり得る。ｎ＝２４またはより多くの有効なインデックスに対して、ＸＯＲ積の数は、２５６より大きくなり得る。単に２５５の異なるＸＯＲ積が可能である時、これは、インデックス（セグメント値）の複数の対が同一のＸＯＲ積を生じ得るということを意味する。
【００４３】
この観察に基づいて、本発明は、テーブルまたは他のデータ構造に個別のエントリを格納する代わりに、いわゆるＸＯＲ積ビット・ベクトル内部に、全ての決定されたＸＯＲ積の表現を保管する効率的な方法も含む。ｋビットに等しいセグメント・サイズに対して、ＸＯＲ積ビット・ベクトルは、可能なＸＯＲ積値‘０００００００１ｂ’，‘００００００１０ｂ’，‘００００００１１ｂ’から‘１１１１１１１１ｂ’までに対応する２k−１ビットを含み得る。一定のＸＯＲ積が生成された場合、ビット・ベクトル内の対応するビットがセットされる。図７は、上述の例における３つのＸＯＲ積に対するＸＯＲ積ビット・ベクトルの値を示す。ＸＯＲ積ビット・ベクトルの概念を用いて、全てのＸＯＲ積を決定し、最適のインデックス・マスクを決定するプログラミング言語“Ｃ”での可能な実施例を以下に示す。
【００４４】
【表５】
0003782950.tif 000006
【００４５】
改良圧縮
図５における第２のレベルでの上位のテーブルは、以下のプレフィックスと同一のプレフィックスに全て関連する１６のエントリを含む。
【００４６】
【表６】
0003782950.tif 000007
【００４７】
このテーブルは、例証する目的のために２進数インデックス表記を用いて図８において再度示される。
【００４８】
プレフィックスは、そこから図８に示される圧縮インデックスが引き出される検索キー・セグメントの半分だけを（値Ｅを表す４ビットを用いて）‘範囲とする’。範囲とされないセグメントの最後の部分は４ビットからなる。これが、このプレフィックスに関連した情報を保管するためにレベル２でのテーブルにおける２4＝１６エントリが必要とされる理由である。というのは、これらの最後の４ビットの全ての可能な値は、図２に示された圧縮されないテーブルにおける有効なインデックスをもたらすからである。全てのこれら有効なインデックスは、実際にプレフィックスに関連する唯一の関係のあるビットであり、従って、保管テスト値に対してテストされることを必要とする唯一のビットである同じ最初の４ビットを共用する。
【００４９】
この観察に基づいて、図９は、テスト値のどの部分がセグメント値に対してテストされることを必要とするか指示するためのテスト値を有するいわゆるプレフィックス・マスクを保管することによって、テーブルをさらに圧縮する方法を示す。結果として、セグメントの最後の４ビットの全ての可能な値のための１６の個別のテーブル・エントリの代わりに、ただ１つのテーブル・エントリだけが必要とされる。これは、示される‘００ｈ’に等しいポインティング・エントリ内のインデックス・マスクに対応する。これは、インデックス・マスクの計算が、以下に説明するように、同様に適合されなければならないということを示す。
【００５０】
図１０は、プレフィックス・マスクの概念を、図５に示された例に適用する結果を示す。プレフィックス・マスクは、検索結果を含むテーブル・エントリに必要とされるだけである。次のセグメントからの部分によって指示され得る次のレベルでのテーブルに対するポインタを含むテーブル・エントリに対し、全体の現行のセグメント値がテストされる（これは、最長マッチング・プレフィックス検索の特質である）。図１０における第３のレベルでのテーブル内の３つの有効なエントリは、全体のテスト値が関係あるということを指示するプレフィックス・マスク‘ＦＦｈ’を含む。図１１は、プレフィックス・マスクの概念に適合された、図６に示されるフロー図に基づくフロー図を示す。
【００５１】
改良圧縮のための最適のインデックス・マスクの決定
改良圧縮スキームのための最適のインデックス・マスク生成は、圧縮インデックスを決定するための元のスキームに対する以下の変更を伴う。
【００５２】
１）対応するプレフィックス・マスクによって指示される有効なインデックスの関係のある部分だけが、ＸＯＲ積を決定するために用いられることが望ましい。ＸＯＲ積が、異なるプレフィックスに関連する２つの有効なインデックスに対してゼロに等しい場合には、これは、これら２つのプレフィックスのうちの１つが、他方のプレフィックスのプレフィックスであるということを意味する。この場合において、プレフィックス・マスクのＸＯＲ積は、最適のインデックス・マスクにおいて１にセットされなければならないビットの基本セットを指示する（これを、以下に述べる）。
【００５３】
２）上述のビットの全ての基本セットに対して少なくとも１にセットされたビットを有する非ゼロ・インデックス・マスクだけが生成される。第１のステップにおいて生成された非ゼロＸＯＲ積だけが評価される。残りの手順は同一である。
【００５４】
以下の３つのプレフィックスを有する例を、最適のインデックス・マスクを改良圧縮方法に対してどのように決定できるのか説明するために用いる。
【００５５】
【表７】
0003782950.tif 000008
【００５６】
第１のプレフィックスは、図２に示された圧縮されないデータ構造内に既に存在していた。追加の他の２つのプレフィックスは、ただ、図２における第２のレベルでの上位のテーブルを、図１２に示される圧縮されないテーブルに変化させ得るだけである。この例において、第１のプレフィックスは、第２のプレフィックスのプレフィックスである。
【００５７】
検索キー・セグメントの関係のあるビット、従って図１２における有効なインデックスの関係のあるビットは、以下のプレフィックス・マスクによって３つのプレフィックスに対して表される。
【００５８】
【表８】
0003782950.tif 000009
【００５９】
対応するプレフィックス・マスクによって指示されるこれらの有効なインデックスの関係のあるビット間のＸＯＲ積は、
【００６０】
【表９】
0003782950.tif 000010
【００６１】
第１のＸＯＲ積は、プレフィックスのプレフィックスを指示するゼロに等しい。それから、これらの有効なインデックスｆおよびｇに対応する２つのプレフィックス・マスク１１１１００００ｂおよび１１１１１１００ｂのＸＯＲ積を取ると、００００１１００ｂの結果になる。第２のステップにおいて、このＸＯＲ積と同じ位置で１にセットされたビットを有するインデックス・マスクだけが生成される。これは、以下のテーブルに示される。
【００６２】
【表１０】
0003782950.tif 000011
【００６３】
両方の非ゼロＸＯＲ積に対して非ゼロ・ビット単位ＡＮＤ積をもたらす第１のインデックス・マスクは、０１００１１００ｂ（ステップ６）である。これは、図１３において用いられる最適のインデックス・マスクである。
【００６４】
プログラミング言語“Ｃ”での元の実施例は、ここに述べられる圧縮インデックス生成を実行するための以下の方法に変更され得る。
【００６５】
【表１１】
0003782950.tif 000012
【００６６】
まとめとして、本発明の構成に関して以下の事項を開示する。
（１）保管テーブルを備える木構造データベースにおける順次的プレフィックス検索により、および一定の長さの各検索キーの連続するセグメントを評価することにより、前記入力検索キーに応答して出力情報を決定する方法であって、ａ）検索キー・セグメントを評価する少なくとも１つのステップにおいて、前記セグメントの選択されたビットは、そのセグメントに関連した保管テスト値のテーブルにアクセスするための圧縮インデックスとして使用され、ｂ）前記圧縮インデックスによってアクセスされた前記テスト値は、前記評価された検索キー・セグメントの少なくとも残りの部分と比較され、前記比較結果は、さらにいっそうの処理または前記検索プロシージャの結果を決定する方法。
（２）圧縮インデックスを決定するための前記検索キーのセグメントの前記ビットの選択は、事前記憶インデックス・マスクを用いるマスキング・オペレーションによって行われる上記（１）に記載の方法。
（３）前記事前記憶インデックス・マスクは、前記選択されたセグメント・ビットによって指示され、かつ前記個別テスト値を含むテーブルへのポインタをさらに含むテーブル・エントリから得られる上記（２）に記載の方法。
（４）評価された検索キー・セグメントから、圧縮インデックスを構成するビットを選択するインデックス・マスクを生成するために、ａ）前記個別検索キー・セグメントにおいて発生可能であり、前記指示されたテーブル内に保管された前記テスト値に対応し、そこからビットが選択される全ての有効なインデックス値から対状ＸＯＲ積を生成するステップと、ｂ）各暫定インデックス・マスクにおける単一の１ビットから始め、前記暫定インデックス・マスクにおける増加する多数の１ビットに移り、そこからビットが選択される前記検索キー・セグメントにおけるビットの数と等しい総数のビットを各々含む暫定インデックス・マスクを順次的に作成するステップと、ｃ）前記作成された暫定インデックス・マスクの各々に関して、前記個別暫定インデックス・マスクとステップ（ａ）においてあらかじめ生成された前記ＸＯＲ積の全てとの間のビット単位ＡＮＤ積を連続して生成するステップと、ｄ）暫定インデックス・マスクに関して生成された前記ＡＮＤ積の各々が、少なくとも１つの１ビットを含む場合には、前記プロシージャを終了し、前記個別検索キー・セグメントに対する最適のインデックス・マスクとして前記個別暫定インデックス・マスクを保管するステップとを含む上記（１）または（２）に記載の方法。
（５）前記個別検索キー・セグメントにおいて発生可能であり、各々がｋビットを含む全ての有効なインデックス値に対して対状ＸＯＲ積を生成する時に、ステップ（ａ）の間に、前記可能なＸＯＲ積の１つへ各々割り当てられた２kビット位置を備えるＸＯＲ積ビット・ベクトルを与え、全ての生成されたＸＯＲ積がステップ（ｃ）における前記ＡＮＤ積の生成まで保存される必要があるわけではないように、特定ＸＯＲ積の生成の後に、前記ＸＯＲビット・ベクトルにおける前記個別ビット位置を１にセットする付加的なサブステップを含む上記（４）に記載の方法。
（６）新しい有効なテスト値および対応するインデックス値を挿入する必要がある場合に、前記検索データ構造を更新するために、全ての有効なインデックス値に基づき請求項４に従って、関連した各インデックス・マスクを新たに計算し、前記新しいインデックス・マスクを組み込むステップを含む上記（１）または（２）に記載の方法。
（７）プレフィックス・マスクが、少なくとも１つの特定テスト値と共にテーブル内に付加的に保管され、個別エントリが圧縮インデックスによってアクセスされる時に、前記プレフィックス・マスクによって選択された前記個別テスト値のビットだけが前記評価された検索キー・セグメントと比較され、従って、ビットの共通サブグループを含むいくつかの有効なテスト値に対して、プレフィックス・マスクを有する１つのテスト値だけが保管されることを必要とし、縮小圧縮インデックス値が使用可能である上記（１）または（２）に記載の方法。
（８）保管テーブルを備えるデータ構造における順次的なプレフィックス検索により、および一定の長さの各検索キーの連続するセグメントを評価することにより、前記入力検索キーに応答して出力情報を決定するためのデータ構造であって、評価される少なくとも１つの検索キー・セグメントと、ａ）前記関連した検索キー・セグメントからビット位置を選択して圧縮インデックスを得るための保管インデックス・マスクと、ｂ）前記関連した検索キー・セグメントの現行値と比較されるテスト値を含むノード・テーブルとを備え、前記ノード・テーブルは、前記保管テスト値の１つを得るために、前記保管インデックス・マスクで選択された前記圧縮インデックス・ビットによってアクセスされるデータ構造。
（９）固有の識別を可能にするため、および前記個別セグメントに関連した全ての可能な有効なテスト値を含む前記関連したテーブルに含まれた各テスト値のアクセスのために、検索キー・セグメントから最小数のビットを、前記インデックス・マスクが選択するように設計された上記（８）に記載のデータ構造。
【図面の簡単な説明】
【図１】フル検索キーを用いる１ステップ・フル検索手順を示す図である。
【図２】フル・ルックアップ・テーブルを用いるセグメント化検索手順を説明する図である。
【図３】テーブルへのインデックスとして検索キー・セグメントを使用する部分検索を示す図である。
【図４】圧縮ルックアップ・テーブルを用いる本発明、および圧縮テーブルにアクセスするための圧縮インデックスとしての検索キー・セグメントの選択されたビットの使用法の基本的な説明であり、また、ビット選択のためのインデックス・マスクを示す。
【図５】検索のいくつかの選択された段階において、インデックス・マスクおよび圧縮インデックスを用いるマルチレベル最長マッチング・プレフィックス検索を示す図である。
【図６】図５に示される構成における検索手順のフロー図である。
【図７】ストレージ・スペースおよび最適のインデックス・マスクの生成の際の処理時間を節約するために使用可能なＸＯＲ積ビット・ベクトルを説明する図である。
【図８】共通部分を有する保管テスト値にアクセスするための圧縮インデックスを用いる例を示す図である。
【図９】同一の部分を有するテスト値の場合において、ストレージ・スペースおよび検索時間を節約するための、図８の例に対するプレフィックス・マスクの使用を説明する図である。
【図１０】ビット・マスクによって生成された圧縮インデックスを用い、補足的にプレフィックス・マスクを用いる、圧縮テーブルにおける段階的な検索を説明する図である。
【図１１】図１０に示される構成における検索手順のフロー図である。
【図１２】改良圧縮を可能にするインデックス値間の関係を用いる圧縮されないテーブルを示す図である。
【図１３】改良圧縮方法に起因する、図１２の例に対する圧縮検索テーブルを説明する図である。
【図１】
0003782950.tif 000013
【図２】
0003782950.tif 000014
【図３】
0003782950.tif 000015
【図４】
0003782950.tif 000016
【図５】
0003782950.tif 000017
【図６】
0003782950.tif 000018
【図７】
0003782950.tif 000019
【図８】
0003782950.tif 000020
【図９】
0003782950.tif 000021
【図１０】
0003782950.tif 000022
【図１１】
0003782950.tif 000023
【図１２】
0003782950.tif 000024
【図１３】
0003782950.tif 000025