信息索引技术

1、搜索引擎技术主讲教师：王旭 博士 深圳大学计算机与软件学院未来媒体技术与计算研究所Email: 1模块一：商用搜搜索引擎擎架构与与原理搜索引擎擎基础网页抓取取技术网页信息息预处理理技术信息索引引技术信息查询询与评价价技术参考书籍籍：袁津生，李群编编著，搜索引擎擎基础教教程，清华大大学出版版社其他文献献/互联网资资料深圳大学学未来媒媒体技术术与计算算研究所所2深圳大学学未来媒媒体技术术与计算算研究所所信息索引引技术经过网页页预处理理后，可可以建立立索引数数据库。对于数数目庞大大的文档档数据库库使用简简单匹配配方法是是不可行行的，需需要对文文档的表表示建立立索引。为了提提高检索索效率，应该按按照一

2、定定的规则则建立索索引。索索引文件件一般是是按照倒倒排文件件的格式式存放的的，索引引的建立立包括：（1）分析：处理文文件中可可能的错错误。（2）索引：完成分分析的文文件被编编码存入入索引数数据库。（3）排序：将索引引数据库库按照一一定的规规则排序序，产生生全文索索引。3深圳大学学未来媒媒体技术术与计算算研究所所信息索引引技术5.1顺排检索索5.2倒排索引引5.3文本压缩缩技术4深圳大学学未来媒媒体技术术与计算算研究所所5.1顺顺排检检索顺排文档档检索的的主要思思想是将将文档中中的每一一条记录录依次去去匹配用用户的检检索提问问集合，文档处处理完毕毕后，将将各提问问的命中中结果归归并分发发给有关关

3、用户。顺排文档档检索是是用文档档中记录录一条一一条去匹匹配提问问的，是是顺序对对文档记记录检索索的方法法，所以以称为顺顺排文档档检索。顺排文档档的关键键技术是是采用列列表处理理方法将将提问逻逻辑式（检索式式）变换换成等价价的提问问展开式式，按提提问展开开表的内内容对顺顺排文档档的每篇篇文献进进行检索索。常用的顺顺排文档档检索方方法主要要有：表表展开法法、逻辑辑树法等等5深圳大学学未来媒媒体技术术与计算算研究所所表展开法法表展开法法的主要要思想是是：将代代表用户户提问的的逻辑提提问式转转换成表表的形式式，该表表规定了了表的内内容走向向和是否否命中的的判断，检索时时根据表表的走向向及其他他相关信信

4、息来判判断每条条记录是是否命中中。展开表概概念用表来表表达逻辑辑提问式式，要求求能够将将提问式式中复杂杂的逻辑辑运算关关系充分分体现，每个检检索词的的检索匹匹配要求求能够精精确反映映，记录录最终的的命中与与否应能能准确给给出6深圳大学学未来媒媒体技术术与计算算研究所所表展开法法地址栏确确定了每每个检索索词在表表中的位位置，当当检索条条件满足足或不满满足时应应做什么么处理指指向告之之当该词词满足（不满足足）检索索条件后后应做什什么处理理。7深圳大学学未来媒媒体技术术与计算算研究所所展开表生生成生成展开开表是一一个复杂杂的过程程，需要要考虑到到检索词词、检索索运算符符、改变变运算次次序的括括号等，

5、并生成成可供检检索匹配配的表格格形式。整个生生成过程程分为两两部分：前处理理和后处处理。前处理的的任务是是：逐个个检查逻逻辑提问问式中的的字符，并从上上至下填填写表格格。后处理的的主要任任务就是是填满整整个表的的空白单单元，填填表的依依据是表表中“级级位”栏栏的前后后级位值值，填表表的顺序序是从下下向上，直至表表的顶部部，从而而得到一一个完整整的提问问展开表表。8深圳大学学未来媒媒体技术术与计算算研究所所展开表生生成示例例逻辑提问问式A*（BC）（D*（EF*G）的的展开表表生成过过程：9深圳大学学未来媒媒体技术术与计算算研究所所表展开法法的检索索检索时，需将所所有提问问展开表表输入内内存以提

6、提高查比比速度。查比时，每从数数据库中中读取一一条记录录，就为为该记录录生成一一个检索索标识表表，检索索标识表表由该记记录的可可检索项项组成，然后将将检索标标识表中中的每一一检索项项去查对对展开表表，并对对命中的的检索词词做上标标记。当该记录录标识表表中的所所有检索索项查询询完毕后后，再根根据每一一展开表表的查询询情况，分析提提问是否否命中。对于命中中者，就就在相应应的提问问号下记记下记录录号及相相关信息息，然后后再取下下一条记记录进行行对比。全部查比比完毕后后，才能能得到本本次检索索的最终终结果。10深圳大学学未来媒媒体技术术与计算算研究所所逻辑树展展开法逻辑树展展开法是是将逻辑辑提问式式展

7、开成成树型结结构（下下称主树树），运运算符构构成树的的结点，检索词词被视为为树叶，所有检检索词也也按照有有限自动动机原理理构造成成字符树树（下称称辅树），主树树与辅树树间的相相关元素素用指针针链接。检索时，采取爬爬树原则则，先用用文档中中的索引引词逐字字符的对对比爬行行辅树，走到树树的一个个端头（树叶），然后后依照指指针登记记主树，并根据据倒爬树树方式分分析提问问是否命命中。逻辑树展展开法包包括三个个部分：逻辑提提问式的的分解、字符树树的生成成、检索索实现。11深圳大学学未来媒媒体技术术与计算算研究所所逻辑树展展开法1逻辑提提问式分分解逻辑提问问式分解解的分解解目标为为：提供供可直接接用于检检

8、索实现现的主逻逻辑树表表、检索索词地址址表以及及检索词词在检索索式中的的位置表表。这些些表在检检索实践践中分别别发挥着着应有的的作用。（1）主逻辑辑树表主逻辑树树表是逻逻辑提问问式的一一种树形形表达形形式，它它用层次次型的树树形结构构把运算算符、运运算项关关联起来来，其主主要内容容包括；运算种种类、子子项个数数、父项项地址以以及检索索处理登登记栏。12深圳大学学未来媒媒体技术术与计算算研究所所逻辑树展展开法（2）检检索词地地址表检索词地地址表是是主逻辑辑树表与与辅表的的联系纽纽带，在在检索中中，当一一个检索索词命中中以后，通过辅辅表找到到其在检检索词地地址表的的位置，再根据据该表中中记录的的主

9、表位位置进行行检索处处理（在在检索处处理栏加加1等操操作）。该表由两两个字段段组成：检索状状况登录录区、检检索词在在主表中中位置。13深圳大学学未来媒媒体技术术与计算算研究所所逻辑树展展开法（3）检检索词位位置表检索词位位置表是是在逻辑辑提问式式转换成成逻辑树树表的过过程中，临时生生成的一一个中间间处理过过程表，该表还还将作为为从逻辑辑提问式式到词逻逻辑树（辅表）的桥梁梁，一旦旦辅表生生成完毕毕，该表表将被清清除。14深圳大学学未来媒媒体技术术与计算算研究所所逻辑树展展开法（4）中中间工作作表由于在进进行逻辑辑提问式式到逻辑辑树表的的转换过过程中，涉及一一些中间间数据，这些数数据在生生成逻辑辑

10、树时需需多次使使用，因因此需要要建立一一个中间间过程工工作区（中间工工作表）来记录录这些数数据，一一旦主逻逻辑树生生成完毕毕，该表表即可以以清除。15深圳大学学未来媒媒体技术术与计算算研究所所逻辑树展展开法（5）主主逻辑树树表的生生成主逻辑树树表的生生成算法法思想为为：采用用多次扫扫描的分分层分解解构造法法。首先先分解出出逻辑式式中最外外层“”号下下的子项项，括号号内的项项暂时不不分解；其次扫扫描已分分解出的的子项（在最外外层没有有“”项的情情况下对对整个逻逻辑式进进行）中中的“*”号的的运算子子项，若若该子项项为括号号括起项项，则仍仍分解“”号号子项；最后分分解“-”号子子项。16深圳大学学

11、未来媒媒体技术术与计算算研究所所逻辑树展展开法2检索词词字符树树表检索词字字符树表表的生成成吸收了了Aho和Corasick的思想，将所有有检索词词构造成成有限自自动机状状态表，该表是是一个由由字符（英文字字母、数数字及其其他符号号）和状状态层次次组成的的二维表表 。17深圳大学学未来媒媒体技术术与计算算研究所所逻辑树展展开法字符树表表内容根根据状态态转移函函数g（n，x）填写写，一个个检索词词结束就就调用函函数output（x）填写写地址表表指针。例如，检索词词簇he，she，his，hers，shot，history，它它们在检检索词地地址表中中的位置置如下：18深圳大学学未来媒媒体技术术

12、与计算算研究所所19深圳大学学未来媒媒体技术术与计算算研究所所检索词字字符树结结构20深圳大学学未来媒媒体技术术与计算算研究所所逻辑树展展开法3逻辑树树法检索索逻辑提问问式最终终转换为为逻辑树树的三个个表：主主逻辑树树表、检检索词地地址表、检索词词字符树树表。这三个表表构成了了用户检检索提问问档，整整个检索索主要依依赖这三三个表。21深圳大学学未来媒媒体技术术与计算算研究所所BF（Brute-Force）算法BF算法法是一种种串的模模式匹配配的算法法。BF算法法的设计计思想是是将主串串S的第第一个字字符和模模式T的的第1个个字符比比较，若若相等，继续逐逐个比较较后续字字符；若若不等，从主串串S

13、的下下一字符符起，重重新与T第一个个字符比比较。直直到主串串S的一一个连续续子串字字符序列列与模式式T相等等。返回回值为S中与T匹配的的子序列列第一个个字符的的序号，即匹配配成功。否则，匹配失失败，返返回值1。22深圳大学学未来媒媒体技术术与计算算研究所所BF（Brute-Force）算法主串S=“abbcdefg”，模模式串T=“cde”，则模模式匹配配的过程程。23深圳大学学未来媒媒体技术术与计算算研究所所KMP(Knuth-Morris-Pratt)算法假设P为给定的的子串（也叫模模式串），T是待查找找的字符符串（也也叫目标标串），要求从从T中找出与与P相同的所所有子串串，这称称为模式式

14、匹配问问题。我我们先来来看个例例子。从T的最左边边开始比比较，使使得TK= PK,则匹配成成功。24深圳大学学未来媒媒体技术术与计算算研究所所KMP算算法若P=“aaaba”，T=“aaabbaaaba“。用P中的字字符依次次与T中中的字符符进行比比较，遇遇到不相相等的字字符，则则可将P右移一一个字符符，重新新进行比比较，直直到某次次匹配成成功或者者到达P的最右右字符移移出T为为止。25深圳大学学未来媒媒体技术术与计算算研究所所BM（Boyer-Moore）算算法给定一个个特定的的字串P（通常又又称为模模式），在一个个大的文文本T中进行查查找，确确定P是否在T中出现，出现则则给出相相应位置置。

15、BM算法的基基本思想想是先对对模式P进行预处处理，计计算两个个偏移函函数：BadChar和Goodsuffix，然后将将文本和和模式对对齐，从从右往左左进行匹匹配，当当文本字字符与模模式字符符不匹配配时，根根据函数数BadChar和Goodsuffix计算出的的偏移值值，取两两者中的的大者。将文本本指针往往右移，匹配成成功则予予以输出出。26深圳大学学未来媒媒体技术术与计算算研究所所5.2倒倒排索索引Indexesaredatastructures designed to makesearch fasterWebSearch的需求:快速响应应时间(fasterresponsetime)支持更新

16、新(supportsupdates)基于Ranking的文本搜搜索方法法文件内容容QueryRanking算法Ranking抽象模型型27Ranking抽象模型型深圳大学学未来媒媒体技术术与计算算研究所所28Ranking抽象模型型(例子）时效性重要性深圳大学学未来媒媒体技术术与计算算研究所所29深圳大学学未来媒媒体技术术与计算算研究所所倒排索引引倒排文档档是一种种面向单单词的索索引机制制，相对对顺排文文档而言言，是将将顺排文文档中可可检索字字段的作作者名、关键词词、分类类号等取取出，按按一定规规则排序序，归并并相同词词汇，并并把在顺顺排文档档中相关关记录的的记录号号集合赋赋予其后后，以保保证

17、通过过某一特特征词能能够快速、方便地获取相相关记录录。30倒排索引引示例“Collection”深圳大学学未来媒媒体技术术与计算算研究所所31最简单形形式的倒倒排索引引深圳大学学未来媒媒体技术术与计算算研究所所32包含计数数信息的的倒排索索引深圳大学学未来媒媒体技术术与计算算研究所所33包含位置置信息的的倒排索索引深圳大学学未来媒媒体技术术与计算算研究所所34ProximityMatches短语匹配配e.g.,tropicalfish,or“findtropicalwithin5wordsoffish”包含位置置信息的的倒排索索引深圳大学学未来媒媒体技术术与计算算研究所所35域(Field)和

18、ExtentList搜索中的的文档结结构信息息限制性信信息：时时间，来来源等重要信息息：标题题解决方案案:根据域的的类型建建立倒排排索引倒排索引引添加域域信息使用extentlists深圳大学学未来媒媒体技术术与计算算研究所所36ExtentListsExtent:文件中的的邻近区区域单词位置置信息每个域属属性都有有相应的的Extentlistextentlist深圳大学学未来媒媒体技术术与计算算研究所所37其他预先计算算出倒排排索引中中的分数数“fish”(1:3.6),(3:2.2)提升速度度，降低低动态调调整的性性能基于分数数顺序的的索引只关注与与分数最最高的文文档对单词索索引队列列效果

19、最最佳深圳大学学未来媒媒体技术术与计算算研究所所38深圳大学学未来媒媒体技术术与计算算研究所所倒排索引引倒排文档档的检索索算法一一般分成成如下三三步进行行：（1）词汇查查找将查询串串中的单单词和模模式分割割成独立立的部分分，短语语和近似似查询串串被分割割成单个个词汇。（2）查找词词汇出现现的情况况获取与查查询串中中所有词词汇相关关的出现现情况列列表。（3）词汇出出现情况况的操作作主要是通通过对上上一步中中获取的的词汇出出现情况况的操作作实现短短语查询询、近似似查询和和布尔查查询。39深圳大学学未来媒媒体技术术与计算算研究所所倒排文档档倒排文档档的组成成元素主主要包括括：关键键字（作作者、主主题

20、词、分类号号等）、目长（含有该该关键字字记录的的条数）、记录录号集合合（所有有与该关关键字有有关的记记录号）。倒排文档档的建立立是建筑筑在顺排排文档（主文档档）的基基础之上上，它是是从主文文档中提提取可检检索字段段内容，也有采采取自动动从标题题、文摘摘或全文文中提取取关键词词，利用用所得到到的这些些属性词词来建立立倒排文文档。40深圳大学学未来媒媒体技术术与计算算研究所所倒排文档档的建立立由顺排文文档构造造倒排文文档需要要经过抽抽词、排排序、归归并和组组织等过过程，具具体实现现步骤如如下：选择需要要做索引引的字段段属性（如作者者、关键键词等），抽出出其中的的内容，并在其其后附上上其记录录号。对

21、抽出的的内容进进行排序序，使之之便于归归并相同同内容。对相同内内容进行行归并，把合并并后的内内容放入入倒排文文档的主主键字段段（如标标引词、作者等等），统统计每一一数据的的频次作作为目长长，把每每一内容容后的记记录号顺顺序放在在记录号号集合字字段。41构建方法法(简单法)索引的构构建相当当于从正正排表到到倒排表表的建立立过程。当我们们分析完完网页时时,得到的是是以网页页为主码码的索引引表。当当索引建建立完成成后,应得到倒倒排表,具体流程程如图所所示：流程描述述如下：1）将文档档分析称称单词term标记，2）使用hash去重单词词term3）对单词词生成倒倒排列表表倒排列表表就是文文档编号号Do

22、cID，没有包包含其他他的信息息（如词词频，单单词位置置等），这就是是简单的的索引。这个简单单索引功功能可以以用于小小数据，例如索索引几千千个文档档。然而而它有两两点限制制：1）需要有有足够的的内存来来存储倒倒排表，对于搜搜索引擎擎来说， 都是是G级别数据据，特别别是当规规模不断断扩大时时,我们根本本不可能能提供这这么多的的内存。2）算法是是顺序执执行，不不便于并并行处理理。深圳大学学未来媒媒体技术术与计算算研究所所42构建方法法(合并并法)深圳大学学未来媒媒体技术术与计算算研究所所1）页面分分析，生生成临时时倒排数数据索引引A，B，当临时时倒排数数据索引引A，B占满内存存后，将将内存索索引A

23、，B写入临时时文件生生成临时时倒排文文件，2)对生成的的多个临临时倒排排文件,执行多路路归并,输出得到到最终的的倒排文文件。43更新策略略完全重建建策略：当新增增文档到到达一定定数量，将新增增文档和和原先的的老文档档整合，然后利利用静态态索引创创建方法法对所有有文档重重建索引引，新索索引建立立完成后后老索引引会被遗遗弃。此此法代价价高，但但是主流流商业搜搜索引擎擎一般是是采用此此方式来来维护索索引的更更新再合并策策略：当新增增文档进进入系统统，解析析文档，之后更更新内存存中维护护的临时时索引，文档中中出现的的每个单单词，在在其倒排排表列表表末尾追追加倒排排表列表表项；一一旦临时时索引将将指定内

24、内存消耗耗光，即即进行一一次索引引合并，这里需需要倒排排文件里里的倒排排列表存存放顺序序已经按按照索引引单词字字典顺序序由低到到高排序序，这样样直接顺顺序扫描描合并即即可。其其缺点是是：因为为要生成成新的倒倒排索引引文件，所以对对老索引引中的很很多单词词，尽管管其在倒倒排列表表并未发发生任何何变化，也需要要将其从从老索引引中取出出来并写写入新索索引中，这样对对磁盘消消耗是没没必要的的。原地更新新策略：试图改进进再合并并策略，在原地地合并倒倒排表，这需要要提前分分配一定定的空间间给未来来插入，如果提提前分配配的空间间不够了了需要迁迁移。混合策略略：能够结合不同同索引更更新策略略的长处处，将不不同

25、索引引更新策策略混合合，以形形成更高高效的方法。深圳大学学未来媒媒体技术术与计算算研究所所44深圳大学学未来媒媒体技术术与计算算研究所所5.3文本压缩缩技术45深圳大学学未来媒媒体技术术与计算算研究所所文本压缩缩文本压缩缩是指用用较少的的位或字字节来表表示文本本，这样样将可以以显著地地减小计计算机中中存储文文本的空空间大小小。常规的压压缩方法法是基于于字符的的压缩，但是，为了能能够在信信息检索索系统中中进行快快速的单单词匹配配，压缩缩的基本本单位是是单词而而不是字字符。在选择压压缩方法法时，除除了要考考虑空间间的节省省程度外外，还要要考虑压压缩文档档的编码码和解码码速度。例子：CPU处理速度度

26、：m,内存读取取速度：p，处理速速度：min(m,p)压缩率：r1，解码因因子：d0:only 10 bits, buthard to decode压缩基本本原理Ambiguousencoding:无法解码码another decoding:whichrepresents:useunambiguouscode:编码方案案:Delta编码Word count dataisgoodcandidatefor compressionmany small numbersand fewlargernumbersencodesmallnumberswith small codesDocumentnumber

27、s areless predictablebutdifferencesbetweennumbers in an orderedlistaresmallerandmorepredictableDeltaencoding:encodingdifferencesbetween document numbers(d-gaps)Delta编码Invertedlist (without counts)Differencesbetween adjacent numbersDifferencesforahigh-frequencywordareeasier to compress,e.g.,Differenc

28、esforalow-frequency wordare large,e.g.,深圳大学学未来媒媒体技术术与计算算研究所所统计方法法统计方法法依赖于于对每个个符号在在文本中中出现的的概率进进行估计计，估计计得越准准确，压压缩的效效果就越越好。文本中所所有可能能的符号号的集合合称为字字母表。对每个个符号进进行概率率估计的的任务称称为建模模。模型的本本质是建建立信息息库中文文档的概概率分布布。一旦旦有了这这些概率率，符号号就转成成二进制制数，这这个过程程称为编编码。编编码和解解码都使使用了同同一个模模型，解解码是编编码的逆逆过程。常见的的统计编编码方案案有两种种：霍夫夫曼编码码和算术术编码。51深圳

29、大学学未来媒媒体技术术与计算算研究所所霍夫曼（Huffman）编编码霍夫曼编编码的思思想是为为每一个个不同的的符号分分配一个个固定长长度的位位编码。对给定定的数据据流，计计算每个个字符的的出现频频率。根根据频率率表，运运用霍夫夫曼算法法可确定定分配各各字符的的最小位位数，然然后给出出一个最最优的编编码。给出现频频率较高高的字符符赋以较较短编码码，而给给出现频频率较低低的字符符赋以较较长的编编码。每每个数据据的编码码各不相相同。这些代码码都是二二进制码码，且码码的长度度是可变变的。分分配的码码字存入入编码表表中，从从而实现现压缩。解压的的唯一性性能够得得以保证证是因为为不会有有代码是是另一个个代

30、码的的前缀。52深圳大学学未来媒媒体技术术与计算算研究所所霍夫曼编编码的例例子我们假定定字符集集是A，B，C，D，E，F，G，H，在给每每个字符符分配比比特模式式之前，我们给给每个字字符赋予予一个出出现频率率的权值值。假定定对应的的权值分分别是4、5、6、7、10、10、18和40。然后我我们建立立字符树树，过程程按照下下面的步步骤进行行。统计频频率。将将原始符符号按照照出现概概率递减减(或递增)的顺序排排列；将两个个最小出出现概率率进行合合并相加加，得到到的结果果作为新新符号的的出现概概率；53深圳大学学未来媒媒体技术术与计算算研究所所霍夫曼编编码的例例子重复进进行步骤骤和直到概概率相加加的

31、结果果等于1为止；分配码码字。将将形成的的二叉树树左结点点标0，右结点点标1（或左结结点标1，右结结点标0），从从根结点点回溯到到原始符符号，记记录根结结点到当当前符号号之间的的0，1序列，从而得得到每个个符号的的编码。因为每个个编码都都是通过过树上从从根开始始的不同同路径得得到的，所以没没有一个个编码是是其他编编码的前前缀。54深圳大学学未来媒媒体技术术与计算算研究所所霍夫曼编编码的例例子55深圳大学学未来媒媒体技术术与计算算研究所所霍夫曼编编码的例例子56深圳大学学未来媒媒体技术术与计算算研究所所霍夫曼编编码的例例子57深圳大学学未来媒媒体技术术与计算算研究所所霍夫曼编编码的例例子编码分配

32、配字符权编码字符权编码A400011E100000B50000F10011C60101G18001D70100H40158深圳大学学未来媒媒体技术术与计算算研究所所算术编码码算术编码码的基本本原理是是将编码码的消息息表示成成实数0和1之间的一一个间隔隔（Interval），消息息越长，编码表表示它的的间隔就就越小，表示这这一间隔隔所需的的二进制制位就越越多。算术编码码用到两两个基本本的参数数：符号号的概率率和它的的编码间间隔。信信源符号号的概率率决定压压缩编码码的效率率，也决决定编码码过程中中信源符符号的间间隔，而而这些间间隔包含含在0到1之间。编编码过程程中的间间隔决定定了符号号压缩后后的输

33、出出。59深圳大学学未来媒媒体技术术与计算算研究所所算术编码码步骤编码器器在开始始时将当当前间隔隔 L，H）设置为为0，1）。对每一一事件，编码器器按步骤骤（a）和（b）进行处处理（a）编码器器将当前前间隔分分为子间间隔，每每一个事事件一个个。（b）一个子子间隔的的大小与与下一个个将出现现的事件件的概率率成比例例，编码码器选择择子间隔隔对应于于下一个个确切发发生的事事件相对对应，并并使它成成为新的的当前间间隔。最后输输出的当当前间隔隔的下边边界就是是该给定定事件序序列的算算术编码码。60深圳大学学未来媒媒体技术术与计算算研究所所算术编码码过程举举例假设信源源符号为为00,01,10,11，这这

34、些符号号的概率率分别为为0.1,0.4,0.2,0.3，根根据这些些概率可可把间隔隔0,1)分分成4个个子间隔隔：0,0.1), 0.1,0.5),0.5,0.7),0.7,1)，其中中x,y)表表示半开开放间隔隔，即包包含x不不包含y。如果二进进制消息息序列的的输入为为：10 00 11 00 10 11 01。整个个编码过过程如图图所示。61深圳大学学未来媒媒体技术术与计算算研究所所算术编码码过程举举例62深圳大学学未来媒媒体技术术与计算算研究所所算术编码码过程举举例63深圳大学学未来媒媒体技术术与计算算研究所所算术编码码过程举举例64深圳大学学未来媒媒体技术术与计算算研究所所字典方法法字

35、典编码码根据的的是数据据本身包包含有重重复代码码这个特特性。字字典编码码法的种种类很多多，归纳纳起来大大致有两两类。第一类字字典编码码的想法法是查找找正在压压缩的字字符序列列是否在在以前输输入的数数据中出出现过，然后用用已经出出现过的的字符串串替代重重复的部部分，它它的输出出仅仅是是指向早早期出现现过的字字符串的的“指针针”。这这里所指指的“字字典”是是指用以以前处理理过的数数据来表表示编码码过程中中遇到的的重复部部分。第二类字字典编码码的想法法是从输输入的数数据中创创建一个个短语词词典，这这种短语语不一定定是具有有具体含含义的短短语，它它可以是是任意字字符的组组合。65深圳大学学未来媒媒体技

36、术术与计算算研究所所第一类字字典编码码66深圳大学学未来媒媒体技术术与计算算研究所所第二类字字典编码码67深圳大学学未来媒媒体技术术与计算算研究所所算法中用用到的几几个术语语（1）输入数数据流。指被压压缩的字字符序列列。（2）字符。输入数数据流中中的基本本单元。（3）编码位位置。输输入数据据流中当当前要编编码的字字符位置置，指前前向缓冲冲存储器器中的开开始字符符。（4）前向缓缓冲存储储器。存存放从编编码位置置到输入入数据流流结束的的字符序序列的存存储器。（5）窗口。指包含含W个字符的的窗口，字符是是从编码码位置开开始向后后数也就就是最后后处理的的字符数数。（6）指针。指向窗窗口中的的匹配串串且

37、含长长度的指指针。68深圳大学学未来媒媒体技术术与计算算研究所所LZ77编码算算法（1）把编码码位置设设置到输输入数据据流的开开始位置置。（2）查找窗窗口中最最长的匹匹配串。（3）以“(Pointer,Length)Characters”的格式输输出，其其中Pointer是指向窗窗口中匹匹配串的的指针，Length表示匹配配字符的的长度，Characters是前向缓缓冲存储储器中的的不匹配配的第1个字符。（4）如果前前向缓冲冲存储器器不是空空的，则则把编码码位置和和窗口向向前移（Length+1）个字符符，然后后返回到到步骤（2）。69深圳大学学未来媒媒体技术术与计算算研究所所LZ77编码算算

38、法70深圳大学学未来媒媒体技术术与计算算研究所所LZW编编码LZW编编码是围围绕称为为词典的的转换表表来完成成的。转转换表用用来存放放称为前前缀（Prefix）的字符符序列，并且为为每个表表项分配配一个码码字（Code word），或者者叫做序序号。转换表实实际上是是把8位位ASCII字字符集进进行扩充充，增加加的符号号用来表表示在文文本或图图像中出出现的可可变长度度ASCII字字符串。扩充后后的代码码可用9位、10位、11位位、12位甚至至更多的的位来表表示。71深圳大学学未来媒媒体技术术与计算算研究所所LZW编编码算法法的执行行步骤步骤1：开始时时的词典典包含所所有可能能的根（Root），

39、而当当前前缀缀P是空的；步骤2：当前字字符(C)：=字符流中中的下一一个字符符；步骤3：判断新新的字符符串P+C是否在词词典中（1）如果“是”：P：= P+C/（用C扩展P）；（2）如果“否” 把代代表当前前前缀P的码字输输出到码码字流； 把新新的字符符串P+C添加到词词典； 令P：= C/（现在的的P仅包含一一个字符符C）；72深圳大学学未来媒媒体技术术与计算算研究所所LZW编编码算法法的执行行步骤步骤4：判断码码字流中中是否还还有码字字要译（1）如如果“是是”，就就返回到到步骤2；（2）如如果“否否” 把代代表当前前前缀P的码字字输出到到码字流流； 结束束。73深圳大学学未来媒媒体技术术与

40、计算算研究所所LZW编编码算法法举例74深圳大学学未来媒媒体技术术与计算算研究所所LZW编编码算法法举例75深圳大学学未来媒媒体技术术与计算算研究所所倒排文档档压缩倒排文档档是信息息检索系系统中最最普遍使使用的索索引机制制，而索索引文件件的压缩缩能大大大提高检检索速度度和节约约磁盘空空间。通通过压缩缩倒排文文件列表表可以减减少倒排排文件的的尺寸。由于倒倒排文件件列表中中的文档档号是以以升序排排列的，这样文文档号之之间的差差距可以以看作是是文档号号之间的的间隙。倒排文档档通常由由两部分分组成：词汇表表和事件件表。词汇表就就是放我我们分词词词典的的地方，事件表表就是放放这个文文档中对对应于词词汇表中中词汇出出现的位位置。76深圳大学学未来媒媒体技术术与计算算研究所所倒排文档档的实现现原理D1：“百名名山村教教师进京京迎奥运运”D2：“沪教教师为促促学生加加强锻炼炼自制活活动器械械”D3：“大学学教师兼兼教练的的苦与乐乐”经过分词词，过滤滤高频词词后可以以构建如如下的倒倒排文档档：奥运-D1，1；教师-D1，1；D2，1；D3，1；大学-D3，1；教练-D3，1；77变长的压压缩方法法(1)一一元编码码（unary code）方法对于要压压缩的整整数N来来说