基于小对象的SMAZ 压缩算法

基于小对象的压缩算法。一个叫做 Smaz 的项目，https://github.com/antirez/smaz 目前应用在redis数据库上面。与传统的压缩算法不同的是，Smaz更适合小对象的压缩，比如几个字节到几十个字节不等。除开字典的硬编码部分，压缩过程和解压过程加起来120行代码，非常的短小精罕，却有不俗的表现。平均测试能够达到40%～50%左右的压缩效果。当然，代码在某些方面不是完美的，也不健壮，但是很实用。 antirez坚持追求高速度而放弃部分的安全性。一些相关讨论，请看

http://news.ycombinator.com/item?id=540048

 Smaz的核心代码只有两部分：

1. 字典的设计
2. Hash函数

字典方面，Smaz 采用了硬编码的方式，antirez应该是对大量的相关语料进行统计，分析，进而得出最常用的字符组合

C++代码

1. static char *Smaz_rcb[254] = {
2. “ ”, ”the”, ”e”, ”t”, ”a”, ”of”, ”o”, ”and”, ”i”, ”n”, ”s”, ”e ”, ”r”, ” th”,
3. “ t”, ”in”, ”he”, ”th”, ”h”, ”he ”, ”to”, ”", ”l”, ”s ”, ”d”, ” a”, ”an”,
4. “er”, ”c”, ” o”, ”d ”, ”on”, ” of”, ”re”, ”of ”, ”t ”, ”, ”, ”is”, ”u”, ”at”,
5. “ ”, ”n ”, ”or”, ”which”, ”f”, ”m”, ”as”, ”it”, ”that”, ”n”, ”was”, ”en”,
6. “ ”, ” w”, ”es”, ” an”, ” i”, ”r”, ”f ”, ”g”, ”p”, ”nd”, ” s”, ”nd ”, ”ed ”,
7. “w”, ”ed”, ”http://”, ”for”, ”te”, ”ing”, ”y ”, ”The”, ” c”, ”ti”, ”r ”, ”his”,
8. “st”, ” in”, ”ar”, ”nt”, ”,”, ” to”, ”y”, ”ng”, ” h”, ”with”, ”le”, ”al”, ”to ”,
9. “b”, ”ou”, ”be”, ”were”, ” b”, ”se”, ”o ”, ”ent”, ”ha”, ”ng ”, ”their”, ”"”,
10. “hi”, ”from”, ” f”, ”in ”, ”de”, ”ion”, ”me”, ”v”, ”.”, ”ve”, ”all”, ”re ”,
11. “ri”, ”ro”, ”is ”, ”co”, ”f t”, ”are”, ”ea”, ”. ”, ”her”, ” m”, ”er ”, ” p”,
12. “es ”, ”by”, ”they”, ”di”, ”ra”, ”ic”, ”not”, ”s, ”, ”d t”, ”at ”, ”ce”, ”la”,
13. “h ”, ”ne”, ”as ”, ”tio”, ”on ”, ”n t”, ”io”, ”we”, ” a ”, ”om”, ”, a”, ”s o”,
14. “ur”, ”li”, ”ll”, ”ch”, ”had”, ”this”, ”e t”, ”g ”, ”e”, ” wh”, ”ere”,
15. “ co”, ”e o”, ”a ”, ”us”, ” d”, ”ss”, ”n”, ”r”, ”=”", ” be”, ” e”,
16. “s a”, ”ma”, ”one”, ”t t”, ”or ”, ”but”, ”el”, ”so”, ”l ”, ”e s”, ”s,”, ”no”,
17. “ter”, ” wa”, ”iv”, ”ho”, ”e a”, ” r”, ”hat”, ”s t”, ”ns”, ”ch ”, ”wh”, ”tr”,
18. “ut”, ”/”, ”have”, ”ly ”, ”ta”, ” ha”, ” on”, ”tha”, ”-”, ” l”, ”ati”, ”en ”,
19. “pe”, ” re”, ”there”, ”ass”, ”si”, ” fo”, ”wa”, ”ec”, ”our”, ”who”, ”its”, ”z”,
20. “fo”, ”rs”, ”>”, ”ot”, ”un”, ”<”, ”im”, ”th ”, ”nc”, ”ate”, ”><”, ”ver”, ”ad”,
21. “ we”, ”ly”, ”ee”, ” n”, ”id”, ” cl”, ”ac”, ”il”, ”</”, ”rt”, ” wi”, ”div”,
22. “e, ”, ” it”, ”whi”, ” ma”, ”ge”, ”x”, ”e c”, ”men”, ”.com”
23. };

然后将这些字符串尽可能的均匀分散到每一个slot中，提高查询的速度，Hash的设计看起来很简单

C++代码

1. h1 = h2 = in[0]<<3;
2. if (inlen > 1) h2 += in[1];
3. if (inlen > 2) h3 = h2^in[2];

不过要弄清楚里面的原理可不容易，你可以看一下解码用的字典，每一个组合的分布是非常的均匀的，说明 Hash的效果理想

C++代码

1. static char *Smaz_cb[241] = {
2. “�02s,266″,
3. “�03had232�02leW”,
4. “�03on 216″,
5. “”,
6. “�01yS”,
7. “�02ma255�02li227″,
8. “�03or 260″,
9. “”,
10. “�02ll230�03s t277″,
11. “�04fromg�02mel”,
12. “”,
13. “�03its332″,
14. “�01z333″,
15. “�03ingF”,
16. “�01>336″,
17. “�01 �00�03   (�02nc344″,
18. “�02nd=�03 on312″,
19. “�02ne213�03hat276�03re q”,
20. “”,
21. “�03, a224″
22. };

引用 Marc Lehmann 的一句话：”… the hashing function might seem strange, just believe me, it works ! ” Hash的设计应该是与统计分析的结果相关的，而且h1与h2等存在一定的独立性。举个假设，先处理h1，看字典的分布状态，再接着处理h2，让字 典的分布更趋于均匀，h3类推等等。这样就可以得到很好的效果。当然，很多细微的技术不是一下子就能领悟出来的，设计的精妙在于过程，而不是成果

应用到redis中

小对象的压缩有什么好处？

好处是明显的，应用场合也有很多，传统的数据压缩算法解决不了所有问题，例如集群环境下的socket通信以及千万级别的持久服务，并发处理数十万的客户链接，如果每次通信携带的数据长度是是50bytes左右。

(10*100000*50/1024/1024)*50% M/s = 20M/s

这个数据对于提升机房紧张的带宽资源是相当可观的。

这个还好，redis改进后的lzf算法更诡异