數(shù)據(jù)壓縮基礎ppt課件(編輯修改稿)
2024-11-30 22:14 本頁面
【文章內(nèi)容簡介】 A B C D E A B C D E D E 符號 A B C D E 次數(shù) 15 7 7 6 5 0 1 0 1 0 0 1 1 34 算術編碼 ? Huffman 編碼的局限性： Huffman 編碼使用整數(shù)個二進制位對符號進行編碼，這種方法在許多情況下無法得到最優(yōu)的壓縮效果。假設某個字符的出現(xiàn)概率為 80%，該字符事實上只需要 log2() = 位編碼，但 Huffman 編碼一定會為其分配一位 0 或一位 1 的編碼?？梢韵胂?，整個信息的 80% 在壓縮后都幾乎相當于理想長度的 3 倍左右。 35 算術編碼 ? 基本思想：算術編碼不是將單個信源符號映射成一個碼字， 而是把真?zhèn)€信源表示為實數(shù)線上的 0到 1之間的一個區(qū)間，其長度等于該序列的概率，再在該區(qū)間內(nèi)選擇一個代表性的小數(shù)，轉(zhuǎn)化為二進制作為實際的編碼輸出 。消息序列中的每個元素都要用來縮短這個區(qū)間。消息序列中元素越多，所得到的區(qū)間就越小，當區(qū)間變小時，就需要更多的數(shù)位來表示這個區(qū)間。 ? 采用算術編碼每個符號的平均編碼長度可以為小數(shù)。 36 算術編碼舉例（一） 符號 00 01 10 11 概率 初始區(qū)間 [0, ) [, ) [, ) [, 1) 37 算術編碼舉例（二） ? 最后的子區(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 算術編碼的具體實現(xiàn) ? 因為實際只能用有限長的寄存器，這就要求將已編碼的高位碼字及時輸出，但又不能輸出過早，以免后續(xù)運算還要調(diào)整已輸出的碼位。（請看參考書上給出的算法） ? 算術編碼每次遞推都要做乘法，所以效率比較低。 二進制算術編碼 是一種實用的編碼算法，用移位代替了乘法，使效率大大提高。 ? 自適應算術編碼 可以在編碼過程中根據(jù)符號出現(xiàn)的頻繁程度動態(tài)的修改分布概率，這樣可以避免在編碼之前必須精確求出信源概率的難題。 39 自適應算術編碼舉例 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ù)字段再加上一個重復字符標志實現(xiàn)壓縮。 ? 例如： RTTTTTTTTABBCDG被轉(zhuǎn)換為：R8TABBCDG， 其中“＃”作為轉(zhuǎn)義字符，表明其后所跟的字符表示長度。 ? 行程編碼多用于黑白二值圖像的壓縮中。例如00000000111111111111000001111111被轉(zhuǎn)化為一系列黑串和白串長度的編碼： 81257。因為串長度并非等概率分布，所以一般要配合以統(tǒng)計編碼（ Huffman編碼）。 41 詞典編碼 ? 詞典編碼主要利用數(shù)據(jù)本身包含許多重復的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。 我們?nèi)绻靡恍┖唵蔚拇柎孢@些字符串，就可以實現(xiàn)壓縮，實際上就是利用了信源符號之間的相關性。字符串與代號的對應表就是詞典。 ? 實用的詞典編碼算法的核心就是如何動態(tài)地形成詞典，以及如何選擇輸出格式以減小冗余。 42 第一類詞典編碼 ? 第一類詞典法的想法是企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，然后用已經(jīng)出現(xiàn)過的字符串替代重復的部分，它的輸出僅僅是指向早期出現(xiàn)過的字符串的 “ 指針 ” 。 43 LZ77算法 ? LZ77 算法在某種意義上又可以稱為“滑動窗口壓縮”，該算法將一個虛擬的，可以跟隨壓縮進程滑動的窗口作為詞典，要壓縮的字符串如果在該窗口中出現(xiàn)，則輸出其出現(xiàn)位置和長度。使用固定大小窗口進行詞語匹配，而不是在所有已經(jīng)編碼的信息中匹配，是因為匹配算法的時間消耗往往很多，必須限制詞典的大小才能保證算法的效率；隨著壓縮的進程滑動詞典窗口，使其中總包含最近編碼過的信息，是因為對大多數(shù)信息而言，要編碼的字符串往往在最近的上下文中更容易找到匹配串。 44 LZ77編碼的基本流程 從當前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動窗口中找出最長的匹配字符串，如果找到，則進行步驟 2，否則進行步驟 3。 輸出三元符號組 ( off, len, c )。 其中 off 為窗口中匹配字符串相對窗口邊界的偏移， len 為可匹配的長度， c 為下一個字符，即不匹配的第一個字符。然后將窗口向后滑動 len + 1 個字符，繼續(xù)步驟 1。 輸出三元符號組 ( 0, 0, c )。 其中 c 為下一個字符。然后將窗口向后滑動 1 個字符，繼續(xù)步驟 1。 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通過輸出真實字符解決了在窗口中出現(xiàn)沒有匹配串的問題，但這個解決方案包含有冗余信息。冗余信息表現(xiàn)在兩個方面，一是空指
教學課件相關推薦
鄂ICP備17016276號-1