一題有關huffman coding的問題

james2371507

題目大概是這樣
INPUT: one single line containing only"A-Z""a-z""0-9",totally 62posiible characters
            of length less than 10000.
OUTPUT:the number of bits of its Huffman encoding
EX: input: AAABBBAABCAAAABD
      output: 25


不用給完整的code  因為現在是完全不知如何下手
有沒有什麼建議呢?

ahijup

小弟提供一個方法
我是把每一個Huffman碼全部算出來
然後再去算結果

1. #include <iostream>
   
2. using namespace std;
   
3. struct Huffman {
   
4.         char ch ;
   
5.         int times ;
   
6.         char *code ;
   
7.         bool isLeaf ;
   
8.         Huffman *r , *l , *next ;
   
9. } ;
   
10. void InsertionSort ( Huffman *x , int size ) ;
    
11. Huffman * MergerCode ( Huffman *x , int size ) {
    
12.         if ( size == 1 )                                        //如果size = 1的時候，代表整棵樹已經建立完成
    
13.                 return x ;                                                //回傳x
    
14.         InsertionSort(x , size ) ;                        //把x根據times & ch 排序
    
15.        
    
16.        
    
17. 
    
18.         Huffman tmp ;
    
19.         tmp.ch = NULL ;
    
20.         tmp.times = x[0].times + x[1].times ;        //把最小的前兩個code合併成一個code
    
21.         tmp.l = &x[0] ;
    
22.         tmp.r = &x[1] ;
    
23.         tmp.isLeaf = false ;
    
24. 
    
25.         Huffman *t = new Huffman[size - 1] ;        //建一個比input還要小一個的空間
    
26.         int i ;
    
27.         for ( i = 2 ; i < size  ; i++ )                        //把後面的code放入t
    
28.                 t[i - 2 ] = x[i] ;
    
29.         t[i-2] = tmp ;                                                        //最後把合併的code放入t的最後一個
    
30. 
    
31.         return MergerCode ( t , size - 1) ;                //遞迴呼叫自己的函式
    
32. }
    
33. class SimpleSearch {
    
34. private:
    
35.         Huffman *sQueue , *ptr ;
    
36.         bool SelectNode () {
    
37.                 if ( ! this->sQueue->isLeaf ){                        //如果現在指向的元素不是樹葉
    
38.                         Huffman *t = this->sQueue ;                        //point to current vQueue
    
39.                        
    
40.                         while ( t->next != NULL )                        //找到sQueue的最後一個指標
    
41.                                 t = t->next ;
    
42. 
    
43.                         int i = 0 ;
    
44.                         char *buffer = new char [50] ;
    
45. 
    
46.                         for ( ; i < (int)strlen(this->sQueue->code) ; i++ )                        //把目前的節點的code記錄到buffer裡面
    
47.                                 buffer[i] = this->sQueue->code[i] ;
    
48. 
    
49.                         buffer[i] = '\0' ;
    
50. 
    
51.                         t->next = this->sQueue->l ;                                                                        //把目前的節點的左子樹加入sQueue最後
    
52.                         t->next->code = new char [50] ;
    
53. 
    
54.                         for ( i = 0 ; i < (int) strlen ( buffer ) ; i++ )                       
    
55.                                 t->next->code [i] = buffer[i] ;
    
56.                         t->next->code[i++] = '0' ;
    
57.                         t->next->code[i] = '\0' ;
    
58.                         t = t->next ;
    
59. 
    
60.                         t->next = this->sQueue->r ;                                                                        //把目前的節點的右子樹加入sQueue最後
    
61.                         t->next->code = new char [50] ;
    
62. 
    
63.                         for( i = 0 ; i < (int) strlen( buffer ) ; i++ )
    
64.                                 t->next->code[i] = buffer[i] ;
    
65.                         t->next->code[i++] = '1' ;
    
66.                         t->next->code[i] = '\0' ;
    
67.                        
    
68.                         t->next->next = NULL ;
    
69. 
    
70.                         delete []buffer ;
    
71.                 }
    
72. 
    
73.                 this->sQueue = this->sQueue->next ;                                                                //指向下一個code
    
74.                 if ( this->sQueue == NULL )
    
75.                         return false ;
    
76.                 return true ;
    
77.         } ;
    
78. public:
    
79.         Huffman *first ;
    
80. 
    
81.         SimpleSearch(Huffman *root ) {
    
82.                 this->first = new Huffman() ;
    
83.                 this->ptr = first ;
    
84. 
    
85.                 this->sQueue = root ;
    
86.                 this->sQueue->code = new char [50] ;
    
87.                 this->sQueue->code[0] = '\0' ;
    
88.                 this->sQueue->next = NULL ;
    
89.         } ;
    
90.         void BFS( ) {
    
91.                 if ( !SelectNode( ) ) {
    
92.                         return ;
    
93.                 } else {
    
94.                         if ( this->sQueue->ch != NULL ) {                        //如果目前的.ch 不是NULL
    
95.                                 ptr->next = this->sQueue ;                                //把目前的節點加入ptr後面
    
96.                                 ptr = ptr->next ;
    
97.                         }
    
98.                         BFS() ;
    
99.                 }
    
100.         } ;
     
101. } ;
     
102. void InsertionSort ( Huffman *x , int size ) {
     
103.         for ( int i = 1 ; i < size ; i++ ) {
     
104.                 int j = i ;
     
105.                 while ( j > 0 ) {
     
106.                         if ( x[j].times < x[j-1].times )
     
107.                                 swap(x[j] , x[j-1] ) ;
     
108.                         else if ( x[j].times == x[j-1].times ) {
     
109.                                 if ( x[j].ch < x[j-1].ch )
     
110.                                         swap(x[j] , x[j-1] ) ;
     
111.                         }
     
112.                         j -= 1;
     
113.                 }
     
114.         }
     
115. }
     
116. int main() {
     
117.         char input[80] ;
     
118.         cin.getline(input , 80 , '\n') ;
     
119. 
     
120.         cout << "input-> " << input << endl ;
     
121. 
     
122.         Huffman Codes[80] ;
     
123.         int i = 0 , ammount = 0 ;
     
124.        
     
125.         //把輸入字元做統計
     
126.         while ( input[i] != '\0' ) {                       
     
127.                 bool flag = false ;
     
128.                 for ( int j = 0 ; j < ammount ; j++ ){
     
129.                         if( Codes[j].ch == input[i] ) {
     
130.                                 flag = true ; Codes[j].times ++ ; break ;
     
131.                         }
     
132.                 }
     
133. 
     
134.                 if( !flag ) {
     
135.                         Codes[ammount].isLeaf = true ;
     
136.                         Codes[ammount].l = NULL ;
     
137.                         Codes[ammount].r = NULL ;
     
138.                         Codes[ammount].ch = input[i] ;
     
139.                         Codes[ammount++].times = 1 ;
     
140.                        
     
141.                 }
     
142.                 i++ ;
     
143.         }
     
144. 
     
145.         Huffman *t = MergerCode( Codes , ammount) ;                //合併codes
     
146. 
     
147.         SimpleSearch x(t) ;                                                               
     
148.         x.BFS() ;                                                                                //走訪每個節點
     
149.         i = 0 ;
     
150.         //輸出coding的結果
     
151. 
     
152.         cout << "After encoding->" ;
     
153.         while ( input[i] != '\0' ) {
     
154.                 //查表
     
155.                 Huffman *t = x.first->next ;
     
156.                 while (t != NULL ) {
     
157.                         if ( t->ch == input[i] ) {
     
158.                                 cout << t->code << "|" ; break ;
     
159.                         }
     
160.                         t = t->next ;
     
161.                 }
     
162.                 i++ ;
     
163.         }
     
164. 
     
165.         cout << endl ;
     
166. 
     
167.         int s = 0 ;
     
168.         //統計總共要多少位元數
     
169.         while( x.first != NULL ) {
     
170.                 if (x.first->ch != NULL )
     
171.                         s += x.first->times * (int) strlen(x.first->code) ;
     
172.                 x.first = x.first->next ;
     
173.         }
     
174.         cout << "Total bits->" << s << endl ;
     
175.         system("pause") ;
     
176.         return 0 ;
     
177. }

複製代碼

裡面寫了linked list & tree結構，兩個寫在同一個struct裡面
Complier: vc++ 2008
剛剛試了一下輸入 / 輸出是OK的，給你參考看看!!...

瀏覽完整內容，請先 註冊 或 登入會員

poorpoorpoor

提供一個使用HEAP的方法

1.統計各個字元的數量
2.全部PUSH到HEAP中
3.若HEAP大小等於1則跳到步驟6否則繼續
4.POP出2個值最小的元素並丟入一新元素其大小是兩元素的大小和
5.跳回步驟3
6.加總每個字元的取出次數*字元數即為答案

EX:AAABBBAABCAAAABD
A9個 B5個 C1個 D1個
取出C和D丟入(C+D)
取出(C+D)和B丟入(B+C+D)
取出(B+C+D)和A丟入(A+B+C+D)
...

瀏覽完整內容，請先 註冊 或 登入會員