【手続補正書】
【提出日】平成19年12月7日(2007.12.7)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
サブツリーインデックスによってアクセスされる複数個のサブツリーエントリと、
第１のサブツリーエントリに記憶される稠密サブツリー記述子とを含み、前記稠密サブツリー記述子は、稠密サブツリーの各葉ごとに値の表示を含み、さらに、
第２のサブツリーエントリに記憶される複数個の疎サブツリー記述子を含み、各疎サブツリー記述子は少なくとも１つのノード記述子を含む、サブツリーの葉のための値を与えるルックアップテーブル。
【請求項２】
前記ノード記述子は、疎サブツリーの一組の葉のための共通値を識別する、請求項１に記載のルックアップテーブル。
【請求項３】
前記稠密サブツリー記述子において「１」にセットされたビットの数に依存して前記稠密サブツリーの葉に対応する値を選択するマッパ論理をさらに含む、請求項１に記載のルックアップテーブル。
【請求項４】
サブツリーエントリに複数個の疎サブツリー記述子を記憶するために設けられたビットの数は、前記稠密サブツリー記述子におけるビットの数に等しい、請求項１に記載のルックアップテーブル。
【請求項５】
前記ノード記述子は、ランレングス符号化を用いて符号化される、請求項１に記載のルックアップテーブル。
【請求項６】
前記ノード記述子におけるビットの数は、サブツリー葉におけるビットの数に１を加えたものに等しい、請求項５に記載のルックアップテーブル。
【請求項７】
複数のサブツリーの葉のための値は、「１」にセットされた最初の最下位ビットの位置に依存して前記ノード記述子に符号化される、請求項６に記載のルックアップテーブル。
【請求項８】
前記ノード記述子におけるビットの数は９であり、前記サブツリー葉におけるビットの数は８である、請求項６に記載のルックアップテーブル。
【請求項９】
前記サブツリー葉によってサーチ可能な連想メモリと、
選択された疎サブツリー記述子において前記ノード記述子を選択し、前記ノード記述子を８ビット符号化値に変換し、前記８ビット符号化値を前記連想メモリに記憶する変換論理とをさらに含む、請求項８に記載のルックアップテーブル。
【請求項１０】
前記ノード記述子は、「１」にセットされた前記最初の最下位ビットの右側の最下位ビットを「ドントケア」にセットし、「１」にセットされた前記最初の最下位ビットを除去することにより変換される、請求項９に記載のルックアップテーブル。
【請求項１１】
サブツリーインデックスによってアクセスされる複数個のサブツリーエントリと、
第１のサブツリーエントリに記憶される稠密サブツリー記述子とを含み、前記稠密サブツリー記述子は、稠密サブツリーの各葉ごとに値の表示を含み、さらに、
第２のサブツリーエントリに複数個の疎サブツリー記述子を記憶するための手段を含み、各疎サブツリー記述子は少なくとも１つのノード記述子を含む、サブツリーの葉のための値を与えるルックアップテーブル。
【請求項１２】
前記ノード記述子は、疎サブツリーの一組の葉のための共通値を識別する、請求項１１に記載のルックアップテーブル。
【請求項１３】
前記稠密サブツリー記述子において「１」にセットされたビットの数に依存して前記稠密サブツリーの葉に対応する値を選択するための手段をさらに含む、請求項１２に記載のルックアップテーブル。
【請求項１４】
サブツリーエントリに複数個の疎サブツリー記述子を記憶するために設けられたビットの数は、前記稠密サブツリー記述子におけるビットの数に等しい、請求項１２に記載のルックアップテーブル。
【請求項１５】
前記ノード記述子は、ランレングス符号化を用いて符号化される、請求項１２に記載のルックアップテーブル。
【請求項１６】
前記ノード記述子におけるビットの数は、サブツリー葉におけるビットの数に１を加えたものに等しい、請求項１５に記載のルックアップテーブル。
【請求項１７】
複数のサブツリーの葉のための値は、「１」にセットされた最初の最下位ビットの位置に依存して前記ノード記述子に符号化される、請求項１６に記載のルックアップテーブル。
【請求項１８】
前記ノード記述子におけるビットの数は９であり、前記サブツリー葉におけるビットの数は８である、請求項１７に記載のルックアップテーブル。
【請求項１９】
前記サブツリー葉によってサーチ可能な連想メモリと、
選択された疎サブツリー記述子において前記ノード記述子を選択し、前記ノード記述子を８ビット符号化値に変換し、前記８ビット符号化値を前記連想メモリに記憶する変換するための手段とをさらに含む、請求項１８に記載のルックアップテーブル。
【請求項２０】
前記ノード記述子は、「１」にセットされた前記最初の最下位ビットの右側の最下位ビットを「ドントケア」にセットし、「１」にセットされた前記最初の最下位ビットを除去することにより変換される、請求項１９に記載のルックアップテーブル。
【請求項２１】
サブツリーインデックスによって複数個のサブツリーエントリにアクセスするステップと、
第１のサブツリーエントリに稠密サブツリー記述子を記憶するステップとを含み、前記稠密サブツリー記述子は、稠密サブツリーの各葉ごとに値の表示を含み、さらに、
第２のサブツリーエントリに複数個の疎サブツリーを記憶するステップを含み、各疎サブツリー記述子は少なくとも１つのノード記述子を含む、ルックアップテーブルに実現されるサブツリーの葉のための値を与えるための方法。
【請求項２２】
前記ノード記述子は、疎サブツリーの一組の葉のための共通値を識別する、請求項２１に記載の方法。
【請求項２３】
前記稠密サブツリー記述子において「１」にセットされたビットの数に依存して前記稠密サブツリーの葉に対応する値を選択するステップをさらに含む、請求項２１に記載の方法。
【請求項２４】
サブツリーエントリに複数個の疎サブツリー記述子を記憶するために設けられたビットの数は、前記稠密サブツリー記述子におけるビットの数に等しい、請求項２１に記載の方法。
【請求項２５】
前記ノード記述子は、ランレングス符号化を用いて符号化される、請求項２１に記載の方法。
【請求項２６】
前記ノード記述子におけるビットの数は、サブツリー葉におけるビットの数に１を加えたものに等しい、請求項２５に記載の方法。
【請求項２７】
複数のサブツリー葉のための値は、「１」にセットされた最初の最下位ビットの位置に依存して前記ノード記述子に符号化される、請求項２６に記載の方法。
【請求項２８】
前記ノード記述子におけるビットの数は９であり、前記サブツリー葉におけるビットの数は８である、請求項２７に記載の方法。
【請求項２９】
前記サブツリー葉によってサーチ可能な連想メモリを設けるステップと、
選択された疎サブツリー記述子において前記ノード記述子を選択するステップと、
前記ノード記述子を８ビット符号化値に変換するステップと、
前記８ビット符号化値を前記連想メモリに記憶するステップとをさらに含む、請求項２８に記載の方法。
【請求項３０】
前記ノード記述子は、「１」にセットされた前記最初の最下位ビットの右側の最下位ビット「ドントケア」にセットし、「１」にセットされた前記最初の最下位ビットを除去することにより変換される、請求項２９に記載の方法。
【請求項３１】
複数レベルルックアップテーブル中のキーに対応するルートをサーチするための方法であって、
サブツリーインデックスによってサブツリーを選択するステップと、
選択されたサブツリーエントリ中の複数個の疎サブツリー記述子のうち１つを選択するステップとを含み、前記疎サブツリー記述子は複数個のノード記述子を含み、さらに
選択された前記疎サブツリー記述子中の前記ノード記述子をマスクされた値に変換するステップと、
前記マスクされた値を最長プレフィックスの順序でメモリにロードするステップと、
前記キーの部分の最長プレフィックス一致を求めて前記メモリをサーチするステップと
、
前記最長プレフィックス一致のアドレスに依存して別のメモリに記憶される前記ルートを選択するステップとを含む、方法。
【請求項３２】
前記メモリは連想メモリである、請求項３１に記載の方法。
【請求項３３】
前記ノード記述子は、疎サブツリーの一組の葉のための共通値を識別する、請求項３２に記載の方法。
【請求項３４】
前記ノード記述子は、ランレングス符号化を用いて符号化される、請求項３３に記載の方法。
【請求項３５】
前記ノード記述子におけるビットの数は、サブツリー葉におけるビットの数に１を加えたものに等しい、請求項３４に記載の方法。
【請求項３６】
複数のサブツリー葉のためのマスクされた値は、「１」にセットされた最初の最下位ビットの位置に依存して前記ノード記述子に符号化される、請求項３５に記載の方法。
【請求項３７】
前記ノード記述子におけるビットの数は９であり、前記マスクされた値におけるビットの数は８である、請求項３６に記載の方法。
【請求項３８】
前記ノード記述子は、「１」にセットされた前記最初の最下位ビットの右側の最下位ビットを「ドントケア」にセットし、「１」にセットされた前記最初の最下位ビットを除去することにより変換される、請求項３７に記載の方法。