搜索引擎基本原理及实现技术——索引

《搜索引擎基本原理及实现技术——索引》由会员分享，可在线阅读，更多相关《搜索引擎基本原理及实现技术——索引（38页珍藏版）》请在金锄头文库上搜索。

1、搜索引擎基本原理及实现技术索引技术网络爬虫辛辛苦苦的把网页爬回来之后预处理系统主要工作信息抽取分词分类等处理工作生成正排发送 到索引系统生成倒排索引。信息抽取去标签和去噪去标签 构造 DOM 树。tinyHTML，htmlParser， Jsoup；去噪 去掉与正文不相关的广告或者其他信息。 如广告，评论，导航条，版权信息，友情 链接等等。分词分词的目的是为了提取文件特征，文件特 征即网页内容的结构化表现形式。分词方法 基于字符串匹配的分词方法 基于理解的分词方法 基于统计的分词方法分词思想设计的原则1、颗粒度越大越好：用于进行语义分析的文本分词，要求 分词结果的颗粒度越大，即单词的字数越多，

2、所能表示的 含义越确切，如： “公安局长”可以分为“公安 局长”、“公 安局 长”、“公安局长”都算对，但是要用于语义分析，则“ 公安局长”的分词结果最好（当然前提是所使用的词典中 有这个词） 2、切分结果中非词典词越少越好，单字字典词数越少越好 ，这里的“非词典词”就是不包含在词典中的单字，而“单字 字典词”指的是可以独立运用的单字，如“的”、“了”、“和” 、“你”、“我”、“他”。例如：“技术和服务”，可以分为“技 术 和服 务”以及“技术 和 服务”，但“务”字无法独立成词（ 即词典中没有），但“和”字可以单独成词（词典中要包含 ），因此“技术 和服 务”有1个非词典词，而“技术 和

3、服务” 有0个非词典词，因此选用后者。3、总体词数越少越好，在相同字数的情况下 ，总词数越少，说明语义单元越少，那么 相对的单个语义单元的权重会越大，因此 准确性会越高。基于字符串匹配的分词方法也叫做基于字典的分词方法，它是以字典为 依据的。按照一定的策略将待分析的汉字 串与一个“充分大的”机器词典中的词条进行 匹配。若在词典中找到某个字符串，则匹 配成功，即识别出一个词。 又分为三种： 正向最大匹配法（由左到右的方向）； 逆向最大匹配法（由右到左的方向）； 双向最大匹配法。最大匹配法最大匹配是指以词典为依据，取词典中最 长单词为第一个次取字数量的扫描串，在 词典中进行扫描。例如：词典中最长词

4、为“ 中华人民共和国”共7个汉字，则最大匹配起 始字数为7个汉字。然后逐字递减，在对应 的词典中进行查找。 下面以“我们在野生动物园玩”详细说明一下这 几种匹配方法：正向最大匹配法 1、正向最大匹配法： 正向即从前往后取词，从7-1，每次减一个字，直到词典命中或剩下1个单字。 第1次：“我们在野生动物”，扫描7字词典，无 第2次：“我们在野生动”，扫描6字词典，无 。 第6次：“我们”，扫描2字词典，有 扫描中止，输出第1个词为“我们”，去除第1个词后开始第2轮扫描，即： 第2轮扫描： 第1次：“在野生动物园玩”，扫描7字词典，无 第2次：“在野生动物园”，扫描6字词典，无 。 第6次：“在野

5、”，扫描2字词典，有 扫描中止，输出第2个词为“在野”，去除第2个词后开始第3轮扫描，即： 第3轮扫描： 第1次：“生动物园玩”，扫描5字词典，无 第2次：“生动物园”，扫描4字词典，无第3次：“生动物”，扫描3字词典，无 第4次：“生动”，扫描2字词典，有 扫描中止，输出第3个词为“生动”，第4轮扫描，即： 第4轮扫描： 第1次：“物园玩”，扫描3字词典，无 第2次：“物园”，扫描2字词典，无 第3次：“物”，扫描1字词典，无 扫描中止，输出第4个词为“物”，非字典词数加1，开始第5轮扫描，即： 第5轮扫描： 第1次：“园玩”，扫描2字词典，无 第2次：“园”，扫描1字词典，有 扫描中止，输

6、出第5个词为“园”，单字字典词数加1，开始第6轮扫描，即： 第6轮扫描： 第1次：“玩”，扫描1字字典词，有 扫描中止，输出第6个词为“玩”，单字字典词数加1，整体扫描结束。正向最大匹配法，最终切分结果为：“我们/在野/生动/物/园/玩”，其中 单字字典词为2，非词典词为1。逆向最大匹配法：逆向即从后往前取词，其他逻辑和正向相同。即： 第1轮扫描：“在野生动物园玩” 第1次：“在野生动物园玩”，扫描7字词典，无 第2次：“野生动物园玩”，扫描6字词典，无 。 第7次：“玩”，扫描1字词典，有 扫描中止，输出“玩”，单字字典词加1，开始第2轮扫描 第2轮扫描：“们在野生动物园” 第1次：“们在野

7、生动物园”，扫描7字词典，无 第2次：“在野生动物园”，扫描6字词典，无 第3次：“野生动物园”，扫描5字词典，有 扫描中止，输出“野生动物园”，开始第3轮扫描 第3轮扫描：“我们在” 第1次：“我们在”，扫描3字词典，无 第2次：“们在”，扫描2字词典，无第3次：“在”，扫描1字词典，有 扫描中止，输出“在”，单字字典词加1，开始第4轮扫描 第4轮扫描：“我们” 第1次：“我们”，扫描2字词典，有 扫描中止，输出“我们”，整体扫描结束。 逆向最大匹配法，最终切分结果为：“我们/在/野生动物园/ 玩”，其中，单字字典词为2，非词典词为0。双向最大匹配法正向最大匹配法和逆向最大匹配法，都有局限性

8、。 因此有人又提出了双向最大匹配法，双向最大匹配法。即，两种 算法都切一遍，然后根据大颗粒度词越多越好，非词典词和单 字词越少越好的原则，选取其中一种分词结果输出。 正向最大匹配法，最终切分结果为：“我们/在野/生动/物/园/玩” ，其中，两字词3个，单字字典词为2，非词典词为1。 逆向最大匹配法，最终切分结果为：“我们/在/野生动物园/玩”， 其中，五字词1个，两字词1个，单字字典词为2，非词典词为0 。 非字典词：正向(1)逆向(0)（越少越好） 单字字典词：正向(2)=逆向(2)（越少越好） 总词数：正向(6)逆向(4)（越少越好） 因此最终输出为逆向结果。基于理解的分词方法该方法又称基

9、于人工智能的分词方法。 它是利用汉语的语法知识和语义知识以及心 理学知识进行分词，需要建立分词数据库 、知识库和推理机。这种分词方法需要使 用大量的语言知识和信息。 目前还处在试验阶段。基于统计的分词方法又称为无字典分词，它的主要思想是：词 是稳定的组合，因此在上下文中，相邻的 字同时出现的次数越多，就越有可能构成 一个词。因此字与字相邻出现的概率或频 率能较好地反映成词的可信度。可以对训 练文本中相邻出现的各个字的组合的频度 进行统计，计算它们之间的互现信息。分词工具IkAnalyzer2012，国外有名的分析系统， 也可以处理中文。使用简单。NLPIR2014, NLPIR2015 ICT

10、CLAS5.0 中科院开发的专门针对中文的分词系统， 中文分词较准确，稍微麻烦点教育学院/n_new/3.34/2#学院 /n/2.58/19#教育/vn/1.74/3#信息 /n/1.74/3#工程/n/1.34/5#教学 /vn/1.27/3#网页特征提取所有分出来的词都要保留 吗？我该如何取舍呢？只保留一定数量的能代表 网页内容特征的关键词。最简单的就是统计词频， 将出现频率最高的n个词保 留。索引索引是对数据库表中一列或多列的值进行 排序的一种结构。 此处指的是将爬取的网页进行预处理之后 的，将关于这个URL的信息存入数据库，被 称为索引库。索引库中关于URL的信息不仅是组成页面内 容

11、的关键词及其特征(位置、格式等)，还有 链接、更新情况等信息。建立倒排索引的基本过程（1）页面分析将原始页面的不同部分进行识 别并标记，例如：title、keywords、content、 link、anchor、评论、其他非重要区域等等；（2）对网页内容分词。分词的过程实际上包 括了切词分词同义词转换同义词替换等等。以 对某页面title分词为例，得到的将是这样的数 据：term文本、termid、词类、词性等等；（3）之前的准备工作完成后，接下来即是建 立倒排索引，形成termdoc，倒排索引(Inverted Index)可以根据单词快速获 取包含这个单词的文 档列表。是实现“单词-文档

12、矩阵” 的一种具体存储形式。倒排索引的建立实际上在建立倒排索引的最后还需要有一个入 库写库的过程，而为了提高效率这个过程还需 要将全部term保存在文件头部，并且对数据进 行压缩，这些涉及到的技术自行学习。建立索引两遍文档遍历法（2-Pass In-Memory Inversion）在第一遍扫描文档集合时，该方法并没有立即开始建立 索引，而是收集一些全局的统计信息。比如文档集合包 含的文档个数N，文档集合内所包含的不同单词个数M ，每个单词在多少个文档中出现过的信息DF。每一项记 载某个文档的文档ID和单词在该文档对应的出现次数TF 。第一遍扫描的主要目的是获得一些统计信息，并根据统 计信息分

13、配内存等资源，同时建立好了单词相对应倒排 列表在内存中的位置信息，即主要做些资源准备工作。在第二遍扫描的时候，开始真正建立每个单词的倒排列 表信息，即对于某个单词来说，获得包含这个单词的每 个文档的文档ID，以及这个单词在文档中的出现次数TF ，这样就可以不断填充第一遍扫描所分配的内存空间。排序法（Sort-basedInversion ）在建立索引的过程中，始终在内存中分配 固定大小的内存，用来存放词典信息和索 引的中间结果，当分配的内存被消耗光的 时候，把中间结果写入磁盘，清空内存里 中间结果所占内存，以用作下一轮存放索 引中间结果的存储区。 中间结果如何存储，中间结果如何排序自 行学习。

14、归并法（Merge- basedInversion）。“归并法”对此做出了改进，即每次将内存中 数据写入磁盘时，包括词典在内的所有中间结 果信息都被写入磁盘，这样内存所有内容都可 以被清空，后续建立索引可以使用全部的定额 内存。 图3-14是“归并法”的示意图。其整体流程和 排序法大致相同，也是分为两个大的阶段，首 先在内存里维护中间结果，当内存占满后，将 内存数据写入磁盘临时文件，第二阶段对临时 文件进行归并形成最终索引。正排索引也称为“前向索引“。它是创建倒排索引的基础 ，具有以下字段。 （1）LocalId字段（表中简称“Lid“）：表示 一个文档的局部编号。 （2）WordId字段：表

15、示文档分词后的编号 ，也可称为“索引词编号“。 （3）NHits字段：表示某个索引词在文档中 出现的次数。 （4）HitList变长字段：表示某个索引词在文 档中出现的位置，即相对于正文的偏移量 。多字段索引（自学）针对每个不同的字段，分别建立一个索引 ，当用户指定某个字段作为搜索范围时， 可以从相应的索引里提取结果。倒排列表方式扩展列表方式索引更新完全重建策略（CompleteRe-Build）当新增文档达到一定数量，将新增文档和 原先的老文档进行合并，然后利用前述章 节提到的建立索引的方式，对所有文档重 新建立索引。新索引建立完成后，老的索 引被遗弃释放，之后对用户查询的响应完 全由新的索

16、引负责。 再合并策略（Re-Merge）有新增文档进入搜索系统时，搜索系统在 内存维护临时倒排索引来记录其信息，当 新增文档达到一定数量，或者指定大小的 内存被消耗完，则把临时索引和老文档的 倒排索引进行合并，以生成新的索引。原地更新策略（In-Place） 原地更新策略试图改进“再合并策略”的缺 点。就是说，在索引更新过程中，如果老 索引的倒排列表没有变化，可以不需要读 取这些信息，而只对那些倒排列表变化的 单词进行处理。即使老索引的倒排列表发 生变化，只在其末尾进行追加操作，而不 需要读取原先的倒排列表并重写到磁盘另 外一个位置? 在索引合并时，不生成新的索引文件，而 是直接在原先老的索引文件里进行追加操 作，将增量索引里单词的倒排列表项追加 到老索引相应位置的末尾混合策略（Hybrid）将单词根据其不同性质进行分类，不同类 别的单词，对其索引采取不同的索引更新 策略。根据单词的倒排列表长度进行区分，将单 词划分为“长倒排列表单词”-原地更新策略“