• / 26
  • 下载费用:20 金币  

高级数据结构Trie3

关 键 词:
高级 数据结构 Trie3
资源描述:
Higher Order Tries • Key = Social Security Number. § 441-12-1135 § 9 decimal digits. • 10-way trie (order 10 trie). 0 1 2 3 4 5 6 7 8 9 Height height = 1. § Strides of 16, 8, and 8 for levels 1, 2, and 3 = only 3 levels. Multibit Trie Example 0 1 0null null0111011 00 0 S =1 S =2 S =1 1 000001 011011 Multibit Tries • Node whose stride is s uses s bits for branching. § Node has 2s children and 2s element/prefix fields. § Prefixes that end at a node are stored in that node. § Short prefixes are expanded to length represented by node. § When root stride is 3, prefixes whose length is 3 are expanded to length 3. § P = 00* expands to P0 = 000* and P1 = 001*. § If Q = 000* already exists P0 is eliminated because Q represents a longer match for any destination. Web Resource • See Web writeup for additional applications of tries. § Prefix search. § Automatic command (or phone number or URL) completion. § LZW compression (longest matching prefix). Web Resource • See Web writeup for alternative node structures for tries. § Array § Chain § Binary search tree § Hash table
展开阅读全文
  麦档网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:高级数据结构Trie3
链接地址:https://www.maidoc.com/p-15695385.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2018-2020 maidoc.com版权所有  文库上传用户QQ群:3303921 

麦档网为“文档C2C模式”,即用户上传的文档所得金币直接给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的金币归上传人(含作者)所有。
备案号:蜀ICP备17040478号-3  
川公网安备:51019002001290号 


收起
展开