基本思想
- 以字符的使用頻率作為權(quán)構(gòu)建一顆哈弗曼樹，然后利用哈弗曼樹對字符進(jìn)行編碼汞扎。
- 構(gòu)造一顆哈弗曼樹季稳，是將要編碼的字符作為葉子節(jié)點(diǎn)，該字符在文件中的使用頻率作為葉子節(jié)點(diǎn)的權(quán)值澈魄，以自底向上的方式景鼠，通過n-1次的‘合并’后構(gòu)造的一棵樹，核心思想是權(quán)值越大的葉子離跟很近痹扇。
貪心策略
- 每次從樹的集合中取出沒有雙親且權(quán)值最小的兩顆樹作為左右子樹
算法步驟
- 確定合適的數(shù)據(jù)結(jié)構(gòu)铛漓。需要考慮情況有：
- 哈弗曼樹中沒有度為一的節(jié)點(diǎn)，則一顆有n個葉子節(jié)點(diǎn)的哈弗曼樹共有2n-1個節(jié)點(diǎn)（n-1次的合并鲫构，每次產(chǎn)生一個新節(jié)點(diǎn)）
- 構(gòu)成哈弗曼樹后浓恶，為求編碼，需從葉子節(jié)點(diǎn)出發(fā)走一條從葉子到根的路徑结笨。
- 譯碼需要從根出發(fā)走一條從根到葉子的路徑包晰，那么我們需要知道每個節(jié)點(diǎn)頂點(diǎn)權(quán)值、雙親炕吸、左孩子伐憾、右孩子和節(jié)點(diǎn)的信息。
- 初始化赫模。構(gòu)造n棵節(jié)點(diǎn)為n個字符的單節(jié)點(diǎn)樹集合T={t1,t2,t3,...,tn}树肃，每棵樹只有一個帶權(quán)的根節(jié)點(diǎn)，權(quán)值為該字符的使用頻率瀑罗。
- 如果T中只剩下一棵樹扫外，則哈弗曼樹構(gòu)造成功，調(diào)到步驟6廓脆。否則筛谚，從集合T中取出沒有雙親且權(quán)值最小的兩棵樹ti和tj，將他們合并成一顆新樹Zk停忿，新樹的左孩子為ti驾讲，右孩子為tj，Zk的權(quán)值為ti和tj的和。
- 從集合T中刪除ti和tj吮铭，加入Zk时迫。
- 重復(fù)步驟3-4。
- 約定做分支上的編碼為“0”谓晌，右分支上的編碼為“1”掠拳。從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)逆向求處每個字符的哈弗曼編碼，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑上的字符組成的字符串為該葉子節(jié)點(diǎn)的哈弗曼編碼纸肉。算法結(jié)束
