探讨无损数據压缩.PDFVIP

探討無損數據壓縮 篇名： 探討無損數據壓縮 作者： 陳立中。國立基隆高中。214班 蘇冠綸。國立基隆高中。206班 　張逸。國立基隆高中。214班 1 探討無損數據壓縮 壹●前言 在細談這篇論文的目的之前，我們要先了解甚麼是「無損數據壓縮」。在電腦上，時常有一 些程式可以將數據壓縮，使他們的大小變小。數據壓縮主要分成兩種－－無損數據壓縮 (Lossless Data Compression)與有損數據壓縮（Lossy Data Compression ）。其中，無損數據壓 縮指的是當數據被壓縮並解壓縮後，與原來的數據是一樣的，而反之，有損數據壓縮指的是 被壓縮並解壓縮後的數據與原來的有所不同，因有部份於壓縮過程中損失，或被扭曲以便壓 縮。 俗說：「天下沒有白吃的午餐」。所以，我常思索著，原來需要這麼多儲存空間的數據，怎 麼可能不付出甚麼，就把這些數據變小，其中想必有些奇妙的數學。因次，借此次的機會， 我嘗試找出無損數據壓縮是如何做到的。 貳●正文 一、無損數據壓縮的演算法 有許多種演算法（方法）可以壓縮數據，而在本篇論文中將介紹幾個較為知名的壓縮演算法。 1. 字典式壓縮法 其中一種最常用的無損數據壓縮演算法就是字典式的壓縮法。字典是壓縮法的運作原理，就 是找出數據中重複出現的資料，然後以較短的數據來代替他。 A. 游程編碼 遊程編碼指的是將數據中連續且重複的資料用比較短的方式表達，例如說：（註一） 以下有一段數據： 0.999999999998 若用遊程編碼，則以上數據可以用這個方式表達： 0.[9x11]8 由於在原始數據中，「9」這個字重複了十一遍。所以，再遊程編碼時，所有的十一個「9」 都用 [9x11]取代。遊程編碼只是一種方法，所以每一個程式所使用的語法不一定相同。 遊程編碼的優點是如果數據的性質符合，則遊程編碼的壓縮比例可以很高。在數學上面，遊 程編碼這個演算法屬於 On 種類的演算法，因為運算所需要的時間與運算的原始數據大 小成正比。所以用這種方法壓縮大且含有大量連續且重複的資料可以達到不錯的效率。 遊程編碼的缺點是，很少有數據是含有大量重複且連續的資料。現實生活上，唯一有這種性 2 探討無損數據壓縮 質的數據就是黑白圖片，因為黑白圖片上的每一格都可以用0或1 來代表，而且，一般圖片 上，常有許多重複且連續的黑或白格子。 B. LZ77/LZ78 LZ77/LZ78 是一種稍微比遊程編碼應用更廣泛的演算法。LZ77/LZ78 中，需要有一個「字典」， 這個「字典」裡，有一些數據中常出現的資料，並給每一筆資料一個代碼。（註二）則在其 餘的數據中，將在自典裡出現的資料替換成那資料的代碼，以結省空間。例如說：以下有一 原始數據： I am doing this thesis on a train, because it is fun to do thesis on a train, and a train likes to have a thesis done onboard it. 很明顯的，在以上數據中，重複出現的數據（字）有： a train, thesis 所以，字典裡的數據有： 1=a train 2=thesis 而其餘的數據是： I am doing this $2 on $1, because it is fun to do $2 on $1, and $1 likes to have a $2 done onboard it. 值得注意的是壓縮後的數據也包含字典。 LZ77/LZ78 是目前最常用的無損數據壓縮計算法。市面上常見的.zip 檔中所用的 DEFLATE 壓 縮法就是使用 LZ77 ， 還有.gz 檔也是使用 LZ77 ，另外，壓縮率很強的7-zip ，也是使用一種 LZ77/LZ78 的變種，叫做LZMA 。 LZ77/LZ78 的優點就是可以壓縮很多種資料，可以被LZ77/LZ78 壓縮的資料也很多，例如說 最常見的文字檔，網頁，等。LZ77/LZ78 的程式也很好寫，一版編程的初學者大