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

1、搜索引擎基本原理及实现(shxin)技术索引(suyn)技术共三十九页网络爬虫辛辛苦苦(xn xn k k)的把网页爬回来之后共三十九页预处理系统(xtng)主要工作信息抽取(chu q)分词分类等处理工作生成正排发送 到索引系统生成倒排索引。共三十九页信息(xnx)抽取去标签和去噪去标签构造 DOM 树。tinyHTML，htmlParser，Jsoup；去噪去掉与正文不相关(xinggun)的广告或者其他信息。如广告，评论，导航条，版权信息，友情链接等等。共三十九页分词(fn c)分词的目的(md)是为了提取文件特征，文件特征即网页内容的结构化表现形式。分词方法基于字符串匹配的分词方法基于

2、理解的分词方法基于统计的分词方法共三十九页分词(fn c)思想设计的原则1、颗粒度越大越好：用于进行语义分析的文本分词，要求分词结果的颗粒度越大，即单词的字数越多，所能表示的含义越确切，如： “公安局长”可以(ky)分为“公安 局长”、“公安局 长”、“公安局长”都算对，但是要用于语义分析，则“公安局长”的分词结果最好（当然前提是所使用的词典中有这个词）2、切分结果中非词典词越少越好，单字字典词数越少越好，这里的“非词典词”就是不包含在词典中的单字，而“单字字典词”指的是可以独立运用的单字，如“的”、“了”、“和”、“你”、“我”、“他”。例如：“技术和服务”，可以分为“技术 和服 务”以及“

3、技术 和 服务”，但“务”字无法独立成词（即词典中没有），但“和”字可以单独成词（词典中要包含），因此“技术 和服 务”有1个非词典词，而“技术 和 服务”有0个非词典词，因此选用后者。共三十九页3、总体词数越少越好，在相同(xin tn)字数的情况下，总词数越少，说明语义单元越少，那么相对的单个语义单元的权重会越大，因此准确性会越高。共三十九页基于(jy)字符串匹配的分词方法也叫做基于字典(zdin)的分词方法，它是以字典为依据的。按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配。若在词典中找到某个字符串，则匹配成功，即识别出一个词。又分为三种：正向最大匹配法（由左到

4、右的方向）；逆向最大匹配法（由右到左的方向）；双向最大匹配法。共三十九页最大匹配(ppi)法 最大匹配是指以词典为依据，取词典中最长单词为第一个次取字数量的扫描串，在词典中进行扫描。例如：词典中最长词为“中华人民共和国”共7个汉字(Hnz)，则最大匹配起始字数为7个汉字。然后逐字递减，在对应的词典中进行查找。下面以“我们在野生动物园玩”详细说明一下这几种匹配方法：共三十九页正向(zhn xin)最大匹配法1、正向最大匹配法：正向即从前往后取词，从7-1，每次减一个字，直到词典命中或剩下1个单字。第1次：“我们在野生动物”，扫描7字词典，无第2次：“我们在野生(yshng)动”，扫描6字词典，无

5、。第6次：“我们”，扫描2字词典，有扫描中止，输出第1个词为“我们”，去除第1个词后开始第2轮扫描，即：第2轮扫描：第1次：“在野生动物园玩”，扫描7字词典，无第2次：“在野生动物园”，扫描6字词典，无。第6次：“在野”，扫描2字词典，有扫描中止，输出第2个词为“在野”，去除第2个词后开始第3轮扫描，即：第3轮扫描：第1次：“生动物园玩”，扫描5字词典，无第2次：“生动物园”，扫描4字词典，无共三十九页第3次：“生动物”，扫描3字词典，无第4次：“生动”，扫描2字词典，有扫描中止，输出第3个词为“生动”，第4轮扫描，即：第4轮扫描：第1次：“物园玩”，扫描3字词典，无第2次：“物园”，扫描2字

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

7、园玩”，扫描7字词典，无第2次：“野生动物园玩”，扫描6字词典，无。第7次：“玩”，扫描1字词典，有扫描中止(zhngzh)，输出“玩”，单字字典词加1，开始第2轮扫描第2轮扫描：“们在野生动物园”第1次：“们在野生动物园”，扫描7字词典，无第2次：“在野生动物园”，扫描6字词典，无第3次：“野生动物园”，扫描5字词典，有扫描中止，输出“野生动物园”，开始第3轮扫描第3轮扫描：“我们在”第1次：“我们在”，扫描3字词典，无第2次：“们在”，扫描2字词典，无共三十九页第3次：“在”，扫描1字词典，有扫描中止，输出“在”，单字字典词加1，开始第4轮扫描第4轮扫描：“我们”第1次：“我们”，扫描2字

8、词典，有扫描中止，输出“我们”，整体扫描结束。逆向(n xin)最大匹配法，最终切分结果为：“我们/在/野生动物园/玩”，其中，单字字典词为2，非词典词为0。共三十九页双向最大匹配(ppi)法正向最大匹配法和逆向最大匹配法，都有局限性。因此有人又提出了双向最大匹配法，双向最大匹配法。即，两种算法都切一遍，然后根据大颗粒度词越多越好，非词典词和单字词越少越好的原则，选取其中(qzhng)一种分词结果输出。正向最大匹配法，最终切分结果为：“我们/在野/生动/物/园/玩”，其中，两字词3个，单字字典词为2，非词典词为1。逆向最大匹配法，最终切分结果为：“我们/在/野生动物园/玩”，其中，五字词1个，

9、两字词1个，单字字典词为2，非词典词为0。非字典词：正向(1)逆向(0)（越少越好）单字字典词：正向(2)=逆向(2)（越少越好）总词数：正向(6)逆向(4)（越少越好）因此最终输出为逆向结果。共三十九页基于(jy)理解的分词方法该方法又称基于人工智能的分词方法。它是利用(lyng)汉语的语法知识和语义知识以及心理学知识进行分词，需要建立分词数据库、知识库和推理机。这种分词方法需要使用大量的语言知识和信息。目前还处在试验阶段。共三十九页基于统计(tngj)的分词方法又称为无字典分词，它的主要思想(sxing)是：词是稳定的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。

10、因此字与字相邻出现的概率或频率能较好地反映成词的可信度。可以对训练文本中相邻出现的各个字的组合的频度进行统计，计算它们之间的互现信息。共三十九页分词(fn c)工具IkAnalyzer2012，国外有名的分析系统，也可以处理中文(zhngwn)。使用简单。NLPIR2014, NLPIR2015ICTCLAS5.0中科院开发的专门针对中文的分词系统，中文分词较准确，稍微麻烦点共三十九页教育学院(xuyun)/n_new/3.34/2#学院(xuyun)/n/2.58/19#教育/vn/1.74/3#信息/n/1.74/3#工程/n/1.34/5#教学/vn/1.27/3#共三十九页网页(wn

11、y)特征提取所有分出来的词都要保留吗？我该如何取舍(qsh)呢？只保留一定数量的能代表网页内容特征的关键词。最简单的就是统计词频，将出现频率最高的n个词保留。共三十九页索引(suyn)索引是对数据库表中一列或多列的值进行排序(pi x)的一种结构。此处指的是将爬取的网页进行预处理之后的，将关于这个URL的信息存入数据库，被称为索引库。 索引库中关于URL的信息不仅是组成页面内容的关键词及其特征(位置、格式等)，还有链接、更新情况等信息。共三十九页建立倒排索引的基本(jbn)过程（1）页面分析将原始(yunsh)页面的不同部分进行识别并标记，例如：title、keywords、content、l

12、ink、anchor、评论、其他非重要区域等等；（2）对网页内容分词。分词的过程实际上包括了切词分词同义词转换同义词替换等等。以对某页面title分词为例，得到的将是这样的数据：term文本、termid、词类、词性等等；（3）之前的准备工作完成后，接下来即是建立倒排索引，形成termdoc，共三十九页倒排索引(suyn)(Inverted Index)可以根据单词快速获取包含这个(zh ge)单词的文档列表。是实现“单词-文档矩阵”的一种具体存储形式。共三十九页倒排索引(suyn)的建立共三十九页实际上在建立倒排索引的最后还需要有一个入库写库的过程，而为了提高效率这个(zh ge)过程还需要

13、将全部term保存在文件头部，并且对数据进行压缩，这些涉及到的技术自行学习。共三十九页建立(jinl)索引两遍文档遍历法（2-Pass In-Memory Inversion）在第一遍扫描文档集合时，该方法并没有立即开始建立索引，而是收集一些全局的统计信息。比如文档集合包含的文档个数N，文档集合内所包含的不同单词个数M，每个单词在多少个文档中出现过的信息DF。每一项记载某个文档的文档ID和单词在该文档对应的出现次数TF。第一遍扫描的主要目的是获得一些统计信息，并根据(gnj)统计信息分配内存等资源，同时建立好了单词相对应倒排列表在内存中的位置信息，即主要做些资源准备工作。在第二遍扫描的时候，开

14、始真正建立每个单词的倒排列表信息，即对于某个单词来说，获得包含这个单词的每个文档的文档ID，以及这个单词在文档中的出现次数TF，这样就可以不断填充第一遍扫描所分配的内存空间。共三十九页排序(pi x)法（Sort-basedInversion）在建立索引的过程中，始终在内存中分配(fnpi)固定大小的内存，用来存放词典信息和索引的中间结果，当分配(fnpi)的内存被消耗光的时候，把中间结果写入磁盘，清空内存里中间结果所占内存，以用作下一轮存放索引中间结果的存储区。中间结果如何存储，中间结果如何排序自行学习。共三十九页归并(gubng)法（Merge-basedInversion）。“归并(gu

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

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

17、负责。共三十九页再合并策略（Re-Merge）有新增文档进入搜索系统时，搜索系统在内存维护临时倒排索引来记录(jl)其信息，当新增文档达到一定数量，或者指定大小的内存被消耗完，则把临时索引和老文档的倒排索引进行合并，以生成新的索引。共三十九页原地更新策略（In-Place）原地更新策略试图改进“再合并策略”的缺点。就是说，在索引更新过程中，如果老索引的倒排列表没有变化，可以不需要读取这些信息，而只对那些倒排列表变化的单词进行处理。即使老索引的倒排列表发生变化，只在其末尾进行追加操作，而不需要读取原先的倒排列表并重写到磁盘另外一个位置(wi zhi)? 在索引合并时，不生成新的索引文件，而是直接

18、在原先老的索引文件里进行追加操作，将增量索引里单词的倒排列表项追加到老索引相应位置的末尾共三十九页混合策略（Hybrid）将单词根据其不同性质进行分类，不同类别的单词，对其索引采取不同的索引更新策略。根据单词的倒排列表长度进行区分，将单词划分(hu fn)为“长倒排列表单词”-原地更新策略“短倒排列表单词”- -再合并策略因为“原地更新策略” 策略能够节省磁盘读写次数。而 “短倒排列表单词”读写开销不算太大，所以利用“再合并策略”来处理，充分利用其顺序读写优势共三十九页共三十九页索引(suyn)建立的过程1 正向索引路径的输入 正向索引路径的建立最好建立在文件中，因为它只是建立索引的中间(zhngjin)过程，不需要存入数据中路径的格式：1）相对路径2）绝对路径2 建立正向索引1）分词（lucene分词工具）共三十九页2）停用词(yn c)的去除 public static String transJe(String testString, String c1, String c2) String result = ; try Analyzer analyzer =