信息索引技术

主讲教师：王旭博士深圳大学计算机与软件学院未来媒体技术与计算研究所Email:[e-mail]1模块一：商用搜索引擎架构与原理搜索引擎基础网页抓取技术网页信息预处理技术信息索引技术信息查询与评价技术参考书籍：袁津生，李群编著，《搜索引擎基础教程》，清华大学出版社其他文献/互联网资料深圳大学未来媒体技术与计算研究所2深圳大学未来媒体技术与计算研究所信息索引技术经过网页预处理后，可以建立索引数据库。对于数目庞大的文档数据库使用简单匹配方法是不可行的，需要对文档的表示建立索引。为了提高检索效率，应该按照一定的规则建立索引。索引文件一般是按照倒排文件的格式存放的，索引的建立包括：（1）分析：处理文件中可能的错误。（2）索引：完成分析的文件被编码存入索引数据库。（3）排序：将索引数据库按照一定的规则排序，产生全文索引。3深圳大学未来媒体技术与计算研究所信息索引技术5.1顺排检索5.2倒排索引5.3文本压缩技术4深圳大学未来媒体技术与计算研究所5.1顺排检索顺排文档检索的主要思想是将文档中的每一条记录依次去匹配用户的检索提问集合，文档处理完毕后，将各提问的命中结果归并分发给有关用户。顺排文档检索是用文档中记录一条一条去匹配提问的，是顺序对文档记录检索的方法，所以称为顺排文档检索。顺排文档的关键技术是采用列表处理方法将提问逻辑式（检索式）变换成等价的提问展开式，按提问展开表的内容对顺排文档的每篇文献进行检索。常用的顺排文档检索方法主要有：表展开法、逻辑树法等5深圳大学未来媒体技术与计算研究所5.2倒排索引IndexesaredatastructuresdesignedtomakesearchfasterWebSearch的需求:快速响应时间(fasterresponsetime)支持更新(supportsupdates)基于Ranking的文本搜索方法文件内容QueryRanking算法Ranking抽象模型27Ranking抽象模型深圳大学未来媒体技术与计算研究所28Ranking抽象模型(例子）时效性重要性深圳大学未来媒体技术与计算研究所29深圳大学未来媒体技术与计算研究所倒排索引倒排文档是一种面向单词的索引机制，相对顺排文档而言，是将顺排文档中可检索字段的作者名、关键词、分类号等取出，按一定规则排序，归并相同词汇，并把在顺排文档中相关记录的记录号集合赋予其后，以保证通过某一特征词能够快速、方便地获取相关记录。30倒排索引示例“Collection”深圳大学未来媒体技术与计算研究所31最简单形式的倒排索引深圳大学未来媒体技术与计算研究所32包含计数信息的倒排索引深圳大学未来媒体技术与计算研究所33包含位置信息的倒排索引深圳大学未来媒体技术与计算研究所34ProximityMatches短语匹配e.g.,tropicalfish,or“findtropicalwithin5wordsoffish”包含位置信息的倒排索引深圳大学未来媒体技术与计算研究所35域(Field)和ExtentList搜索中的文档结构信息限制性信息：时间，来源等重要信息：标题解决方案:根据域的类型建立倒排索引倒排索引添加域信息使用extentlists深圳大学未来媒体技术与计算研究所36ExtentListsExtent:文件中的邻近区域单词位置信息每个域属性都有相应的Extentlistextentlist深圳大学未来媒体技术与计算研究所37其他预先计算出倒排索引中的分数“fish”[(1:3.6),(3:2.2)]提升速度，降低动态调整的性能基于分数顺序的索引只关注与分数最高的文档对单词索引队列效果最佳深圳大学未来媒体技术与计算研究所38深圳大学未来媒体技术与计算研究所倒排索引倒排文档的检索算法一般分成如下三步进行：（1）词汇查找将查询串中的单词和模式分割成独立的部分，短语和近似查询串被分割成单个词汇。（2）查找词汇出现的情况获取与查询串中所有词汇相关的出现情况列表。（3）词汇出现情况的操作主要是通过对上一步中获取的词汇出现情况的操作实现短语查询、近似查询和布尔查询。39深圳大学未来媒体技术与计算研究所倒排文档倒排文档的组成元素主要包括：关键字（作者、主题词、分类号等）、目长（含有该关键字记录的条数）、记录号集合（所有与该关键字有关的记录号）。倒排文档的建立是建筑在顺排文档（主文档）的基础之上，它是从主文档中提取可检索字段内容，也有采取自动从标题、文摘或全文中提取关键词，利用所得到的这些属性词来建立倒排文档。40深圳大学未来媒体技术与计算研究所倒排文档的建立由顺排文档构造倒排文档需要经过抽词、排序、归并和组织等过程，具体实现步骤如下：选择需要做索引的字段属性（如作者、关键词等），抽出其中的内容，并在其后附上其记录号。对抽出的内容进行排序，使之便于归并相同内容。对相同内容进行归并，把合并后的内容放入倒排文档的主键字段（如标引词、作者等），统计每一数据的频次作为目长，把每一内容后的记录号顺序放在记录号集合字段。41构建方法(简单法)索引的构建相当于从正排表到倒排表的建立过程。当我们分析完网页时,得到的是以网页为主码的索引表。当索引建立完成后,应得到倒排表,具体流程如图所示：流程描述如下：1）将文档分析称单词term标记，2）使用hash去重单词term3）对单词生成倒排列表倒排列表就是文档编号DocID，没有包含其他的信息（如词频，单词位置等），这就是简单的索引。这个简单索引功能可以用于小数据，例如索引几千个文档。然而它有两点限制：1）需要有足够的内存来存储倒排表，对于搜索引擎来说，都是G级别数据，特别是当规模不断扩大时,我们根本不可能提供这么多的内存。2）算法是顺序执行，不便于并行处理。深圳大学未来媒体技术与计算研究所42构建方法(合并法)深圳大学未来媒体技术与计算研究所1）页面分析，生成临时倒排数据索引A，B，当临时倒排数据索引A，B占满内存后，将内存索引A，B写入临时文件生成临时倒排文件，2)对生成的多个临时倒排文件,执行多路归并,输出得到最终的倒排文件。43更新策略完全重建策略：当新增文档到达一定数量，将新增文档和原先的老文档整合，然后利用静态索引创建方法对所有文档重建索引，新索引建立完成后老索引会被遗弃。此法代价高，但是主流商业搜索引擎一般是采用此方式来维护索引的更新再合并策略：当新增文档进入系统，解析文档，之后更新内存中维护的临时索引，文档中出现的每个单词，在其倒排表列表末尾追加倒排表列表项；一旦临时索引将指定内存消耗光，即进行一次索引合并，这里需要倒排文件里的倒排列表存放顺序已经按照索引单词字典顺序由低到高排序，这样直接顺序扫描合并即可。其缺点是：因为要生成新的倒排索引文件，所以对老索引中的很多单词，尽管其在倒排列表并未发生任何变化，也需要将其从老索引中取出来并写入新索引中，这样对磁盘消耗是没必要的。原地更新策略：试图改进再合并策略，在原地合并倒排表，这需要提前分配一定的空间给未来插入，如果提前分配的空间不够了需要迁移。混合策略：能够结合不同索引更新策略的长处，将不同索引更新策略混合，以形成更高效的方法。深圳大学未来媒体技术与计算研究所44深圳大学未来媒体技术与计算研究所5.3文本压缩技术45深圳大学未来媒体技术与计算研究所文本压缩文本压缩是指用较少的位或字节来表示文本，这样将可以显著地减小计算机中存储文本的空间大小。常规的压缩方法是基于字符的压缩，但是，为了能够在信息检索系统中进行快速的单词匹配，压缩的基本单位是单词而不是字符。在选择压缩方法时，除了要考虑空间的节省程度外，还要考虑压缩文档的编码和解码速度。例子：CPU处理速度：m,内存读取速度：p，处理速度：min(m,p)压缩率：r1，解码因子：d1，处理速度：min(mr,pd)无损压缩(Losslesscompression)46压缩基本原理基本概念：频率高的用短码字，频率低的用长码字数字序列:编码方式:00-0:only10bits,buthardtodecode压缩基本原理Ambiguousencoding:无法解码anotherdecoding:whichrepresents:useunambiguouscode:编码方案:Delta编码WordcountdataisgoodcandidateforcompressionmanysmallnumbersandfewlargernumbersencodesmallnumberswithsmallcodesDocumentnumbersarelesspredictablebutdifferencesbetweennumbersinanorderedlistaresmallerandmorepredictableDeltaencoding:encodingdifferencesbetweendocumentnumbers(d-gaps)Delta编码•Invertedlist(withoutcounts)•Differencesbetweenadjacentnumbers•Differencesforahigh-frequencywordareeasiertocompress,e.g.,•Differencesforalow-frequencywordarelarge,e.g.,深圳大学未来媒体技术与计算研究所统计方法统计方法依赖于对每个符号在文本中出现的概率进行估计，估计得越准确，压缩的效果就越好。文本中所有可能的符号的集合称为字母表。对每个符号进行概率估计的任务称为建模。模型的本质是建立信息库中文档的概率分布。一旦有了这些概率，符号就转成二进制数，这个过程称为编码。编码和解码都使用了同一个模型，解码是编码的逆过程。常见的统计编码方案有两种：霍夫曼编码和算术编码。51深圳大学未来媒体技术与计算研究所霍夫曼（Huffman）编码霍夫曼编码的思想是为每一个不同的符号分配一个固定长度的位编码。对给定的数据流，计算每个字符的出现频率。根据频率表，运用霍夫曼算法可确定分配各字符的最小位数，然后给出一个最优的编码。给出现频率较高的字符赋以较短编码，而给出现频率较低的字符赋以较长的编码。每个数据的编码各不相同。这些代码都是二进制码，且码的长度是可变的。分配的码字存入编码表中，从而实现压缩。解压的唯一性能够得以保证是因为不会有代码是另一个代码的前缀。52深圳大学未来媒体技术与计算研究所霍夫曼编码的例子我们假定字符集是{A，B，C，D，E，F，G，H}，在给每个字符分配比特模式之前，我们给每个字符赋予一个出现频率的权值。假定对应的权值分别是4、5、6、7、10、10、18和40。然后我们建立字符树，过程按照下面的步骤进行。①统计频率。将原始符号按照出现概率递减(或递增)的顺序排列；②将两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率；53深圳大学未来媒体技术与计算研究所霍夫曼编码的例子③重复进行步骤①和②直到概率相加的结果等于1为止；④分配码字。将形成的二叉树左结点标0，右结点标1（或左结点标1，右结点标0），从根结点回溯到原始符号，记录根结点到当前符号之间的0，1序列，从而得到每个符号的编码。因为每个编码都是通过树上从根开始的不同路径得到的，所以没有一个编码是其他编码的前缀。54深圳大学未来媒体技术与计算研究所霍夫曼编码的例子55深圳大学未来媒体技术与计算研究所霍夫曼编码的例子56深圳大学未来媒体技术与计算研究所霍夫曼编码的例子57深圳大学未来媒体技术与计算研究所霍夫曼编码的例子编码分配字符权编码字符权编码A400011E100000B50000F10011C60101G18001D70100H40158深圳大学未来媒体技术与计算研究所算术编码算术编码的基本原理是将编码的消息表示成实数0和1之间