第五讲文本索引和搜索

第五讲文本索引和搜索索引：是一种数据结构，它在关键词与包含该关键词的文档之间建立了一种映射关系，从而加快检索的速度。搜索：一般定义为在不使用索引技术时而快速在给定文本或文本集合中查找是否出现某一关键词，通常也称为单模式匹配。本讲就是针对以上三种索引结构和三种搜索算法来进行介绍和学习。常用的文本索引技术：倒排文件、后缀数组和签名文件。常用的文本搜索技术：BF算法、KMP算法和BM算法。倒排文件结构关于倒排文件在第四讲有所介绍，你还记得吗？湖畔夏夜花园蛙鸣诗社诗会d1：log3/2：1d2：log3/2：1,6d1：log3：4d2：log3：9,12d2：1/2log3/2：15d3：log3/2：2，10d3：1/2log3：5d3：1/2log3：13词汇表记录表倒排文件一般由词汇表和记录表两部分组成。在记录表中可存储词在文档中出现的位置、文档编号等需要存储的信息。d1：湖畔的夏夜常常很凉d2：湖畔有家“湖畔”花园，花园里蛙鸣一片d3：“蛙鸣”诗社举办“蛙鸣”诗会倒排文件另一种结构湖畔：2夏夜：1花园：1蛙鸣：2诗社：1诗会：1d1：log3/2：1d2：log3/2：1,6d1：log3：4d2：log3：9,12d2：1/2log3/2：15d3：log3/2：2,10d3：1/2log3：5d3：1/2log3：13词汇表记录表显然，若记录表采用顺序存储，则不利于文档集合的更新。湖畔有家“湖畔”花园，花园里蛙鸣一片文档数湖畔的夏夜常常很凉“蛙鸣”诗社举办“蛙鸣”诗会文档集合倒排文件的使用利用倒排文件进行检索，通常分为三个步骤：1、词汇表检索：即利用查询中的词检索词汇表。2、记录表检索：即检索出所有找到的词的记录表。3、记录表操作：即对检索出的记录表进行后处理，以实现相似度计算、摘要生成等所需要任务。显然，就倒排文件索引结构而言，词汇表检索的速度将决定该索引的效率。对于词汇表的组织一般可采用以下几种方式：1、排序数组：即将词排序顺序存储，采用二分法查找。2、散列：可按词的首字机内编码进行散列，但词的第二个字再散列就不再适合散列处理，一般采用线性表存放。3、B树：4、Trie树：B树和Trie树在《数据结构》中有所介绍。下面仅给出示例加以说明。B树与Trie树结构B树结构花园蛙鸣湖畔夏夜Trie树结构诗会诗社记录表湖畔记录表花园诗会社蛙鸣夏夜显然，Trie树结构不太适合于汉语词汇的组织。你还记得在第三讲切词中所采用的方法吗？推荐方法：所有词存放在一个数组中，词所在的数组下标即为词的编号；而倒排文件中的词汇表即按此词编号顺序存储，即词编号就是词汇表中词所在数组的下标。在对查询文本切词时将查询中的词转换为对应的词编号，利用此词编号即可在词汇表中直接进行定位。这个过程相当于对词的散列。推荐方法示例d1：log3/2：1d2：log3/2：1,6d1：log3：4d2：log3：9,12d2：1/2log3/2：15d3：log3/2：2，10d3：1/2log3：5d3：1/2log3：13词汇数组例如，查询为“花园”，在切词时即可获得该词编号为3，则通过A[3]可立即得到该词所对应的记录表信息。湖畔夏夜花园蛙鸣诗社诗会123456123456倒排文件A倒排文件的存储一般来说，检索系统的词汇表都是长期驻留内存的。而文档集合都是在磁盘上以文件的方式存储。若检索系统的文档集合不大，即倒排文件的记录表完全可以存储在内存中，则此时在对每一个文档进行描述的过程中即可在内存中建立该倒排文件结构。正如第四讲所述。若检索系统的文档集合非常庞大，以致于记录表无法存储在内存中。此时可考虑为每个词所对应的记录表建立一个文件。文件的命名可以利用词汇名或词汇组号。如图所示。显然，此时I/O次数就成为检索系统效率的瓶颈。湖畔：2夏夜：1花园：1蛙鸣：2诗社：1诗会：1d1：log3/2：1d2：log3/2：1,6d1：log3：4d2：log3：9,12d2：1/2log3/2：15d3：log3/2：2,10d3：1/2log3：5d3：1/2log3：13词汇表文件1文件2文件3文件4文件5文件6磁盘倒排文件的使用所谓磁盘倒排文件：是指倒排文件的记录表以文件的方式存储在磁盘上。显然，针对用户所提交的每一个查询词都必须通过读取磁盘文件来获得该词的记录信息。问题：如何才能最大限度地减少I/O次数呢？方法是建立一个内存缓冲区。该缓冲区内维护一个小型的倒排文件子集。此时需要在检索系统中开发一个缓冲区管理程序，来负责缓冲区的维护。磁盘湖畔：2夏夜：1花园：1蛙鸣：2诗社：1诗会：1d1：log3/2：1d2：log3/2：1,6d3：1/2log3：5d3：1/2log3：13词汇表缓冲区调度原则：1、当用户检索词记录表在缓冲区中，则不必I/O操作记录表内存缓冲区2、若用户检索词记录表不在缓冲区，则从磁盘读出对应记录。若缓冲区有空，则放入缓冲区；若缓冲区已满，则覆盖掉使用频率最低的词条对应的记录表磁盘倒排文件的维护这里所谓的维护是指在倒排文件中插入、删除或更新文档或文档集合。一般情况下，文档的更新采用删除再插入的方式来完成。若检索系统的文档集变化较为频繁，则采用每次一文档的维护策略显然会降低检索系统的维护效率，尤其在磁盘倒排文件结构下。因此，常采用批处理的维护方式，即每次对一批文档进行插入或删除。批插入策略如下：1、将一批待插入的文档子集在内存中构造成一个小型的倒排文件结构；批删除策略如下：1、在内存中构造一个待删除文档的列表；2、将内存中的小型倒排文件结构一次性地写入磁盘。显然，若文档插入不及时会影响检索结果；插入过于频繁会影响系统的检索效率。这一矛盾需要根据实现情况进行平衡。2、若用户检索结果中文档出现在述待删除列表中，则不给予检索输出；3、定期或按某种阈值设置一次性在磁盘中删除列表中的文档。显然，若待删除文档列表过长会影响检索效率；删除过于是频繁也会影响检索系统的效率。这也需要根据实现情况进行平衡。词汇表的压缩这里所谓的压缩是指如何能够减少所占用的存储空间。1、若采用一个数组存储词汇表，则数组元素只能设为词的最大长度。2字长词汇表A1n23字长词汇表B1n34字长词汇表C1n4ifn≤n2则A[n]为记录表入口ifn2n≤n3则A[n-n2]为记录表入口ifn3n≤n4则A[n-n2-n3]为记录表入口……2、可考虑将等长的词分别存储在不同的词汇数组中。即长度为2的词汇构成一个数组、长度为3的词汇构成一个数组、……。3、上述存储方式可以最大程度地压缩词汇表空间。缺点是词汇编号不再是该词汇的数组下标，需要设计一种映射原则来实现词汇编号与其所在数组下标的映射关系。设计的不好将影响检索效率。4、如考虑如下策略：将词按字长大小顺序编号，且在切词词典中存储该编号值。当在查询中切得某词编号为n，则按如下规则判断。记录表的压缩1、在记录表中存有文档编号、词汇在文档中的位置等所需数据。可考虑如下策略来压缩词汇位置值数据：①对每一个文档分块，块数最多不超过256块；该策略的优点是减少了记录表的空间，从而减少了I/O的次数。以上所讨论的无论是磁盘倒排文件的批处理维护，还是压缩等问题，目的都是为了解决I/O访问次数。因为目前的硬件环境I/O速度是系统速度的瓶颈。2、以词汇在文档中的位置为例，若采用一个字节来存储该数值，其最大位置值只能是256，即文档长度不能超过256个汉字，这对于是文本文档是不够的。3、若采用两个字节存储，则文档最大长度可达65536个汉字，对于一般的网页性质的文档是够用的。但这也增加了记录表所占用的空间。尤其是文档集数量非常庞大时，所增加的空间较为可观。②记录表中存储的词位置值改为块号，即采用一个字节存储块号。③当需要在文档中定位词的具体位置时，可根据块号在所在块内搜索来定位。缺点是增加了检索时词汇在文档中定位时的运算负担。文本的后缀文本的后缀：是指从文本中任一位置开始直到文本末尾的子串。例如：湖畔有家湖畔花园，花园里蛙鸣一片。该文本的后缀有：湖畔有家湖畔花园，花园里蛙鸣一片。有家湖畔花园，花园里蛙鸣一片。湖畔花园，花园里蛙鸣一片。花园，花园里蛙鸣一片。……1、一个文本的后缀有很多；如将后缀最大长度限定为6个汉字，则上例文本的后缀为：湖畔有家湖畔有家湖畔花园湖畔花园花园花园花园里蛙花园里蛙鸣一蛙鸣一片2、后缀的起始位置一般以某个词开始，如后缀“畔有家……”意义不大；3、若文本较长，则很多后缀子串也较长。可限定后缀的最大长度；4、在后缀中一般不保留标点等符号，也可考虑去掉停用词。后缀数组d2：湖畔有家湖畔花园，花园里蛙鸣一片。13571013湖畔有家湖畔：d2：1有家湖畔花园：d2：3湖畔花园花园：d2：5花园花园里蛙：d2：7花园里蛙鸣一：d2：10蛙鸣一片：d2：13查询：湖畔花园检索策略：1、利用查询串在后缀数组中进行匹配；后缀数组可见，1、该检索方案能实现查询的精确匹配；2、检索过程能体现出检索词在查询中出现的顺序、距离的作用；3、缺点是当文档数量多时，占用大量的存储空间，检索速度慢。2、按匹配的相似度排序，即为检索结果。3、若查询串长度超过后缀长度，要么将查询串截断，要么利用后缀数组中的位置值在文档中继续完成匹配。后缀树d2：湖畔有家湖畔花园，花园里蛙鸣一片。13571013湖畔有家湖畔：d2：1有家湖畔花园：d2：3湖畔花园花园：d2：5花园花园里蛙：d2：7花园里蛙鸣一：d2：10蛙鸣一片：d2：13后缀数组后缀树：即将后缀数组组织成Trie树结构。目的是提高检索的速度。湖畔有花园蛙鸣有花园家花园里一家湖畔花园湖畔花园里蛙蛙一片d2:1d2:5d2:3d2:7d2:10d2:13显然树结构需要大量的磁盘空间，可能需要在磁盘间跳转。还需解决模糊匹配问题。查询：湖畔花园签名文件签名文件：是一种基于散列技术的面向词汇的索引结构。词汇的签名：即将每一个词用一个唯一的二进制数编码表示。例如：技术001000110010教材000010101001检索000000011110信息101000100001文本分块：分块原则可按固定长度分块，或按固定块数分块。例如：这是一本关于|信息检索的教材。|介绍了检索|的基本技术，|……000000000000101010111111000000011110001000110010签名文件101000100001信息000000011110检索000010101001教材101010111111或计算每个文本块的签名：即该块内的所有词按位进行“或”运算而得到。签名文件的使用这是一本关于|信息检索的教材。|介绍了检索|的基本技术，|……000000000000101010111111000000011110001000110010例如：在文本中搜索“检索”技术001000110010教材000010101001检索000000011110信息101000100001查询方法：1、利用待搜索词的签名与每个文本块的签名进行按位“与”运算；例如，由于“检索”一词的签名为000000011110，则计算如下：000000011110000000000000000000000000与000000011110101010111111000000011110与000000011110000000011110000000011110与可见上述文本的第二、三个块内可能包含“检索”词汇。再由块内搜索来确定。2、若“与”运算结果与待搜索词的签名相同，则该块内可能存在该搜索词。若“与”运算结果与待搜索词的签名不同，则该块内不存在该搜索词。词汇签名编码的重要性这是一本关于|信息检索的教材。|介绍了检索|的基本技术，|……000111011001技术001教材010检索011信息100例如，查询“技术”一词，则由于“技术”一词的签名为001，则计算如下：001000000与根据计算结果，文本的第二、三、四块内均可能包含“技术”一词，经块内搜索才可确定第二、三块内并不包含“技术”一词，即出现误检。显然误检的结果会浪费搜索时间。00