稀疏编码目前最常用的字符编码方式

香农范诺编码原理

霍夫曼（Huffman）编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。

同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。

生成霍夫曼编码算法基于一种称为“编码树”（coding tree）的技术。

算法步骤如下： （1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。

（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。

（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。

（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。

以下这个简单例子说明了这一过程。

1)．字母A,B,C,D,E已被编码，相应的出现概率如下： p(A)=0.16, p(B)=0.51, p(C)=0.09, p(D)=0.13, p(E)=0.11 2)．C和E概率最小，被排在第一棵二叉树中作为树叶。

它们的根节点CE的组合概率为0.20。

从CE到C的一边被标记为1，从CE到E的一边被标记为0。

这种标记是强制性的。

所以，不同的哈夫曼编码可能由相同的数据产生。

3)．各节点相应的概率如下： p(A)=0.16, p(B)=0.51, p(CE)=0.20, p(D)=0.13 D和A两个节点的概率最小。

这两个节点作为叶子组合成一棵新的二叉树。

根节点AD的组合概率为0.29。

由AD到A的一边标记为1，由AD到D的一边标记为0。

如果不同的二叉树的根节点有相同的概率，那么具有从根到节点最短的最大路径的二叉树应先生成。

这样能保持编码的长度基本稳定。

4)．剩下节点的概率如下： p(AD)=0.29, p(B)=0.51, p(CE)=0.20 AD和CE两节点的概率最小。

它们生成一棵二叉树。

其根节点ADCE的组合概率为0.49。

由ADCE到AD一边标记为0，由ADCE到CE的一边标记为1。

5)．剩下两个节点相应的概率如下： p(ADCE)=0.49, p(B)=0.51 它们生成最后一棵根节点为ADCEB的二叉树。

由ADCEB到B的一边记为1，由ADCEB到ADCE的一边记为0。

6)．图03-02-2为霍夫曼编码。

编码结果被存放在一个表中： w(A)=001, w(B)=1, w(C)=011, w(D)=000, w(E)=010 图03-02-2 霍夫曼编码例 霍夫曼编码器的编码过程可用例子演示和解释。

下面是另一个霍夫曼编码例子。

假定要编码的文本是： "EXAMPLE OF HUFFMAN CODE" 首先，计算文本中符号出现的概率（表03-02-2）。

表03-02-2 符号在文本中出现的概率 符号 概率 E 2/25 X 1/25 A 2/25 M 2/25 P 1/25 L 1/25 O 2/25 F 2/25 H 1/25 U 1/25 C 1/25 D 1/25 I 1/25 N 2/25 G 1/25 空格 3/25 最后得到图03-02-3所示的编码树。

图03-02-3 霍夫曼编码树 在霍夫曼编码理论的基础上发展了一些改进的编码算法。

其中一种称为自适应霍夫曼编码（Adaptive Huffman code）。

这种方案能够根据符号概率的变化动态地改变码词，产生的代码比原始霍夫曼编码更有效。

另一种称为扩展的霍夫曼编码（Extended Huffman code）允许编码符号组而不是单个符号。

同香农-范诺编码一样，霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。

这是因为这两种方法都自含同步码，在编码之后的码串中都不需要另外添加标记符号，即在译码时分割符号的特殊代码。

当然，霍夫曼编码方法的编码效率比香农-范诺编码效率高一些。

采用霍夫曼编码时有两个问题值得注意：①霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。

但如果码串中有错误，那怕仅仅是1位出现错误，也会引起一连串的错误，这种现象称为错误传播(error propagation)。

计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。

②霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。

尽管如此，霍夫曼码还是得到广泛应用。

“稀疏”的意思？

稀疏 词语名称: 稀疏 词语解释: 1.亦作"稀疎"。

2.不稠密。

3.犹言冷落，疏远。

稀 : 稀 xī 事物中间距离远、空隙大，与“密”相对，稀疏。

稀落（lu?）。

稀客。

依稀。

浓度小，含水分多, 疏 shū 去掉阻塞使通畅：疏导。

疏通。

疏浚。

疏解（ji?）。

分散：疏散。

仗义疏财。

事物间距离大

目前最常用的字符编码方式

汉字的常用编码有三种：输入码、机内码、输出码：输入码：汉字输入码的分类: 汉字是一种拼音,象形和会意文字,本身具有十分丰富的音,形,义等内涵.经过许多的中国人多年的潜心研究,形成了种类繁多的汉字输入码,至今为止,已有好几百种汉字输入码的编码方案问世,其中已经得到了广泛使用的也达几十种之多.按照汉字输入的编码元素取材的不同,可将众多的汉字输入码分为如下三类: 1,拼音码:以汉字的汉语拼音为基础,以汉字的汉语拼音或其一定规则的缩写形式为编码元素的汉字输入码统称为拼音码. 2,拼形码:以汉字的形状结构及书写顺序特点为基础,按照一定的规则对汉字进行拆分,从而得到若干具有特定结构特点的形状,然后以这些形状为编码元素"拼形"而成汉字的汉字输入码统称为拼形码. 3,音形码:这是一类兼顾汉语拼音和形状结构两方面特性的输入码,它是为了同时利用拼音码和拼形码两者的优点,一方面降低拼音码的重码率,另一方面减少拼形码需较多学习和记忆的困难程度而设计的.音形码的设计目标是要达到普通用户的要求,重码少,易学,少记,好用.音形码虽然从理论上看很具有吸引力,但在具体设计时尚存在一定的困难.自然码是一种适应而较广的音形码. 4,序号码:这是一类基于国标汉字字符集的某种形式的排列顺序的汉字输入码.将国标汉字字符集以某种方式重新排列以后,以排列的序号为编码元素的编码方案即是汉字的序号码. 常用的有：拼音和五笔两种,教程重点讲述五笔字型汉字输入法. 机内码：在设备和信息处理系统内部存储、处理、传输汉字用的代码。

目前用的机内码是：大陆GB2313-80字符集，GB 代表国标（ Guo Biao），即「国家标准」的简称。

收入汉字6763个，符号715个，总计7478个字符。

GBK字符集，GB2312-80,GB 2312-80 的扩展、延伸,“ K”代表扩展 Kuozhan,收入21003个汉字，882个符号，共计21885个字符。

GB18030字符集GB18030字符集，包含GBK字符集、CJK Ext-A 全部6582个汉字，共计27533个汉字。

台湾BIG-5字符集，中文大五码。

是于1984年由台湾财团法人信息工业策进会和五间软件公司创立，故称大五码。

此五公司为：宏碁 、神通 、佳佳, 零壹 、及大众 。

收入13060个繁体汉字，808个符号，总计13868个字符，目前普遍使用于台湾、香港地区。

也是台湾大多数字体/字型的字数。

输出码：汉字的输出主要是指汉字字形的输出，48 X 48点阵的一个汉字要用 288字节来表示.