數(shù)據(jù)壓縮基礎(chǔ)ppt課件(已改無錯(cuò)字)
2022-12-04 22:14:22 本頁面
【正文】 針，二是編碼器可能輸出額外的字符，這種字符是指可能包含在下一個(gè)匹配串中的字符。 ? LZSS算法的思想是如果匹配串的長度比指針本身的長度長就輸出指針（匹配串長度大于等于MIN_LENGTH）， 否則就輸出真實(shí)字符。另外要輸出額外的標(biāo)志位區(qū)分是指針還是字符。 48 LZSS編碼的基本流程 從當(dāng)前壓縮位置開始，考察未編碼的字符，并試圖在滑動(dòng)窗口中找出最長的匹配字符串，如果匹配串長度 len大于等于最小匹配串長度（ len = MIN_LENGTH）， 則進(jìn)行步驟 2，否則進(jìn)行步驟 3。 輸出指針二元組 ( off, len)。 其中 off 為窗口中匹配字符串相對(duì)窗口邊界的偏移， len 為匹配串的長度，然后將窗口向后滑動(dòng) len 個(gè)字符，繼續(xù)步驟 1。 輸出當(dāng)前字符 c， 然后將窗口向后滑動(dòng) 1 個(gè)字符，繼續(xù)步驟 1。 49 LZSS編碼舉例 位置 1 2 3 4 5 6 7 8 9 10 11 字符 A A B B C B B A A B C 步驟 位置 匹配串 輸出 1 1 －－ A 2 2 A A 3 3 －－ B 4 4 B B 5 5 －－ C 6 6 BB （ 3， 2） 7 8 AAB （ 7， 3） 8 11 C C 輸入數(shù)據(jù)流： 編碼過程 MIN_LEN =2 50 LZSS算法 ? 在相同的計(jì)算機(jī)環(huán)境下， LZSS算法比 LZ77可獲得比較高的壓縮比，而譯碼同樣簡單。這也就是為什么這種算法成為開發(fā)新算法的基礎(chǔ)，許多后來開發(fā)的文檔壓縮程序都使用了 LZSS的思想。例如， PKZip, GZip, ARJ, LHArc和 ZOO等等，其差別僅僅是指針的長短和窗口的大小等有所不同。 ? LZSS同樣可以和熵編碼聯(lián)合使用，例如 ARJ就與霍夫曼編碼聯(lián)用，而 PKZip則與 ShannonFano聯(lián)用，它的后續(xù)版本也采用霍夫曼編碼。 51 第二類詞典編碼 ? 第二類算法的想法是企圖從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)“短語詞典 (dictionary of the phrases)”， 這種短語可以是任意字符的組合。編碼數(shù)據(jù)過程中當(dāng)遇到已經(jīng)在詞典中出現(xiàn)的“短語”時(shí)，編碼器就輸出這個(gè)詞典中的短語的“索引號(hào)”，而不是短語本身。 52 LZ78算法 ? LZ78的編碼思想是不斷地從字符流中提取新的字符串 (String)， 通俗地理解為新“詞條”，然后用“代號(hào)”也就是碼字 (Code word)表示這個(gè)“詞條”。這樣一來，對(duì)字符流的編碼就變成了用碼字 (Code word)去替換字符流 (Char stream)， 生成碼字流 (Code stream)， 從而達(dá)到壓縮數(shù)據(jù)的目的。 ? LZ78編碼器的輸出是碼字 字符 (W,C)對(duì)，每次輸出一對(duì)到碼字流中，與碼字 W相對(duì)應(yīng)的字符串(String)用字符 C進(jìn)行擴(kuò)展生成新的字符串 (String)，然后添加到詞典中。 53 LZ78編碼算法 步驟 1：將詞典和當(dāng)前前綴 P都初始化為空。 步驟 2：當(dāng)前字符 C:=字符流中的下一個(gè)字符。 步驟 3：判斷 P＋ C是否在詞典中 （ 1）如果“是”，則用 C擴(kuò)展 P， 即讓 P:=P＋ C， 返回到步驟 2。 （ 2）如果“否”，則 輸出與當(dāng)前前綴 P相對(duì)應(yīng)的碼字 W和當(dāng)前字符 C， 即（ W， C）； 將 P＋ C添加到詞典中； 令 P:=空值，并返回到步驟 2 54 LZ78編碼舉例 位置 1 2 3 4 5 6 7 8 9 字符 A B B C B C A B A 步驟 位置 詞典 輸出 1 1 A (0, A) 2 2 B (0, B) 3 3 BC (2, C) 4 5 BCA (3, A) 5 8 BA (2, A) 輸入數(shù)據(jù)流： 編碼過程： 55 LZW算法 1978年首次發(fā)表了介紹第二類詞典編碼算法的文章。在他們的研究基礎(chǔ)上， Terry 1984年發(fā)表了改進(jìn)這種編碼算法的文章，因此把這種編碼方法稱為 LZW(LempelZiv Walch)壓縮編碼。 在編碼原理上， LZW與 LZ78相比有如下差別： LZW只輸出代表詞典中的字符串 (String)的碼字 (code word)。 這就意味在開始時(shí)詞典不能是空的，它必須包含可能在字符流出現(xiàn)中的所有單個(gè)字符 。 即在編碼匹配時(shí)，至少可以在詞典中找到長度為 1的匹配串。 LZW編碼是圍繞稱為詞典的轉(zhuǎn)換表來完成的。 56 LZW算法的詞典 LZW編碼器 (軟件編碼器或硬件編碼器 )就是通過管理這個(gè)詞典完成輸入與輸出之間的轉(zhuǎn)換。 LZW編碼器的輸入是字符流 (Char stream)， 字符流可以是用 8位 ASCII字符組成的字符串，而輸出是用 n位(例如 12位 )表示的碼字流 (Code stream)， 碼字代表單個(gè)字符或多個(gè)字符組成的字符串(String)。 57 LZW編碼算法 步驟 1：將詞典初始化為包含所有可能的單字符，當(dāng)前前綴 P初始化為空。 步驟 2：當(dāng)前字符 C:=字符流中的下一個(gè)字符。 步驟 3：判斷 P＋ C是否在詞典中 （ 1）如果“是”，則用 C擴(kuò)展 P， 即讓 P:=P＋ C， 返回到步驟 2。 （ 2）如果“否”，則 輸出與當(dāng)前前綴 P相對(duì)應(yīng)的碼字 W； 將 P＋ C添加到詞典中； 令 P:=C，并返回到步驟 2 58 LZW編碼舉例 位置 1 2 3 4 5
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1