壓縮 (1)
高一的時候，參加建中電研社學習 C語言，第一次上課後看了一點書大致上就學會了，上那個課比較大的收穫反倒在於接觸到了一些電研社的人和一些拿軟體的管道。
壓縮就是在這個時候接觸的。整套 TURBO C 2.0放在軟碟片中，由於容量的關係，整個TC是用PKZIP 壓起來的。那時完全沒有見過這類的東西，帶著懷疑的心態使用磁片中所負的PKUNZIP 把TC解開，詳細比較大小，發現真的所言不需，真的可把大的檔案變小，簡直就像魔術一樣。
為什麼？為什麼會這樣？如果真的是這樣的話，那不是可以用小小的磁片裝很多的東西嗎？那電腦的效能不是可以提高很多嗎？如果連續壓很多次，那不是會變得更小嗎？
好奇心的驅使之下，找人拿到了 PKZIP回來玩玩看，（那時還拿了一些其他有趣的東西，包括用pc speaker念英文的軟體等等），發現真的效果宏大，戰無不克，不過有一個小例外，重複壓縮，把檔案壓縮到非常小的這種理想無法達成。
受到 PKZIP威力的震撼，問題還是在是，同樣大小的檔案，比方說 10k好了，現在我差不多都能用 PKZIP把它壓成了5k，那 PKZIP是怎麼做到的？所有 10K的檔案有2^(10k)個，把它壓成了 5k的話，只有2^(5k)個，少了很多，怎麼可能壓成功？由鴿籠原理知道那是不可能的啊？
那個時候，學長的解釋是，壓縮的原理就好像是縮寫，比方說"1111111111"，壓縮之後我們用 "10個1"來表示，就能夠節省很多空間。這當然還帶來很多疑惑，"1111111111"這種東西太過特殊，一般哪有這麼好，再來後面的符號中用到了 個，而前面只有數字，顯然後面的每一個符號需要更多的位元來儲存，實際上真的能夠達到壓縮的作用嗎？更詳細的解釋學長也做不到，我只好自己去找答案了。
一開始找到了一些資訊量的東西，瞭解了原來真實世界上，資訊是不平均的，瞭解了可以把一些常用的字元用比較短的碼來表示。但要如何編 碼？我想一些演算法也實作出來了，但都不滿意，直到我看到了霍夫曼碼，才恍然大悟。令人挫折的是，我是看到了才知道，而不是自己想到的，而且那時看到了之 後我也沒有概念要如何想出這類的東西，實在很洩氣。稍微扳回一點顏面的是我能夠證明他是最短的編碼法。能證明他是對的和能發明的差距不可以道里計。
除了面對自己無法想出答案的洩氣之外，知道這樣的答案還是令人興奮的。不過，及使知道這樣的答案還是不夠的，一兩階的霍夫曼碼，或 者，即使是計算他的一兩階熵量也知道，至少要三階甚至更高階才能達到 PKZIP的壓縮率。以當時640k的記憶體來說，根本做不到，即使是現在也不容易。明顯的， PKZIP還有我不知道的秘密。
當然那個時候資訊不多，我能找到的資訊也不多，除了上面的之外，了不起也只知道pcx 的run length這類的東西。差不多高中畢業的時候，才學到了Lempel-Ziv(簡稱LZ)一類的方法，然後才瞭解了混和LZ法，熵量法和run length才能達到逼近 pkzip 的能力。當然這時的pkzip也不是我高一時的pkzip，壓縮率和稍後出來的ARJ等等的壓縮器一樣高了，速度又快。
ARJ當然是pkzip的一個歷史上的強敵，兩者並立至今。我高中時有所謂的ARJ壓縮的比較小但zip比較快的說法。其他知名的壓 縮器還有差不多的LZH，其他如ARC等等的比較老舊的壓縮器。 zip，arj，lzh，主要都是用LZ+霍夫曼來壓縮的，效率雖有差距但差距不大。我閱讀了zip，gzip 的原始碼和一些文件，並且利用了一些自己的技巧，做出了壓縮率高過 pkzip和 arj一點但速度差很多的壓縮器，有得時候壓縮率甚至還會好蠻多的。但差不多這個時候，出現了一個更厲害的壓縮器了，ultra compressor ，壓縮率之高讓zip,arj 至今望塵莫及。當然除了UC之外，還有好幾個壓縮氣得壓縮率也比arj和zip好很多，包括HA等等，好幾個名字我都記不起來了，因為現在包括UC在內， 這些壓縮器都已經沒有什麼人在用了。
為什麼？因為他們都有一個共同的特點，慢。大部分也都沒有什麼新的版本出來（話又說回來，ZIP和ARJ也沒有什麼長足的進步）。
0 意見:
張貼留言