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

1、1搜索引擎基本原理及实现技术2网络爬虫辛辛苦苦的把网页爬回来之后3预处理系统主要工作信息抽取分词分类等处理工作生成正排发送 到索引系统生成倒排索引。4信息抽取去标签和去噪去标签构造 DOM 树。，Jsoup；tinyHTML，htmlParser去噪去掉与正文不相关的广告或者其他信息。如广告，评论，导航条，版权信息，友情链接等等。5分词分词的目的是为了提取文件特征，文件特征即网页内容的结构化表现形式。分词方法基于字符串匹配的分词方法基于理解的分词方法基于统计的分词方法6基于字符串匹配的分词方法也叫做基于字典的分词方法，它是以字典为依据的。按照一定的策略将待分析的汉字串与一个“充分大的”机器词典

2、中的词条进行匹配。若在词典中找到某个字符串，则匹配成功，即识别出一个词。又分为三种：正向最大匹配法（由左到右的方向）；逆向最大匹配法（由右到左的方向）；最少切分法（使每一句中切出的词数最小）。7基于理解的分词方法该方法又称基于人工智能的分词方法。它是利用汉语的语法知识和语义知识以及心理学知识进行分词，需要建立分词数据库、知识库和推理机。这种分词方法需要使用大量的语言知识和信息。目前还处在试验阶段。8基于统计的分词方法又称为无字典分词，它的主要思想是：词是稳定的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻出现的概率或频率能较好地反映成词的可信度。可以对训

3、练文本中相邻出现的各个字的组合的频度进行统计，计算它们之间的互现信息。9分词工具IkAnalyzer2012，国外有名的分析系统，也可以处理中文。使用简单。NLPIR2014, NLPIR2015ICTCLAS5.0中科院开发的专门针对中文的分词系统，中文分词较准确，稍微麻烦点10教育学院/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#11网页特征提取所有分出来的词都要保留吗？我该如何取舍呢？只保留一定数量的能代表网页内容特征的关键词。最简单的就是统计词频，将出现频率最高的n个词保留。12

4、索引索引是对数据库表中一列或多列的值进行排序的一种结构。此处指的是将爬取的网页进行预处理之后的，将关于这个URL的信息存入数据库，被称为索引库。 索引库中关于URL的信息不仅是组成页面内容的关键词及其特征(位置、格式等)，还有链接、更新情况等信息。13建立倒排索引的基本过程（1）页面分析将原始页面的不同部分进行识别并标记，例如：title、keywords、content、link、anchor、评论、其他非重要区域等等；（2）对网页内容分词。分词的过程实际上包括了切词分词同义词转换同义词替换等等。以对某页面title分词为例，得到的将是这样的数据：term文本、termid、词类、词性等等；

5、（3）之前的准备工作完成后，接下来即是建立倒排索引，形成termdoc，14倒排索引(Inverted Index)可以根据单词快速获取包含这个单词的文档列表。是实现“单词单词-文档矩阵文档矩阵”的一种具体存储形式存储形式。15倒排索引的建立16实际上在建立倒排索引的最后还需要有一个入库写库的过程，而为了提高效率这个过程还需要将全部term保存在文件头部，并且对数据进行压缩，这些涉及到的技术自行学习。17建立索引建立索引两遍文档遍历法（两遍文档遍历法（2-Pass In-Memory Inversion）在第一遍扫描文档集合时，该方法并没有立即开始建立索引，而是收集一些全局的统计信息。比如文档

6、集合包含的文档个数N，文档集合内所包含的不同单词个数M，每个单词在多少个文档中出现过的信息DF。每一项记载某个文档的文档ID和单词在该文档对应的出现次数TF。第一遍扫描的主要目的是获得一些统计信息，并根据统计信息分配内存等资源，同时建立好了单词相对应倒排列表在内存中的位置信息，即主要做些资源准备工作。在第二遍扫描的时候，开始真正建立每个单词的倒排列表信息，即对于某个单词来说，获得包含这个单词的每个文档的文档ID，以及这个单词在文档中的出现次数TF，这样就可以不断填充第一遍扫描所分配的内存空间。18排序法（排序法（Sort-basedInversion）在建立索引的过程中，始终在内存中分配固定大

7、小的内存，用来存放词典信息和索引的中间结果，当分配的内存被消耗光的时候，把中间结果写入磁盘，清空内存里中间结果所占内存，以用作下一轮存放索引中间结果的存储区。中间结果如何存储，中间结果如何排序自行学习。19归并法（归并法（Merge-basedInversion）。“归并法”对此做出了改进，即每次将内存中数据写入磁盘时，包括词典在内的所有中间结果信息都被写入磁盘，这样内存所有内容都可以被清空，后续建立索引可以使用全部的定额内存。 图3-14是“归并法”的示意图。其整体流程和排序法大致相同，也是分为两个大的阶段，首先在内存里维护中间结果，当内存占满后，将内存数据写入磁盘临时文件，第二阶段对临时文

8、件进行归并形成最终索引。20正排索引也称为前向索引。它是创建倒排索引的基础，具有以下字段。（1）LocalId字段（表中简称Lid）：表示一个文档的局部编号。（2）WordId字段：表示文档分词后的编号，也可称为索引词编号。（3）NHits字段：表示某个索引词在文档中出现的次数。（4）HitList变长字段：表示某个索引词在文档中出现的位置，即相对于正文的偏移量。21多字段索引（自学）针对每个不同的字段，分别建立一个索引，当用户指定某个字段作为搜索范围时，可以从相应的索引里提取结果。倒排列表方式扩展列表方式22索引更新索引更新完全重建策略（完全重建策略（CompleteRe-Build）当新增

9、文档达到一定数量，将新增文档和原先的老文档进行合并，然后利用前述章节提到的建立索引的方式，对所有文档重新建立索引。新索引建立完成后，老的索引被遗弃释放，之后对用户查询的响应完全由新的索引负责。23再合并策略（再合并策略（Re-Merge）有新增文档进入搜索系统时，搜索系统在内存维护临时倒排索引来记录其信息，当新增文档达到一定数量，或者指定大小的内存被消耗完，则把临时索引和老文档的倒排索引进行合并，以生成新的索引。24原地更新策略（原地更新策略（In-Place）原地更新策略试图改进“再合并策略”的缺点。就是说，在索引更新过程中，如果老索引的倒排列表没有变化，可以不需要读取这些信息，而只对那些倒排列表变化的单词进行处理。即使老索引的倒排列表发生变化，只在其末尾进行追加操作，而不需要读取原先的倒排列表并重写到磁盘另外一个位置? 在索引合并时，不生成新的索引文件，而是直接在原先老的索引文件里进行追加操作，将增量索引里单词的倒排列表项追加到老索引相应位置的末尾25混合策略（混合策略（Hybrid）将单词根据其不同性质进行分类