LZ77持有在未压缩数据流出现过的数据的单一拷贝，并且将重复出现的的同样数据替换成对这一份数据的引用，以 实现数据压缩的目的。
匹配 每一个匹配都被编码成(length, distance)对，即长度为length的字符串中的每个字符与相同字符在未压缩的位置相差distance个字符。:question:
滑动窗口 编码器追踪指定数量的最近数据，数量为2KB， 4KB 或 32KB。
pseudocode
while input is not empty do
prefix := longest prefix of input that begins in window
if prefix exists then
i := distance to start of prefix
l := length of prefix
c := char following prefix in input
else
i := 0
l := 0
c := first char of input
end if
output (i, l, c)
s := pop l+1 chars from front of input
discard l+1 chars from front of window
append s to back of window
repeat压缩算法
字符串解析成长度不超过指定长度$L_s$的子串或者单词，编码框架将其映射为固定长度$L_c$的唯一可解密的编码。
二者之间的关系为：$L_c = 1 + \lceil log(n - L_s) \rceil + \lceil logL_s \rceil$(1)，其中对数的基底是字符集A的基$Card(A) = \alpha$
概念和定义
字符集：A = {0, 1, $\cdots$ , $\alpha$ - 1}
字符串长度：$l(S) = k$， 表示k元有序对$S = s_1s_2\cdots s_k$
子串：$S(i, j)$，当$i \leq j$时，$S(i, j) = s_is_{i+1}\cdots s_j$，当$i \gt j$时，$S(i, j) = NULL$
字符串结合：$S = QR$ ，且$l(S) = l(Q) + l(R)$
(真)前缀：$S(1, j)$叫做字符串S的前缀，如果$j \lt l(S)$，那么$S(1, j)$叫做真前缀。$0 \leq j \leq l(S)$
给定真前缀$S(1, j)$和整数$i \leq j$， $L(i)$ 表示满足$l \leq l(S) - j$的最大非负整数：$S(i, i + l - 1) = S(j + 1, j + l)$，并且让p是$S(1, j)$是其中一个位置满足$L(p) = max_{1\leq i \leq j}\{L(i)\}$
那么，子串$S(j+1, j+L(p))$就被称为字符串S中$S(1, j)$的可重现延伸
现在，为了描述编码过程，令$S = s_1s_2\cdots$表示源发出的字符串。S的序列化编码使得S解析成连续的源单词，$S=S_1S_2\cdots$，并且为每个$S_i$赋值一个编码$C_i$。对于有界延迟编码(bounded-delay encoding)，每个$S_i$的长度$l_i$最多等于已确定的参数$L_s$，而每个编码$C_i$的长度为固定长度$L_c$。
为了初始化编码过程，我们假定源的输出S前的字符串Z是$n - L_s$个零，并且我们将$B_1 = ZS(1, L_s)$存储在buffer中。如果$S(1, j)$是字符串$ZS(1, L_s - 1)$中$Z$的可重现延伸，那么$S_1 = S(1, j+1)$以及$l_1 = j + 1$。为了确定下一个源词，我们把前$l_1$个符号从缓存中移出，并且填入下$l_1$个S的符号得到字符串$B_2 = B_1(l_1+1, n)S(L_s+1, L_s+l_1)$。现在我们寻找$B_2(1, n-1)$中$B_2(1, n-L_s)$的可重现延伸E。并且令$S_2 = Es$，此处$s$是在$B_2$中紧接E的符号。总之，如果$B_i$表示buffer中的n个源符号的字符串当我们准备好确定第$ith$个源词$S_i$，连续的编码步骤可以形式化表达如下：
以上完整地描述了编码过程。很容易验证由(2)定义的解析法则在每次迭代中确保了一个有界，正的源词长度。实际上，$1 \leq l_i \leq L_s$对于每个$i$都成立，因此考虑到$l_i - 1$和来自于A的$（\lceil log（L_s)\rceil$个字符的$radix-\alpha$表示。因为$1 \leq p_i \leq n -L_s$对于每个$i$都成立，表示$p_i-1$和来自A的$\lceil log(n - L_s)\rceil$个字符是可能的。
解码过程只要将编码过程逆过来即可。我们采用长度为$n - L_s$的buffer来存储最近的解码字符。最开始，buffer中填充$n-L_s$个零字符。如果$D_i = d_1d_2\cdots d_{n-L_s}$表示buffer中的内容在$C_{i-1}$已经被解码成$S_i - 1$，然后
$，S_{i-1} = D_i(n - L_s - l_{i-1} + 1， n - L_s),\quad l_{i-1} = l(s_{i-1})$
同时，$D_{i+1}$可以根据$D_i$和$C_i$获取，具体方式如下：
可以根据第一个$\lceil log(n - L_s)\rceil$和$C_i$的下$\lceil logL_s\rceil$个字符确定$p_i - 1$和$l_i - 1$。然后，在填充$p_i$到$n-L_s$的同时进行$l_i-1$次位移操作。第一次移位操作会将缓存内容由$D_i$变成：
$D_{i}^{(1)} = d_2d_3\cdots d_{n-L_s}d_{p_i}= d_{1}^{(1)}d_{2}^{(1)}\cdots d_{n-L_s}^{(1)}$
类似地，如果$j \lt l(S_i - 1)$，第j个移位将$D_{i}^{(j-1)} = d_1^{(j-1)}d_2^{(j-1)}\cdots d_{n-L_s}^{(j-1)}$转换为$D_{i}^{(j)} = d_1^{(j)}d_2^{(j)}\cdots d_{n-L_s}^{(j)}$，完成$l_i - 1$次移位操作之后，再移位一次，把$C_i$的最后一个字符移入buffer的位置$n-L_s$。很容易验证buffer在最后的$l_i = l(S_i)$个位置上包含$S_i$。
$\alpha = 3$
$S = 001010210210212021021200\cdots$
$L_s = 9$
$n = 18$
根据(1)得到$L_c = 1 + log_{3}(18 - 9) + log_{3}9 = 5$
最开始buffer填充$n - L_s = 9$个零值，紧接着是S的前$L_s = 9$个字符，即 $$ B_1 = \underbrace{000000000}_{n - L_s = 9} + \underbrace{001010210}_{L_s = 9} $$
为了确定第一个源词$S_1$，我们必须找到$B_1(10, 17) = 00101021$的最长前缀$B_1(10, 9+l_1-1)$。匹配$B_1$中起始位置$p_1 \leq 9$的子串然后设$S_1 = B_1(10, 9+l_1)$。易得$S_1 = 001,\ l_1 = 3$。指针$p_1$可以是1-9之间的任何一个数。令$p_1 = 9$。以3为基数的$p_1 - 1 = 8$两位数表示为$C_{11} = 22$，$C_{12} = 02$，$C_{i3}$是$S_i$的最后一个字符，即$C_{13} = 1$。由此得出$C_1 = 22021$。
为了得到buffer内容$B_2$，将前$l_1 = 3$个字符移出并填入下3个字符$S(10, 12) = 210$。第2，3和4步的细节展示如下： $$ B_2 = 000000000\overset{\downarrow}{0}1010210, \quad C_2 = 21102 \\ B_3 = 000010\overset{\downarrow}{1}02102102120, \quad C_3 = 20212\\ B_4 = 21\overset{\downarrow}{0}210212021021200, \quad C_4 = 02220 $$