snappy是google开源的压缩算法实现，通过测试表明snappy拥有极高的性能表现，但google并没有发表相关论文，可以认为snappy是一个工业算法。snappy借鉴了LZ77的思路，LZ77的匹配过程时间复杂度过高，google对其做了许多优化。在讲snappy之前，我先简单说明LZ77的基本思想。
LZ77
假设我们有一个数列\(S=[9,8,2,3,4,5,6,2,3,4]\)，我们发现子数列\(S_{2,4}=[2,3,4]\)与\(S_{7,9}=[2,3,4]\)是相同的，则我们可以将该数列编码为\(S=[9,8,2,3,4,5,6,(2,3)]\)，2表示开始位置，3表示位数。解码时，我们将该元组替换为子数列\(S_{2,2+3-1}\)，即\(S_{2,4}\)。
完整的描述是，对于数列\(S\)，编码时，当发现子数列\(S_{i,j}\)与\(S_{m,n}\)相同，则可将\(S_{m,n}\)替换为元组\((i,j-i+1)\)；解码时，则将元组\((i,n)\)替换为子数列\(S_{i,i+n-1}\)。
对于匹配相同子数列的过程，即使用模式串去查找匹配串的过程。假设数列\(S\)，\(n\)为数列长度，\(i\)为模式串开始位置，\(w\)为模式串固定大小，也称为窗口大小。\(j=i+w+1\)为匹配串开始位置，最大匹配长度为\(b\)，即我们要用\(S_{i,i+w}\)去匹配\(S_{j,j+b}\)。时间复杂度大概为\(O(n*w*b)\)。
Snappy
为了直观，我先简单说明Snappy的编码和解码的核心过程，然后在其基础上分析其优化点。
编码
对于数组\(S\)，匹配串开始位置为\(j\)，\(j\)将以一定步长\(s\)增长，我们把找过的\(j\)存于数组\(T\)中，而模式串开始位置\(i\)必须\(T\)中获取，我们不限定模式串和匹配串的最大长度，而是限定它们的最小长度为\(m=4\)，并直到无法匹配为止，假设最终匹配长度为\(l\)，则\(S_{i,i+l}\)与\(S_{j,j+l}\)匹配。我们将\(S_{j,j+l}\)编码为一个三元组，在数组中将用三个位置去表示它，具体参数见下面的说明。
匹配过程为：
- \(j = j + s\)
- \(T = T + j\)，把\(j\)放入数组\(T\)
- \(i = T_u\)，从\(T\)中获取\(i\)，\(u\)暂且为随机数
- 若\(S_{i,i+l}==S_{j,j+l}, \; l>m\) 则认为两个子串相匹配
找到一个匹配后需要对其编码，假设把编码结果放在数组\(D\)中，其上一次编码后的位置为\(d\)，而模式串上一次最后匹配位置为\(v\)，
（1）编码模式串
\[ \begin{aligned} &D_{d}=tag0 \\ &D_{d+1}=i-v+1 \\ &D_{d+2,:}=S_{v,i} \\ &d=d+2+(i-v+1) \end{aligned} \]
编码后的第一个数是编码标记\(tag0\)，是一个指定数值，用于解码时进行辨识；第二个数是模式串长度；第三个数开始是模式串的拷贝，\(D_{d+2,:}\)中的结束位以\(:\)表示省略，因为长度可由\(S_{v,i}\)确定。这是对不需要压缩的数据，即模式串，进行一个简单拷贝，我们也把该数据称为literal。
（2）编码匹配串
\[ \begin{aligned} &D_{d}=tag1 \\ &D_{d+1}=j-i \\ &D_{d+1}=l \\ &d=d+3 \\ &v=i+l \end{aligned} \]
用3个数表示，\(tag1\)是编码标记，是一个指定数值，\(j-i\)是模式串相对于匹配串的位移，\(l\)为匹配长度
编码完成后，重复匹配过程，直到数组末尾。
解码
对于数组\(S\)，将其解码至\(D\)，对\(S\)解码的上次最后位置位\(i\)，而\(D\)的最后位置是\(j\)，
若\(S_i=tag0\)，解码模式串，
\[ \begin{aligned} &l=S_{i} \\ &D_{j,:}=S_{i+1,i+1+l} \\ &j=j+l \\ &i=i+1+l \end{aligned} \]
若\(S_i=tag1\)，解码匹配串，
\[ \begin{aligned} &o=S_{i+1} \\ &l=S_{i+2} \\ &D_{j,j+l}=D_{j-o,:} \\ &j=j+l \\ &i=i+2 \end{aligned} \]
优化
上面的说明主要为了快速展现算法核心，其实省略了很多工程上的问题，google为其增加了很多优化点，但并没有特地写论文来为这些优化点提供数学支持。
编码位
在实际使用中，我们的数组将是一个常见的uint8数组，即每个元素为1个字节大小。当我们发现模式串与匹配串至少有连续4个相同字节时，我们就会进行编码，替换为3个整数的标记，但一个32位整数就要占4个字节，意味着，最少对4个字节的数据进行编码时，却要花费3*4=12个字节的空间。所以我们会根据这三个整数或两个整数的数值大小，通过位运算对其压缩，确保至少不会比4个字节更大。
比如我们在编码模式串(Literal)时，当匹配长度\(l<60\)，则\(S_{d}=l<<2|tag0\)，用高位两位表示\(l\)，用低位两位表示\(tag0\)，相当于把两个32位整数压成了一个8位整数。解码时，\(s=S_{i}\&3\)取出后两位，若\(s=tag0\)，则\(l=S_{i}>>2\)取前两位，即可得到模式串的长度。
对于编码位压缩的更多种情况，snappy设计了4种tag来区分，这里不再赘述，具体可参考源码。
哈希查找
前面编码时说到，会把找过的匹配串位置放入数组\(T\)中，之后的模式串位置会从\(T\)中获取\(i = T_u\)，之前说\(u\)是随机数，但这里应该是要通过hash函数获得的值，并且为了减少重复查找同一个匹配位，获取过的位置会被替换位新的匹配位。假设hash函数为\(H\)，则
- \(j = jn\)
- \(jn = j + s\) 预先计算下一个匹配串位置
- \(i = T_u\)
- \(T = T + j\)
- \(u = H(jn)\) 计算下一次模式串位置
- 若\(S_{i,i+l}==S_{j,j+l}, \; l>m\) 则认为两个子串相匹配
通过hash来增加随机性，因为是根据匹配串位置来计算的哈希值，所以确保同一数据进行多次编码可以得到相同的结果。同时，当发现可编码数据后，会一次往\(T\)中插入两次匹配串位置，以增加碰撞几率。
步长
匹配位移动会根据步长\(s\)移动，步长一开始是1，每比较\(2^5=32\)次模式串和匹配串，步长\(s\)加1。当\(s=k\)时，在没有匹配成功的情况下，匹配位移动32次后实际移动了\(2^{4+k}\)位，随着\(k\)增大，总移动位数为\(\sum_1^k 2^{4+k}\)。
对于长度为\(n\)的数组，可得
\[ \large n = argmax_k \sum_1^k 2^{4+k} \]
\(k\)每加一，比较32次，每次比较4字节，所以在没有发现可编码数据时，时间复杂度为\(O(32*k*4)\)
Comments