LZ77算法實現 - 下載本文

LZ77壓縮算法的實現

專 業: 班 級: 學 號: 姓 名: 報告日期:

LZ77壓縮算法的實現

學生姓名: 指導老師:

摘 要 文本壓縮是根據一定方法對大量數據進行編碼處理以達到信息壓縮存儲過程,被壓縮的數據應該能夠通過解碼恢復到壓縮以前的原狀態,而不會發生信息丟失現象。發展到現在已經有很多關于文本壓縮的算法,主要有LZ編碼、Huffman 編碼、算術編碼等無損壓縮和預測編碼、量化、變換編碼等有損壓縮。本文將討論LZ77算法實現過程,以及LZ77算法的優劣性和改進方法。

關鍵詞 多媒體技術;文本壓縮算法;LZ77算法;C++程序設計;數據結構;字符串查找;文本匹配;

1

目 錄

1 引 言........................................................................................................................................... 3

1.1課程設計目的 ..................................................................................................................... 3 1.2課程設計內容 ..................................................................................................................... 3 2 算法基本原理 ............................................................................................................................... 4

2.1算法概述 ............................................................................................................................. 4 2.2 LZ77壓縮 .......................................................................................................................... 4 2.3 LZ77解壓縮 ...................................................................................................................... 5 3 LZZ算法實現 .............................................................................................................................. 6

3.1三元組的設計 .................................................................................................................... 6 3.2查找匹配串 ........................................................................................................................ 6 4 實驗結果和結果分析 ................................................................................................................... 8

4.1 實驗結果 ........................................................................................................................... 8 4.2 實驗結果分析 ................................................................................................................... 9 5 結束語......................................................................................................................................... 10 參考文獻......................................................................................................................................... 11 附錄1:LZ77主要代碼清單 ........................................................................................................ 12

2

1 引 言

隨著計算機技術的快速發展,各種系統數據量越來越大,給信息存儲特別是網絡傳輸帶來諸多的困難,己成為有效獲取和使用信息的瓶頸。為了節省信息的存儲空間和提高信息的傳輸效率,必須對大量的實際數據進行壓縮。實踐證明,采用數據壓縮技術可以節省80%以上的費用,且一些難點問題通過壓縮技術能夠實現。

數據壓縮技術種類繁多、應用廣泛,技術不斷發展,一些分支已成為當今研究的焦點。按照編碼的失真程度數據壓縮可以分為有損壓縮和無損壓縮。有損壓縮即原始數據不能完全恢復,主要應用于圖像和數字化的語音方面。無損壓縮就是經過一個壓縮后,能夠產生和輸入完全一致的壓縮技術,主要用于存儲數據庫記錄或處理文本文件。其中,LZ77算法是無損壓縮中常用到的算法。

1.1課程設計目的

研究多媒體數據壓縮技術是實現實時有效地處理、傳輸和存儲龐大的多媒體數據的關鍵技術。許多應用領域對多媒體信息的實時壓縮提出了更高的要求,快速、高效的壓縮算法是解決這一問題的關鍵。針對多媒體數據在空間、時間、結構、視覺、知識等方面所產生的冗余,利用有損壓縮和無損壓縮等方法,對圖像、音頻、視頻等多媒體數據進行壓縮,以保留盡可能少的有用信息。本文主要是把所學的數據結構和算法設計的知識應用于實踐,對LZ77壓縮算法加以研究。

通過課程設計,可以更好地掌握和理解文本壓縮算法,學習常用的壓縮算法,并通過比較壓縮算法,來加深對多媒體技術的理解。

1.2課程設計內容

本次課程設計為LZ77算法的實現,通過用C++語言來這個算法,然后用隨機生成的數據來分別對程序進行壓縮和解壓,檢驗壓縮結果是否正確和測試程序壓縮的效率。

3

2 算法基本原理

2.1算法概述

這一算法是由Jacob Ziv 和 Abraham Lempel 于 1977 年提出,所以命名為 LZ77。傳統的算法,如Huffman 算法都是建立在靜態的字典模型上,但是靜態字典模型并不是好的選擇。首先,靜態模型的適應性不強,我們必須為每類不同的信息建立不同的字典;其次,對靜態模型,我們必須維護信息量并不算小的字典,這一額外的信息量影響了最終的壓縮效果。LZ77采用了自適應的字典模型,也就是說,將已經編碼過的信息作為字典,如果要編碼的字符串曾經出現過,就輸出該字符串的出現位置及長度,否則輸出新的字符串。如下圖2.1所示。

圖 2.1 LZ77算法舉例

2.2 LZ77壓縮

LZ77算法使用\滑動窗口\的方法,來尋找文件中的相同部分,也就是匹配串。這里說的串,是指一個任意字節的序列,而不僅僅是可以在文本文件中顯示出來的那些字節的序列。這里的串強調的是它在文件中的位置,它的長度隨著匹配的情況而變化。

LZ77從文件的開始處開始,一個字節一個字節的向后進行處理。一個固定大

小的窗口(在當前處理字節之前,并且緊挨著當前處理字節),隨著處理的字節不斷的向后滑動。對于文件中的每個字節,用當前處理字節開始的串,和窗口中的每個串進行匹配,尋找最長的匹配串。窗口中的每個串指,窗口中每個字節開始的串。如果當前處理字節開始的串在窗口中有匹配串,就用(之間的距離,匹配長度) 這樣一對信息,來替換當前串,然后從剛才處理完的串之后的下一個字節,繼續處理。如果當前處理字節開始的串在窗口中沒有匹配串,就不做改動的輸出當前處理字節。

處理文件中第一個字節的時候,窗口在當前處理字節之前,也就是還沒有滑

到文件上,這時窗口中沒有任何內容,被處理的字節就會不做改動的輸出。隨著處理的不斷向后,窗口越來越多的滑入文件,最后整個窗口滑入文件,然后整個

4





重庆快乐十分现场开奖