1霍夫曼编码简介
21.1前言1.2霍夫曼编码1.3有效的译码器1.4不等代价的编码法1.5错误更正能力1.7作业1.2.1静态式1.3.1省空间式1.2.2动态式1.3.2省时间式
31.2霍夫曼编码
1.2.1静态式图1.1先编S7和S8图1.2合并图1.1和S6图1.3合并S5和S4给定一符号集为，对应的频率为??
4图1.4最终的霍夫曼树符号码s100s210s3011s4111s5110s60101s701000s801001图1.5建成的码表霍夫曼编码的确反应了常出现的符号所编成的码之长度较短，而不常出现的符号所编成的码之长度较长。
51.2.2动态式给一符号集且其出现的对应频率集为，最佳的霍夫曼树需满足为最小，这里表示的高度。将霍夫曼树上的节点从下层到上层和从左到右依序描扫，可得递增数列，且满足下式(1.1)图1.6二种可能的霍夫曼树(a)(b)
6假设。若读入符号，则会变为4，由图1.7可知和的父亲节点之频率变为6，序列就不具递增性了。图1.7加入符号(a)第一次调动(b)第二次调动图1.8经二次调动后的霍夫曼树先将x4的子树和最右边编号且频率为5的子树对调得到图1.8(a)，接着将x8的子树和x9的子树对调而得到图1.8(b)。在图1.8(b)上加入一个s2，并不会破坏霍夫曼编码的最佳性。
7假设m为尚未出现过的字母个数；令，且k为其在未出现过字母中的顺位，则当时，可用个位元的来表示该字母，否则，用e个位元的来表示该字母。动态式霍夫码的实作令字母集={A,B,C,D,…,Z,!,;}，一开始。假设待编码的讯息为CCHUNG。读入C?由，且因C为第个字母，并满足，所以将C编码成5(=4+1)位元的，即00010。读入C?用位元‘1’编C即可。图1.9处理完符号C后的霍夫曼树(a)起始霍夫曼树(b)处理完符号C后图1.10处理完CC后的霍夫曼树
8图1.12处理完CCHU后的霍夫曼树图1.13处理完CCHUN后的霍夫曼树读入H?，且H为第个字母，又满足，再加上霍夫曼树的0，所以H可编码为000111。读入U?，且U为第个字母，又，所以将U编码成4位元的，加上霍夫曼树的00，得U的码为001010。读入N?N可编成000101101。图1.11处理完CCH后的霍夫曼树
91.3有效的译码器
1.3.1省空间式?图1.4最终的霍夫曼树图1.14建构好的单边成长霍夫曼树令，，为单边成长霍夫曼树的之码。首先令且。根据式子，得到。
10代表第i层的外部节点数，，内部节点数之序列为，储存符号集的阵列可安排为A[0…7]。假设收方收到的位元字符串为‘010’读出位元‘0’，，所以需再读入一个符号。读了‘01’，由可知路径是停在第二层的内部节点。再读入第三个符号‘0’，因为