【文章內(nèi)容簡介】 法編碼方法，不僅不能壓縮圖像數(shù)據(jù)，反而可能使原來的圖像數(shù)，不僅不能壓縮圖像數(shù)據(jù)，反而可能使原來的圖像數(shù)據(jù)變得更大。據(jù)變得更大。 ? 譯碼時按照與編碼時采用的相同規(guī)則進行，還原后得譯碼時按照與編碼時采用的相同規(guī)則進行，還原后得到的數(shù)據(jù)與壓縮前的數(shù)據(jù)完全相同。因此，到的數(shù)據(jù)與壓縮前的數(shù)據(jù)完全相同。因此， RLE屬于屬于無損壓縮技術(shù)。無損壓縮技術(shù)。行程編碼的應(yīng)用行程編碼的應(yīng)用 算術(shù)編碼（算術(shù)編碼（ arithmetic coding AC））l20世紀世紀 60年代初，年代初， Elias提出了算術(shù)編碼概提出了算術(shù)編碼概念；念； 1976年，年， Rissanen和和 Pasco首次介紹了首次介紹了它的實用技術(shù)。它的實用技術(shù)。l基本原理：基本原理： 將編碼的信息序列表示成實數(shù)將編碼的信息序列表示成實數(shù) 0和和 1之間的一個間隔之間的一個間隔 (Interval)，信息序列，信息序列越長，編碼表示它的間隔就越小，表示這越長，編碼表示它的間隔就越小，表示這一間隔所需的二進制位就越多。一間隔所需的二進制位就越多。假設(shè)某個字符的出現(xiàn)概率為 80% ，該字符事實上只需要 log2() = 個二進制位進行編碼。難道真的能只輸出 個 0 或 個 1 嗎？算術(shù)編碼的輸出是：一個小數(shù)算術(shù)編碼對整條信息（無論信息有多么長），其輸出僅僅是一個數(shù)，而且是一個介于 0和 1之間的二進制小數(shù)。例如算術(shù)編碼對某條信息的輸出為 1010001111，那么它表示小數(shù)，也即十進制數(shù) 算術(shù)編碼算術(shù)編碼例： 假設(shè)信源符號為 {A, B, C, D}，這些符號的概率分別為 { , , , }，根據(jù)這些概率可把間隔 [0, 1]分成 4個子間隔： [0, ） , [, ） , [, ） , [, 1），其中 [x,y） 表示半開放間隔，即包含 x不包含 y，如表 21所示。符號符號 A B C D概率概率 初始編碼間隔初始編碼間隔 [0,））[,））[,）） [,1））表 21 信源符號、概率和初始編碼間隔如果消息序列的輸入為： CADACDB，其編碼過程如下：首先輸入的符號是 C，找到它的編碼范圍是 [, ）；由于消息中第 2個符號 A的編碼范圍是 [0, ），因此它的間隔就取[, ）的第一個 1/10作為新間隔 [, ）；編碼第 3個符號 D時取新間隔為 [, ）；編碼第 4個符號 A時，取新間隔為 [, ）， … 。算術(shù)編碼過程算術(shù)編碼過程消息的編碼輸出可以是最后一個間隔中的任意數(shù)，整個編碼過程如圖 43所示。最后在 [,） 中選擇一個數(shù)作為編碼輸出值：。解碼時，解碼器由編碼輸出值： ，可馬上解得一個字符為 C，然后依次得到唯一解 A,D,A,C,D,B。Character probability Range ^(space) 1/10 A 1/10 B 1/10 E 1/10 G 1/10 I 1/10 L 2/10 S 1/10 T 1/10算術(shù)編碼示例算術(shù)編碼示例T^GILSABE IL L^算術(shù)編碼示例算術(shù)編碼示例 (續(xù)續(xù) )編碼輸入符號序列編碼輸入符號序列 : BILL^ GATES– New character Low value High value– B – I – L – L – ^(space) – G – A – T – E – S 算術(shù)編碼示例算術(shù)編碼示例 (續(xù)續(xù) )最終編碼（標簽）是 ，它可以通過解碼還原初始序列? 解碼是編碼的逆過程解碼是編碼的逆過程? 因為因為 位于位于 至至 , 所以解碼的第所以解碼的第一個字符是一個字符是 ‘B’.? 通過減去通過減去 ‘B’的最低值，去除的最低值，去除 ’B’的影響。碼值變?yōu)椋旱挠绊?。碼值變?yōu)椋?? 碼值除以碼值除以 ‘B’的范圍的范圍 ，碼值變?yōu)椋?，碼值變?yōu)椋? .? 碼值落入碼值落入 ‘I’的范圍的范圍? 重復(fù)上述過程，直到重復(fù)上述過程，直到 0值或字符序列長度為止值或字符序列長度為止解碼過程解碼過程解碼結(jié)果解碼結(jié)果r c Low High range B I L L ^(space) G A T E S 詞典編碼詞典編碼l 通用編碼技術(shù)：通用編碼技術(shù)： 有許多場合，開始時有許多場合，開始時不知道要編碼數(shù)據(jù)的統(tǒng)計特性，也不不知道要編碼數(shù)據(jù)的統(tǒng)計特性，也不一定允許你事先知道它們的統(tǒng)計特一定允許你事先知道它們的統(tǒng)計特性。性。l 詞典編碼：詞典編碼： 主要利用數(shù)據(jù)本身包含有主要利用數(shù)據(jù)本身包含有重復(fù)代碼這個特性。例如文本文件和重復(fù)代碼這個特性。例如文本文件和光柵圖像就具有這種特性。光柵圖像就具有這種特性。l 詞典編碼法分類：詞典編碼法分類：l 指針法指針法l 索引法索引法 詞典編碼詞典編碼l 通用編碼技術(shù)：通用編碼技術(shù)： 有許多場合，開始時有許多場合，開始時不知道要編碼數(shù)據(jù)的統(tǒng)計特性，也不不知道要編碼數(shù)據(jù)的統(tǒng)計特性，也不一定允許你事先知道它們的統(tǒng)計特一定允許你事先知道它們的統(tǒng)計特性。性。l 詞典編碼：詞典編碼： 主要利用數(shù)據(jù)本身包含有主要利用數(shù)據(jù)本身包含有重復(fù)代碼這個特性。例如文本文件和重復(fù)代碼這個特性。例如文本文件和光柵圖像就具有這種特性。光柵圖像就具有這種特性。l 詞典編碼法分類：詞典編碼法分類：l 指針法指針法l 索引法索引法指針法指針法查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，然后用已經(jīng)出現(xiàn)過的字符串替代重復(fù)的出現(xiàn)過，然后用已經(jīng)出現(xiàn)過的字符串替代重復(fù)的部分，它的輸出僅僅是指向早期出現(xiàn)過的字符串部分，它的輸出僅僅是指向早期出現(xiàn)過的字符串的的 “指針指針 ”。典型算法為。典型算法為 LZ77算法及算法及 LZSS算法。算法。索引法索引法從輸入的數(shù)據(jù)中創(chuàng)建一個從輸入的數(shù)據(jù)中創(chuàng)建一個 “短語詞典短語詞典 (dictionary of the phrases)”，這種短語不一定是像，這種短語不一定是像 “嚴謹勤奮求實創(chuàng)新嚴謹勤奮求實創(chuàng)新 ”和和 “國泰民安是坐穩(wěn)總統(tǒng)寶座的根本國泰民安是坐穩(wěn)總統(tǒng)寶座的根本 ”這類具有具體含這類具有具體含義的短語，它可以是任意字符的組合。編碼數(shù)據(jù)過程義的短語，它可以是任意字符的組合。編碼數(shù)據(jù)過程中當遇到已經(jīng)在詞典中出現(xiàn)的中當遇到已經(jīng)在詞典中出現(xiàn)的 “短語短語 ”時，編碼器就輸時，編碼器就輸出這個詞典中的短語的出這個詞典中的短語的 “索引號索引號 ”，而不是短語本身。，而不是短語本身。LZ77算法算法 (指針法指針法 )字典模型：《現(xiàn)代漢語詞典》以及下面的例子L77算法算法主要術(shù)語：主要術(shù)語：1. 輸入數(shù)據(jù)流輸入數(shù)據(jù)流 (input stream)：要被壓縮的字符：要被壓縮的字符序列。序列。 2. 字符字符 (character)：輸入數(shù)據(jù)流中的基本單元。：輸入數(shù)據(jù)流中的基本單元。 3. 編碼位置編碼位置 (coding position)：輸入數(shù)據(jù)流中當：輸入數(shù)據(jù)流中當前要編碼的字符位置，指前向緩沖存儲器中的前要編碼的字符位置，指前向緩沖存儲器中的開始字符。開始字符。 4. 前向緩沖存儲器前向緩沖存儲器 (Lookahead buffer)：存放從：存放從編碼位置到輸入數(shù)據(jù)流結(jié)束的字符序列的存儲編碼位置到輸入數(shù)據(jù)流結(jié)束的字符序列的存儲器。器。 5. 窗口窗口 (window)：指包含已編碼：指包含已編碼 WW 個字符的窗個字符的窗口?？?。 6. 指針指針 (pointer)：指向窗口中的匹配串且含長度：指向窗口中的匹配串且含長度的指針。的指針。LZ77編碼算法編碼算法? 編碼算法的具體執(zhí)行步驟如下：– （１）把編碼位置設(shè)置到輸入數(shù)據(jù)流的開始位置。 – （２）查找窗口中最長的匹配串。 – （３）以 “ (Pointer, Length) Characters” 的格式輸出，其中 Pointer是指向窗口中匹配串的指針， Length表示匹配字符的長度，Characters是前向緩沖存儲器中的不匹配的第 1個字符。 – （４）如果前向緩沖存儲器不是空的，則把編碼