數(shù)據(jù)壓縮基礎(chǔ)ppt課件-文庫吧資料
2024-11-09 22:14本頁面
【正文】 下， LZSS算法比 LZ77可獲得比較高的壓縮比，而譯碼同樣簡單。 其中 off 為窗口中匹配字符串相對窗口邊界的偏移， len 為匹配串的長度，然后將窗口向后滑動 len 個字符，繼續(xù)步驟 1。 48 LZSS編碼的基本流程 從當(dāng)前壓縮位置開始，考察未編碼的字符，并試圖在滑動窗口中找出最長的匹配字符串，如果匹配串長度 len大于等于最小匹配串長度（ len = MIN_LENGTH）， 則進(jìn)行步驟 2，否則進(jìn)行步驟 3。 ? LZSS算法的思想是如果匹配串的長度比指針本身的長度長就輸出指針（匹配串長度大于等于MIN_LENGTH）， 否則就輸出真實(shí)字符。 45 LZ77算法 46 LZ77編碼舉例 A A B C B B A B C A 步驟 位置 匹配串 輸出 1 1 －－ 0, 0, A 2 2 A 1, 1, B 3 4 －－ 0, 0, C 4 5 B 2, 1, B 5 7 ABC 5, 3, A 47 LZSS算法 ? LZ77通過輸出真實(shí)字符解決了在窗口中出現(xiàn)沒有匹配串的問題，但這個解決方案包含有冗余信息。 其中 c 為下一個字符。然后將窗口向后滑動 len + 1 個字符，繼續(xù)步驟 1。 輸出三元符號組 ( off, len, c )。使用固定大小窗口進(jìn)行詞語匹配，而不是在所有已經(jīng)編碼的信息中匹配，是因?yàn)槠ヅ渌惴ǖ臅r間消耗往往很多，必須限制詞典的大小才能保證算法的效率；隨著壓縮的進(jìn)程滑動詞典窗口，使其中總包含最近編碼過的信息，是因?yàn)閷Υ蠖鄶?shù)信息而言，要編碼的字符串往往在最近的上下文中更容易找到匹配串。 42 第一類詞典編碼 ? 第一類詞典法的想法是企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，然后用已經(jīng)出現(xiàn)過的字符串替代重復(fù)的部分，它的輸出僅僅是指向早期出現(xiàn)過的字符串的 “ 指針 ” 。字符串與代號的對應(yīng)表就是詞典。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。因?yàn)榇L度并非等概率分布，所以一般要配合以統(tǒng)計編碼（ Huffman編碼）。 ? 行程編碼多用于黑白二值圖像的壓縮中。 39 自適應(yīng)算術(shù)編碼舉例 c b a c 1/3 1/4 2/5 3/6 b 1/3 2/4 2/5 2/6 a 1/3 1/4 1/5 1/6 輸入序列為： bcc………. 40 行程編碼（ RLE） ? 行程編碼（ RunLength Encoding）： 它通過將信源中相同符號序列轉(zhuǎn)換成一個計數(shù)字段再加上一個重復(fù)字符標(biāo)志實(shí)現(xiàn)壓縮。 二進(jìn)制算術(shù)編碼 是一種實(shí)用的編碼算法，用移位代替了乘法，使效率大大提高。 36 算術(shù)編碼舉例（一） 符號 00 01 10 11 概率 初始區(qū)間 [0, ) [, ) [, ) [, 1) 37 算術(shù)編碼舉例（二） ? 最后的子區(qū)間起始位置＝ 85/256 = ? 子區(qū)間長度 ＝ 27/256 = ? 子區(qū)間尾 ＝ 7/16 = ? 取編碼區(qū)間中的一個值，最后編碼為： 011 符號 0 1 頻度 1/4 3/4 消息序列 1 0 1 1 區(qū)間起始 1/4 1/4 19/64 85/256 區(qū)間長度 3/4 3/16 9/64 27/256 信源分布： 38 算術(shù)編碼的具體實(shí)現(xiàn) ? 因?yàn)閷?shí)際只能用有限長的寄存器，這就要求將已編碼的高位碼字及時輸出，但又不能輸出過早，以免后續(xù)運(yùn)算還要調(diào)整已輸出的碼位。消息序列中元素越多，所得到的區(qū)間就越小，當(dāng)區(qū)間變小時，就需要更多的數(shù)位來表示這個區(qū)間。 35 算術(shù)編碼 ? 基本思想：算術(shù)編碼不是將單個信源符號映射成一個碼字， 而是把真?zhèn)€信源表示為實(shí)數(shù)線上的 0到 1之間的一個區(qū)間，其長度等于該序列的概率，再在該區(qū)間內(nèi)選擇一個代表性的小數(shù)，轉(zhuǎn)化為二進(jìn)制作為實(shí)際的編碼輸出 。假設(shè)某個字符的出現(xiàn)概率為 80%，該字符事實(shí)上只需要 log2() = 位編碼，但 Huffman 編碼一定會為其分配一位 0 或一位 1 的編碼。 （ 3）編碼。 （ 2）用遞歸的方法分成兩部分，使兩個部分的概率和接近于相等。 ? 輸入符號數(shù)受限于可實(shí)現(xiàn)的碼表尺寸 ? 譯碼復(fù)雜 ? 需要實(shí)現(xiàn)知道輸入符號集的概率分布 ? 沒有錯誤保護(hù)功能 32 香農(nóng)－范諾編碼 ? 香農(nóng)－范諾編碼與 Huffman編碼相反，采用從上到下的方法。 ),...,|( 121lim ??? nnnXXXXH28 熵編碼 ? 熵編碼 包括香農(nóng)－范諾編碼、霍夫曼編碼和算術(shù)編碼，其宗旨在于找到一種編碼使得平均碼長到達(dá)熵極限，基本思想就是對出現(xiàn)概率較大的符號取較短的碼長，而對出現(xiàn)概率較小的符號取較大的碼長。 ? 壓縮的基本途徑之三：可利用條件概率進(jìn)行編碼，階越高越有利。 25 聯(lián)合熵與條件熵 ? 設(shè)隨機(jī)變量 X和 Y分別取值于符號表 {a1, a2, …a m}和 {b1, b2, b3, …b n} ? 定義 X與 Y的聯(lián)合熵為： ? 定義 X關(guān)于 Y的條件熵為： ? ?? ???mjnkkjkj baPbaPYXH1 1),(l o g),(),(? ?? ???mjnkkjkj baPbaPYXH1 1)|(l o g),()|(26 離散有記憶信源的冗余 )()|( XHYXH ?)()()|()(),( YHXHXYHXHYXH ????聯(lián)合熵與其可能達(dá)到的最大值之
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1