自制搜索引擎[试读]
1-1 理解搜索引擎的构成
在体验搜索引擎的开发过程之前,我们先在第1 章介绍一下搜索引擎的基本概念。搜索引擎的基础是应用于信息检索、数据库等领域的信息技术,要想开发搜索引擎,横跨多个领域的广泛知识是不可或缺的。在本章我们尽可能通俗易懂、简明扼要地总结归纳了这些知识。由于本章讲解的是后续章节的背景知识,所以恳请诸位认真地读下去。 1-1 理解搜索引擎的构成 在本节,我们首先介绍什么是搜索引擎,然后再大略地讲解其基本架构。由于从1-2 节开始还会详细地讲解有关内容,所以在本节就让我们先在大体上了解一下搜索引擎的全貌吧。 什么是搜索引擎 搜索引擎是一类系统或软件的统称,作用是从文档的集合中查找(检索)... 查看全部[ 1-1 理解搜索引擎的构成 ]
1-2 实现了快速全文搜索的索引结构
本节讲解的是用于快速进行全文搜索的索引结构。在讲解广泛应用于全文搜索的、名为倒排索引的索引结构之前,让我们先来梳理一下全文搜索的方法。 全文搜索的两种方法 全文搜索大致上可以分为两种方法,一种是利用全扫描进行全文搜索,一种是利用索引进行全文搜索。 利用全扫描进行全文搜索 第一种方法是从头到尾扫描作为检索对象的文档,以此来搜索要检索的字符串。由于Unix 的字符串检索命令“grep”也是以同样的方式进行搜索的,所以有时也将这种方法称为“grep 型搜索”。 在利用全扫描进行全文搜索时,虽然不需要事先处理作为检索对象的文档,但问题是文档数越多检索时间就越长。因此,一般... 查看全部[ 1-2 实现了快速全文搜索的索引结构 ]
1-3 深入理解倒排索引
至此为止,我们就讲解完了倒排索引的概要。下面,就让我们再来略微详细地了解一下倒排索引吧。 倒排索引= 词典+ 倒排文件 倒排索引是由单词的集合“词典”和倒排列表的集合“倒排文件”构成的。词典和倒排文件以及作为这二者构成要素的单词和倒排列表的关系如图1-2 所示。 图 1-2 倒排索引的结构 词典中的每个单词都持有一段引用信息,指明了对应着该单词的倒排列表。利用这段引用信息,我们就可以从词典中的各个单词那里获取到相应的倒排列表了。 从倒排索引中查找单词 若要从倒排索引中查找出包含了某个单词的文档,只需要先从词典中找到该单词,然后获取与之对应的倒排列表,最后从倒... 查看全部[ 1-3 深入理解倒排索引 ]
1-4 制作中文文档的倒排索引
至此为止,我们就讲解完了针对英文文档的倒排索引。在英文的句子中,由于单词之间留有空白,所以通过用空白划分句子就可以提取出句中的单词。但是在中文的句子中,由于各单词是词间不留空白连续书写的,所以就需要使用不同于英文的方法,才能将句子分割成单词或字符的序列。在本节我们详细地看一下分割中文句子的方法。 分割中文句子的方法 若要将类似中文的句子,即单词无法通过空白划分出来的句子分割成单词序列,通常有以下两种方法。 词素解析分割法 N-gram(q-gram)分割法 下面就让我们详细地看一看这两种分割方法吧。 词素解析分割法 词素解析(Morphologica... 查看全部[ 1-4 制作中文文档的倒排索引 ]
1-5 实现倒排索引
至此为止,我们已经逐渐了解了倒排索引的逻辑结构。下面,就让我们再来了解一下倒排索引的具体实现吧。 实现词典 在实现词典时,为了能够快速地获取到对应着单词的倒排列表,通常都会使用哈希表、树等数据结构。例如,常用的树形数据结构有保存着各个单词顺序关系的二叉查找树(Binary Search Tree)和字典树(Trie)等。 用二叉查找树实现词典 使用二叉查找树实现词典时,要先将数据对(的列表)按照单词的词典顺序排列,然后存储到存储器中。数据对是由单词和对应着该单词的倒排列表的引用信息构成的。例如,若用内存上的二叉查找树实现之前例子中的词典,就会得到如图1-3 所示的树形结... 查看全部[ 1-5 实现倒排索引 ]
1-6 使用倒排索引进行检索
前面我们已经了解了由索引管理器管理的倒排索引的结构以及具体的实现方法。下面,就让我们再来了解一下在索引检索器上使用倒排索引进行检索的方法吧。 布尔检索 在1-2 节,我们提到了如何从倒排索引中查找出同时包含多个单词的文档,即先获取与各单词相对应的倒排列表,然后用AND 运算符计算出其中包含的文档编号的交集。 使用由多个单词通过逻辑运算符连接而成的查询进行检索,称为“布尔检索”(Boolean Retrieval)。逻辑运算符(Boolean Operator)有AND、OR、NOT 等,其含义分别如下所示。 AND:两边的单词都要包含(逻辑与) OR:包含任意... 查看全部[ 1-6 使用倒排索引进行检索 ]
1-7 构建倒排索引
前面我们已经了解了由索引管理器管理的倒排索引的结构以及在索引检索器上进行检索处理的流程。下面,就让我们再来看一下如何在索引构建器上构建倒排索引吧。 使用内存构建倒排索引 生成了与文档编号对应的单词表后对该表进行倒排,在1-2 节我们通过这种方法生成了倒排索引。若让计算机来处理的话也是如此,先在内存上生成与文档编号对应的单词表(二维数组),然后用相同的方法倒排该表,就可以构建出倒排索引了。但是,由于大多数情况下倒排索引都是非常稀疏的表,因此这种构建方法可能会消耗大量的内存。 于是就有了用链表实现倒排列表这一优化方法。相比之下,该方法只需少量的内存就可以构建出倒排索引。 使... 查看全部[ 1-7 构建倒排索引 ]
1-8 准备要检索的文档
前面我们以“想要进行检索的数据已经在手边了”为前提,讲解了搜索引擎的结构及其构成要素。但是,在实际中这些数据来自哪里呢?在本章的最后,让我们再来大略地了解一下如何收集、整理作为检索对象的数据吧。 收集数据 搜索引擎中作为检索对象的数据来自哪里呢? 一种情况是要检索的数据已经存在了。有时是大量的数据已经存在于企业的文件服务器、邮件服务器,或每个人的PC 中了;有时是运营博客或社会化书签等Web 应用程序的公司,已将由应用程序的用户添加、更新的信息存入数据库等系统中了。在这种情况下,数据并不是我们亲自收集的,而是自然而然地储存起来的。 与此相对,还有一种是难以亲自收集数据的... 查看全部[ 1-8 准备要检索的文档 ]