压缩搜索引擎教程

多媒体搜索引擎多媒体文档及其内容理解(2)多媒体信息的存储压缩与编码多媒体信息都很大1百万字的小说:2MB10分钟CD质量音频:100MB10分钟普通电视质量视频:8.
5GB直接存储难以承受如何节约存储空间压缩压缩为什么数据可以被压缩信息的表达形式有冗余DieFreiheit,dieLiebe,Tunbeidemirnot:MitLustfürdieLiebeGeh'ichindenTod,Dochopfr'ichauchsieWenndieFreiheitbedroht!
生命诚可贵爱情价更高若为自由故两者皆可抛压缩为什么数据可以被压缩信息的表达形式有冗余用典"效田光故事""二桃杀三士""墨守成规"压缩为什么数据可以被压缩冗余的本质数据交换的本质从发送者向接收者传递信息…………压缩为什么数据可以被压缩冗余的本质数据交换的本质从发送者向接收者传递信息但是,如果接收者有一些先验知识……………压缩为什么数据可以被压缩冗余的本质先验知识:可以更好地表示数据的模型收到的信息实际获得的信息先验知识预测器压缩为什么数据可以被压缩冗余的本质先验知识:可以更好地表示数据的模型需要传递的信息实际传递的信息预测模型预测器反向预测器获得的信息压缩预测器如何预测10101001110……如果正反出现的概率各50%无法预测压缩预测器如何预测10101001110……如果正面出现的概率90%预测正面出现:命中率90%只需传递反面出现的情况压缩预测器输入数据的概率分布不是完全均匀的福尔摩斯:跳舞的小人"你们也知道,在英文字母中E最常见,它出现的次数多到即使在一个短的句子中也是最常见的.
第一张纸条上的十五个符号,其中有四个完全一样,因此把它估计为E是合乎道理的……"压缩预测器输入数据的概率分布不是完全均匀的压缩预测器输入数据的概率分布不是完全均匀的如何把非均匀分布的信息实际用于压缩信息论香农(ClaudeShannon)http://en.
wikipedia.
org/wiki/Claude_E.
_Shannon《AMathematicalTheoryofCommunication》1948压缩信息论消息(message):收到的一个信息1,0A,B,C,D,……天,地,玄,黄……消息集报文(sequenceofmessages):一串消息压缩信息论香农:通信的模型传递的"东西":信息如何度量压缩信息论信息的度量单个消息的信息量消息s出现的概率符号集大小对数底与信息量的单位有关自信息如果正反概率相等:I(正)=log(1/0.
5)=log(2)如果底为2,则:I(正)=1比特(bit)压缩信息论信息的度量报文中消息的平均信息量{0,1},均匀分布I(0)=1bit,I(1)=1bit平均信息量1bit{0,1},分布{0.
9,0.
1}I(0)=0.
15bit,I(1)=3.
32bit平均信息量(0.
15+3.
32)/2=1.
735bit压缩信息论信息的度量报文中消息的平均信息量报文中各个消息的出现概率是不同的!
按概率加权{0,1},分布{0.
9,0.
1}I(0)=0.
15bit,I(1)=3.
32bit(0.
15*0.
9+3.
32*0.
1)=0.
467bit每收到一个这样的消息,获知0.
467比特信息可以压缩!
熵压缩信息论{0,1},分布{0.
9,0.
1}如何压缩如果最小输出信息单位是1比特如果输入信息必须以单比特处理每个输入比特至少需要一个输出比特无法压缩必须至少去除一个限制压缩信息论{0,1},分布{0.
9,0.
1}如果输入信息可以联合处理多个bit报文可以很长{00,01,10,11}{0.
81,0.
09,0.
09,0.
01}000,0110,10110,11111最短码长:1,最长码长:3平均码长:0.
81*1+0.
09*2+0.
09*3+0.
01*3=1.
291.
29/2=0.
645<1熵为0.
467编码压缩霍夫曼码(HuffmanCoding)按输入消息的概率分布,编制最佳的码书码书(codebook):输入消息和输出码字的对应关系码字(code):一个比特串可以被正确译码废话……前缀码一个码书中,任何码字都不是别的码字的前缀压缩霍夫曼码(HuffmanCoding)前缀码非前缀码会导致译码困难000,0101,10110,11111试译码:0110也许可以译码,但必须查看后续符号如何根据概率分布构造最优的前缀码码书霍夫曼树压缩霍夫曼码霍夫曼树000.
81010.
09100.
09110.
01A0.
1B0.
19C101010100001101011011111压缩霍夫曼码优点编解码均非常简单编码效率非常接近熵英文字母:熵4.
5,霍夫曼码平均码长:4.
7缺点给定概率分布,编码不唯一只能输出整数比特的码字压缩算术编码整个输入报文作为整体处理整个输入编码也以整体输出可以输出"小数码字"{A,B},分布{0.
9,0.
1}01ABAABA00.
900.
810.
7290.
810.
7290.
8019输出:区间中的任意一个数压缩算术编码需要无限精度的浮点运算不可能实现有限精度的整数实现如果编码器和解码器都使用相同的舍入方式,则有限精度整数实现是可能的普通实现:采用二进制RangeCode:采用很高的进制压缩零阶熵编码(霍夫曼码,算术编码)利用消息非均匀分布的特性实现压缩平均码长接近消息集的熵可以非常接近,但很难等于,一定不可能小于需要消息的概率模型编码器和解码器都需要如果概率模型不符合实际消息分布可能实际反而扩展数据大小如何保证解码器使用编码器所使用的同一个概率模型压缩零阶熵编码概率模型静态:整个编码过程中使用同一个概率模型完全静态:编码器和解码器事先协商好概率模型MPEG标准,JPEG标准可能不是最佳的预先统计:先把需要编码的数据预先扫描一次,获得最佳的概率模型JPEG标准需要同时传递概率模型运算量大,存储开销大,不适合大数据量应用压缩零阶熵编码概率模型动态:编码中依据前面输入的消息调整概率模型只要编码器和解码器都按照相同的规则特征概率模型,即可保证解码出正确的信息自适应编码自适应霍夫曼码较复杂,很少使用自适应算术编码自适应熵编码一般都是算术编码算术编码一般都使用自适应技术压缩零阶熵编码自适应算术编码AABAA:1B:10100.
5A:2B:100.
333A:3B:10.
250.
333A:3B:20.
250.
3A:4B:2假设:已经知道不同消息的个数如果不知道压缩零阶熵编码自适应算术编码转义消息(ESC)AABAESC:101遇到A:尚未遇到过,先输出ESC01区间未变:等效于输出0bit以其它手段输出消息AESC:2A:10.
6671A:2ESC:2……压缩零阶熵编码目前为止:只使用消息本身的信息进行编码"自信息":只与自身有关的信息如果考虑前面出现过的消息例:英文单词以th开头的:没有thh,thj,thk,thm,thn……开头的单词"_th"后面的字母的概率分布和"_"后面不一样利用上下文进行更精确的预测压缩一阶熵编码利用前面一个消息来预测本次消息零阶概率表:统计单个消息的概率一阶概率表:统计跟在某个消息后的消息的概率每个零阶概率表中的消息下连一个一阶概率表编码中:如果发现前一个消息的一阶概率表中有当前消息的记录,则使用该记录编码;如果没有,则利用该一阶概率表输出一个ESC,然后用零阶概率表输出本次消息如果零阶概率表还没有再ESC压缩高阶熵编码(PPM:PredictionbyPartialMatch)一阶概率表还可接二阶概率表利用前面2个信息进行预测还可以接更高阶概率表内存需求量随阶的增加指数增加例:英语文字8阶熵:2.
4(零阶熵:4.
5)等效于7阶熵编码估计的无穷阶熵:1.
3理论最佳压缩率(目前最佳:RK,1.
89)如何现实地进行高阶预测压缩压缩编码小结能够实现压缩的条件可以较准确地预测下一个消息预测越准确,压缩率越高可以用于预测的信息预先的知识压缩和解压缩器必须事先约定好报文中已经传递的消息统计前面的消息预测后面的消息两个方面:(1)概率分布;(2)上下文如何尽可能加长用于预测的上下文压缩字典编码LZ77及其变种(滑动窗口)不吃葡萄倒吐葡萄皮……吃葡萄不吐葡萄皮用什么预测最好输出信息:三元组(指针,长度,字符)指针:指向前面最长匹配串长度:最长匹配串长度字符:输入消息的下一个字符压缩字典编码LZ77及其变种(滑动窗口)最长匹配:1(NULL,0,不)吃葡萄不吐葡萄皮不吃葡萄倒吐葡萄皮压缩字典编码LZ77及其变种(滑动窗口)吃葡萄不吐葡萄皮不吃葡萄倒吐葡萄皮(NULL,0,不)最长匹配:3(-9,3,倒)这个字有很大的概率找不到长匹配直接输出压缩字典编码LZ77及其变种(滑动窗口)吃葡萄不吐葡萄皮不吃葡萄倒吐葡萄皮(NULL,0,不)最长匹配:4(-9,3,倒)(-9,4,)输出:3个三元组利用熵编码可以进一步压缩三元组LZ77的各种变种有很多细节上的差异(如:输出不同的三元组)致谢:复旦大学计算机系赵进教授http://homepage.
fudan.
edu.
cn/~jzhao/course/mm2008/index.
htm压缩字典编码LZ77及其变种(滑动窗口)ZIP,gzip窗口大小:32KB7-zip(LZMA)窗口大小:64KB-1024MB比ZIP高30-70%压缩率的情况下,和ZIP差不多的速度解决的问题:如何快速找到最长匹配索引压缩字典编码LZ78及其变种维护一个字典,字典中记录了最有可能出现的词条.
如果输入流中发现一个词条,则输出代号而不是词条本身.
GIF:LZW算法,字典4096项适合压缩超长串大量重复的文件(如卡通图片)不适合压缩短串经常重复的文件如文字文档:LZ77更适合压缩基于各种变换的编码BTW,MTF,……适合语音和图像的编码下一堂课