最新 | 最热门 | 最高评价

+1  100行代码的压缩前缀树: 50% smaller

Tag: algo | memory | succinct | trie | bitmap
张炎泼(xp) 发于 2021年02月01日 08:00 | 点击: 833 | 展开摘要
这文介绍一个压缩前缀树实现的sorted set(github: succinct.Set), 区区95行代码, 包含了一组完整的功能:

用 前缀树 存储一个排序数组, 去掉指针, 压缩掉50%的空间;
例如在本文的例子中, 存储2.4MB的200万个单词, 只需要1.2MB.

创建: 从key列表创建一个压缩的前缀树;

查询: 支持Has() 操作来查询1个key是否存在;

优化: 通过索引来加速 bitmap 的操作, 将较大的 bitmap 操作优化到O(1)的

查看全文: http://www.udpwork.com/item/17474.html

+0  Trie树和其它数据结构的比较

Tag: Algorithm & Data Structure | Recommended | Trie树 | 比较
四火 发于 2013年12月10日 13:39 | 点击: 2060 | 展开摘要
Trie树,又叫做前缀树或者是字典树,是一种有序的树。从空字符串的根开始,往下遍历到某个节点,确定了对应的字符串,也就是说,任意一个节点的所有子孙都具备相同的前缀。每一棵Trie树都可以被看做是一个简单版的确定有限状态的自动机(DFA,deterministic finite automaton),也就是说,对于一个任意给定的属于该自动机的状态(①)和一个属于该自动机字母表的字符(②),都可以根据给定的转移函数(③)转到下一个状态去。其中:

① 对于Trie树中的每一个节点

查看全文: http://www.udpwork.com/item/11305.html
|<<<1>>>| 一共1页, 2条记录