发明授权
US07099881B2 Method for increasing average storage capacity in a bit-mapped tree-based storage engine by using remappable prefix representations and a run-length encoding scheme that defines multi-length fields to compactly store IP prefixes
有权
通过使用可重映射的前缀表示法增加位映射的基于树的存储引擎中的平均存储容量的方法以及定义多长度字段以紧凑地存储IP前缀的游程长度编码方案
- 专利标题： Method for increasing average storage capacity in a bit-mapped tree-based storage engine by using remappable prefix representations and a run-length encoding scheme that defines multi-length fields to compactly store IP prefixes
- 专利标题（中）： 通过使用可重映射的前缀表示法增加位映射的基于树的存储引擎中的平均存储容量的方法以及定义多长度字段以紧凑地存储IP前缀的游程长度编码方案
-
申请号： US10313416申请日： 2002-12-06
-
公开(公告)号： US07099881B2公开(公告)日： 2006-08-29
- 发明人: Nicholas Julian Richardson , Suresh Rajgopal , Lun Bin Huang
- 申请人： Nicholas Julian Richardson , Suresh Rajgopal , Lun Bin Huang
- 申请人地址： US TX Carrollton
- 专利权人： STMicroelectronics, Inc.
- 当前专利权人： STMicroelectronics, Inc.
- 当前专利权人地址： US TX Carrollton
- 代理商 Lisa K. Jorgenson; William A. Munck
- 主分类号： G06F12/00
- IPC分类号： G06F12/00 ; G06F17/30
摘要：
Sparsely distributed prefixes within a bitmapped multi-bit trie are compressed by one or more of: replacing a single entry table string terminating with a single prefix end node with a parent table entry explicitly encoding a prefix portion; replacing a table with only two end nodes or only an end node and an internal node with a single parent table entry explicitly encoding prefix portions; replacing two end nodes with a single compressed child entry at a table location normally occupied by an internal node and explicitly encoding prefix portions; and replacing a plurality of end nodes with a prefix-only entry located at the table end explicitly encoding portions of a plurality of prefixes. The compressed child entry and the prefix-only entry, if present, are read by default each time the table is searched. Run length encoding allows variable length prefix portions to be encoded.
信息查询
