数学建模社区-数学中国

标题: huffman 树的问题 [打印本页]
作者: hnrjeff    时间: 2009-9-5 15:18
标题: huffman 树的问题
到底huffman树是怎么样的，具体的应用呢
作者: wen1055    时间: 2009-9-5 16:34
信息论里面有个哈夫曼编码，就是概率小的码元编的码长，概率小的编的码小~~最终目标是使平均码长最短~从而提高传输效率~
作者: liuyaliss    时间: 2009-9-6 15:03
对文件进行压缩编码
作者: liuyaliss    时间: 2009-9-6 15:10
哈夫曼树的应用
$ w; Z, V/ N! d9 r8 Z) i$ d/ \* \哈夫曼树的应用十分广泛，在不同的应用中，对叶子结点的权和带权路径长度有不同的解释。% q+ G/ z$ C9 [+ b7 S
5 \! C6 }/ ?! z+ V
哈夫曼树的应用之一是用于优化判断过程，利用哈夫曼树得到最佳判定算法。例如，将百分制转换成五级制的算法。显然，此算法很简单，只需利用if语句描述即可。
+ o* v) J- p4 [! @) g, f0 T, H, A5 u$ X" Q  h
if ( x<60)( c% |2 x. K) @& j( @* M4 E& q
: B- w% r) y  ?  B$ T% A# }' K
     score=’不及格’;
# Z7 `0 _% @% g8 G3 C) q7 F  j) J, a1 }: l0 c
else if ( x<70)
9 W$ Z+ g% a2 ^$ Q+ l4 ?
4 H3 r+ q" m9 D4 F( U4 Z     score=’及格’;' C% X+ H- u8 F. O" s- J1 R) e
# x5 ]4 K3 t' t- G$ Y! W# Q
else if ( x<80)1 X8 |% P4 X8 \( `0 v; ?

6 t9 Y! A' U- _. [/ g     score=’中’;/ ~9 R/ J7 U. N( n+ B5 R* w

) p0 @1 R( h; D1 \. Telse if ( x<90)- n( s0 u& V' X
. L) {3 H+ F0 w
     score=’良’;
8 L5 s9 Z& k: g4 k% A
3 A# k+ L' Y: qelse
: h5 Z6 ?3 C* K* i+ |* j0 Z1 V/ J& j& u* O4 p; \2 P
     score=’优’;
2 L9 i4 U4 z% Y" x+ O. {
& a  \+ a4 V$ e8 I6 T; u- w4 e此判定过程可以用图6.33(a)的判定树来表示。如果学生规模很大，该算法需反复多次执行，就应该考虑算法执行的时间问题。在实际应用中，学生的成绩呈正态分布，大部分在70~89分之间，优秀和不及格的概率较小。假设不及格、及格、中、良、优的百分比为5％、12%、40%、35%、8%，则上述算法80%以上的成绩需要进行三次或三次以上的比较才能得到结果。若以这些百分比值5,12,40,35,8为权值，使用哈夫曼算法来构造一棵判定树，则得到图6.33(b)所示的判定过程，可使多数成绩经过较少的比较即可得到结果。但由于每个判定框都有两次比较，将两次比较分开，得到如图6.33(c)所示的判定树，按此判定树构造程序，显然可以大大减少比较次数。5 R" f5 i9 d4 s( z" A+ L
# ~5 A+ ^6 A* F/ ~6 h" L" q
                x                                      x " w( q8 Y1 H8 ?; Y

7 O* x# u! l0 \/ S" r
! ~/ c& a: f8 p" H! Y7 \* E' Q+ ~  {! b' }4 R! {# _

5 M2 Z' j& m: d; X# H$ P( ~, T  R
% Y4 ^. L; c8 S0 g& C; z' ~+ [4 |             x<60                                 70≤x<800 T; f3 X, q# G  H6 T3 t+ k0 K

. a. E8 y1 W8 F6 Z# v1 P          Y         N                          Y           N
$ Z4 n% O7 T0 T  u1 N/ a4 T9 x4 |0 ?( _4 D* y/ P* ]
     不及格        x<70                       中         80≤x<90
5 C- x- T6 i: a& h$ n' B/ j  f* J2 U5 h; K9 J2 b. I
               Y         N                           Y            N
! M) x; T8 t+ c. ]  K2 F7 B) Q+ y0 c  ]
$ T3 t) T! z. O- i  r% y% A0 U           及格         x<80                         良        60≤x<706 k; C% F' [: g; @1 w2 N

/ g; g. n1 k- ~% J0 l3 _                    Y         N                             Y          N
* }8 i% B1 X: }3 N# }1 |
( c) f8 X, j9 V1 e! ], {8 a                 中          x<90                          x<60      及格/ i0 {6 Y# Q6 S$ z0 h
/ ?3 L8 ]0 _  [7 m0 \+ x% _9 W4 V
                         Y         N                 Y         N  
) p+ N  C' _. K3 u3 }
) b! [. t# i* ?' T& J0 L                      良           优             不及格        优" F. k0 Z4 b, T( W

9 W3 N  a1 Z# V% g6 L) A(a)                                                                                                                   (b)
) i& @0 @5 x; P
- d. X: P* |! c, X  n, c                x7 ]7 E6 a+ i$ ]' x: H
/ ]' {+ x4 R; X% \( Y

  ?1 d: n  X0 ?: p9 s( j- o2 m4 K( a& u
              x<80$ I: |& M" M8 D5 J4 ~* r3 d2 u

4 O& H% i3 I! O# w       Y
8 K2 F3 ^8 T5 A  M, l# f+ `8 F9 _
    x<70                x<90
4 |3 t+ x6 X' `' A( w; @" j5 B
/ W! D3 |# s0 Y' S4 z  ~5 x3 {Y         N        Y          N. ]. ~3 [) s! P5 j0 E

( L4 b% t7 t( {! ]( h                       x<60         中       良          优) V5 p6 ]6 x3 T1 J& K2 ?
; t3 c3 `4 j& V0 }
                   Y         N
0 t5 f* j4 u/ E1 j+ Y1 N) L, ?" m. E# N! s
                不及格       及格
' X3 _1 M  Q# {' U; X
" j: P0 U+ J0 J  m           （c）1 s% d6 \" v! v: t: D9 s3 q7 i! _

3 j) J. k4 F+ |4 S" @                       图6.33 百分制转换五级制的判定过程
6 S& q4 `" y) ]! p: D, S; g' d# o3 S' S1 u8 b( J0 A) Q, B/ ?+ W

# o/ u/ N+ e# d) Y3 K/ L
# m8 s* W! l) u( Y0 d$ V& F哈夫曼树在通信、编码和数据压缩等技术领域也有着广泛的应用。下面我们介绍哈夫曼树在数据编码中的应用，即数据的最小冗余编码问题。- B3 G1 r, F, _# E

% a3 f$ ?4 k, [5 ~" j在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“AFTER  DATA  EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符，则固定编码长度为5。然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。但这样长短不等的编码又会产生一个新问题，即如何解译成原文？除非设计时能够保证任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀，符合此要求的编码称为前缀编码。
0 {! O6 r# i% ~! D9 Y
! w; l, r! k" ~1 T8 ]/ }! O为使不等长编码为前缀编码，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于求出了传送报文的最短长度。因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。
; }. y8 a  o+ Z! c) n) T& k
$ G$ G) K; @- H+ B# G% Y我们用上述各字母出现的次数{8，4，5，3，1，1}作为权构造哈夫曼树，如图6.36所示。约定左分支表示字符“0”，右分支表示字符“1”，则可以从根结点到叶子结点的路径的分支上的字符组成的字符串作为该叶子对应字符的编码。可以证明，如此得到的必为二进制前缀编码，而且是一种最优前缀编码。我们称这样的树为哈夫曼编码树，由此得到的编码称为哈夫曼编码。本例中字母A、E、R、T、F、D的哈夫曼编码分别为11、00、01、011、0100、0101。可以看出，出现次数较多的字母A、E、R，具有最短的编码，长度均为2；而出现次数最少的字母F、D，具有最长的编码，长度均为4。报文的最短传送长度为：   
/ _7 _/ @7 ?) E: P2 M" o$ r, n
: D, v' ?2 E% J. q) [& _' T& i       6
: g7 U, D/ e! E4 f3 z0 P% E- S; J3 t
. n( ^  i$ [1 u   L=WPL=S(wklk)=4×2+5×2+8×2+3×3+1×4+1×4=51
" D2 }! g8 [9 R$ [5 P# s3 q) [4 ^2 u7 ~' j
          k=1
6 k' s1 U+ L$ S) S) p0 q2 ]) ~6 u; a8 \# M# J
若采用等长编码，报文的传送长度为
9 D5 d; [% q  i3 X, I, [- x
" k9 g# K% c4 _6 vL=8×3+4×3+5×3+3×3+1×3+1×3=66
% k8 }: ~1 F: ]0 _( I0 j( K# |3 {: |) c" `2 C2 V! V+ J1 w
显然，哈夫曼编码比等长编码所得到的报文长度要短得多。哈夫曼编码是最优前缀编码。" g! }5 d; g2 ^& E" I: b* d

& n5 ^! R& C: d" c+ c! K
* o( v* k% i, L
7 o3 M, e5 v  ~0 J$ q+ `                          22
' c9 L) @4 ?8 B
0 ?# L* F/ [, j/ x. B0 O                        0     16 y4 W1 U! q  v
0 n9 u" Z, o3 c8 S  e
9                         13; Z7 Q4 K, l/ k7 }0 b
* X! ~7 H% s% _( ]2 }3 A1 i
                        0     1   0     1
8 u" X2 q! U9 ~  l+ I% ]) i2 W0 X4 i" \  X8 e/ D" @
                       4      5   5      8
4 ]6 Y+ c. q: a1 s) I0 O
. R, t. Y: ^$ _4 [$ R                      E    0    1  R     A
$ @" p- u, l6 O- O% j4 a
7 H  W5 L/ v3 i; K3 p) X2      3, c: T: q5 ]% N5 ^
6 W* [* h2 s! C5 }( d- u  {) y
                        0    1   T
; v% M& i8 z  ]( z# C2 D9 M& J6 o) B7 V+ l  R! L6 c. j6 z1 \
                      1      1! q  z% F$ O+ Q

4 U3 Y0 J/ f. `/ |                  F      D6 ^+ Z4 x1 s/ L4 [( x2 U

' S- N- a( X4 i9 Q  k$ m( `+ i9 e图6. 36   哈夫曼编码树
* R  V4 Q6 {6 r+ `
3 c% N1 d  `0 |* I一个任意长度的编码序列可被唯一地翻译为一个字符序列（单词）。依次取出编码序列中的0或1，从哈夫曼编码树的根结点开始寻找一条路径。若为0，则沿着左分支向下走；若为1，则沿着右分支向下走。每到达一个叶子外结点时，就译出一个相应的字符，然后再回到哈夫曼树的根结点处，依次译出余下的字符，最后得到一个单词。
作者: liuyaliss    时间: 2009-9-6 15:10
哈夫曼树的应用
8 }/ ^! c: Y9 k. Q0 g- D: c哈夫曼树的应用十分广泛，在不同的应用中，对叶子结点的权和带权路径长度有不同的解释。4 @0 Z3 }9 Y5 w' a+ C9 S
, ~" b( w9 [/ Y& z) H! ^) a; R$ {
哈夫曼树的应用之一是用于优化判断过程，利用哈夫曼树得到最佳判定算法。例如，将百分制转换成五级制的算法。显然，此算法很简单，只需利用if语句描述即可。
: }0 D% a6 x8 g9 E+ u
$ I& _) @+ |: g, V9 \$ ~4 r' P& Rif ( x<60)
2 f; M/ g1 ~7 _
1 _  Z9 W9 j% l4 ]     score=’不及格’;3 Z: d6 ]  x/ b4 Y3 e- G
7 ]1 w8 `* {9 ]4 y
else if ( x<70)
3 Y1 j. h+ O2 @" B
- ]7 s6 n- c3 O8 L     score=’及格’;7 @. w" w* r$ W5 u: ^: x( H* T8 X
& w. i3 `# p* Q8 r3 d: p
else if ( x<80)0 x$ ?4 S, ]  I

6 ]' P' z1 q- y8 z9 A5 \     score=’中’;' G* O, f9 U0 }+ ]- d' m5 h

' k" k' c' j/ P9 u* L  y) p! delse if ( x<90)
: t/ q% Y: I; k# W5 n5 W# H
- I! U7 {& {. G2 F3 l. E* o     score=’良’;, F$ C+ u3 n+ u$ {) R1 T

$ Q9 j! v# x4 F) V4 q" ielse3 t0 ?# j% X' m2 {5 I: m; k

5 D2 f2 L/ ^/ Z% E     score=’优’;' l) K% \! J' ^7 w1 X+ C8 b4 k

0 h9 g; B+ v9 z. ?3 n此判定过程可以用图6.33(a)的判定树来表示。如果学生规模很大，该算法需反复多次执行，就应该考虑算法执行的时间问题。在实际应用中，学生的成绩呈正态分布，大部分在70~89分之间，优秀和不及格的概率较小。假设不及格、及格、中、良、优的百分比为5％、12%、40%、35%、8%，则上述算法80%以上的成绩需要进行三次或三次以上的比较才能得到结果。若以这些百分比值5,12,40,35,8为权值，使用哈夫曼算法来构造一棵判定树，则得到图6.33(b)所示的判定过程，可使多数成绩经过较少的比较即可得到结果。但由于每个判定框都有两次比较，将两次比较分开，得到如图6.33(c)所示的判定树，按此判定树构造程序，显然可以大大减少比较次数。& S  H0 g% b' D: v- I

  H" I( i! U( }( `( k# D2 V                x                                      x 4 ]8 X0 J5 s" \, [( A9 A, W1 U/ b
& d# n  W" i0 X, w1 Q  H0 {/ `
3 t' m- H9 h! W- O( X: g
, _/ \' q7 ]9 F; \9 ~

$ b7 _# p# H! ^- ~5 D8 r' D" N! [3 V' n" t& b( L
             x<60                                 70≤x<800 b8 T# i+ j" x

7 C2 e# O% y6 ]( F% ^# U5 {          Y         N                          Y           N
# ]5 d& _. @( z( W& x- t4 f8 c; E" h
" r( }" E* e9 t) o4 P/ x3 E- u+ @     不及格        x<70                       中         80≤x<90 - z- D7 N+ a5 p
7 Q0 c; p% y; h
               Y         N                           Y            N 0 p' h6 u9 x( B- O- U
- i% l1 g0 _& Z' f2 x0 m" i
           及格         x<80                         良        60≤x<70
4 }" B4 P! ?' o3 q* W# F
2 N) `7 p1 H! t! ~/ w% J                    Y         N                             Y          N
; m9 {& Y6 ]$ j& b
% |0 s5 [$ I+ a                 中          x<90                          x<60      及格$ ]' M- Z6 t4 r" t' g, V" W; `: L% V

1 v+ V% a3 F& p& o( e                         Y         N                 Y         N  
) p8 t6 I2 ~' P/ w- k* f) A' s8 r" n& o( @; Y$ p$ t* Q
                      良           优             不及格        优
( c$ F6 Z& L+ {3 ?. G2 m$ r  w2 u) ?. k: Z, r  W
(a)                                                                                                                   (b)
+ N; e3 c- W" R7 Q! g0 X" Y) e9 l& M% s
                x
% _- S  q: ^8 S5 X' W7 W+ u4 a( R+ u' e9 P6 ~& d
: K* b! o2 B9 Z; A7 U
$ v6 W2 @( T, y) l. W
              x<809 I# r9 v, ?5 C2 T! [

, e: J" C* L; u& S6 {       Y
1 a6 O  }" K% ^* Z9 J, V1 @% X$ D
# p5 q9 D) t0 G    x<70                x<90 + I; j& _: K. [! {, A& u; M4 i* N
/ V5 p! z( z5 e' P- C/ Q, Q
Y         N        Y          N
* B' s8 q6 p5 T2 N' R8 W" H1 J) J. z) z! @4 S. X! |% a' M3 W3 M" U% G
                       x<60         中       良          优) E* S7 m8 I+ b3 h- B
5 S. g4 U% K+ k& y" E! ~
                   Y         N
2 S" B8 j1 @$ c2 n: f9 U
% Q4 o: J6 W# k% l9 e4 u2 r0 R                不及格       及格% n) w3 w; w: ]- |, `% G) e
' \5 ^0 V0 B5 J: c
           （c）
$ @, ~  k3 T2 A$ x1 T( v* I
9 @9 f/ T' e$ Z9 }! W5 P+ H) A$ D                       图6.33 百分制转换五级制的判定过程; \7 J+ f" T- q

0 e0 l, O6 |& l6 ]1 ^% y
" k% g7 B3 O% T7 }/ F( r7 w
0 v( Z0 V% F/ B哈夫曼树在通信、编码和数据压缩等技术领域也有着广泛的应用。下面我们介绍哈夫曼树在数据编码中的应用，即数据的最小冗余编码问题。2 ?* U' f# J* a. d' |3 G
+ p2 N$ ]: K' q( Y3 V
在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“AFTER  DATA  EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符，则固定编码长度为5。然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。但这样长短不等的编码又会产生一个新问题，即如何解译成原文？除非设计时能够保证任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀，符合此要求的编码称为前缀编码。' J% A5 K; K; u* @2 Q8 d9 ~
3 M9 b2 c$ j; P, ]
为使不等长编码为前缀编码，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于求出了传送报文的最短长度。因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。; G- }' d4 T3 A/ N& |1 G

# a: Y% [- ^; q我们用上述各字母出现的次数{8，4，5，3，1，1}作为权构造哈夫曼树，如图6.36所示。约定左分支表示字符“0”，右分支表示字符“1”，则可以从根结点到叶子结点的路径的分支上的字符组成的字符串作为该叶子对应字符的编码。可以证明，如此得到的必为二进制前缀编码，而且是一种最优前缀编码。我们称这样的树为哈夫曼编码树，由此得到的编码称为哈夫曼编码。本例中字母A、E、R、T、F、D的哈夫曼编码分别为11、00、01、011、0100、0101。可以看出，出现次数较多的字母A、E、R，具有最短的编码，长度均为2；而出现次数最少的字母F、D，具有最长的编码，长度均为4。报文的最短传送长度为：   ; t/ P$ _. i& @# Q; g3 P+ G9 ]' z2 z

5 x3 ]$ Q' Z* Z6 h       68 T4 u1 D0 g3 ]1 ?1 d9 Y4 N

$ N. \; y. s9 z   L=WPL=S(wklk)=4×2+5×2+8×2+3×3+1×4+1×4=51
2 W/ k% H* U4 q. U# }6 }9 }& L) a0 p+ J5 ~1 U6 _& p; Z! B0 ]2 l
          k=19 D2 j/ D& x! T" _. C3 Z: q7 }

8 X8 Q% J. t  c3 B! u7 W; }7 n1 V1 L' D若采用等长编码，报文的传送长度为 2 l: s) n+ i+ }

9 Y9 [# z! ^5 n3 N- ]& }" f- {9 ML=8×3+4×3+5×3+3×3+1×3+1×3=66
. r* X: L! `" K9 U  L. A( d
" W* P+ ~8 O" ^1 J. q% X; h5 Z显然，哈夫曼编码比等长编码所得到的报文长度要短得多。哈夫曼编码是最优前缀编码。5 W: v+ Q8 C0 c4 T
- X0 F. P7 `+ x5 F% z

8 j5 P& d: V7 Z0 l( i
) }2 O! L* Y6 p/ p                          22
; V5 Y$ V6 P* C, |  w8 l  j, w0 C8 C
                        0     1
! E" m( I4 ]2 Q" i8 f& t1 t( P+ J+ t0 J; F) x
9                         13
' b! u) q9 Q- d  l( ]" }) ~8 r; J# m5 ]5 z3 r( n- M7 }3 I
                        0     1   0     12 s0 t2 p1 E" {& m2 w+ B

6 [9 @! {$ D8 `6 T$ t                       4      5   5      8
6 J- o5 O$ C: {1 G
5 f3 R- Z1 }& X& G9 E- p                      E    0    1  R     A
' {( R3 I; ]6 {( S  L8 ^* A$ C  |; Y* L' h% Z- O% `3 c
2      3
, F" ~* O( o4 P" M) t
. I' x4 V3 H& J0 H0 P! f' D8 c                        0    1   T
- M4 Q& F+ f+ H7 h2 k+ @: W4 \& w  e8 p' j+ @
                      1      1
- E0 L7 P2 m: T) a, c7 ^. {: r& J$ {; p& }; F
                  F      D# {4 B" h# e8 R2 d* d  X+ R) X

& H7 x7 @, G0 ~图6. 36   哈夫曼编码树0 R) ~+ x5 x) w7 r. l' i

# ]$ J* J# f1 B7 Y" y- f一个任意长度的编码序列可被唯一地翻译为一个字符序列（单词）。依次取出编码序列中的0或1，从哈夫曼编码树的根结点开始寻找一条路径。若为0，则沿着左分支向下走；若为1，则沿着右分支向下走。每到达一个叶子外结点时，就译出一个相应的字符，然后再回到哈夫曼树的根结点处，依次译出余下的字符，最后得到一个单词。
作者: liuyaliss    时间: 2009-9-6 15:12
不好意思 多发了一次



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5