level 8
徐一凡_exe
楼主
关于哈夫曼编码的优化（打算写成一片大作）（这不是水贴，而是伪技术贴）
我们都知道，哈夫曼编码是一种很牛的东西，任何一个文件，任何一篇文章，只要用了它，就可以“略微甚至大幅缩小”所需的储存空间。因为这个特性，很多压缩软件在使用自己的方法压缩文件之后，都采用哈夫曼编码保存文件，以“将压缩进行到底”。关于哈夫曼编码的原理和应用，详见此网站：http://www.baidu.com。
从以上网站中可以看到，哈夫曼编码采用各字符在文件中出现的次数来建立一个树，保存文件时，就将各字符替换为“树根到此字符的路径”，顺便把这棵树也保存进文件头，方便解码。
哈夫曼编码就是一种“将等长编码换为变长编码”的编码。（原谅楼主语文素养不高，这句描述的话应该把哈夫曼编码的本质讲清了吧）
现在，楼主举个例子。有一个句子为：
I'm a pig and you're a pig too.I'm a pig so you're a pig.You're a pig because I'm a pig.
通过你的数学的神奇天赋，你会发现——————————————这句话有88个字节！这是多么吉利的数字呀，这句话也一定是一句吉祥的话。
此句话包含了
（为了方便，楼主将大小写一视同仁了，在实际引用中是万万不可的）
9个“I”，
6个“’”，
3个“M”，
19个空格，
8个“A”，
6个“P”，
6个“G”，
1个“N”，（楼主差点忽略了这个字符）
1个“D”，
3个“Y”，
6个“O”，
4个“U”，
3个“R”，
5个“E”，
1个“T”，
3个“.”，（楼主差点忽略了这种字符）
2个“S”，
1个“B”，
1个“C”，
常识告诉我们，每个字符（字节）有8位（二进制），楼主将他们编码为变长的，而不是8位等长的。怎么编呢？出现次数多的字符，比如空格，编的短一点；出现次数少的，比如“C”，就编的长一点，反正空间也占的少。（楼主就是这么懒）
（大家被英语老师骗了，平均出现次数最多的字符不是“E”，而是空格）
（就如Minecraft中生成最多的矿物不是铁矿石，而是圆石，其次是石头，再是基岩，然后才是铁矿石）
（此处应有掌声）
（扯太远了）
正题来了！
谈优化哈夫曼编码！
你可能会说，哈夫曼编码已是“最优编码”了，不可能再优化。
可是信息学总是在不断进步的。
楼主的优化方法其实已经稍稍脱离了“编码”这一东西，和一个独立的压缩算法有些接近了。
前面说过了，哈夫曼编码是一种“将等长编码换为变长编码”的编码，而楼主的编码是一种“将变长编码换为变长编码”的编码。乍一看，好像这编码啥都没做？好吧，解释一下，“哈夫曼编码”是以“字符”为单位进行编码的，而“楼主编码”是以“字符、词语或短句”为单位进行编码的，其它原理与哈夫曼编码无异，都要建一棵树。
单位不同，有一些地方则还需要改变。
假设这两个编码都是以“单位估分”为依据进行建树的，
则以字符为单位的哈夫曼编码的估分公式如下：
估分=该单位在文件中出现的次数
以字符、词语或短句为单位的楼主编码的估分公式如下：
估分=【（该单位在文件中出现的次数-1）*（该单位的长度）+1】*该单位的长度
这是楼主编码最值得称道的地方。
举一个例子，有一个这样的句子：
I'm a pig and you're a pig too.I'm a pig so you're a pig.You're a pig because I'm a pig.
（如果这句子在其他地方出现过，纯属巧合）
此句话包含了以下单位：
“I'm ”，估分为36，
“a pig”，估分为130，
“ and ”，估分为5，
“you're ”，估分为105，
“ too”，估分为4，
“.”，估分为3，
“ so ”，估分为4，
“ because ”，估分为9，
对比可以发现，楼主编码果然比哈夫曼编码有的一拼。怎么编码？编码原则如下：估分高的单位，比如“a pig”，就编的短一点；估分低的，比如“.”，就编的长一点，反正空间也占的少。
虽看看，楼主编码如此简单实用，但是用程序来进行编码，却异常困难，光是用“贪心加枚举”来获取各个单位，就要反复扫描文件，效率远不及哈夫曼编码。
此帖是楼主脑子一抽想出来的，所以没有代码，不妥之处，尽请谅解。
好了，此帖结束，而且这编码也有了名字。
2017年04月09日 07点04分
1
我们都知道，哈夫曼编码是一种很牛的东西，任何一个文件，任何一篇文章，只要用了它，就可以“略微甚至大幅缩小”所需的储存空间。因为这个特性，很多压缩软件在使用自己的方法压缩文件之后，都采用哈夫曼编码保存文件，以“将压缩进行到底”。关于哈夫曼编码的原理和应用，详见此网站：http://www.baidu.com。
从以上网站中可以看到，哈夫曼编码采用各字符在文件中出现的次数来建立一个树，保存文件时，就将各字符替换为“树根到此字符的路径”，顺便把这棵树也保存进文件头，方便解码。
哈夫曼编码就是一种“将等长编码换为变长编码”的编码。（原谅楼主语文素养不高，这句描述的话应该把哈夫曼编码的本质讲清了吧）
现在，楼主举个例子。有一个句子为：
I'm a pig and you're a pig too.I'm a pig so you're a pig.You're a pig because I'm a pig.
通过你的数学的神奇天赋，你会发现——————————————这句话有88个字节！这是多么吉利的数字呀，这句话也一定是一句吉祥的话。
此句话包含了
（为了方便，楼主将大小写一视同仁了，在实际引用中是万万不可的）
9个“I”，
6个“’”，
3个“M”，
19个空格，
8个“A”，
6个“P”，
6个“G”，
1个“N”，（楼主差点忽略了这个字符）
1个“D”，
3个“Y”，
6个“O”，
4个“U”，
3个“R”，
5个“E”，
1个“T”，
3个“.”，（楼主差点忽略了这种字符）
2个“S”，
1个“B”，
1个“C”，
常识告诉我们，每个字符（字节）有8位（二进制），楼主将他们编码为变长的，而不是8位等长的。怎么编呢？出现次数多的字符，比如空格，编的短一点；出现次数少的，比如“C”，就编的长一点，反正空间也占的少。（楼主就是这么懒）
（大家被英语老师骗了，平均出现次数最多的字符不是“E”，而是空格）
（就如Minecraft中生成最多的矿物不是铁矿石，而是圆石，其次是石头，再是基岩，然后才是铁矿石）
（此处应有掌声）
（扯太远了）
正题来了！
谈优化哈夫曼编码！
你可能会说，哈夫曼编码已是“最优编码”了，不可能再优化。
可是信息学总是在不断进步的。
楼主的优化方法其实已经稍稍脱离了“编码”这一东西，和一个独立的压缩算法有些接近了。
前面说过了，哈夫曼编码是一种“将等长编码换为变长编码”的编码，而楼主的编码是一种“将变长编码换为变长编码”的编码。乍一看，好像这编码啥都没做？好吧，解释一下，“哈夫曼编码”是以“字符”为单位进行编码的，而“楼主编码”是以“字符、词语或短句”为单位进行编码的，其它原理与哈夫曼编码无异，都要建一棵树。
单位不同，有一些地方则还需要改变。
假设这两个编码都是以“单位估分”为依据进行建树的，
则以字符为单位的哈夫曼编码的估分公式如下：
估分=该单位在文件中出现的次数
以字符、词语或短句为单位的楼主编码的估分公式如下：
估分=【（该单位在文件中出现的次数-1）*（该单位的长度）+1】*该单位的长度
这是楼主编码最值得称道的地方。
举一个例子，有一个这样的句子：
I'm a pig and you're a pig too.I'm a pig so you're a pig.You're a pig because I'm a pig.
（如果这句子在其他地方出现过，纯属巧合）
此句话包含了以下单位：
“I'm ”，估分为36，
“a pig”，估分为130，
“ and ”，估分为5，
“you're ”，估分为105，
“ too”，估分为4，
“.”，估分为3，
“ so ”，估分为4，
“ because ”，估分为9，
对比可以发现，楼主编码果然比哈夫曼编码有的一拼。怎么编码？编码原则如下：估分高的单位，比如“a pig”，就编的短一点；估分低的，比如“.”，就编的长一点，反正空间也占的少。
虽看看，楼主编码如此简单实用，但是用程序来进行编码，却异常困难，光是用“贪心加枚举”来获取各个单位，就要反复扫描文件，效率远不及哈夫曼编码。
此帖是楼主脑子一抽想出来的，所以没有代码，不妥之处，尽请谅解。
好了，此帖结束，而且这编码也有了名字。
![[滑稽]](/static/emoticons/u6ed1u7a3d.png)
![[真棒]](/static/emoticons/u771fu68d2.png)
毕竟算法学发展这么久了，自己想要搞出别的更好的算法还是有点困难的
![[怒]](/static/emoticons/u6012.png)
