回复：压缩算法入门

3.Huffman编码
Huffman编码的思路也非常容易理解，就是采用变长编码，减少高频字符的码长，增加低频字符的码长。
Huffman编码是一种前缀码（即没有任何码字是其他码字的前缀）。与任何字符编码相比，前缀码可以保证达到最优数据压缩率，并简化解码过程。
我们这样构造Huffman编码。将字母表里的所有字符按优先队列的形式组织起来，每次从中取两个最低频的字符并将其组合成一个新的字符（新字符的频率为两者之和），然后再将新字符插入队列中。如此这般，我们便可以构造出编码树。
如果你无法理解，请查阅《算法导论》的6.3节。这里附上了相关证明：

接下来我们来实现一个简单的HuffComp和HuffUnComp。
如果我们要解码一段用Huffman编码压缩的数据，那么我们必须得获取相应的编码树。这里详细讲讲如何存储编码树。
为了节省空间，如果一个字符从来没有出现过，那么我们就不把它放入编码树。
在最前面，我们用一个字节来表示编码树的尺寸，以便定位编码的数据区。此外，我们用一个字节来存储一个结点。其中，最高位表示左孩子是叶结点，次高位表示右孩子是叶结点，低6位表示孩子结点的偏移。
不难发现，这种存储方式由于偏移十分有限，可能无法存储一棵有着256个叶结点的树，所以在这种情况下，我们需要使用16个叶子结点的树。该采用何者由压缩头attr的低4位指定。
基于上述说明，我们可以很容易地写出以下代码：
解压缩函数

压缩函数

服了，涉嫌引流都来了

2.LZ77编码
LZ77编码的思路也非常容易理解，就是如果接下来的这段数据在之前已经出现过了，那么就用“偏移+长度”来表示，从而达到压缩的目的。
程序尝试在Search Buffer中查找与Lookahead Buffer相匹配的最大字符串，并根据匹配的结果决定采用何种编码方式。

这里放一张图片供读者理解。我们不会逐步讲解，不然便显得太过繁冗了。虽说这是入门的文章，但是我们假定你已经知道门在哪里了。如果你无法理解，网络上有很多给出细致例子及讲解的博客。
接下来我们来实现一个简单的LZ77Comp和LZ77UnComp。
那么我们自然要用一个标志位来指示是直接写一个字节还是用上述的表示方法来表示已出现数据。
但是，直接简单粗暴地写一个bit无疑破坏了跟在它后面的字节的完整性，这使得后续的操作会变得非常麻烦。怎么避免这种情况呢？我们不妨把8个标志位放在一起组成一个字节，一组一组地处理，这样就方便多了。
我们用一个u16来表示“偏移+长度”，并用大端序存储。在大端序下，高4位用来表示长度，低12位用来表示偏移。同样的，我们要求使用这种表示法的数据的最小长度为3。
基于上述说明，我们可以很容易地写出以下代码：
解压缩函数

压缩函数

恭喜！你已经完成了这三种算法的具体实现！
但是还有件事，正如我们在一开始就提到的，为什么要采用这种实现方式呢？答案是：本文采用的实现方式便是GBA BIOS中提供的实现方式。让我们来看看吧：



（反汇编代码来源：BATGBA v2.25b）
这段LZ77在最后处理return的时候有问题，会导致越界读写（虽说GBA没有内存管理，也没什么越界的概念），但是问题不大，因为一般都是写进EWRAM的缓冲区和VRAM，多写点也没啥影响。
现在，赶紧试着去抽取GBA里的图片吧！

EOF