多媒體數(shù)據(jù)壓縮技術(shù)

第四章數(shù)據(jù)壓縮技術(shù)

DataCompressionTechnologies本章主要介紹目前用得最多和技術(shù)最成熟的數(shù)據(jù)壓縮編碼技術(shù)。數(shù)據(jù)壓縮可分成兩種類(lèi)型，一種叫做無(wú)損(lossless)壓縮，另一種叫做有損(lossy)壓縮。無(wú)損壓縮編碼技術(shù)包括霍夫曼編碼、算術(shù)編碼、RLE編碼和詞典編碼。有損壓縮技術(shù)如離散余弦變換、小波變換等。2024/5/141內(nèi)容提綱4.1

數(shù)據(jù)壓縮技術(shù)概述4.2

霍夫曼(Huffman)編碼算法4.3

算術(shù)(Arithmetic)編碼算法4.4RLE編碼(RunLengthEncoding)算法4.5

詞典(Dictionary)編碼算法參考文獻(xiàn)與作業(yè)2024/5/142作業(yè)運(yùn)用Huffman,算術(shù)編碼，LZ77分別對(duì)下段文字進(jìn)行編解碼：(Huffman編碼可設(shè)置碼表)Gridcomputingisbecominganimportantframeworkforenablingapplicationstoutilizewidelydistributedcollectionsofcomputationalanddataresources,howevercurrentgridsoftwareisstillimmatureandratherdifficulttouse.TheGlobusGridToolkitisasetoflow-leveltools,protocolsandservicesthathasbecomeadefactostandardforbasicgridcomputinginfrastructure.TheGlobusResourceAllocationandManagement(GRAM)serviceprovidesforthemanagementandremoteexecutionofjobsdefinedusingastandardResourceSpecificationLanguage(RSL).Currently,theGRAMhasverylimitedfunctionality,whichmakesitmoredifficulttodevelopgridapplications.Onelimitationisthelackofsupportforapplicationsthatrequireaspecialexecutionenvironment,suchasJavaapplicationsthatrunwithinaJavaVirtualMachine.Cumbersomeworkaroundsarenecessarytorunsuchapplications.ThecurrentGRAMaddressestheseproblemsinaratheradhocwayforcertainspecificcases,howeverthereisnogeneral,well-definedmechanismforsupportingarbitraryexecutionenvironments.HereweoutlinesomeoftheproblemswiththecurrentGlobusGRAMspecificationandprovideaproposalforhowtheymightbeaddressedbydefiningsomeextensionstothestandardRSLsupportedbytheGRAM,aswellassomemodificationstothedesignoftheGRAMthatwouldenableittosupportarbitraryexecutionenvironments.WegiveexamplesofhowourproposedsystemcanprovideimprovedsupportforJavaapplicationsandclustermanagementsystems,anddescribeourongoingworkinimplementingprototypesoftheseproposedGRAMextensions.2024/5/143參考文獻(xiàn)題名：多媒體數(shù)據(jù)壓縮技術(shù)叢編題名：全國(guó)高技術(shù)重點(diǎn)圖書(shū)ISBN號(hào)：7-5053-2206-0出版項(xiàng)：北京電子工業(yè)出版社1994.4著者：高文題名：數(shù)據(jù)壓縮技術(shù)及其應(yīng)用叢編題名：計(jì)算機(jī)科學(xué)大眾叢書(shū)ISBN號(hào)：

7-5053-3253-8出版項(xiàng)：北京電子工業(yè)出版社1995著者：袁玫,袁文題名：數(shù)據(jù)壓縮技術(shù)原理與范例ISBN號(hào)：

7-03-004846-6出版項(xiàng)：北京科學(xué)出版社1995著者：(美)MarkNelson題名：數(shù)據(jù)壓縮技術(shù)及其應(yīng)用ISBN號(hào)：7-115-03835-X出版項(xiàng)：北京人民郵電出版社1989.6著者：(美)林奇(Lynch,T.J.)2024/5/144數(shù)據(jù)壓技術(shù)縮概述

AnIntroductiontoDataCompression基本概念與定義數(shù)據(jù)壓縮技術(shù)的分類(lèi)常用的數(shù)據(jù)壓縮方法§4.12024/5/145數(shù)據(jù)壓縮的必要性數(shù)據(jù)通信數(shù)據(jù)存儲(chǔ)…24BitBitmap(193k)JPEG(10k)2024/5/146考慮的因素不能失真磁盤(pán)文件。。。允許失真在不影響“質(zhì)量”的情況下ABCAACBBCABCAACBBC#$%^&*壓縮編碼數(shù)據(jù)還原256color(66k)24bit(193k)2024/5/147基本概念無(wú)損壓縮(LosslessCompression)是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)(或者叫做還原，解壓縮)，重構(gòu)后的數(shù)據(jù)與原來(lái)的數(shù)據(jù)完全相同。有損壓縮(LossyCompression)是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來(lái)的數(shù)據(jù)有所不同，但不影響人對(duì)原始資料表達(dá)的信息造成誤解。無(wú)損壓縮用于要求重構(gòu)的信號(hào)與原始信號(hào)完全一致的場(chǎng)合。一個(gè)很常見(jiàn)的例子是磁盤(pán)文件的壓縮。根據(jù)目前的技術(shù)水平，無(wú)損壓縮算法一般可以把普通文件的數(shù)據(jù)壓縮到原來(lái)的1/2～1/4。一些常用的無(wú)損壓縮算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv&Welch)壓縮算法。有損壓縮適用于重構(gòu)信號(hào)不一定非要和原始信號(hào)完全相同的場(chǎng)合。例如，圖像和聲音的壓縮就可以采用有損壓縮，因?yàn)槠渲邪臄?shù)據(jù)往往多于我們的視覺(jué)系統(tǒng)和聽(tīng)覺(jué)系統(tǒng)所能接收的信息，丟掉一些數(shù)據(jù)而不至于對(duì)聲音或者圖像所表達(dá)的意思產(chǎn)生誤解，但可大大提高壓縮比。2024/5/148數(shù)據(jù)壓縮技術(shù)的分類(lèi)2024/5/149統(tǒng)計(jì)編碼中“熵”的基本概念熵(Entropy)熵是信息量的度量方法，它表示某一事件出現(xiàn)的消息越多，事件發(fā)生的可能性就越小，數(shù)學(xué)上就是概率越小。某個(gè)事件的信息量用表示，其中pi為第i個(gè)事件的概率，0<pi

≤1。信源s的熵的定義：按照香農(nóng)(Shannon)的理論，信源s的熵定義為

其中：pi

為si

在s中出現(xiàn)的概率，表示包含在si

中的信息量，也就是編碼所需要的位數(shù)，例如，一幅用256級(jí)灰度表示的圖像，如果每一個(gè)象素點(diǎn)灰度的概率均為pi=1/256，編碼每一個(gè)象素點(diǎn)就需要8位。2024/5/1410常用的壓縮方法統(tǒng)計(jì)編碼圖像。。。預(yù)測(cè)編碼音頻。。。變換編碼圖像。。?；旌暇幋a標(biāo)準(zhǔn)量化也是實(shí)現(xiàn)數(shù)據(jù)壓縮的一種手段2024/5/1411霍夫曼編碼

HuffmanEncodingSystem霍夫曼(Huffman)在1952年提出的一種編碼方法，即從下到上的編碼方法。該方法根據(jù)待編碼信息的統(tǒng)計(jì)特征(熵)，先按出現(xiàn)頻率的大小從下到上構(gòu)建編碼樹(shù)；然后按類(lèi)似于前序(后序)遍歷的方法賦予樹(shù)的每條邊一個(gè)碼值，“0”或“1”；最后探索根到葉結(jié)點(diǎn)，根到葉所經(jīng)歷邊碼的序列即為該字符的“碼值”。霍夫曼編碼分為定長(zhǎng)編碼和變長(zhǎng)編碼兩種。后者的應(yīng)用比較廣泛。此外，霍夫曼編碼自含同步碼，碼串中不需要另加標(biāo)記。§4.22024/5/1412編碼算法主要步驟(可變長(zhǎng)編碼)統(tǒng)計(jì)各字符出現(xiàn)的頻率根據(jù)貪心策略構(gòu)建編碼樹(shù)按類(lèi)似于前序遍歷的方法遞歸地遍歷編碼樹(shù)，對(duì)于連接左子樹(shù)的邊賦予邊碼為“0”，連接右樹(shù)的邊碼為“1”。反過(guò)來(lái)亦可。即算從“根”到“葉”的邊碼序列，得到某字符的編碼。0.12820.15380.15390.17950.38460.28200.33340.61541.000001001110ABCDEA:“0”B:“100”C:“101”D:“110”E:“111”2024/5/1413編碼方法Huffman編碼舉例符號(hào)出現(xiàn)的次數(shù)log2(1/pi)分配的代碼需要的位數(shù)A15(0.3846)1.38015B7(0.1795)2.4810021C6(0.1538)2.7010118D6(0.1538)2.7011018E5(0.1282)2.9611115從下到上按貪心策略進(jìn)行選擇來(lái)構(gòu)建二進(jìn)制編碼樹(shù)。在進(jìn)行編碼樹(shù)遍歷時(shí)規(guī)定連接“左”子數(shù)的邊碼為“0”，右子樹(shù)的碼為“1”。反過(guò)來(lái)也可以。從根到葉的邊碼序列為該葉節(jié)點(diǎn)的編碼，如C的編碼為“101”。2024/5/1414霍夫曼編碼小結(jié)霍夫曼碼的碼長(zhǎng)雖然是可變的，但卻不需要另外附加同步代碼(自含同步碼，在編碼之后的碼串中都不須要另外添加標(biāo)記符號(hào))。例如，碼串中的第1位為0，那末肯定是符號(hào)A，因?yàn)楸硎酒渌?hào)的代碼沒(méi)有一個(gè)是以0開(kāi)始的，因此下一位就表示下一個(gè)符號(hào)代碼的第1位。同樣，如果出現(xiàn)“110”，那么它就代表符號(hào)D。如果事先編寫(xiě)出一本解釋各種代碼意義的“詞典”，即碼簿，那么就可以根據(jù)碼簿一個(gè)碼一個(gè)碼地依次進(jìn)行譯碼采用霍夫曼編碼時(shí)有兩個(gè)問(wèn)題值得注意：霍夫曼碼沒(méi)有錯(cuò)誤保護(hù)功能，在譯碼時(shí)，如果碼串中沒(méi)有錯(cuò)誤，那么就能一個(gè)接一個(gè)地正確譯出代碼。但如果碼串中有錯(cuò)誤，哪僅是1位出現(xiàn)錯(cuò)誤，不但這個(gè)碼本身譯錯(cuò)，更糟糕的是一錯(cuò)一大串，全亂了套，這種現(xiàn)象稱(chēng)為錯(cuò)誤傳播(errorpropagation)。計(jì)算機(jī)對(duì)這種錯(cuò)誤也無(wú)能為力，說(shuō)不出錯(cuò)在哪里，更談不上去糾正它?；舴蚵a是可變長(zhǎng)度碼，因此很難隨意查找或調(diào)用壓縮文件中間的內(nèi)容，然后再譯碼，這就需要在存儲(chǔ)代碼之前加以考慮。2024/5/1415算術(shù)編碼

ArithmeticEncodingSystem算術(shù)編碼在圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)(如JPEG，JBIG)中扮演了重要的角色。在算術(shù)編碼中，消息用0到1之間的實(shí)數(shù)進(jìn)行編碼，算術(shù)編碼用到兩個(gè)基本的參數(shù)：符號(hào)的概率和它的編碼間隔。信源符號(hào)的概率決定壓縮編碼的效率，也決定編碼過(guò)程中信源符號(hào)的間隔，而這些間隔包含在0到1之間。編碼過(guò)程中的間隔決定了符號(hào)壓縮后的輸出?！?.32024/5/1416關(guān)于算術(shù)編碼簡(jiǎn)要?dú)v史：20世紀(jì)60年代初，Elias提出了算術(shù)編碼(ArithmeticCoding)概念。1976年Rissanen和Pasco首次介紹該實(shí)用技術(shù)。基本原理：將編碼的信息用0到1之間的實(shí)數(shù)區(qū)間進(jìn)行編碼算術(shù)編碼用到兩個(gè)基本的參數(shù)：符號(hào)的概率：信源符號(hào)的概率決定壓縮編碼的效率，也決定編碼過(guò)程中信源符號(hào)的間隔，而這些間隔包含在0到1之間。

編碼間隔：編碼過(guò)程中的間隔決定了符號(hào)壓縮后的輸出。

2024/5/1417算術(shù)編碼簡(jiǎn)介編碼舉例假設(shè)信源符號(hào)、出現(xiàn)的概率和處世間隔如下：編碼過(guò)程：假設(shè)消息序列的輸入順序?yàn)椋?0001100101101。符號(hào)00011011概率0.10.40.20.3初始編碼間隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)2024/5/1418算法描述考慮一個(gè)有M個(gè)符號(hào)ai=(1,2,…,M)的字符表集，假定ai的概率p(ai)=pi，而輸入的符號(hào)用xn表示，第n個(gè)子間隔的范圍用 表示，其中：

l0=0,d0=0,p0=0, ln表示間隔左邊界的值， rn表示間隔右邊界的值， dn=rn-ln表示間隔長(zhǎng)度。2024/5/1419算法描述編碼步驟如下：步驟1：首先在1和0之間給每個(gè)符號(hào)分配一個(gè)初始子間隔，子間隔的長(zhǎng)度等于它的概率，初始子間隔的范圍為I1。令d1=r1-l1，L=l1

和R=r1。步驟2：L和R的二進(jìn)制表達(dá)式分別表示為：

和

其中uk

和vk

等于“1”或者“0”。比較u1

和v1

：①如果

，不發(fā)送任何數(shù)據(jù)，轉(zhuǎn)到步驟3。反之，發(fā)送二進(jìn)制符號(hào)u1。

比較u2

和v2

：①如果

，不發(fā)送任何數(shù)據(jù)，轉(zhuǎn)到步驟3；反之，發(fā)送二進(jìn)制符號(hào)u2。

…這種比較一直進(jìn)行到兩個(gè)符號(hào)不相同為止。步驟3：令n=n+1，讀下一個(gè)符號(hào)。假設(shè)第n個(gè)輸入符號(hào)為xn=ai

，按照以前的步驟把這個(gè)間隔分成子間隔In；并令L=In

，R=rn

和dn=rn-ln，

轉(zhuǎn)步驟2。2024/5/1420算法描述編碼過(guò)程：步驟輸入符號(hào)編碼間隔編碼判決110[0.5,0.7)符號(hào)的間隔范圍[0.5,0.7)200[0.5,0.52)[0.5,0.7)間隔的第一個(gè)1/10311[0.514,0.52)[0.5,0.52)間隔的最后一個(gè)1/10400[0.514,0.5146)[0.514,0.52)間隔的第一個(gè)1/10510[0.5143,0.51442)[0.514,0.5146)間隔的第五個(gè)1/10開(kāi)始，二個(gè)1/10611[0.514384,0.51442)[0.5143,0.51442)間隔的最后3個(gè)1/10701[0.5143836,0.514402)[0.514384,0.51442)間隔的4個(gè)1/10，從第1個(gè)1/10開(kāi)始8從[0.5143876,0.514402中選擇一個(gè)數(shù)作為輸出：0.51438762024/5/1421算法描述譯碼過(guò)程步驟間隔譯碼符號(hào)譯碼判決1[0.5,0.7)100.51439在間隔[0.5,0.7)2[0.5,0.52)000.51439在間隔[0.5,0.7)的第1個(gè)1/103[0.514,0.52)110.51439在間隔[0.5,0.52)的第7個(gè)1/104[0.514,0.5146)000.51439在間隔[0.514,0.52)的第1個(gè)1/105[0.5143,0.51442)100.51439在間隔[0.514,0.5146)的第5個(gè)1/106[0.514384,0.51442)110.51439在間隔[0.5143,0.51442)的第7個(gè)1/107[0.51439,0.5143948)010.51439在間隔[0.51439,0.5143948)的第1個(gè)1/107譯碼的消息：100011001011012024/5/1422算術(shù)編碼小結(jié)在算術(shù)編碼中需要注意的幾個(gè)問(wèn)題：由于實(shí)際的計(jì)算機(jī)的精度不可能無(wú)限長(zhǎng)，運(yùn)算中出現(xiàn)溢出是一個(gè)明顯的問(wèn)題，但多數(shù)機(jī)器都有16位、32位或者64位的精度，因此這個(gè)問(wèn)題可使用比例縮放方法解決。算術(shù)編碼器對(duì)整個(gè)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在間隔[0,1)中的一個(gè)實(shí)數(shù)，因此譯碼器在接受到表示這個(gè)實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。算術(shù)編碼也是一種對(duì)錯(cuò)誤很敏感的編碼方法，如果有一位發(fā)生錯(cuò)誤就會(huì)導(dǎo)致整個(gè)消息譯錯(cuò)。算術(shù)編碼可以是靜態(tài)的或者自適應(yīng)的。在靜態(tài)算術(shù)編碼中，信源符號(hào)的概率是固定的。在自適應(yīng)算術(shù)編碼中，信源符號(hào)的概率根據(jù)編碼時(shí)符號(hào)出現(xiàn)的頻繁程度動(dòng)態(tài)地進(jìn)行修改。2024/5/1423RLE編碼

RunLengthEncodingSystem現(xiàn)實(shí)中有許多這樣的圖像，在一幅圖像中具有許多顏色相同的圖塊。在這些圖塊中，許多行上都具有相同的顏色，或者在一行上有許多連續(xù)的象素都具有相同的顏色值。在這種情況下就不需要存儲(chǔ)每一個(gè)象素的顏色值，而僅僅存儲(chǔ)一個(gè)象素的顏色值，以及具有相同顏色的象素?cái)?shù)目就可以，或者存儲(chǔ)一個(gè)象素的顏色值，以及具有相同顏色值的行數(shù)。這種壓縮編碼稱(chēng)為行程編碼，常用(runlengthencoding，RLE)表示，具有相同顏色并且是連續(xù)的象素?cái)?shù)目稱(chēng)為行程長(zhǎng)度?！?.42024/5/1424RLE簡(jiǎn)介設(shè)有一幅灰度圖像第n行的象素值為：用RLE編碼方法得到的代碼為：80315084180。 代碼中用黑體表示的數(shù)字是行程長(zhǎng)度，黑體字后面的數(shù)字代表象素的顏色值。例如黑體字50代表有連續(xù)50個(gè)象素具有相同的顏色值，它的顏色值是8。2024/5/1425RLE簡(jiǎn)介(cont.)問(wèn)題：編碼如何處理多行圖像數(shù)據(jù)呢？RLE編碼小結(jié)RLE壓縮編碼尤其適用于計(jì)算機(jī)生成的圖像，對(duì)減少圖像文件的存儲(chǔ)空間非常有效。然而，RLE對(duì)顏色豐富的自然圖像就顯得力不從心，在同一行上具有相同顏色的連續(xù)象素往往很少，而連續(xù)幾行都具有相同顏色值的連續(xù)行數(shù)就更少。如果仍然使用RLE編碼方法，不僅不能壓縮圖像數(shù)據(jù)，反而可能使原來(lái)的圖像數(shù)據(jù)變得更大。請(qǐng)注意，這并不是說(shuō)RLE編碼方法不適用于自然圖像的壓縮，相反，在自然圖像的壓縮中還真少不了RLE，只不過(guò)是不能單純使用RLE一種編碼方法，需要和其他的壓縮編碼技術(shù)聯(lián)合應(yīng)用。2024/5/1426詞典編碼

DictionaryEncodingSystem4.5.1

詞典編碼的思想4.5.2

LZ77

(Lempel–Ziv)算法4.5.3

LZSS

(Lempel–Ziv–Storer–Szymanski)算法4.5.4

LZ78

(Lempel–Ziv)算法4.5.5

LZW

(Lempel–Ziv–Waltch)算法§4.52024/5/1427詞典編碼的思想第一類(lèi)詞典編碼企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過(guò)，然后用已經(jīng)出現(xiàn)過(guò)的字符串替代重復(fù)的部分，它的輸出僅僅是指向早期出現(xiàn)過(guò)的字符串的“指針”。這里所指的“詞典”是指用以前處理過(guò)的數(shù)據(jù)來(lái)表示編碼過(guò)程中遇到的重復(fù)部分。2024/5/1428詞典編碼的思想(cont.)第二類(lèi)詞典編碼企圖從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)“短語(yǔ)詞典(dictionaryofthephrases)”，這種短語(yǔ)不一定是具有具體含義的短語(yǔ)，它可以是任意字符的組合。編碼數(shù)據(jù)過(guò)程中當(dāng)遇到已經(jīng)在詞典中出現(xiàn)的“短語(yǔ)”時(shí)，編碼器就輸出這個(gè)詞典中的短語(yǔ)的“索引號(hào)”，而不是短語(yǔ)本身。2024/5/1429LZ77算法幾個(gè)術(shù)語(yǔ)輸入數(shù)據(jù)流(inputstream)：要被壓縮的字符序列。字符(character)：輸入數(shù)據(jù)流中的基本單元。編碼位置(codingposition)：輸入數(shù)據(jù)流中當(dāng)前要編碼的字符位置，指前向緩沖存儲(chǔ)器中的開(kāi)始字符。前向緩沖存儲(chǔ)器(Lookaheadbuffer)：存放從編碼位置到輸入數(shù)據(jù)流結(jié)束的字符序列的存儲(chǔ)器。窗口(window)：指包含W個(gè)字符的窗口，字符是從編碼位置開(kāi)始向后數(shù)也就是最后處理的字符數(shù)。指針(pointer)：指向窗口中的匹配串且含長(zhǎng)度的指針。2024/5/1430LZ77算法(cont.)LZ77編碼算法的核心是查找從前向緩沖存儲(chǔ)器開(kāi)始的最長(zhǎng)的匹配串。編碼算法的具體執(zhí)行步驟如下：把編碼位置設(shè)置到輸入數(shù)據(jù)流的開(kāi)始位置。查找窗口中最長(zhǎng)的匹配串。以“(Pointer,Length)Characters”的格式輸出，其中Pointer是指向窗口中匹配串的指針，Length表示匹配字符的長(zhǎng)度，Characters是前向緩沖存儲(chǔ)器中的不匹配的第1個(gè)字符。如果前向緩沖存儲(chǔ)器不是空的，則把編碼位置和窗口向前移(Length+1)個(gè)字符，然后返回到步驟2。2024/5/1431LZ77算法(cont.)LZ77算法舉例位置123456789字符AABCBBABC步驟位置匹配串字符輸出11--A(0,0)A22AB(1,1)B34--C(0,0)C45BB(2,1)B57ABC(5,2)C步驟：表示編碼步驟。位置：表示編碼位置，輸入數(shù)據(jù)流中的第1個(gè)字符為編碼位置1。匹配串：欄表示窗口中找到的最長(zhǎng)的匹配串。字符：表示匹配之后在前向緩沖存儲(chǔ)器中的第1個(gè)字符。輸出：以“(Back_chars,Chars_length)Explicit_character”格式輸出。2024/5/1432LZ77算法

(cont.)LZ77算法小結(jié)存在的缺點(diǎn)LZ77通過(guò)輸出真實(shí)字符解決了在窗口中出現(xiàn)沒(méi)有匹配串的問(wèn)題，但這個(gè)解決方案包含有冗余信息。冗余信息表現(xiàn)在如下兩個(gè)方面：一是空指針二是編碼器可能輸出額外的字符，這種字符是指可能包含在下一個(gè)匹配串中的字符。2024/5/1433LZSS算法LZSS編碼算法的具體執(zhí)行步驟如下：把編碼位置置于輸入數(shù)據(jù)流的開(kāi)始位置。在前向緩沖存儲(chǔ)器中查找與窗口中最長(zhǎng)的匹配串

①Pointer：=匹配串指針。

②Length：=匹配串長(zhǎng)度。判斷匹配串長(zhǎng)度Length是否大于等于最小匹配串長(zhǎng)度(Length≥

MIN_LENGTH)，

如果“是”：輸出指針，然后把編碼位置向前移動(dòng)Length個(gè)字符。

如果“否”：輸出前向緩沖存儲(chǔ)器中的第1個(gè)字符，然后把編碼位置向前移動(dòng)一個(gè)字符。如果前向緩沖存儲(chǔ)器不是空的，就返回到步驟2。2024/5/1434LZSS算法(cont.)LZSS算法舉例設(shè)有下列字符串編碼步驟如下：位置1234567891011字符AABBCBBAABC步驟位置匹配串輸出11--A22AA33--B44BB55--C66BB(3,2)78AAB(7,3)811CC2024/5/1435LZSS算法

(cont.)LZSS算法小結(jié)在相同的計(jì)算機(jī)環(huán)境下，LZSS算法比LZ77可獲得比較高的壓縮比，而譯碼同樣簡(jiǎn)單。這也就是為什么這種算法成為開(kāi)發(fā)新算法的基礎(chǔ)，許多后來(lái)開(kāi)發(fā)的文檔壓縮程序都使用了LZSS的思想。例如，PKZip,ARJ,LHArc和ZOO等等，其差別僅僅是指針的長(zhǎng)短和窗口的大小等有所不同。LZSS同樣可以和熵編碼聯(lián)合使用，例如ARJ就與霍夫曼編碼聯(lián)用，而PKZip則與Shannon-Fano聯(lián)用，它的后續(xù)版本也采用霍夫曼編碼。2024/5/1436LZ78算法幾個(gè)術(shù)語(yǔ)符號(hào)字符流(Charstream)：要被編碼的數(shù)據(jù)序列。字符(Character)：字符流中的基本數(shù)據(jù)單元。前綴(Prefix)：在一個(gè)字符之前的字符序列。綴-符串(String)：前綴＋字符。碼字(Codeword)：碼字流中的基本數(shù)據(jù)單元，代表詞典中的一串字符。碼字流(Codestream)：碼字和字符組成的序列，是編碼器的輸出。詞典(Dictionary)：綴-符串表。按照詞典中的索引號(hào)對(duì)每條綴-符串(String)指定一個(gè)碼字(Codeword)。當(dāng)前前綴(Currentprefix)：在編碼算法中使用，指當(dāng)前正在處理的前綴，用符號(hào)P表示。當(dāng)前字符(Currentcharacter)：在編碼算法中使用，指當(dāng)前前綴之后的字符，用符號(hào)C表示。當(dāng)前碼字(Currentcodeword)：在譯碼算法中使用，指當(dāng)前處理的碼字，用W表示當(dāng)前碼字，String.W表示當(dāng)前碼字的綴-符串。2024/5/1437LZ78算法(cont.)LZ78編碼算法步驟1：在開(kāi)始時(shí)，詞典和當(dāng)前前綴P都是空的。步驟2：當(dāng)前字符C：=字符流中的下一個(gè)字符。步驟3：判斷P+C是否在詞典中：(1)如果“是”：用C擴(kuò)展P，讓P：=P+C；(2)如果“否”：①輸出與當(dāng)前前綴P相對(duì)應(yīng)的碼字和當(dāng)前字符C；②把字符串P+C添加到詞典中。③令P：=空值。(3)判斷字符流中是否還有字符需要編碼①如果“是”：返回到步驟2。②如果“否”：若當(dāng)前前綴P不是空的，輸出相應(yīng)于當(dāng)前前綴P的碼字，然后結(jié)束編碼。LZ78編碼器的輸出是碼字–字符(W,C)對(duì)，每次輸出一對(duì)到碼字流中，與碼字W相對(duì)應(yīng)的綴-符串(String)用字符C進(jìn)行擴(kuò)展生成新的綴-符串(String)，然后添加到詞典中。LZ78編碼的具體算法如下：2024/5/1438LZ78算法(cont.)LZ78譯碼算法LZ78編碼器的輸出是碼字-字符(W,C)對(duì)，每次輸出一對(duì)到碼字流中，與碼字W相對(duì)應(yīng)的綴-符串(String)用字符C進(jìn)行擴(kuò)展生成新的綴-符串(String)，然后添加到詞典中。LZ78編碼的具體算法如下：步驟1：在開(kāi)始時(shí)詞典是空的。步驟2：當(dāng)前碼字W：=碼字流中的下一個(gè)碼字。步驟3：當(dāng)前字符C：=緊隨碼字之后的字符。步驟4：把當(dāng)前碼字的綴-符串(string.W)輸出到字符流(Charstream)，然后輸出字符C。步驟5：把string.W+C添加到詞典中。步驟6：判斷碼字流中是否還有碼字要譯(1)如果“是”，就返回到步驟2。(2)如果“否”，則結(jié)束。2024/5/1439LZ78算法(cont.)LZ78算法舉例假設(shè)有下列編碼字符串：編碼過(guò)程如下：位置123456789字符

ABBCBCABA步驟位置詞典輸出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)步驟：編碼步驟。位置：在輸入數(shù)據(jù)中的當(dāng)前位置。詞典：添加到詞典中的綴-符串，綴-符串的索引等于“步驟”序號(hào)。輸出：以(當(dāng)前碼字W,當(dāng)前字符C)簡(jiǎn)化為(W,C)的形式輸出。與LZ77相比，LZ78的最大優(yōu)點(diǎn)是在每個(gè)編碼步驟中減少了綴-符串(String)比較的數(shù)目，而壓縮率與LZ77類(lèi)似。2024/5/1440LZW算法LZW算法中使用的術(shù)語(yǔ)與LZ78使用的相同，僅增加了一個(gè)術(shù)語(yǔ)—前綴根(Root)，它是由單個(gè)字符串組成的綴-符串(String)。在編碼原理上，LZW與LZ78相比有如下差別：LZW只輸出代表詞典中的綴-符串(String)的碼字(codeword)。這就意味在開(kāi)始時(shí)詞典不能是空的，它必須包含可能在字符流出現(xiàn)中的所有單個(gè)字符，即前綴根(Root)。由于所有可能出現(xiàn)的單個(gè)字符都事先包含在詞典中，每個(gè)編碼步驟開(kāi)始時(shí)都使用一字符前綴(one-characterprefix)，因此在詞典中搜索的第1個(gè)綴-符串有兩個(gè)字符。2024/5/1441LZW算法(cont.)LZW編碼算法2024/5/1442LZW算法(cont.)LZW編碼算法LZW編碼算法的具體執(zhí)行步驟如下：步驟1：開(kāi)始時(shí)的詞典包含所有可能的根(Root)，而當(dāng)前前綴P是空的；步驟2：當(dāng)前字符(C)：=字符流中的下一個(gè)字符；步驟3：判斷綴-符串P+C是否在詞典中

(1)如果“是”：P：=P+C //用C擴(kuò)展P；

(2)如果“否”

①把代表當(dāng)前前綴P的碼字輸出到碼字流;

②把綴-符串P+C添加到詞典;

③令P：=C //現(xiàn)在的P僅包含一個(gè)字符C;步驟4：判斷碼字流中是否還有碼字要譯

(1)如果“是”，就返回到步驟2；

(2)如果“否”

①把代表當(dāng)前前綴P的碼字輸出到碼字流;

②結(jié)束。2024/5/1443L