【正文】 – （４）如果前向緩沖存儲(chǔ)器不是空的，則把編碼位置和窗口向前移 (Length+1)個(gè)字符，然后返回到步驟 2。 – （２）查找窗口中最長的匹配串。的指針?？?。器。開始字符。：輸入數(shù)據(jù)流中的基本單元。序列。而不是短語本身。編碼數(shù)據(jù)過程義的短語，它可以是任意字符的組合。算法。典型算法為。光柵圖像就具有這種特性。例如文本文件和重復(fù)代碼這個(gè)特性。性。光柵圖像就具有這種特性。例如文本文件和重復(fù)代碼這個(gè)特性。性。碼值變?yōu)椋旱挠绊?。解碼時(shí)，解碼器由編碼輸出值： ，可馬上解得一個(gè)字符為 C，然后依次得到唯一解 A,D,A,C,D,B。算術(shù)編碼過程算術(shù)編碼過程消息的編碼輸出可以是最后一個(gè)間隔中的任意數(shù)，整個(gè)編碼過程如圖 43所示。例如算術(shù)編碼對某條信息的輸出為 1010001111，那么它表示小數(shù)，也即十進(jìn)制數(shù) 算術(shù)編碼算術(shù)編碼例： 假設(shè)信源符號(hào)為 {A, B, C, D}，這些符號(hào)的概率分別為 { , , , }，根據(jù)這些概率可把間隔 [0, 1]分成 4個(gè)子間隔： [0, ） , [, ） , [, ） , [, 1），其中 [x,y） 表示半開放間隔，即包含 x不包含 y，如表 21所示。假設(shè)某個(gè)字符的出現(xiàn)概率為 80% ，該字符事實(shí)上只需要 log2() = 個(gè)二進(jìn)制位進(jìn)行編碼。l基本原理：基本原理： 將編碼的信息序列表示成實(shí)數(shù)將編碼的信息序列表示成實(shí)數(shù) 0和和 1之間的一個(gè)間隔之間的一個(gè)間隔 (Interval)，信息序列，信息序列越長，編碼表示它的間隔就越小，表示這越長，編碼表示它的間隔就越小，表示這一間隔所需的二進(jìn)制位就越多。行程編碼的應(yīng)用行程編碼的應(yīng)用 算術(shù)編碼（算術(shù)編碼（ arithmetic coding AC））l20世紀(jì)世紀(jì) 60年代初，年代初， Elias提出了算術(shù)編碼概提出了算術(shù)編碼概念；念； 1976年，年， Rissanen和和 Pasco首次介紹了首次介紹了它的實(shí)用技術(shù)。因此， RLE屬于屬于無損壓縮技術(shù)。 ? 譯碼時(shí)按照與編碼時(shí)采用的相同規(guī)則進(jìn)行，還原后得譯碼時(shí)按照與編碼時(shí)采用的相同規(guī)則進(jìn)行，還原后得到的數(shù)據(jù)與壓縮前的數(shù)據(jù)完全相同。? 然而，由于顏色豐富的自然圖像在同一行上具有相同然而，由于顏色豐富的自然圖像在同一行上具有相同顏色的連續(xù)像素往往很少，而連續(xù)幾行都具有相同顏顏色的連續(xù)像素往往很少，而連續(xù)幾行都具有相同顏色值的連續(xù)行數(shù)就更少，如果仍然使用色值的連續(xù)行數(shù)就更少，如果仍然使用 RLE編碼方法編碼方法，不僅不能壓縮圖像數(shù)據(jù)，反而可能使原來的圖像數(shù)，不僅不能壓縮圖像數(shù)據(jù)，反而可能使原來的圖像數(shù)據(jù)變得更大。 RLE壓壓縮編碼尤其適用于計(jì)算機(jī)生成的圖像，對減少圖像文縮編碼尤其適用于計(jì)算機(jī)生成的圖像，對減少圖像文件的存儲(chǔ)空間非常有效。 如數(shù)字序列：如數(shù)字序列： 742300000000000000000055 編碼為：編碼為： 7423Z1855行程編碼示例行程編碼示例? RLE的性能好壞主要取決于圖像本身的特點(diǎn)。確實(shí)是一種壓縮技術(shù)，而且編碼技術(shù)實(shí)用。這說明。例如斜體字 50代表有連續(xù)代表有連續(xù) 50個(gè)像素具個(gè)像素具有相同的顏色值，它的顏色值是有相同的顏色值，它的顏色值是 8。? 代碼斜體表示的數(shù)字是行程長度，斜體字后面的數(shù)字代代碼斜體表示的數(shù)字是行程長度，斜體字后面的數(shù)字代表像素的顏色值。代。最簡單的編碼方法之一。有所下降。通?？稍诮?jīng)碼，這就限制了實(shí)際的應(yīng)用。的效率高，是最佳變長碼。一般。方式得到的平均碼字長度。于概率小的符號(hào)編以長字長的碼。位。平均碼長 Lc的計(jì)算公式為：（ j=1,2,… ,n）其中： P(xj) 是信源 X發(fā)出 xj的概率， L(xj)為 xj的編碼長度。Lc＝ H(S) 最佳編碼（ Lc稍大于 H(S)）。若以 Lc表示編碼器輸出碼字的平均碼長，則當(dāng)Lc≥H(S) 有冗余，不是最佳。? 信源 S發(fā)出的 xj（ j=1,2,…,n ） 共 n個(gè)隨機(jī)事件的自信息統(tǒng)計(jì)平均，即? H(X)稱為信源 X的 “熵 ”，即信源 X發(fā)出任意一個(gè)隨機(jī)變量的平均信息量。 I(xj)的含義是，信源 X發(fā)出xj這個(gè)消息（隨機(jī)事件）后，接收端收到的信息的量度。 數(shù)據(jù)壓縮編碼方法分類數(shù)據(jù)壓縮編碼方法分類分類方法二：壓縮編碼方法的原理進(jìn)行分類分類方法二：壓縮編碼方法的原理進(jìn)行分類1）統(tǒng)計(jì)編碼）統(tǒng)計(jì)編碼 : Huffman， Shannon， REL,詞典編碼詞典編碼2）預(yù)測編碼）預(yù)測編碼 : PCM， DPCM， DM， LPC3) 變換編碼變換編碼 : DCT4) 子帶（子帶（ subband)編碼編碼5) 模型編碼模型編碼壓縮技術(shù)分類通用數(shù)據(jù)壓縮（均為無損壓縮）通用數(shù)據(jù)壓縮（均為無損壓縮） 多媒體數(shù)據(jù)壓縮（無損和有損壓縮）多媒體數(shù)據(jù)壓縮（無損和有損壓縮）基于統(tǒng)計(jì)模型基于統(tǒng)計(jì)模型的壓縮技術(shù)的壓縮技術(shù)基于字典模型基于字典模型的壓縮技術(shù)的壓縮技術(shù)Huffman編碼編碼算術(shù)編碼算術(shù)編碼LZ77 LZ78 LZW圖像壓縮圖像壓縮 音頻和視頻壓縮音頻和視頻壓縮MPEG等等二值圖像二值圖像CCITTJBIG等等灰度圖像灰度圖像FELICSJPEG等等彩色圖像彩色圖像RLE編碼編碼JPEG等等矢量圖像矢量圖像PostScriptWMFCAD等等壓縮技術(shù)的應(yīng)用壓縮技術(shù)的應(yīng)用電報(bào)、傳真 (CCITT)通訊 (Modem/網(wǎng)絡(luò)協(xié)議 )存儲(chǔ) (壓縮池 )文件系統(tǒng) (壓縮扇區(qū) )圖像 (GIF/TIFF/JPEG)音頻 (MP3)視頻 (MPEG/RM)數(shù)據(jù)庫 (B+樹 )歸檔 (TAR/ZIP)密碼學(xué) (消除數(shù)據(jù)的原始特征 )全文索引 (倒排索引表 )編譯 (JAVA)程序設(shè)計(jì) (算法 /空間和時(shí)間效率 )人工智能 (專家系統(tǒng) /知識(shí)樹 ) 信息熵及基本概念信息熵及基本概念 ? 1．信息量? 信息量 是指從 N個(gè)相等的可能事件中選出一個(gè)事件所需要的信息度量或含量，也就是在辨識(shí) N個(gè)事件中特定的一個(gè)事件的過程中所需要提問 “是或否 ”的最少次數(shù)。– 典型的編碼方法有：典型的編碼方法有： PCM 編碼、預(yù)測編碼、變換編碼、預(yù)測編碼、變換編碼、子帶編碼等。信息造成誤解。的壓縮。重新將這些值插入到數(shù)據(jù)中，恢復(fù)原始數(shù)據(jù)。冗余，這種冗余即為信息熵冗余。余，即信息熵冗余。第第 2章章 多媒體數(shù)據(jù)壓縮基礎(chǔ)多媒體數(shù)據(jù)壓縮基礎(chǔ) 數(shù)據(jù)壓縮編碼簡介數(shù)據(jù)壓縮編碼簡介 統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼 詞典編碼詞典編碼 預(yù)測編碼預(yù)測編碼 變換編碼變換編碼 數(shù)據(jù)壓縮編碼簡介數(shù)據(jù)壓縮編碼簡介 數(shù)據(jù)壓縮的必要性數(shù)據(jù)壓縮的必要性●文本文本 : 若若 1024768顯示分辨率、顯示分辨率、 1616點(diǎn)陣文字、點(diǎn)陣文字、 4 Byte/字，則一屏漢字的總字，則一屏漢字的總數(shù)據(jù)量為數(shù)據(jù)量為 : (1024/16)(768/16)4 = 12288 Byte (12KB)●圖片圖片 ：若采用：若采用 1024768顯示分辨率，則滿屏圖像的總數(shù)據(jù)量為顯示分辨率，則滿屏圖像的總數(shù)據(jù)量為 : 102476824247。8 = 2359296Byte (2304 KB)●音頻：音頻： 若采樣頻率為若采樣頻率為 44100Hz， 16bit (2Byte)，立體聲，立體聲 (2聲道聲道 )， 則則 1分鐘的總數(shù)據(jù)量為分鐘的總數(shù)據(jù)量為 : 441002 Byte2 (STEREO) 60s = 10336 KB (10MB)●視頻：視頻： 若圖像分辨率為若圖像分辨率為 352240， 24位色彩，幀率為位色彩，幀率為 25幀幀 /秒，秒， 則則 1分鐘的總數(shù)據(jù)量為分鐘的總數(shù)據(jù)量為 : 352240 3 Byte2560s = 371250 KB ()○○○○●○○○○○○○○○○○○○○○○○○○●○○○○○○○○○○○●●○○○○○○○○○○○○○○○○○○●●○○○○○○○○○○○●●○○○○○●●●●●●●●●●●●●●●○○○○○○○○○○●●●○○○○●●●●●●●●●●●●●●●●○○○○○○○○○●●●○○○○●●○○○○○○○○○○●●○○○○○○○○○○○○●●○○○○●●○○○○○○○○○○●●○○○○○○○○○○○○○○○○○○●●○○○○●●○○○○●●○○○○○○○○○○○○○○○○●○●●○○○○●●○○○○●●○○○○○○●●●●●●●●●●●●●●○○○○●●○○○○●●○○○○○○●●●●●●●●●●●●●●○○○○●●○○○○●●○○○○○○○○○○○○○○●●○○●●○○○○●●○○○○●●○○○○○○○○○○○○○●●●○○●●○○○○●●○○○○●●○○○○○○○○○○○○●●●○○○●●○○○○●●○○○○●●○○○○○○○○○○○●●●○○○○●●○○○○●●○○○○●●○○○○○○○○○○●●●●○○○○●●○○○○●●○○○○●●○○○○○○○○○●●●●●○○○○●●○○○○