霍夫曼編碼 | 2021全台活動資訊網

2020年1月27日—建立節點，並且刪除兩個最小頻率，樹葉為兩最小頻率，樹根為兩者和並入堆積。剩餘根部時完成.產生編碼#.在進行霍夫曼編碼時，統計文字頻率 ...

Mon, 2020 Jan 27

在進行霍夫曼編碼時，統計文字頻率並使高頻文字 生成最少長度編碼達成壓縮的效果。

透過優先佇列用來產生霍夫曼樹，依序提取兩個頻率最小者合併並產生新的樹根， 將新節點放入優先佇列，其中優先佇列可以採用heap進行實做，這裡採用STL提供的函數庫。

當我們完成一個霍夫曼樹時進行遍歷，這裡設往左方編碼為0， 右方為1，可以採用簡單的遞迴產生編碼表。

為了探討編碼的保存，以ascii (8 bit)進行計算時，最大編碼長度為255， 試圖使huffman樹呈現最深的情況將會得到(n - 1)(當檔案含有兩種以上的字元)。

而255 bit至少要32個位元進行保存路徑，也可以透過一些方式繼續縮減大小， 如保存頻度表可以減少檔頭的大小。

編碼參見範例1[1]

這裡定義檔頭，tableSize保存頻率表的大小，frequency保存字元頻率並且要求輸入的頻率表， 必須由ascii順序排列，避免霍夫曼樹不同。

length用來保存霍夫曼編碼後的檔案長度，單位為bytes。 eofCounter用來標記結尾，值為右移次數。