【轉】zip 的壓縮原理與實現(xiàn)

。======================================= 短語式重復的傾向和字節(jié)取值分布不均勻的傾向是可以壓縮的基礎，兩種壓縮的順序不能互換的原因也說了，下面我們來看編碼式壓縮的要求及方法：首先，為了使用不定長的編碼表示單個字符，編碼必須符合“前綴編碼”的要求，即較短的編碼決不能是較長編碼的前綴，反過來說就是，任何一個字符的編碼，都不是由另一個字符的編碼加上若干位 0 或 1 組成，否則解壓縮程序將無法解碼?？匆幌虑熬Y編碼的一個最簡單的例子：符號 編碼a 0b 10c 110d 1110e 11110有了上面的碼表，你一定可以輕松地從下面這串二進制流中分辨出真正的信息內容了：1110010101110110111100010 - dabbdceaab要構造符合這一要求的二進制編碼體系，二叉樹是最理想的選擇。考察下面這棵二叉樹： 根(root) 0 | 1 +-------+--------+ 0 | 1 0 | 1 +-----+------+ +----+----+ | | |