实现了一个压缩算法，在数据高度压缩的前提下，还可以快速查找 key
最近写了一个算法，可用于 (key,value) 存储，key 当然是 string 类型。
用一个 2.3G 的 url 集合做测试，如果不计 value 占用的空间，key 集合的存储空间可以被压缩70倍！压缩后整个数据结构仅占31M内存！压缩率比 bzip2 还要高。
本质性的不同于： gzip, bzip2 等压缩算法仅仅是压缩而已，无法快速地从压缩数据中查找。
我实现的这个算法能高效地支持对 key 的查找，并且查找的时间复杂度仅与 key 的长度有关，不管数据集合有多大，时间复杂度总是 O(strlen(key))。实际数据：当 key 长度均值为 76 字节时（该 url 集合中所有 url 的平均长度），平均查找时间大约 900 纳秒(笔记本 i7-720M)。
可能有人以为是 bloom filter, MD5 之类投机取巧的实现方式，我付责任的地说：不是，该算法是确定性的。bloom filter/MD5 … 是概率的，并且它们的内存占用还要更多。
如果要让 key 再对应一个 value，并且仍然要以 O(strlen(key)) 的时间复杂度访问 value，需要再多用一点点空间用于索引结构，仍以前面 url 压缩为例，需要在 31M 的基础上多大约 4M 的空间。当然，value 本身占的空间是另外一回事。
有需要该算法的公司或个人，请联系本人
我目前使用huffman压缩和索引，同时对你的方法很感兴趣，求交往。。。
xiaoxia AT xiaoxia.org
[reply]huangguan[/reply]
你的方法可以按 key 实时查询？ huffman 编码好像没有这个能力
又加入了一些优化，对 2.3G url 的压缩率达到了 84 倍！
之前编译选项忘了加 -mpopcnt，加上该选项后，平均查找时间从900纳秒降到了460纳秒
还是服务器的 CPU 快，平均查找时间只有 280纳秒
真想不通为嘛要遮遮掩掩，公开一下多好。
不就一个算法么，算法导论上那么多都公开了。
按描述特点，我猜是树算法。
[reply]lovexyz[/reply]
是基于自动机的算法，虽然很多编译原理、自动机教材上都讲自动机，但我还没看到任何一本书上有讲过这个算法。有一些教授的paper讲到了这个算法，但教授们给出的参考实现都很差，按他们paper中说的性能，比我的实现要差100倍以上，并且用的内存也更多。当然那些教授都很聪明，不过他们主要关注的是理论，我只是理论结合实践……
[reply]lovexyz[/reply]
有个基本算法是： Hopcroft DFA minimization algorithm, 那些教授们的 paper copy-paste 的成分也很大，在所有我能找到的paper中的描述的算法都有一个曾经令我很崩溃的很隐晦的bug，并且是同一个bug！你如果有兴趣的话，可以自己去实现一下，看看需要多少内存，能达到什么性能。还有其它一些 onfly minimization algorithm, 你也可以试着去实现
有兴趣，能学习吗？
babam@sohu.com
实际代码请参考：http://code.google.com/p/febird
[reply]babam[/reply]
可否方便提供一下联系方式啊。
[reply]sulmassoft[/reply]
csdn 站内联系
站内发不了信息啊，你没有关注我，所以我发不了站内信息啊。
可以分享一下代码吗？？想学习一下
代码不开源