wdcp网站备份,中国最大的网站排名,制作网站流程,减粘装置设备设计要点索引的建立和更新 索引的建立 前一总结里说到#xff0c;如果索引结构建立好了#xff0c;可以提高搜索的速度#xff0c;那么给定一个文档集合#xff0c;索引是如何建立起来的呢#xff1f;建立索引的方式有很多种#xff0c;在这里我就书中提到的三种方法简单总结一下…索引的建立和更新 索引的建立 前一总结里说到如果索引结构建立好了可以提高搜索的速度那么给定一个文档集合索引是如何建立起来的呢建立索引的方式有很多种在这里我就书中提到的三种方法简单总结一下。 两遍文档遍历法 第一次文档遍历第一次扫描文档集合时并没有立即开始建立索引而是收集一些的统计信息比如文档集合包含的文档个数N、文档集合内包含的不同单词个数M以及每个单词在哪些文档中出现过的信息DF等等。将所有单词对应的DF值全部相加就可以知道建立最终的索引需要多少内存了然后在内存中将连续存储区划分成不同大小的片段词典内某个单词根据自己对应的DF信息可以通过指针指向属于自己的内存片段的起始位置和终止位置 这样在第二遍扫描中这个单词对应的倒排列表信息会被填充进这个片段中。 第二次文档遍历这一次扫描的时候就开始真正建立每个单词的倒排列表信息了即对每个单词来说获得包含这个单词的每个文档的文档ID以及这个单词在文档中出现的次数这样就可以不断填充第一次遍历扫描所分配的内存空间。当然如果要记录单词在文档中出现的位置也是可以的第一次扫描中分配内存时加上这个位置信息就可以了。 值得注意的是此方法完全是在内存里完成索引的创建过程的而后面两种方法则是通过内存和磁盘相互配合来完成索引建立任务的。而正因为创建索引是在内存中完成的所以就要求内存一定要足够大否则文档集合太大的话内存不能够满足需求。而对文档集合进行两遍扫描所以从速度上相比后面两种方法不占优势。 排序法 排序法在建立索引的过程中始终在内存中分配固定大小的空间用来存放词典信息和索引的中间结果当分配的空间被消耗光的时候把中间结果写入磁盘清空内存里中间结果所占的空间以用作下一轮存放索引中间结果的存储区。这种情况下可以把内存看做驿站它只是一个中间转折点。这种方法分为两个步骤中间结果内存排序和合并中间结果。 为什么要进行排序呢主要是为了方便后续的处理。因为在形成中间结果文件前已经按照单词ID和文档ID进行了排序所以进入内存缓冲区的数据都是已经排好序的合并过程中将不同缓冲区中包含同一个单词ID的信息进行合并如果某个单词ID的所有信息全部合并完成那么说明这个单词的倒排列表已经构建完成了将其写入最终索引中同时将各个缓冲区中对应这个单词ID信息清空。就这样一直往下进行直到所有的单词ID对应的倒排列表都已经创建完成。最后的结果就是最终的索引文件。 归并法 由于排序法有一个不足之处那就是在将中间结果写入磁盘的时候词典信息一直在内存中进行维护这样也会占据一部分的内存。归并法就是对排序法做出了改进即每次将内存中数据写入磁盘时包括词典在内的所有中间结果信息都被写入磁盘这样内存所有内容都可以被清空。 归并法整体流程也是分为两个大的阶段首先在内存里维护中间结果当内存占满时将内存数据写入磁盘临时文件第二阶段对临时文件进行归并形成最终索引。 归并法和排序法的区别 首先排序法在内存中存放的是词典信息和三元组数据单词ID文档ID单词频率在建立索引的过程中词典和三元组数据并没有直接的联系词典只是为了将单词映射为单词ID。而归并法则是在内存中建立一个完整的内存索引结构相当于对目前处理的文档子集建立起了一个倒排索引。 其次在将中间结果写入磁盘临时文件时归并法将整个内存的倒排索引写入临时文件对于某个单词的倒排列表在写入磁盘文件时将词典项放在列表最前端之后跟随相应的倒排列表这样依次将单词和对应的倒排列表写入磁盘文件随后彻底清空所占内存。而排序法只是将三元组数据排序后写入磁盘文件词典作为一个映射表一直存储在内存中。 在最后合并为最终索引的过程中排序法是根据同一单词ID的这样三元组依次进行合并归并法的临时文件则是每个单词对应的部分倒排列表所以在合并时针对每个单词的倒排列表进行合并形成这个单词的最终倒排列表就可以了与此同时最后的合并过程中也会形成最终的词典信息。如果大家对算法里的归并排序有所了解的话就很清楚这种方法了吧。 索引更新策略 常用的索引更新策略有4种完全重建策略、再合并策略、原地更新策略以及混合策略。 完全重建策略很直观的方法当新增文档达到一个数量时将新增文档和原先的老文档进行合并然后利用上文提到的建立索引的方式对所有文档重新建立索引。 再合并策略有新增文档进入搜索系统时搜索系统在内存维护临时倒排索引来记录信息当新增文档达到一定数量的时候则把临时索引文件和老文档的倒排索引文件进行合并以生成新的索引。 原地更新策略在索引合并时并不生成新的索引文件而是直接在原先的索引文件里进行追加操作将增量索引里单词的倒排列表项追加到老索引对应的倒排列表项的末尾这样的话就只更新增量索引里出现的单词相关信息其他单词信息不做变动。 混合策略结合不同索引更新策略的优势将不同的索引更新策略混合以形成更高效的方法。 混合策略一般会将单词根据其不同性质进行分类不同类别的单词对其索引采取不同的索引更新策略。常见的做法是根据单词的倒排列表长度进行划分因为有些单词经常在不同文档中出现所以其对应的倒排列表就较长而有些单词很少见其倒排列表就较短。那么长倒排列表单词采取原地更新策略因为这种策略能够节省磁盘读写次数而短倒排列表就采取再和并策略。通过这种根据实际情况来分别采取实际策略的方法效果体现的比较显著磁盘的读写操作和各种策略的优势都充分体现出来了。 转载于:https://www.cnblogs.com/BaiYiShaoNian/p/4548817.html
