王詠剛20xx年2月(編輯修改稿)
2024-11-17 08:38 本頁面
【文章內(nèi)容簡(jiǎn)介】 ) = 個(gè)二進(jìn)制位進(jìn)行編碼 難道真的能只輸出 個(gè) 0 或 個(gè) 1 嗎？ 算術(shù)編碼的輸出是：一個(gè)小數(shù) 算術(shù)編碼對(duì)整條信息（無論信息有多么長(zhǎng)），其輸出僅僅是一個(gè)數(shù)，而且是一個(gè)介于 0和 1之間的二進(jìn)制小數(shù)。 例如算術(shù)編碼對(duì)某條信息的輸出為 1010001111，那么它表示小數(shù) ，也即十進(jìn)制數(shù) 算術(shù)編碼 例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb 第一步 ：在沒有開始?jí)嚎s進(jìn)程之前，假設(shè)我們對(duì) a b c 三者在信息中的出現(xiàn)概率一無所知（我們采用的是自適應(yīng)模型），即認(rèn)為三者的出現(xiàn)概率相等，也就是都為 1/3，我們將 01區(qū)間按照概率的比例分配給三個(gè)字符，即 a從 ， b從 ， c從 。用圖形表示就是： Pc = 1/3 Pb = 1/3 Pa = 1/3 算術(shù)編碼 第二步 ：現(xiàn)在我們拿到第一個(gè)字符 b， 讓我們把目光投向 b對(duì)應(yīng)的區(qū)間。這時(shí)由于多了字符 b， 三個(gè)字符的概率分布變成：Pa=1/4， Pb=2/4， Pc=1/4。 好，讓我們按照新的概率分布比例劃分，劃分的結(jié)果可以用圖形表示為： Pc = 1/4 Pb = 2/4 Pa = 1/4 例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb 算術(shù)編碼 第三步 ：接著我們拿到字符 c， 我們現(xiàn)在要關(guān)注上一步中得到的 c的區(qū)間 。新添了 c以后，三個(gè)字符的概率分布變成 Pa=1/5，Pb=2/5， Pc=2/5。 我們用這個(gè)概率分布劃分區(qū)間 ： Pc = 2/5 Pb = 2/5 Pa = 1/5 例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb 算術(shù)編碼 第四步 ：現(xiàn)在輸入下一個(gè)字符 c， 三個(gè)字符的概率分布為： Pa=1/6，Pb=2/6， Pc=3/6。 我們來劃分 c的區(qū)間 ： Pc = 3/6 Pb = 2/6 Pa = 1/6 例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb 算術(shù)編碼 第五步 ：輸入最后一個(gè)字符 b， 因?yàn)槭亲詈笠粋€(gè)字符，不用再做進(jìn)一步的劃分了，上一步中得到的 b的區(qū)間為 ，好，讓我們?cè)谶@個(gè)區(qū)間內(nèi)隨便選擇一個(gè)容易變成二進(jìn)制的數(shù)，例如 ，將它變成二進(jìn)制 ，去掉前面沒有太多意義的 0和小數(shù)點(diǎn)，我們可以輸出1010001111，這就是信息被壓縮后的結(jié)果，我們完成了一次最簡(jiǎn)單的算術(shù)壓縮過程 Pc = 3/6 Pb = 2/6 Pa = 1/6 例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb 輸出 :()10 = ()2 自適應(yīng)模型的階 h(t) (t) gh(t) igh(t) 例文： the weight of ... 0階 1階 2階 3階 問題： 1. 半靜態(tài)模型和自適應(yīng)模型 2. 轉(zhuǎn)義碼的使用 3. 存儲(chǔ)空間問題 LZ77算法 字典模型：《現(xiàn)代漢語詞典》以及下面的例子 LZ77算法 LZ77算法的基本流程： “ 滑動(dòng)的窗口 ” 從當(dāng)前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動(dòng)窗口中找出最長(zhǎng)的匹配字符串，如果找到，則進(jìn)行步驟 2，否則進(jìn)行步驟 3。 輸出三元符號(hào)組 (off,len,c)。 其中 off為窗口中匹配字符串相對(duì)窗口邊界的偏移， len為可匹配的長(zhǎng)度， c為下一個(gè)字符。然后將窗口向后滑動(dòng) len+1個(gè)字符，繼續(xù)步驟 1。 輸出三元符號(hào)組 (0,0,c)。 其中 c為下一個(gè)字符。然后將窗口向后滑動(dòng) len+1個(gè)字符，繼續(xù)步驟 1。 LZ77算法 應(yīng)用實(shí)例：窗口大小為 10個(gè)字符，剛編碼過的 10個(gè)字符為 “ abcdbbccaa” ，即將編碼的 10個(gè)字符為 “ abaeaaabaee” 。 1. 我們首先發(fā)現(xiàn)，可以和待編碼字符匹配的最長(zhǎng)串為 ab(off=0,len=2), ab的下一個(gè)字符為 a， 我們輸出三元組： (0,2,a) 2. 現(xiàn)在窗口向后滑動(dòng) 3個(gè)字符，窗口中的內(nèi)容為： dbbccaaaba 3. 下一個(gè)字符 e在窗口中沒有匹配，我們輸出三元組： (0,0,e) 4. 窗口向后滑動(dòng) 1個(gè)字符，其中內(nèi)容變?yōu)椋?bbccaaabae 5. 我們馬上發(fā)現(xiàn)，要編碼的 aaabae在窗口中存在 (off=4,len=6)， 其后的字符為 e， 我們可以輸出： (4,6,e) 6. 這樣，我們將可以匹配的字符串都變成了指向窗口內(nèi)的指針，并由此完成了對(duì)上述數(shù)據(jù)的壓縮。 7. 解壓縮時(shí)，只要我們向壓縮時(shí)那樣維護(hù)好滑動(dòng)的窗口，隨著三元組的不斷輸入，我們?cè)诖翱谥姓业较鄳?yīng)的匹配串，綴上后繼字符 c輸出（如果 off和 len都為 0則只輸出后繼字符 c)即可還原出原始數(shù)據(jù)。 LZ77算法 三元組的編碼方法（編碼方式取決于數(shù)據(jù)的分布概率）： 1. 對(duì)于第一個(gè)分量 ——窗口內(nèi)的偏移
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1