資源描述：
《無損數據壓縮算法的歷史》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。
1、----------專業(yè)最好文檔，專業(yè)為你服務，急你所急，供你所需-------------文檔下載最佳的地方無損數據壓縮算法的歷史引言有兩種主要的壓縮算法：有損和無損。有損壓縮算法通過移除在保真情形下需要大量的數據去存儲的小細節(jié)，從而使文件變小。在有損壓縮里，因某些必要數據的移除，恢復原文件是不可能的。有損壓縮主要用來存儲圖像和音頻文件，同時通過移除數據可以達到一個比較高的壓縮率，不過本文不討論有損壓縮。無損壓縮，也使文件變小，但對應的解壓縮功能可以精確的恢復原文件，不丟失任何數據。無損數據壓縮被廣泛的應用在計算機領域，從節(jié)省你個人電腦的空間，到通過web發(fā)送數
2、據。使用SecureShell交流，查看PNG或GIF圖片。無損壓縮算法可行的基本原理是，任意一個非隨機文件都含有重復數據，這些重復數據可以通過用來確定字符或短語出現概率的統計建模技術來壓縮。統計模型可以用來為特定的字符或者短語生成代碼，基于它們出現的頻率，配置最短的代碼給最常用的數據。這些技術包括熵編碼(entropyencoding)、游程編碼(run-lengthencoding)以及字典壓縮。運用這些技術以及其它技術，一個8-bit長度的字符或者字符串可以用很少的bit來表示，從而大量的重復數據被移除。歷史----------專業(yè)最好文檔，專業(yè)為你服務，急
3、你所急，供你所需-------------文檔下載最佳的地方----------專業(yè)最好文檔，專業(yè)為你服務，急你所急，供你所需-------------文檔下載最佳的地方直到20世紀70年代，數據壓縮才在計算機領域開始扮演重要角色，那時互聯網變得更加流行，Lempel-Ziv算法被發(fā)明出來，但壓縮算法在計算機領域之外有著更悠久的歷史。發(fā)明于1838年的Morsecode，是最早的數據壓縮實例，為英語中最常用的字母比如”e”和”t”分配更短的Morsecode。之后，隨著大型機的興起，ClaudeShannon和RobertFano發(fā)明了Shannon-Fano編碼
4、算法。他們的算法基于符號(symbol)出現的概率來給符號分配編碼(code)。一個符號出現的概率大小與對應的編碼成反比，從而用更短的方式來表示符號。兩年后，DavidHuffman在MIT學習信息理論并上了一門Robert----------專業(yè)最好文檔，專業(yè)為你服務，急你所急，供你所需-------------文檔下載最佳的地方----------專業(yè)最好文檔，專業(yè)為你服務，急你所急，供你所需-------------文檔下載最佳的地方Fano老師的課，Fano給班級的同學兩個選項，寫一篇學期論文或者參加期末考試。Huffman選擇的是寫學期論文，題目是尋找二
5、叉編碼的最優(yōu)算法。經過幾個月的努力后依然沒有任何成果，Huffman決定放棄所有論文相關的工作，開始學習為參加期末考試做準備。正在那時，靈感爆發(fā)，Huffman找到一個與Shannon-Fano編碼相類似但是更有效的編碼算法。Shannon-Fano編碼和Huffman編碼的主要區(qū)別是構建概率樹的過程不同，前者是自下而上，得到一個次優(yōu)結果，而后者是自上而下。早期的Shannon-Fano編碼和Huffman編碼算法實現是使用硬件和硬編碼完成的。直到20世紀70年代互聯網以及在線存儲的出現，軟件壓縮才被實現為Huffman編碼依據輸入數據動態(tài)產生。隨后，1977年A
6、brahamLempel和JacobZiv發(fā)表了他們獨創(chuàng)性的LZ77算法，第一個使用字典來壓縮數據的算法。特別的，LZ77使用了一個叫做slidingwindow的動態(tài)字典。1978年，這對搭檔發(fā)表了同樣使用字典的LZ78算法。與LZ77不同，LZ78解析輸入數據，生成一個靜態(tài)字典，不像LZ77動態(tài)產生。法律問題LZ77和LZ78都快速的流行開來，衍生出多個下圖中所示的壓縮算法。其中的大多數已經沉寂了，只有那么幾個現在被大范圍的使用，包括DEFLATE，LZMA以及LZX。絕大多數常用的壓縮算法都衍生于LZ77，這不是因為LZ77技術更好，只是由于Sperry在1
7、984年申請了LZ78衍生算法LZW的專利，從而發(fā)展受到了專利的阻礙，Sperry開始因專利侵權而起訴軟件提供商，服務器管理員，甚至是使用GIF格式但沒有License的終端用戶。同時，UNIX壓縮工具使用了一個叫LZC的LZW算法微調整版本，之后由于專利問題而被棄用。其他的UNIX開發(fā)者也開始放棄使用LZW。這導致UNIX社區(qū)采用基于DEFLATE的gzip和基于Burrows-WheelerTransform的bzip2算法。長遠來說，對于UNIX社區(qū)這是有好處的，因為gzip和bzip2格式幾乎總是比LZW有更好的壓縮比。圍繞LZW的專利問題已經結束，因為L
8、ZW的專利
