正如动物依靠对环境和食物的认知来维持生存、人类依靠知识和技能来扮演社会角色一样，计算机应用程序和系统也依赖特定的"知识"来完成特定的功能。人类通过五官来获取知识，并通过语言和文字来实现知识的交流、共享和传承，由此建立起人类庞大的知识体系。然而，这些丰富的知识并不能够被计算机系统自然而直接地使用，原因在于当前的计算机程序远未达到理解自然语言和洞悉人类智慧的程度和水平。而我们又确实需要计算机系统能够具备一些知识，以便在不威胁到人类生存的前提下帮助人类完成一些"高级"任务。
正因为前人伟大的工作，我们才有诸如维基百科、百度百科等各种形式的"知识库"，但这些知识库只能被人类手动查询及理解，如果想要让机器理解这些，需要做一些处理。本文所做工作主要是编写爬虫程序从百度百科庞大的知识库中爬取大量的词条信息，然后使用正文提取、索引构建、基于向量空间模型的相似度排序等手段构建一个简易的搜索引擎，该工作因其构建在百度百科知识库上，因此具有内容具有很强的纯粹性，通过指定爬虫初始页面和爬取广度、深度能够控制爬取到的内容的类别，从而为构建知识库、知识图谱等工作提供了很好的数据集。例如， 如果限制爬虫从百度百科分类为电脑的页面开始爬取，使用广度优先搜索，然后限制爬取的深度为1或者2，这样爬取到的内容大多涉及到汽车，就可以标记为汽车类别的数据库，便于后继知识提取、知识图谱构建等工作反过来又能继续提升搜索引擎的性能。构建完整知识图谱主要可以在以下三个方便提升搜索引擎的性能：1、找到最想要的信息。语言可能是模棱两可的 —— 一个搜索请求可能代表多重含义，知识图谱会将信息全面展现出来，让用户找到自己最想要的那种含义。所以凭借知识图谱能够理解这其中的差别，并可以将搜索结果范围缩小到用户最想要的那种含义。2、提供最全面的摘要。搜索引擎可以借助知识图谱更好的理解用户搜索的信息，并总结出与搜索话题相关的内容。例如，当用户搜索"玛丽·居里"时，不仅可看到居里夫人的生平信息，还能获得关于其教育背景和科学发现方面的详细介绍。此外，知识图谱也会帮助用户了解事物之间的关系。3、让搜索更有深度和广度。由于知识图谱构建了一个与搜索结果相关的完整的知识体系，所以用户往往会获得意想不到的发现。在搜索中，用户可能会了解到某个新的事实或新的联系，促使其进行一系列的全新搜索查询。
从功能上来看，整个系统被划分为网络爬虫、正文提取、索引建立、链接排序、结果展示等几大步骤。其中网络爬虫从互联网上按照一定的规则爬取一定的内容；正文提取步骤对其进行去重、提取其中有意义的部分；索引建立步骤是为了加快检索而进行的预处理；链接排序是对搜索引擎检索的结果进行排序从而将高相关度的文章排在前面。总体结构图如图2-1所示。
图2-1 系统总体结构图
以下几章将分别从网络爬虫、正文提取、索引建立、基于向量空间模型的相似度排序几个部分分别阐述算法原理和实现细节。
网络爬虫又被称为网页蜘蛛，是一种按照一定的规则，自动的抓取万维网信息的程序或者脚本，已被广泛应用于互联网领域。搜索引擎使用网络爬虫抓取Web网页、文档甚至图片、音频、视频等资源，通过相应的索引技术组织这些信息，提供给搜索用户进行查询。
网页的抓取策略可以分为深度优先、广度优先和最佳优先三种。深度优先搜索不断深入搜索层次，直到在深度方向上无新链接出现才回溯进行宽度上的进展；广度优先搜索策略则是指在抓取过程中，在完成当前层次的搜索后，才进行下一层次的搜索；而最佳优先搜索策略按照一定的网页分析算法，预测候选URL与目标网页的相似度，或与主题的相关性，并选取评价最好的一个或几个URL进行抓取。深度优先搜索容易产生过分"陷入"问题，其中一个缺点是可能会陷入某些广告、低质量内容的集合中，图3-1展示了使用深度优先搜索进行爬虫设计爬取到的一些URL及其标题：
为了避免这个问题，同时考虑到易于实现，本文选取广度优先搜索方法。
广度优先搜索使用队列来维护所有待访问的URL，开始时向队列中添加一个初始URL，当算法开始时每次从队列中选取第一个URL进行爬取，将爬取到的URL再添加到队尾，这样不断进行，直到爬取到所需要数量的内容或队列为空
图3-1 深度优先搜索内容爬取结果
为止。其次便是从页面提取URL的问题，首先最简单的方式是使用正则表达式从页面内容提取链接，最直接的是使用如下方式：
"https?://[\\w\\-_]+(\\.[\\w\\-_]+)+([\\w\\-\\.,@?^=%&:/~\\+#]*[\\w\\-\\@?^=%&/~\\+#])?"
这个正则表达式虽然能够匹配大多数的链接形式，但是也因此导致爬取到的URL有各种形式的数据，比如css、js文件，图像、音频、视频文件，影响到爬取效率、质量。
考虑到我们要爬取百度百科上的内容，分析一下百度百科URL发现他们有着非常规范的结构，如百度百科上收录"信息检索"这个词条的URL是： http://baike.baidu.com/item/%E4%BF%A1%E6%81%AF%E6%A3%80%E7%B4%A2/831904，那么改写正则表达式为：
"https?://baike\\.baidu\\.com/[\\w\\-_]+/[\\w\\-\\.,@?^=%&:/~\\+#]*"
这样的话可以检索到大多数词条，但是还存在一个问题，分析页面源码容易发现，词条中链接到另一个词条的URL一般都是相对于 http://baike.baidu.com/ 的相对地址，为了解决这个问题，我们使用另外一个正则表达式来匹配相对地址，然后将其转换成绝对地址形式的URL。匹配相对地址的正则表达式可以写作：
"href=\"/ [^\"]+\""
为了保证爬取质量，在实现上我们采用必须以 http://baike.baidu.com/item/ 作为前缀的URL才会被加入队列中，这样最后爬取的部分结果如图3-2所示。
图3-2 本文爬虫爬取部分结果
图3-3展示了上文提到处理技术。
图3-3 网络爬虫最主要处理技术
并且这种方式不违背百度百科的"君子协定"。
对于一个单独的网页，往往最有价值的部分是网页的正文。然而就现在的大多数的网站的网页而言，不仅仅包含正文，网页标签等，其他的如广告，网页链接，插件等占据了网页相当一部分的内容。由于现实的需要，我们往往需要对网页的内容进行分析从而提取有价值的信息。一个网页的内容基本包含在正文中，对于新闻类网页尤其。将网页正文之外其他的内容剔除从而降低分析的难度是一种基本的思路。同时正文内容提取的好坏直接影响到接下来分析工作的质量。
在提取正文内容前，可能需要先进行预处理去除掉不同链接指向相同页面所造成的内容重复的现象，但由于本文所涉及到的领域主要是百度百科，鉴于爬虫爬取到的内容重复率很低，所以本文不做去重处理。涉及到正文提取，搜索引擎所使用的技术主要有：基于标签窗的算法、基于标签密度的算法、基于DOM树的算法、基于内容的方法、基于视觉的方法和基于数据挖掘/机器学习的方法等。考虑到百科页面具有非常规范的结构，本文所采用方法是配置页面正文提取模板，基于所要提取内容的标签及其属性值，通过模板来匹配正文。 具体来说，<title>、<meta>以及各种<h>标签包含网页概括性的内容，比如就百科信息检索页面，这几个标签如下：
<meta name=" description"content=" 信息检索（Information Retrieval）是指信息按一定的方式组织起来，并根据信息用户的需要找出有关的信息的过程和技术。狭义的信息检索就是信息检索过程的后半部分，即从信息集合中找出所需要的信息的过程，也就是我们常说的信息查寻（Information Search 或Information Seek）。一般情况下，信息检索指的就...">
<title> 信息检索（一种信息技术）_百度百科 </title>
<metaname="keywords"content=" 信息检索 信息检索起源 信息检索定义 信息检索类型 信息检索主要环节 信息检索热点 信息检索检索原因 信息检索四个要素 信息检索检索方法 信息检索检索的一般程序">
<h1 > 信息检索 </h1>
<h2> （一种信息技术） </h2>
正文部分需要提取的主要标签有<p>、<div>、<td>、<span>，具体来说，为了提高正文提取质量，对于百度百科正文部分我们提取它的<div class="para">的标签，这部分内容主要是正文详细介绍部分，图4-1展示了按照以上规则对西游记词条进行提取的部分内容：
图4-1 百度百科西游记词条部分HTML（左）与提取到的正文（右）
可以发现，这种方式提取到的内容有着较高的质量。
- 中文分词
当完成正文提取时便获取到了知识数据库，要对这个数据库进行检索。因为一般这个收集到的正文数据库非常庞大，如果采用直接扫描的方式将耗时耗力，为了提高检索效率，可以先对正文进行预处理，即建立索引。常用建立索引的方式是倒排索引，但在此之前还需要对正文进行分词处理，由于涉及到的文档主要是中文，所以需要进行中文分词处理。
中文分词指的是将一个汉字序列切分成一个一个单独的词。分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。在英文的行文中，单词之间是以空格作为自然分界符的，而中文只是字、句和段能通过明显的分界符来简单划界，唯独词没有一个形式上的分界符，虽然英文也同样存在短语的划分问题，不过在词这一层上，中文比之英文要复杂的多、困难的多。现有的分词算法可分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法，本文使用IKAnalyzer包进行中文分词。
IKAnalyzer是一个开源的，基于java语言开发的轻量级的中文分词工具包。其特点主要有以下几点：
1)采用了特有的"正向迭代最细粒度切分算法"，具有60万字/秒的高速处理能力。 2)采用了多子处理器分析模式，支持：英文字母（IP地址、Email、URL）、数字（日期，常用中文数量词，罗马数字，科学计数法），中文词汇（姓名、地名处理）等分词处理。 3)对中英联合支持不是很好,在这方面的处理比较麻烦.需再做一次查询,同时是支持个人词条的优化的词典存储，更小的内存占用。 4)支持用户词典扩展定义。 5)针对Lucene全文检索优化的查询分析器IKQueryParser；采用歧义分析算法优化查询关键字的搜索排列组合，能极大的提高Lucene检索的命中率。
本文不使用Lucene包，只使用IKAnalyzer的分词功能获取每个词组、词组所在文档中的起始位置。
- 倒排索引
在进行中文分词后，开始建立倒排索引。倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引。带有倒排索引的文件我们称为倒排索引文件，简称倒排文档。
倒排文档一般由两部分组成：词汇表和记录表。词汇表是文本或文本集合中所包含的所有不同单词的集合，对于词汇表中的每一个单词，其在文本中出现的位置或者其出现的文本编号构成一个列表，所有这些列表的集合就称为记录表。本文所构建的倒排索引的结构如图5-1所示。
图5-1 倒排索引结构
倒排索引的词汇表可以采用哈希表结构，其后所链接的记录表可以使用链表来表示（当文档集非常庞大时可以考虑更加高效的结构）。当到来新的文档时，首先使用分词工具获取该文档中所有词组及其出现位置，并对每个词组建立一个DocItem的结构。DocItem即图5-1下方的（文档ID，词起始位置，词频）三元组结构，然后查找它在词汇表中的位置并插入到词汇表中，具体流程图如图5-2所示。
图5-2 增加一篇文档倒排表更新流程
这样便完成了倒排索引表的建立，本文方法建立倒排表部分如图5-3所示。
图5-3 本文所建立倒排表部分结构
- 六、基于VSM的链接排序
当接收到用户查询时需要使用倒排表进行检索，为了更好的用户体验，需要对检索到的结果进行排序，Google的 PageRank算法便是链接排序算法之一。在众多的链接排序算法中，向量空间模型 (VSM) 是近几年来应用较多且效果较好的方法之一 。 1969 年， Gerard Salton提出了向量空间模型 VSM ，它是文档表示的一个统计模型。该模型的主要思想是：将每一文档都映射为由一组规范化正交词条矢量张成的向量空间中的一个点。对于所有的文档类和未知文档，都可以用此空间中的词条向量(T1 ,W 1 ,T 2 ,W2 ,…, Tn , Wn )来表示 ( 其中， Ti 为特征向量词条；Wi为Ti的权重 ) 。一般需要构造一个评价函数来表示词条权重，其计算的唯一准则就是要最大限度地区别不同文档。这种向量空间模型的表示方法最大的优点在于将非结构化和半结构化的文本表示为向量形式，使得各种数学处理成为可能。
回到我们的问题，当到来一个查询时，我们可以将这个查询分词、表示成一个词频向量，而倒排表中的每个文档都可以看成一个词频向量，检索句子与文档的相似性问题转化为如果计算这两个向量的相似程度。我们可以把它们想象成空间中的两条线段，都是从原点（[0, 0, ...]）出发，指向不同的方向。两条线段之间形成一个夹角，如果夹角为0度，意味着方向相同、线段重合；如果夹角为90度，意味着形成直角，方向完全不相似；如果夹角为180度，意味着方向正好相反。因此，我们可以通过夹角的大小，来判断向量的相似程度。夹角越小，就代表越相似。因此，我们便得到基于空间模型文档与查询余弦相似度排序问题。
为计算余弦相似度，还需要从倒排表中查找所有包含查询中词组的文档。这可以通过对于查询分词后的每个词组分别在倒排表中查找包含该词组的文档来实现，具体过程如图6-1所示。
图6-1 基于VSM的文档查询向量表示（为简洁省略很多连接线）
由图6-1可以得出，查询的词频向量表示为(1,1,1,1,1)，文档1词频向量表示为(0,2,0,1,0)，以此类推，这样便可以通过以下公式计算查询与所有待排序文档之间的余弦相似度：
cos(q,dj)=∑i=1nqidji∑i=1nqi2∑i=1ndji2
其中 q 表示查询的词频向量 ， dj表示第j个文档，余弦相似度越接近于1说明两者之间的相似度越高。通过以上方式便可得到排序后的文档。
整个程序所使用的软件环境主要是：
- Windows 10 professional
- Eclipse Neon + jdk 1.8.0
- Htmlparser 1.6 (解析HTML，用于正文提取)
- Log4j 1.2.17 (日志管理)
- IKAnalyzer 2012_u6 (中文分词)
在检索到结果之后，程序写出到HTML文件，对于一条查询页面的写出格式为：使用其Title作为标题部分，对内容中第一次出现关键词的位置附近的200个汉字作为详情部分。其中关键词均做高亮显示处理。
其中一次对哈尔滨工业大学的查询结果如图7-1所示：
图7-1 "哈尔滨工业大学"检索结果
其中，想要的结果排在第8位，如图7-2所示。
图7-2 "哈尔滨工业大学"词条排在第8位
图7-3 "花果山猴"检索结果
通过观察很容易得出搜索引擎没有按照期望排序的原因：前几个词条里面包含大量的"哈尔滨"词组，以至于他们与查询的余弦相似度很高，从而导致这样的结果。
本文从网络爬虫到相似度排序完整的实现了一个简易的搜索引擎，能够完成简单的检索功能。但是还存在一些待优化的地方，比如，从图7-2可以看出存在页面重复的现象，还需要对不同链接指向相同页面的情况进行排除、去重；其次，链接排序方面仅使用余弦相似度、Jaccard距离等排序效果不理想，可以探索更多的排序准则；最后，结合Java Web进行Web部署也是待优化的方面。