adaptive huffman

自适应哈夫曼编码（Adaptive Huffman）是一种动态建立哈夫曼编码的方法。传统的哈夫曼编码需要事先知道所有的字符及其频率，然后根据频率建立编码树。而自适应哈夫曼编码则在实际编码过程中，通过动态更新编码树来适应输入字符的变化。

自适应哈夫曼编码的主要特点是在编码过程中，不需要显式地提供字符频率的信息，而是通过根据实际输入的字符进行动态调整。在编码开始时，初始化一个初始编码树，该树包含一个特殊的权重更新节点。当输入一个字符时，首先检查该字符是否已经在编码树中存在，如果存在则直接输出该字符对应的编码，如果不存在则输出该字符的编码，并更新编码树。

更新编码树的过程分为两步。首先，根据当前输入的字符，遍历编码树找到对应的叶子节点。然后从该叶子节点开始向树根方向，逐级更新父节点的权重和位置，直到根节点。在更新过程中，为了保证编码树的平衡性，还需要处理可能出现的过度增长现象，即当某个权重达到一定阈值时，需要进行权重更新节点的旋转操作。

通过不断动态更新编码树，自适应哈夫曼编码能够提供更好的压缩效果。因为它能够更好地适应输入字符的分布，对出现频率较高的字符使用较短的编码，对出现频率较低的字符使用较长的编码。这样在编码过程中，相对常用的字符可以使用较少的比特表示，从而实现更高的压缩率。

总结来说，自适应哈夫曼编码是一种动态建立编码树的方法，能够根据实际输入的字符进行调整，并以较短的编码表示高频率的字符，以较长的编码表示低频率的字符，从而实现更好的压缩效果。