2016秋季多媒體技術(shù)第四章多媒體數(shù)據(jù)壓縮技術(shù)與標準 2學習專業(yè)課件

多媒體技術(shù)

第4章多媒體數(shù)據(jù)壓縮技術(shù)與標準(8學時)劉紹輝計算機科學與技術(shù)學院哈爾濱工業(yè)大學shliu@2016年秋季第4章多媒體技術(shù)數(shù)據(jù)壓縮技術(shù)與標準4.1引言4.1.1數(shù)據(jù)壓縮的必要性與可行性4.1.2數(shù)據(jù)壓縮發(fā)展簡介4.1.3數(shù)據(jù)壓縮分類4.1.4數(shù)據(jù)壓縮系統(tǒng)性能評價4.2量化 4.2.1標量量化 4.2.2量化器設(shè)計原理4.2.3其它量化器4.3無損數(shù)據(jù)壓縮4.3.1熵編碼4.3.2字典編碼4.3.3預(yù)測編碼及應(yīng)用4.3.4變換編碼及應(yīng)用4.4數(shù)據(jù)壓縮標準4.4.1音頻壓縮標準4.4.2靜止圖像壓縮標準4.4.3視頻壓縮標準4.5參考文獻和站點題外話？中華人民共和國----中國7456----氣死我了B4-------BeforeHowru?幾組與容量有關(guān)的數(shù)字時代內(nèi)存硬盤U盤移動硬盤90年代中期256k,1M,2M…100M-400M5英寸盤無1999年左右32M，64M20G3英寸盤少見2003年左右128M，256M40G64K1G目前1G,2G,4G,…500G,1T,2T,3T8G,16G,32G,128G250G,500G,1T,2T容量單位位bit(比特)(BinaryDigits)：存放一位二進制數(shù)，即0或1，最小的存儲單位字節(jié)byte：8個二進制位為一個字節(jié)(B)，最常用的單位存儲單位一般用B，KB，MB，GB，TB，EB，ZB，YB，BB來表示，它們之間的關(guān)系是：

1KB(Kilobyte千字節(jié))=1024B，

1MB(Megabyte兆字節(jié)簡稱“兆”)=1024KB，

1GB(Gigabyte吉字節(jié)又稱“千兆”)=1024MB，

1TB(Trillionbyte萬億字節(jié)太字節(jié))=1024GB，

1PB（Petabyte千萬億字節(jié)拍字節(jié)）=1024TB，

1EB（Exabyte百億億字節(jié)艾字節(jié)）=1024PB，

1ZB(Zettabyte十萬億億字節(jié)澤字節(jié))=1024EB,

1YB(Jottabyte一億億億字節(jié)堯字節(jié))=1024ZB,

1BB(Brontobyte一千億億億字節(jié))=1024YB

/read-htm-tid-174751.html數(shù)據(jù)量迅猛增長據(jù)國外媒體報道，思科公司多年來一直聲稱移動視頻數(shù)據(jù)正處于爆炸性增長態(tài)勢，如今思科公司預(yù)測到2014年，視頻內(nèi)容將占據(jù)所有移動數(shù)據(jù)流量的66%。思科的預(yù)測基于對獨立分析師的預(yù)測和真實數(shù)據(jù)使用習慣研究的匯總分析，其推斷四年內(nèi)運行于移動網(wǎng)絡(luò)上的個人設(shè)備將超過50億臺。研究數(shù)據(jù)包括很多預(yù)計用來處理大量視頻數(shù)據(jù)的設(shè)備，如剛剛發(fā)布的蘋果iPad。更多的移動視頻。到2019年，移動視頻將占到全球移動數(shù)據(jù)流量的72%（2014年為55%）。思科表示到2019年，，智能聯(lián)接產(chǎn)生的流量將占全球移動流量的97%。Cisco

VNI全球移動數(shù)據(jù)流量預(yù)測報告預(yù)測，到2019年全球移動數(shù)據(jù)流量將達到292EB，較2014年的30EB增長顯著。2014年，88%的全球移動數(shù)據(jù)流量為“智能”流量，產(chǎn)生這些流量的設(shè)備大多具備高級計算/多媒體功能，且最低支持3G聯(lián)接，但到2019年，這一數(shù)字有望攀升至97%。2014年，4G聯(lián)接占總移動數(shù)據(jù)流量的40%；到2019年，4G聯(lián)接將占總移動數(shù)據(jù)流量的68%。數(shù)據(jù)流量2011年4月6日，中國移動第九屆戰(zhàn)略發(fā)展論壇，中國移動董事長王建宙表示，數(shù)據(jù)流量不是洪水猛獸，而是收入增長的新引擎，中國移動將進一步重視數(shù)據(jù)流量經(jīng)營，包括提倡精細化經(jīng)營、加強對流量的研究等，處理好增值業(yè)務(wù)與數(shù)據(jù)流量的關(guān)系在2014年舉辦的《2014年通信行業(yè)節(jié)能減排論壇》中，中國移動計劃建設(shè)部節(jié)能減排處副主任李海濱透露，中國移動作為基礎(chǔ)通信運營商，每天話音業(yè)務(wù)量超110億分鐘，短信業(yè)務(wù)約17億條，移動數(shù)據(jù)流量業(yè)務(wù)超過230萬GB。數(shù)據(jù)量-百度百度每天響應(yīng)來自138個國家和地區(qū)的數(shù)十億次搜索請求；百度索引的網(wǎng)頁信息，已經(jīng)相當于60,000多個中國國家圖書館，加上百度地圖每天超過300億次定位需求積累的數(shù)據(jù)，百度已經(jīng)成為中國首家擁有并運營EB級數(shù)據(jù)的公司。百度的機器翻譯技術(shù)，目前支持27種語言，702個翻譯方向，每天響應(yīng)近億次翻譯請求，基于百度強大的海量計算平臺和豐富的海量互聯(lián)網(wǎng)大數(shù)據(jù)處理經(jīng)驗，百度實現(xiàn)了機器翻譯的真正大規(guī)模產(chǎn)業(yè)化應(yīng)用單機群存儲能力達2EB，每天讀取能力達166PB數(shù)據(jù)量-淘寶大：2014年雙十一期間，ODPS在6小時里面處理了100PB的數(shù)據(jù)，規(guī)模算下來大概相當于1秒鐘處理2000部高清電影?？欤涸?015年100TB數(shù)據(jù)排序，ODPS里面的調(diào)度系統(tǒng)，打破了當時的世界紀錄，比上一次的世界紀錄提升了三倍左右。阿里的大數(shù)據(jù)體驗館/experience

4.1引言如果沒有數(shù)據(jù)壓縮技術(shù)，我們就沒法用MP4播放器觀看影片；如果沒有數(shù)據(jù)壓縮技術(shù)，市場上的數(shù)碼錄音筆就只能記錄不到20分鐘的語音；如果沒有數(shù)據(jù)壓縮技術(shù)，從Internet上下載一部電影也許要花半年的時間……2K、4K、8K、10K，2K:1920*1080,4K:3840*2160可是這一切究竟是如何實現(xiàn)的呢？數(shù)據(jù)壓縮技術(shù)又是怎樣從無到有發(fā)展起來的呢？4.1引言數(shù)據(jù)量舉例1秒鐘的CD上音頻數(shù)據(jù)，雙聲道，采樣率44.1kHz，樣本精度16bit，44.1k*16*2=1411.2kbit/秒=172Mbyte/秒1秒鐘的RGB序列，包含25幀，大小為352*288，1*25*352*288*3=7.25Mbyte，顯然，如果一小時的節(jié)目則需要3600*7.25=25.49GbyteHDTV:1080*720*3*25=55.6Mbyte/秒，1小時:195GJPEG：10:1，MP3：15:1，DVD：100:1一張A4(210mm×297mm)幅面的照片，若用中等分辨率(300dpi)的掃描儀按真彩色掃描，其數(shù)據(jù)量為多少？讓我們來計算一下：共有(300×210/25.4)×(300×297/25.4)個象素，每個象素占3個字節(jié)，其數(shù)據(jù)量為26M字節(jié)30分鐘的16bit未壓縮WAV音樂數(shù)據(jù)量大約317M1分鐘320*240的彩色監(jiān)控視頻數(shù)據(jù)量為330M，1小時19G，1天463G4.1引言-BMPvs.JPGBMP:5.49MJPG:305KAdvantages＆Disadvantages?4.1引言-必要性與可行性必要性數(shù)據(jù)量存儲器件網(wǎng)絡(luò)帶寬技術(shù)發(fā)展可行性數(shù)據(jù)本身存在冗余冗余性相關(guān)性人類視覺、聽覺特性聽覺系統(tǒng)的敏感度有限視覺系統(tǒng)的敏感度有限4.1引言-必要性與可行性三種多媒體數(shù)據(jù)類型文字(text)數(shù)據(jù)——無損壓縮根據(jù)數(shù)據(jù)本身的冗余(Basedondataredundancy)聲音(audio)數(shù)據(jù)——有損壓縮根據(jù)數(shù)據(jù)本身的冗余(Basedondataredundancy)根據(jù)人的聽覺系統(tǒng)特性(Basedonhumanhearingsystem)圖像(image)/視頻(video)數(shù)據(jù)——有損壓縮根據(jù)數(shù)據(jù)本身的冗余(Basedondataredundancy)根據(jù)人的視覺系統(tǒng)特性(Basedonhumanvisualsystem)先從文本，逐漸發(fā)展技術(shù)的進步對人類視聽覺系統(tǒng)的認識…154.1引言-數(shù)據(jù)壓縮技術(shù)發(fā)展簡介1948-信息論之父-C.E.Shannon，信息熵1952，MIT,D.A.Huffman1952，Shannon,Fano1976，J.Rissanen—算術(shù)編碼，1982改進1984，算術(shù)編碼與J.G.Cleary和I.H.Witten的部分匹配預(yù)測模型(PPM)結(jié)合速度慢，很難滿足日常需要…逼近信息熵極限164.1引言-數(shù)據(jù)壓縮技術(shù)發(fā)展簡介J.Ziv,A.Lempel脫離Huffman及算術(shù)編碼的設(shè)計思路，提出了LZ系列算法LZ77LZ781984，T.A.Welch，LZ78->LZW1990以后，T.C.Bell提出改進版本Unix中的compress-LZW,ARJ-LZ77,ZIP,GIF,PNG字典思想4.1引言-數(shù)據(jù)壓縮技術(shù)發(fā)展簡介音頻壓縮1939，H.Dudley發(fā)明聲碼器PCMLPCVQATCSBCMPEG1-mp3,MPEG2,MPEG44.1引言-數(shù)據(jù)壓縮技術(shù)發(fā)展簡介圖像壓縮傳真圖像壓縮，CCITT，Group1-4,RLE,Huffman,當前使用的Group31986-1994，JPEG1987-88，GIF（LZW）1993,CCITT聯(lián)合ISO,JBIG1995，PNG(LZ77的改進版本zlib)1996-2001,JPEG20002015-2020,JPEGPLENO/4.1引言-數(shù)據(jù)壓縮技術(shù)發(fā)展簡介視頻壓縮,國際上兩大標準制訂組織：ISO/IECMPEGITU-TVCEG4.1引言-數(shù)據(jù)壓縮技術(shù)發(fā)展簡介1994，BWT壓縮，用在開放源碼的壓縮工具bzip中，對字符串輪轉(zhuǎn)后得到的字符矩陣進行排序和變換分形壓縮1977年,B.Mandelbrot的分析幾何學壓縮編碼方式(語音、圖像、視頻…)無失真編碼Loseless有失真編碼、源編碼Sourcecoding混合編碼Hybridcoding熵編碼EntropyEncoding哈夫曼編碼香農(nóng)法諾編碼算術(shù)編碼游程編碼預(yù)測編碼變換編碼子帶編碼矢量量化JPEGJPEG2000MPEGH.26xAVSDPCMDMFFTDCTKL4.1引言-壓縮技術(shù)分類及應(yīng)用字典編碼LZ77LZ78LZW4.1引言-性能評價壓縮比壓縮質(zhì)量主觀質(zhì)量二元判決，主觀SNR,MOS(MeanOpinionScore),等偏愛度曲線，多維計分等客觀質(zhì)量PSNRSNRSSIM(StructuralSimilarity)比特率(編碼效率)MPEG1:1.5Mb/sMPEG2:1.5-60Mb/sMPEG4:低碼率傳輸復(fù)雜度對稱的非對稱的編碼端復(fù)雜性高，解碼端復(fù)雜性低編碼端復(fù)雜性低，解碼端復(fù)雜性高延時4.1引言-性能評價視頻壓縮比第一代編碼方法第二代編碼方法理論上限與實際對比示意圖4.1引言-性能極限4.2量化-Avisualcommunicationsystem4.2量化(續(xù)1)采樣(Sampling)simplytakingreadingsatfixedpointsintimeorspaceUniformSampling:regularintervalsNon-uniformSampling:irregularintervals量化(Quantization)DigitizingtheamplitudevaluesRepresentingalarge(maybeinfinite)setofvalueswithamuchsmallerset4.2量化(續(xù)1)數(shù)字化有損壓縮中的最有效的工具4.2量化-basicidea決策邊界(Decisionboundaries)orlevels:biReconstructionlevelsorquantizinglevels:yiThestepsizeofthequantizer:thelengthoftheinterval,△b2b3b4b5b6b7b8b9b10b1b0y3y4y2y1y5y6y7y8y9y104.2量化-ModelofQuantization量化:q=A(x):將輸入x映射到量化指標逆量化:x’=B(q)=B(A(x))=Q(x)(x’≠x)量化誤差:e(x)=x–x’qABxx’4.2量化-Rate-DistortionTradeoff量化器中需要確定NumberofbinsBinboundariesReconstructionlevels碼率和失真的均衡Toreducethesizeoftheencodedbits,weneedtoreducethenumberofbinsLessbins->morereconstructionerrors4.2量化-MeasureofDistortion量化誤差:e(x)=x-x’MeanSquaredError(MSE)forquantizationAveragequantizationerrorofallinputvaluesNeedtoknowtheprobabilitydistributionoftheinputNumberofbins:MDecisionboundaries:bi,i=0,1,…,MReconstructionlevels:yi,i=1,…,M重構(gòu):x’=yi,iffbi-1<x≤bi4.2量化-Rate-DistortionOptimizationTwocases:GivenM,finddecisionlevelsandreconstructionlevelsthatminimizetheMSEGivenadistortionconstraintD,findM,decisionandreconstructionlevelssuchthattheMSE≤D4.2量化-Quantization均勻量化(UniformQuantization)中間升量化器(Midrisequantizer)中間平量化器(Midtreadquantizer)量化失真分析(MSEfordifferentsources)帶死區(qū)的量化器(Deadzonequantizer)非均勻量化器(Non-uniformQuantization)4.2量化-UniformQuantizationAllbinshavethesamesizeexceptpossiblyforthetwoouterintervals:biandyiarespacedevenlyThespacingofbiandyiare△,yi=(bi-1+bi)/2UniformMidriseQuantizer354.2量化-UniformMidriseQuantizerOutputlevels:even,0isnotanoutputlevelOutput1.5△3△△-3△-△2.5△3.5△-1.5△-2.5△-3.5△Input0△2△3△-△-2△6binsxminxmax-3△Forfinitexminandxmax:0△2△-△-2△6binsxmin=-∞xmax=∞Forinfinitexminandxmax:4.2量化-UniformMidtreadquantizerOutputlevels:odd,0isanoutputlevel,usedinimage/videocodingOutput△2.5△1.5△-2.5△2△3△-1.5△-2△-3△InputForfinitexminandxmax:Forinfinitexminandxmax:00.5△1.5△2.5△-0.5△-2.5△5binsxminxmax01.5△-1.5△5binsxmin=-∞xmax=∞4.2量化-UniformMidtreadquantizerQuantizationmapping:Outputisanindex:q=A(x)=sign(x)*floor(|x|/△+0.5)Example:x=4.1△,x’=4△Quantizedoutputs:x’=B(q)=q△Output△2.5△1.5△-2.5△2△3△-1.5△-2△-3△Input00.5△1.5△2.5△-0.5△-2.5△5binsxminxmax-0.5Δ0.5Δ-5Δ-4Δ-3Δ-2Δ-Δ0Δ2Δ3Δ4Δ5Δ4.2量化-UniformMidriseQuantizationofaUniformllyDistributedSource輸入x:在區(qū)間[-xmax,xmax]上均勻分布:f(x)=1/(2xmax)量化箱的個數(shù)(Numberofbins):M(even);Stepsize:Δ=2xmax/M誤差:e=x-x’在區(qū)間[-Δ/2,Δ/2]上均勻分布-xmaxxmaxb2b3b4b5b6b7b8b9b10b1b0y3y4y2y1y5y6y7y8y9y10-5Δ-4Δ-3Δ-2Δ-Δ0Δ2Δ3Δ4Δ5Δ-4.5Δ-3.5Δ-2.5Δ-1.5Δ-0.5Δ0.5Δ1.5Δ2.5Δ3.5Δ4.5Δ4.2量化-UniformMidriseQuantizationofaUniformlyDistributedSourceMSE:

MSEq=Δ2/12Optimization:findMsuchthatMSE≤DProvethat:

4.2量化-SignaltoNoiseRatio(SNR)&PSNRVarianceofarandomvariableuniformlydistributedin[-L/2,L/2]:VarianceisameasureofsignalenergyLetM=2n:Eachbinindexcanberepresentedbynbits.n

n+1,Δ

Δ/2,SNRincreasesby6dB4.2量化-UniformQuantizationofaNon-uniformlyDistributedSourceManydataarenon-uniformlydistributedandevenunboundedGenerallynoclosed-formexpressionforMSETheoptimalstepsizecanbesolvedbynumericalmethods4.2量化-UniformQuantizationofaNon-uniformlyDistributedSource Granularnoise:innerbins’quantizationerrorOverloadnoise:theouter-mostbins’quantizationerror4.2量化-QuantizerwithDeadzoneThebinsizearoundzeroisdoubledOtherbinsarestilluniformCreatemorezeros:de-noisingQuantizationmapping:

q=A(x)=sign(x)floor(|x|/Δ)Example:

x=-2.8Δ,q=-2(q=-3formidtreadquantizer)De-quantizationmapping:x’=B(q)=4.2量化-Howtodoiftheinputisnotzeromean?Uniformquantizerissymmetricaboutx=0Ifthemeanvalueofxisnotzero:Step1.subtractthemeanvaluebeforequantizationStep1.Addbackthemeanafterde-quantizationInmanycodingalgorithms,thistrickisused4.2量化-QuantizationUniformQuantizationMidrisequantizerMidtreadquantizerMSEfordifferentsourcesDeadzonequantizerNon-uniformQuantizationLloyd-Maxquantizers4.2量化-Uniformvs.Non-uniformExceptforthespecialcaseoftheuniformlydistributedinputvariablex,theoptimumquantizersshouldbenonuniform4.2量化-Lloyd-MaxQuantizerPDF-optimizedquantizerGivenM,tominimizetheMSE:4.2量化-Lloyd-MaxQuantizerConditionsforoptimalquantizer:Givenbi,onecanfindtheoptimalyiGivenyi,onecanfindtheoptimalbiHowtofindoptimalbi

andyi?4.2量化-LloydAlgorithmStep1.StarfromaninitialsetofoutputlevelsStep2.FindalldecisionlevelsStep3.CalculatetheMSEStep4.StopifMSEisstableStep5.Otherwise,updateyi,gotostep24.2量化-其它量化器Entropy-codedquantizationLloyd-Maxquantizer:Fixed-lengthindexcodingVariable-lengthindexcoding,averagerate<log2MCompanding-ExpandingQuantizationEmbeddedquantizationProgressive/scalabledecodingAdaptivequantizationVectorquantization4.2量化-AdaptiveQuantizationForwardAdaptiveQuantizationBackwardAdaptiveQuantization4.2量化-UsedinCodingUniformquantizer:JPEG-1Deadzonequantizer:JPEG2000Witharbitrarydeadzone:JPEG2000-2Vectorquantizer:TrellisQuantizer(TCQ)inJPEG2000-2RobertM.Gray,DavidL.Neuhoff:QuantizationIEEETransactionsonInformationTheory,Vol.44,No.6,October1998Homework4.3數(shù)據(jù)無損壓縮概述數(shù)據(jù)無損壓縮的理論——信息論(informationtheory)1948年創(chuàng)建的數(shù)學理論的一個分支學科，研究信息的編碼、傳輸和存儲該術(shù)語源于ClaudeShannon(香農(nóng))發(fā)表的“AMathematicalTheoryofCommunication”論文題目，提議用二進制數(shù)據(jù)對信息進行編碼最初只應(yīng)用于通信工程領(lǐng)域，后來擴展到包括計算在內(nèi)的其他多個領(lǐng)域，如信息的存儲、信息的檢索等。在通信方面，主要研究數(shù)據(jù)量、傳輸速率、信道容量、傳輸正確率等問題。數(shù)據(jù)無損壓縮的方法霍夫曼編碼(Huffmancoding)算術(shù)編碼(arithmeticcoding)行程長度編碼(run-lengthcoding)詞典編碼(dictionarycoding)……4.3數(shù)據(jù)無損壓縮概述(續(xù)1)TheFatherofInformationTheory——

ClaudeElwoodShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA/news/2001/february/26/1.html信息論之父介紹4.3數(shù)據(jù)的冗余冗余概念人為冗余在信息處理系統(tǒng)中，使用兩臺計算機做同樣的工作是提高系統(tǒng)可靠性的一種措施在數(shù)據(jù)存儲和傳輸中，為了檢測和恢復(fù)在數(shù)據(jù)存儲或數(shù)據(jù)傳輸過程中出現(xiàn)的錯誤，根據(jù)使用的算法的要求，在數(shù)據(jù)存儲或數(shù)據(jù)傳輸之前把額外的數(shù)據(jù)添加到用戶數(shù)據(jù)中，這個額外的數(shù)據(jù)就是冗余數(shù)據(jù)視聽冗余由于人的視覺系統(tǒng)和聽覺系統(tǒng)的局限性，在圖像數(shù)據(jù)和聲音數(shù)據(jù)中，有些數(shù)據(jù)確實是多余的，使用算法將其去掉后并不會丟失實質(zhì)性的信息或含義，對理解數(shù)據(jù)表達的信息幾乎沒有影響數(shù)據(jù)冗余不考慮數(shù)據(jù)來源時，單純數(shù)據(jù)集中也可能存在多余的數(shù)據(jù)，去掉這些多余數(shù)據(jù)并不會丟失任何信息，這種冗余稱為數(shù)據(jù)冗余，而且還可定量表達4.3數(shù)據(jù)的冗余(續(xù)1)決策量(decisioncontent)在有限數(shù)目的互斥事件集合中，決策量是事件數(shù)的對數(shù)值在數(shù)學上表示為H0=log(n)其中，n是事件數(shù)決策量的單位由對數(shù)的底數(shù)決定Sh,orBit(Shannon):用于以2為底的對數(shù)Nat(naturalunit):用于以e為底的對數(shù)Hart(hartley)：用于以10為底的對數(shù)4.3數(shù)據(jù)的冗余(續(xù)2)信息量(informationcontent)具有確定概率事件的信息的定量度量在數(shù)學上定義為

其中，是事件出現(xiàn)的概率舉例：假設(shè)X={a,b,c}是由3個事件構(gòu)成的集合，p(a)=0.5，p(b)=0.25，p(b)=0.25分別是事件a,b和c出現(xiàn)的概率，這些事件的信息量分別為，I(a)=log2(1/0.50)=1bitI(b)=log2(1/0.25)=2bitsI(c)=log2(1/0.25)=2bits一個等概率事件的集合，每個事件的信息量等于該集合的決策量4.3數(shù)據(jù)的冗余(續(xù)3)熵(entropy)按照香農(nóng)(Shannon)的理論，在有限的互斥和聯(lián)合窮舉事件的集合中，熵為事件的信息量的平均值，也稱事件的平均信息量(meaninformationcontent)用數(shù)學表示為4.3數(shù)據(jù)的冗余(續(xù)4)數(shù)據(jù)的冗余量4.3.1統(tǒng)計編碼 統(tǒng)計編碼給已知統(tǒng)計信息的符號分配代碼的數(shù)據(jù)無損壓縮方法編碼方法香農(nóng)-范諾編碼霍夫曼編碼算術(shù)編碼編碼特性香農(nóng)-范諾編碼和霍夫曼編碼的原理相同，都是根據(jù)符號集中各個符號出現(xiàn)的頻繁程度來編碼，出現(xiàn)次數(shù)越多的符號，給它分配的代碼位數(shù)越少算術(shù)編碼使用0和1之間的實數(shù)的間隔長度代表概率大小，概率越大間隔越長，編碼效率可接近于熵4.3.1統(tǒng)計編碼——香農(nóng)-范諾編碼 香農(nóng)-范諾編碼(Shannon–Fanocoding)在香農(nóng)的源編碼理論中，熵的大小表示非冗余的不可壓縮的信息量在計算熵時，如果對數(shù)的底數(shù)用2，熵的單位就用“香農(nóng)(Sh)”，也稱“位(bit)”?！拔弧笔?948年Shannon首次使用的術(shù)語。例如最早闡述和實現(xiàn)“從上到下”的熵編碼方法的人是Shannon(1948年)和Fano(1949年)，因此稱為香農(nóng)-范諾(Shannon-Fano)編碼法4.3.1統(tǒng)計編碼-香農(nóng)-范諾編碼香農(nóng)-范諾編碼舉例有一幅40個像素組成的灰度圖像，灰度共有5級，分別用符號A，B，C，D和E表示。40個像素中出現(xiàn)灰度A的像素數(shù)有15個，出現(xiàn)灰度B的像素數(shù)有7個，出現(xiàn)灰度C的像素數(shù)有7個，其余情況見表4-1(1)計算該圖像可能獲得的壓縮比的理論值(2)對5個符號進行編碼(3)計算該圖像可能獲得的壓縮比的實際值表4-1符號在圖像中出現(xiàn)的數(shù)目符號ABCDE出現(xiàn)的次數(shù)157765出現(xiàn)的概率15/407/407/406/405/404.3.1統(tǒng)計編碼-香農(nóng)-范諾編碼(續(xù)1)(1)壓縮比的理論值按照常規(guī)的編碼方法，表示5個符號最少需要3位，如用000表示A，001表示B，…，100表示E，其余3個代碼(101，110，111)不用。這就意味每個像素用3位，編碼這幅圖像總共需要120位。按照香農(nóng)理論，這幅圖像的熵為這個數(shù)值表明，每個符號不需要用3位構(gòu)成的代碼表示，而用2.196位就可以，因此40個像素只需用87.84位就可以，因此在理論上，這幅圖像的的壓縮比為120:87.84≈1.37:1，實際上就是3:2.196≈1.374.3.1統(tǒng)計編碼-香農(nóng)-范諾編碼(續(xù)2)(2)符號編碼對每個符號進行編碼時采用“從上到下”的方法。首先按照符號出現(xiàn)的頻度或概率排序，如A，B，C，D和E，見表4-2。然后使用遞歸方法分成兩個部分，每一部分具有近似相同的次數(shù)，如圖4-1所示表4-2Shannon-Fano算法舉例4.3.1統(tǒng)計編碼-香農(nóng)-范諾編碼(續(xù)3)（3）壓縮比的實際值按照這種方法進行編碼需要的總位數(shù)為30+14+14+18+15＝91，實際的壓縮比為120:91≈1.32:1圖4-1香農(nóng)-范諾算法編碼舉例

4.3.1統(tǒng)計編碼—霍夫曼編碼 霍夫曼編碼(Huffmancoding)霍夫曼(D.A.Huffman)在1952年提出和描述的“從下到上”的熵編碼方法根據(jù)給定數(shù)據(jù)集中各元素所出現(xiàn)的頻率來壓縮數(shù)據(jù)的一種統(tǒng)計壓縮編碼方法。這些元素(如字母)出現(xiàn)的次數(shù)越多，其編碼的位數(shù)就越少廣泛用在JPEG,MPEG,H.26X等各種信息編碼標準中4.3.1統(tǒng)計編碼-霍夫曼編碼—CaseStudy1霍夫曼編碼舉例1現(xiàn)有一個由5個不同符號組成的30個符號的字符串：BABACACADADABBCBABEBEDDABEEEBB計算(1)該字符串的霍夫曼碼(2)該字符串的熵(3)該字符串的平均碼長(4)編碼前后的壓縮比4.3.1統(tǒng)計編碼-霍夫曼編碼—CaseStudy1(續(xù)1)符號出現(xiàn)的次數(shù)log2(1/pi）分配的代碼需要的位數(shù)B101.585?A81.907?C33.322?D42.907?E52.585?合計30符號出現(xiàn)的概率4.3.1統(tǒng)計編碼-霍夫曼編碼—CaseStudy1(續(xù)2)(1)計算該字符串的霍夫曼碼步驟①：按照符號出現(xiàn)概率大小的順序?qū)Ψ栠M行排序步驟②：把概率最小的兩個符號組成一個節(jié)點P1步驟③：重復(fù)步驟②，得到節(jié)點P2，P3，P4，……，

PN，形成一棵樹，其中的PN稱為根節(jié)點步驟④：從根節(jié)點PN開始到每個符號的樹葉，從上到下

標上0(上枝)和1(下枝)，至于哪個為1哪個為0則

無關(guān)緊要，但通常把概率大的標成1，概率小的

標成0步驟⑤：從根節(jié)點PN開始順著樹枝到每個葉子分別寫出

每個符號的代碼4.3.1統(tǒng)計編碼-霍夫曼編碼—CaseStudy1(續(xù)3)符號B(10)A(8)E(5)D(4)C(3)P1(7)P2(12)P3(18)P4(30)01101010代碼B(11)A(10)E(00)D(011)C(010)4.3.1統(tǒng)計編碼-霍夫曼編碼—CaseStudy1(續(xù)4)符號出現(xiàn)的次數(shù)log2(1/pi）分配的代碼需要的位數(shù)B101.5851120A81.9071016C33.3220109D42.90701112E52.5850010合計301.06730個字符組成的字符串需要67位5個符號的代碼4.3.1統(tǒng)計編碼-霍夫曼編碼—CaseStudy1(續(xù)5)

(2)計算該字符串的熵

其中，是事件的集合，

并滿足H(S)=(8/30)×log2(30/8)+(10/30)×log2(30/10)+

(3/30)×log2(30/3)+(4/30)×log2(30/4)+

(5/30)×log2(30/5)

=[30lg30–(8×lg8＋

10×lg10＋

3×lg3＋

4

×lg4＋5lg5)]/(30×log22)

=(44.3136－24.5592)/9.0308＝

2.1874(Sh)4.3.1統(tǒng)計編碼-霍夫曼編碼—CaseStudy1(續(xù)6)(3)計算該字符串的平均碼長平均碼長：

＝(2×8＋2×10＋3×3＋3×4＋2×5)/30

＝2.233位/符號

壓縮比:90/67=1.34:1

平均碼長：67/30=2.233位(4)計算編碼前后的壓縮比編碼前：5個符號需3位，30個字符，需要90位編碼后：共67位

4.3.1統(tǒng)計編碼-霍夫曼編碼—CaseStudy2霍夫曼編碼舉例2編碼前N=8symbols:{a,b,c,d,e,f,g,h},3bitspersymbol(N=23=8)P(a)=0.01,P(b)=0.02,P(c)=0.05,P(d)=0.09,P(e)=0.18,P(f)=0.2,P(g)=0.2,

P(h)=0.25計算(1)該字符串的霍夫曼碼(2)該字符串的熵(3)該字符串的平均碼長(4)編碼效率(5)碼本長度4.3.1統(tǒng)計編碼-霍夫曼編碼—CaseStudy2(續(xù)1)4.3.1統(tǒng)計編碼-霍夫曼編碼—CaseStudy2(續(xù)2)(1)Averagelengthpersymbol

(beforecoding):(2)Entropy:(3)Averagelengthpersymbol

(withHuffmancoding):(4)Efficiencyofthecode:(5)Lengthofthecodebook:

Huffman編碼的限制(Limitations)Huffman編碼必須知道信源的概率分布，并且當概率分布滿足一定的條件的時候，可以達到信源熵每個符號都用整數(shù)個bit表示Huffman編碼對信源統(tǒng)計的變化沒法做到自適應(yīng)，怎么樣在壓縮中去設(shè)計一種Huffman編碼呢？在實際的系統(tǒng)中，有可能有的符號概率特別小，那么這時候會出現(xiàn)什么問題？如果信源符號就是二進制符號，怎么辦？Arithmeticcoding(算術(shù)編碼)StatisticalModifiedHuffmancode,CCITT

4.3.1統(tǒng)計編碼-算術(shù)編碼 算術(shù)編碼(arithmeticcoding)給已知統(tǒng)計信息的符號分配代碼的數(shù)據(jù)無損壓縮技術(shù)基本思想是用0和1之間的一個數(shù)值范圍表示輸入流中的一個字符，而不是給輸入流中的每個字符分別指定一個碼字實質(zhì)上是為整個輸入字符流分配一個“碼字”，因此它的編碼效率可接近于熵4.3.1統(tǒng)計編碼-算術(shù)編碼舉例[例]（取自教材）假設(shè)信源符號為{00,01,10,11}，它們的概率分別為{0.1,0.4,0.2,0.3}對二進制消息序列10001100101101…進行算術(shù)編碼4.3.1統(tǒng)計編碼-算術(shù)編碼舉例(續(xù)1)符號00011011概率0.10.40.20.3初始編碼間隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1]表4.3信源符號概率和初始編碼間隔

初始化根據(jù)信源符號的概率把間隔[0,1)分成如表4.3所示的4個子間隔：[0,0.1),[0.1,0.5),[0.5,0.7),[0.7,1)。其中[x,y)的表示半開放間隔，即包含x不包含y，x稱為低邊界或左邊界，y稱為高邊界或右邊界4.3.1統(tǒng)計編碼-算術(shù)編碼舉例(續(xù)2)確定符號的編碼范圍編碼時輸入第1個符號是10，找到它的編碼范圍是[0.5,0.7]消息中第2個符號00的編碼范圍是[0,0.1)，它的間隔就取[0.5,0.7)的第一個十分之一作為新間隔[0.5,0.52)編碼第3個符號11時，取新間隔為[0.514,0.52)編碼第4個符號00時，取新間隔為[0.514,0.5146)依此類推……消息的編碼輸出可以是最后一個間隔中的任意數(shù)整個編碼過程如圖4-3所示編碼和譯碼的全過程分別見表4-4和表4-54.3.1統(tǒng)計編碼-算術(shù)編碼舉例(續(xù)3)圖4-3例中的算術(shù)編碼過程4.3.1統(tǒng)計編碼-算術(shù)編碼舉例(續(xù)4)表4.4例子的編碼過程4.3.1統(tǒng)計編碼-算術(shù)編碼舉例(續(xù)5)表4.5例子的解碼過程作業(yè)2：完成下面的符號串的算術(shù)編碼cacbad4符號字母表為A={a,b,c,d},概率分別為p(a)=0.3,p(b)=0.2,p(c)=0.4,p(d)=0.1，試編碼序列cacbad87IndexSymbolProb.Cumulative.Prob.Range1a0.30.3[0,0,0,3)2b0.20.5[0,3,0.5)3c0.40.9[0.5,0.9)4d0.11.0[0.9,1.0)N:thelengthofthemessage,F(i)isthecum.Prob.oftheithsymbolBeginL=0.0,H=1.0;F(0)=0;for(j=1toN){i=indexofSymbol(j);L=L+(H-L)*F(i-1);H=L+(H-L)*F(i);}Output((L+H)/2);endcacbad[0.576992,0.57728)4.3.1統(tǒng)計編碼-算術(shù)編碼-Shortcomings缺陷用區(qū)間中的一個數(shù)表示一個編碼序列的輸出，如果序列無限長，則這個小數(shù)也會無限長，有可能溢出機器的表示能力不到最后，不能輸出這個區(qū)間，因此也無法輸出任何編碼的結(jié)果，但大部分情況都要求輸入序列后就能獲得輸出，例如，實時的應(yīng)用場景，你不能等所有的序列輸入完后才給出輸出的結(jié)果…需要事先知道符號的概率分布…二進制算術(shù)編碼4.3.1統(tǒng)計編碼-算術(shù)編碼-例2

4.3.1統(tǒng)計編碼-算術(shù)編碼-例2(續(xù)1)其編碼如右所示最后編碼符號串對應(yīng)的區(qū)間為[0.1058175,0.1058250]同時注意以下現(xiàn)象：1.FIFO：先進先出，比LIFO更好，具有對符號統(tǒng)計的自適應(yīng)性2.最存在精度問題：區(qū)間無限細分下去3.必需有終止符號4.與Huffman編碼進行比較，發(fā)現(xiàn)更有效，例如15位的0.000110111111111二進制串，表示數(shù)0.1058211962注意觀察輸出區(qū)間的上下界的變化情況，發(fā)現(xiàn)了什么？(FIFO)4.3.1統(tǒng)計編碼-算術(shù)編碼-例2(續(xù)2)隨著符號的輸入，編碼輸出的區(qū)間越來越小，區(qū)間的上下界越來越接近有什么想法沒有？BinaryArithmeticCodingBACCABAC-ContentAdaptiveBACCase1.if[low,high]entirelybelongstothelowerhalfoftheinterval[0,1)(i.e.high<0.5),theencoderoutputsortransmitsabinarybit0,andrescalestherangebyafactor2as[2*low,2*high)Case2.if[low,high]belongstotheupperhalfof[0,1)(i.e.,low>=0.5),outputsabinarybit1,rescalestherangeas[2*(low-0.5),2*(high-0.5)).Case3.if[low,high]belongstothesecondandthirdquartersof[0,1](i.e.low>=0.25,high<0.75),wekeeptrackofthissituationbyincrementingaspecialcounterSPCL_COUNT,andrescalestherangeas[2*(low-0.25),2*(high–0.2)).Whenevercase1or2arises,theencoderchecksthevalueofSPCL_COUNT.Ifitisgreaterthan0,thosemany1‘(or0’s)areoutputafteritoutputsthebit0(or1)ascase1(or2).Afterallthebinarybitsareoutput,theSPECL_COUNTisresettocount0.Foranyothercases,thereisnoneedtooutputanybinarybitandalsononeedtorescaletherange.Thisisasignificantpartofleadingtolowbitrate.4.3.1統(tǒng)計編碼-二進制算術(shù)編碼-BinaryArithmeticCodingBACCABAC-ContentAdaptiveBACCase1.if[low,high]entirelybelongstothelowerhalfoftheinterval[0,1)(i.e.high<0.5),theencoderoutputsortransmitsabinarybit0,andrescalestherangebyafactor2as[2*low,2*high)Case2.if[low,high]belongstotheupperhalfof[0,1)(i.e.,low>=0.5),outputsabinarybit1,rescalestherangeas[2*(low-0.5),2*(high-0.5)).Case3.if[low,high]belongstothesecondandthirdquartersof[0,1](i.e.low>=0.25,high<0.75),wekeeptrackofthissituationbyincrementingaspecialcounterSPCL_COUNT,andrescalestherangeas[2*(low-0.25),2*(high–0.25)).Whenevercase1or2arises,theencoderchecksthevalueofSPCL_COUNT.Ifitisgreaterthan0,thosemany1‘(or0’s)areoutputafteritoutputsthebit0(or1)ascase1(or2).Afterallthebinarybitsareoutput,theSPECL_COUNTisresettocount0.Foranyothercases,thereisnoneedtooutputanybinarybitandalsononeedtorescaletherange.Thisisasignificantpartofleadingtolowbitrate.4.3.1統(tǒng)計編碼-二進制算術(shù)編碼(例)4.3.1統(tǒng)計編碼-二進制算術(shù)編碼(例)case1case2case34.3.1統(tǒng)計編碼-CABACCABAC上下文自適應(yīng)的二進制算術(shù)編碼，廣泛應(yīng)用于現(xiàn)有的視頻編碼標準當中，例如H.264(2003),H.264SVC(2007),H.265(HEVC)(2013)…Furtherreadings:DetlevMarpe,HeikoSchwarz,andThomasWiegand,Context-basedadaptivebinaryarithmeticcodingintheH.264/AVCvideocompression，IEEECSVTJuly2003，Vol.13(No.7):620-6364.3.1統(tǒng)計編碼-RLC編碼行程長度編碼(Run-LengthCoding)一種無損壓縮數(shù)據(jù)編碼技術(shù)，它利用重復(fù)的數(shù)據(jù)單元有相同的數(shù)值這一特點對數(shù)據(jù)進行壓縮。對相同的數(shù)值只編碼一次，同時計算出相同值重復(fù)出現(xiàn)的次數(shù)。在JPEG，MPEG，H.261和H.263等壓縮方法中，RLE用來對圖像數(shù)據(jù)變換和量化后的系數(shù)進行編碼例:假設(shè)有一幅灰度圖像第n行的像素值如圖所示。用RLE編碼方法得到的代碼為：80315084180圖RLC編碼概念4.3.1統(tǒng)計編碼-RLC編碼(續(xù)1)Assumption:Longsequencesofidenticalsymbols.Example,4.3.1統(tǒng)計編碼-RLC編碼(續(xù)2)

4.3.1統(tǒng)計編碼-RLC編碼(續(xù)3)4.3.2字典編碼-引言迄今為止，我們大多假設(shè)符號是獨立的但這對許多常見數(shù)據(jù)類型來說是不對的如：文本、圖像和源代碼文件基本思想標識經(jīng)常出現(xiàn)的符號模式—保存于字典中對這些常出現(xiàn)的模式采用更有效的編碼方式—用其在字典中的索引作為碼字而對其它部分采用缺?。ú惶行В┑木幋a方式以期總的編碼效率更高注意這對如文本這樣的信源是合理的顯然對（接近）隨機數(shù)據(jù)不會有效吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮4.3.2字典編碼-例考慮某英文文本信源26字母和6個標點符號單字符，定長碼5比特/字符4字符模式，定長碼20比特/模式(324=220=1,048,576)假設(shè)為非均勻分布字典：256個最常出現(xiàn)的模式，每個用8比特編碼對其它模式用20比特編碼再增加1比特用于指示是上述兩種情況中的哪種4.3.2字典編碼-例(續(xù)1)若用p表示使用字典的概率，則比特率為

R=9p+21(1-p)=21-12p壓縮<=>21-12p<20=>p>0.084還不太壞在等概率假設(shè)下，p=0.00025

p越大，性能越好選擇最可能出現(xiàn)的模式存于字典中為了達到好的性能，需要知道信源的結(jié)構(gòu)信息有足夠的先驗信息，靜態(tài)字典否則，在編碼過程中獲得信源的知識自適應(yīng)字典4.3.2字典編碼-靜態(tài)字典靜態(tài)字典對信源的結(jié)構(gòu)有足夠的先驗知識時，利用先驗知識構(gòu)造字典對特定應(yīng)用特別有效只對針對其設(shè)計的特定應(yīng)用和數(shù)據(jù)有效例：電話號碼的區(qū)號例：學校的學生信息表地區(qū)長途區(qū)號北京市010上海市021天津市022重慶市023沈陽市024南京市025……烏魯木齊市0991喀什市09984.3.2字典編碼-自適應(yīng)字典有許多場合，開始時不知道要編碼數(shù)據(jù)的統(tǒng)計特性，也不一定允許事先知道它們的統(tǒng)計特性。字典編碼的思路：根據(jù)數(shù)據(jù)本身包含有重復(fù)代碼的特性例：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮如果用一些簡單的代號代替這些字符串，就可以實現(xiàn)壓縮，實際上就是利用了信源符號之間的相關(guān)性。字符串與代號的對應(yīng)表就是字典。實用的字典編碼算法的核心就是如何動態(tài)地形成字典，以及如何選擇輸出格式以減小冗余。4.3.2字典編碼-自適應(yīng)字典(續(xù)1)開始JacobZiv/AbrahamLempel1977(LZ77/LZ1),1978(LZ78/LZ2)1984TerryWelch(LZW)LZ77vs.LZ78兩種不同的方法有很多變種是很多主流壓縮的基礎(chǔ)4.3.2字典編碼-自適應(yīng)字典-分類第一類編碼算法用已經(jīng)出現(xiàn)過的字符串替代重復(fù)的部分編碼器的輸出僅僅是指向早期出現(xiàn)過的字符串的“指針”典型算法-LZ77圖4-1第一類詞典編碼概念4.3.2字典編碼-自適應(yīng)字典-分類(續(xù)1)第二類編碼算法從輸入的數(shù)據(jù)中創(chuàng)建一個“短語字典(dictionaryofthephrases)”編碼器輸出字典中的短語“索引號”，而不是短語典型算法-LZ78圖4-2第二類詞典編碼概念4.3.2字典編碼-LZ77基本方法：字典為先前已編碼序列的一部分搜索緩沖區(qū)為當前字典，通常為幾千字節(jié)機制：滑動窗口搜索緩沖區(qū)(Searchbuffer)、前向（lookahead）緩沖區(qū)、搜索指針(searchpointer)目標：在搜索緩沖區(qū)中，尋找與搜索指針指向的字符串匹配的最長串，并對其進行編碼基本原理：如果某些模式在局部重復(fù)出現(xiàn)，能得到更有效的表示4.3.2字典編碼-LZ77(續(xù)2)算法：輸入：符號序列輸出：編碼的符號組1、從當前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動窗口中找出最長的匹配字符串，如果找到，則進行步驟2，否則進行步驟3。2、輸出三元符號組(off,len,c)。其中off為窗口中匹配字符串相對窗口邊界的偏移，len為可匹配的長度，c為下一個字符。然后將窗口向后滑動len+1個字符，繼續(xù)步驟1。３、輸出三元符號組(0,0,c)。其中c為下一個字符。然后將窗口向后滑動len+1個字符，繼續(xù)步驟1。4.3.2字典編碼-LZ77(續(xù)3)(o)ffset=searchptr–searchbufferptr=1(l)ength=連續(xù)匹配的字符數(shù)=4(c)odeword=C(‘r’)編碼<o,l,c>=<1,4,C(‘r’)>If|searchbuff|=S,|A|=A,S+|LAbuff|=W定長碼：

log2S

+

log2W+log2A

Searchpointer4.3.2字典編碼-LZ77-編碼舉例序列cabracadabrarrarradW=13,S=7|cabraca|dabrar|rarrad對d，沒有匹配的字符串發(fā)送<0,0,C(d)> (可以做得更好?)|abracad|abrarr|rarrad |abracad|abrarr|rarrad |abracad|abrarr|rarrad |abracad|abrarr|rarrad發(fā)送<0,4,C(r)>4.3.2字典編碼-LZ77-編碼舉例(續(xù)1)|adabrar|rarrad|發(fā)送<4,3,C(r)>|rarrarr|ad|發(fā)送<1,1,C(d)>發(fā)送<4,5,C(d)>總結(jié)：三種情況沒有匹配匹配匹配串超過了搜索緩沖區(qū)4.3.2字典編碼-LZ77-解碼舉例輸入<0,0,C(d)><0,4,C(r)><4,3,C(r)><1,1,C(d)>輸出初始cabraca解碼：<0,0,C(d)>增加一個‘d’:c|abracad|解碼：<0,4,C(r)>從第0個位置開始，拷貝4個字母’abra’，增加一個’r’,解碼C(r) cabrac|adabrar|解碼：<4,3,C(r)>從第4個位置拷貝3個字母，增加一個’r’：cabracadab|rarrarr|解碼:<1,1,C(d)>從第1個位置開始，拷貝1個字母， cabracadab|rarrarr|a增加‘d’,解碼C(d) cabracadab|rarrarra|d解碼結(jié)果：cabracadabrarrarrad如果發(fā)送的是<4,5,C(d)>,怎么解碼?4.3.2字典編碼-LZ77-編碼小結(jié)使用固定大小窗口進行詞語匹配，而不是在所有已經(jīng)編碼的信息中匹配，是因為匹配算法的時間消耗往往很多，必須限制詞典的大小才能保證算法的效率；隨著壓縮的進程滑動詞典窗口，使其中總包含最近編碼過的信息，是因為對大多數(shù)信息而言，要編碼的字符串往往在最近的上下文中更容易找到匹配串。LZ77解碼器比編碼器簡單得多（非對稱壓縮）維持一個與編碼器窗口大小相同的緩沖區(qū)，并在緩沖區(qū)中找出匹配串，將匹配串及第3個字段的字符寫入輸出流，同時移進緩沖區(qū)在如文件壓縮（一次壓縮，多次還原）的場合很有用4.3.2字典編碼-LZ77的變種迄今為止自適應(yīng)模型，沒有先驗知識漸近接近知道信源統(tǒng)計知識的情況但是，局部性起到了很大作用改進變長編碼offset:各數(shù)值基本均勻分布，一般用定長碼length:可用Huffman碼/Golomb碼/Exp-Golomb碼PKZip,Zip,LharcmONG,gzip,ARJ可變緩沖區(qū)大小需設(shè)計較完善的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)對大緩沖區(qū)的快速搜索LZSS：搜索緩沖區(qū)（字典）用對分查找樹保持，前向緩沖區(qū)用循環(huán)隊列表示取消<0,0,C(x)>LZSS：只需增加1一個標記位，用于指示是否為單字符4.3.2字典編碼-LZ78LZ77假設(shè)模式滿足局部性LZ78:沒有搜索緩沖區(qū)——代之以顯式的字典編碼器/解碼器必須同步建立字典如沒有匹配，將字典原有詞條+當前沒有匹配的字符字典的新詞條編碼：<i,c>i=字典索引同LZ77，i=0表示在字典中沒有找到匹配的詞條c=下一字符的碼字4.3.2字典編碼-LZ78舉例索引條目字典：輸入：wabba

wabba

wabba

wabba

woo

woo

woo輸出：4.3.2字典編碼-LZ78舉例(續(xù)1)索引條目1w字典：輸入：

wabba

wabba

wabba

wabba

woo

woo

woo輸出：<0,C(w)>參考索引4.3.2字典編碼-LZ78舉例(續(xù)2)索引條目1w2a字典：輸入：

-abba

wabba

wabba

wabba

woo

woo

woo輸出：<0,C(w)><0,C(a)>參考索引4.3.2字典編碼-LZ78舉例(續(xù)3)索引條目1w2a3b字典：輸入：

--bba

wabba

wabba

wabba

woo

woo

woo輸出：<0,C(w)><0,C(a)><0,C(b)>參考索引4.3.2字典編碼-LZ78舉例(續(xù)4)索引條目1w2a3b4ba字典：輸入：

---ba

wabba

wabba

wabba

woo

woo

woo輸出：<0,C(w)><0,C(a)><0,C(b)><3,C(a)>參考索引4.3.2字典編碼-LZ78舉例(續(xù)5)索引條目1w2a3b4ba5

字典：輸入：

-----

wabba

wabba

wabba

woo

woo

woo輸出：<0,C(w)><0,C(a)><0,C(b)><3,C(a)><0,C()>參考索引4.3.2字典編碼-LZ78舉例(續(xù)6)索引條目1w2a3b4ba5

6wa字典：輸入：

------wabba

wabba

wabba

woo

woo

woo輸出：<0,C(w)><0,C(a)><0,C(b)><3,C(a)><0,C()><1,C(a)>參考索引4.3.2字典編碼-LZ78舉例(續(xù)7)索引條目1w2a3b4ba5

6wa7bb字典：輸入：

--------bba

wabba

wabba

woo

woo

woo輸出：<0,C(w)><0,C(a)><0,C(b)><3,C(a)><0,C()><1,C(a)><3,C(b)>參考索引4.3.2字典編碼-LZ78舉例(續(xù)8)索引條目1w2a3b4ba5

6wa7bb8a字典：輸入：

----------a

wabba

wabba

woo

woo

woo輸出：<0,C(w)><0,C(a)><0,C(b)><3,C(a)><0,C()><1,C(a)><3,C(b)><2,C()>參考索引4.3.2字典編碼-LZ78舉例(續(xù)9)索引條目1w2a3b4ba5

6wa7bb8a9wab字典：輸入：

------------wabba

wabba

woo

woo

woo輸出：<0,C(w)><0,C(a)><0,C(b)><3,C(a)><0,C()><1,C(a)><3,C(b)><2,C()><6,C(b)>參考索引4.3.2字典編碼-LZ78舉例(續(xù)10)索引條目1w2a3b4ba5

6wa7bb8a9wab10ba字典：輸入：

---------------ba

wabba

woo

woo

woo輸出：<0,C(w)><0,C(a)><0,C(b)><3,C(a)><0,C()><1,C(a)><3,C(b)><2,C()><6,C(b)><4,C()>參考索引4.3.2字典編碼-LZ78舉例(續(xù)11)索引條目1w2a3b4ba5

6wa7bb8a9wab10ba字典：輸入：

------------------wabba

woo

woo

woo輸出：<0,C(w)><0,C(a)><0,C(b)><3,C(a)><0,C()><1,C(a)><3,C(b)><2,C()><6,C(b)><4,C()><9,C(b)>11wabb參考索引4.3.2字典編碼-LZ78舉例(續(xù)12)字典：輸入：

----------------------a

woo

woo

woo輸出：<0,C(w)><0,C(a)><0,C(b)><3,C(a)><0,C()><1,C(a)><3,C(b)><2,C()><6,C(b)><4,C()><9,C(b)><8,C(w)>11wabb12aw索引條目1w2a3b4ba5

6