《信息论与编码基础》课件 17 ppm

§6.3PPM编码§6压缩编码方法1.引入2.原理3.讨论§6.3PPM编码1.引入压缩编码的模型:1)precise.精确得到信源符号的分布概率;2)Unequal.由模型产生的越大越好。1.引入?算术编码中使用的小区间联合概率若信源无记忆：算术编码§6.3PPM编码1.引入但是，信源一般是有记忆的。§6.3PPM编码1.引入§6.3PPM编码英文文本存在不同层次的冗余度:1单字符，概率不同；2字符组合，一些组合的概率高于其它；3上下文，文法规定；1.引入§6.3PPM编码AoccdrnigtoarscheearchatCmabrigde

Uinervtisy,itdeosn't

mttaerinwaht

oredrtheltteersinawrodare,theolny

iprmoetnt

tihngistahtthefristandlsat

ltteerbeattherghit

pclae.Thersetcanbeatotalmsesandyoucansitll

raeditwouthit

porbelm.Tihsisbcuseaethehuamn

mnid

deosnotraed

ervey

lteterbyistlef,butthewrodasawlohe.Amzanig!1.引入§6.3PPM编码不同层次，得到不同熵Shannon的结果---->1阶熵，4.12；无穷熵，1~2(0.6~1.3)1.引入§6.3PPM编码PPM试图利用第2/3层次的冗余度例如，‘u’in‘qu’:p(u)=0.0228;模型要求:2)Unequal.由模型产生的越大越好。p(u/q)>=0.951.引入§6.3PPM编码PPM:PredictionbyPartialMatching§6.3PPM编码*Cleary,Witten.Datacompressionusingadaptivecodingandpartialstringmatching.IEEETr

Commun,1984,32(4):396--402*Moffat.ImplementingPPMdatacompressionscheme.IEEETr

Commun,1990,38(11):1917--1921§6.3PPM编码Prof.J.Cleary§6.3PPM编码Prof.I.Witten§6.3PPM编码§6压缩编码方法1.引入2.原理

3.讨论2.原理§6.3PPM编码有记忆系统：

Markov模型N阶Markov模型，x1x2…xN

xN+1p(xN+1|x1x2…xN)2.原理§6.3PPM编码-1阶：单符号，认为符号是均衡的上下文表Contexttable0阶：单符号，符号实际概率1阶,2阶,…N阶：p(xN+1|x1x2…xN)§6.3PPM编码上下文表(第16拍):完成编码“this$is$his$hat$”0阶a:1h:3i:3s:3t:2$:41阶at:1ha:1hi:2is:3s$:3th:1t$:1$h:2$i:12阶at$:1hat:1his:2is$:3s$h:2s$i:1thi:1$ha:1$hi:1$is:1-1阶ahist$2.原理§6.3PPM编码p(a)<p(a|h)<p(a|$h)高阶Markov模型，符合压缩编码希望的:1)precise.精确得到信源符号的分布概率;2)Unequal.由模型产生的越大越好。2.原理§6.3PPM编码PPM编码，利用高阶Markov模型建模，实现高效压缩。§6.3PPM编码§6压缩编码方法1.引入2.原理3.讨论

3.讨论§6.3PPM编码(1)高效压缩英文文本，应用4阶上下文表，PPM编码的平均码长，2.2bits/symbol相同情况，0阶压缩（算术编码，或近似