设计一个检索系统_举例说明什么是事实检索[通俗易懂]

简单实现了各个模块的功能，对整体有了了解，当然不是实用的系统。问题很多，抽时间继续学习。

系统的整体设计

（1）网络爬虫模块：该模块是从URL库中获得输入，解析URL中表明的Web服务器地址，建立连接，发送请求和接受数据，将获得的网页数据存储在原始网页库中，并从其中提取出连接信息放入网页结构库（堆栈或者队列）中，同时将待抓取的URL放入URL库，保证整个过程递归进行，直到URL库为空。使用Key-Value数据库或者文件等实现URL的去重工作保证不对相同的URL重复爬取。

该模块的主要功能：

下载网页数据，为搜索引擎系统提供数据来源，通过网页中的连接信息不断获得网络上的网页。

种子URL集合的选取原则：

(a) 基于主题的数据采集是采集互联网上与某一固定主题相关的数据，所以要选取特定的种子URL，根据这些种子URL采集其周围的数据。

(b) 选择一些重要的、权威的、出度较大的网站的URL作为种子URL。

基本流程：

本实验中，采取深度优先的爬取策略，爬取的流程为：首先是初始化，设置网页爬取的最大深度，将种子连接压入堆栈，并设置这些连接的深度为1，从硬盘中读取保存已经访问过的网页的文件，将这些已访问过的URL保存在HashSet集合中。

循环从栈顶取出URL，直到该URL未被访问过，新建Page对象，设置对象的URL属性。新建URL对象，调用该对象的openStream方法，从该流中按行依次读取网页的内容。如果该网页的深度小于阈值，则需要获得该page页面中的URL。调用getUrlByString方法，该方法中用正则表达式提取文本中的链接，正则表达式为String patternString =”<[a|A]\\s+href=([^>]*\\s*>)”，如果提取出的URL没有在visitedHashSet出现过，则将URL添加到page对象中网页列表中，并设置该URL的深度为父网页的深度加一。

完整读取网页的中的内容后，需要将该网页以HTM的文件格式保存在硬盘中，供后续的预处理、分词、建索引等步骤。该实验中，用网页URL的MD5码作为网页的唯一标识。函数getMD5就是通过传入URL字符序列产生唯一的MD5码。由于网页的数目较多，因此以1000为单位将网页保存不同的文件夹下。该实验中，网页保存在/file/download/目录下。

将分析完的URL添加到visitedHashSet中，表明已经访问过。将网页中的链接列表push到链接的堆栈中。依次从堆栈中取出元素，执行以上过程，直到堆栈为空。

将已访问过的URL写到URLlist.txt文件中，程序结束。

该模块的流程图如下图所示：

（2）正文提取模块：网页中包含各种标签，广告等内容，该模块的功能就是通过基于行块分布函数的正文提取方法，识别和清除网页内容噪音内容，并提取网页的主题，包括网页的标题、摘要、正文等内容。

该模块的主要功能：

从给定的网页中抽取出标题、摘要、正文等信息，去除网页中的噪音，包括网站的导航信息和相关链接广告等内容。

该模块的实现方法：

本实验采用基于行块分布函数的网页正文提取方法（开源项目）。

基本思想：脱离HTML标签，通过建立行块分布函数，用线性时间找出HTML文件的正文。一个网页的正文部分一般是网页中文字信息分布最密集的区域之一，也有可能是较长信息的评论或出现大篇幅的导航信息。这种情况下就要结合行块的长度信息解决该问题。通过分析网页中行块长度的聚升点和聚降点寻找正文。

该算法的基本流程：

首先设置行块的厚度为3，正文区的密度阈值为150，增大该阈值可以去除网页正文中成块的新闻标题，提高准确率，但有可能将部分正文信息去除，降低了召回率。减小该阈值可以保证找到只有一句话的正文，但是降低了召回率。

获取该HTML文件中的文本，根据<title>标签，用正则表达式提取出网页中的标题。将网页中的HTML规范、注释信息、javascript脚本、样式信息、特殊字符等内容用空白符代替，这样就得到只有文字内容的文本，将文本分行保存在list集合中，提供给后序步骤处理。以3行为一块求出每块的长度，即每个块的文本去掉空白符剩下的字符长度。

设置正文的起始位置start、终止位置end、起始标志boolstart和终止位置boolend。从第0个块开始依次遍历每个块，当第i个块的长度大于阈值并且起始标志boolstart为false，第i+1、i+2和第i+3行中某行长度不为0，则说明找到一个聚升点。设置起始标志boolstart为false，起始位置start为i。接着继续往下遍历，当第i行或第i+1行某行长度为0，说明找到一个聚降点，设置终止位置end为i，终止标志boolend为true。这时就找到一个正文段，提取出行号为start到end的文本作为网页的正文。继续遍历往下的块信息，只要找到一个聚升点和一个聚降点，则找到一段正文。

当遍历完所有的块信息后，设置网页的正文、摘要（目前摘要的提取是将文本的前30个字符作为摘要。也可将文档中包含权重最大的词的一段文本作为文档的摘要）。

算法结束。

算法的基本流程如下图所示：

（3）网页去重模块：在大量网页中，存在内容完全相同的网页，也有一些网页内容基本相同，只是有细节上细微的不同，例如转载网页等。系统需要将这种网页进行去重处理。该系统采用基于指纹识别的思想对网页进行重复性判断。

该模块的主要功能：

网络上可能会出现多个域名对应同一个网站的情况或者网站的互相转载。去除重复的网页是为了避免同一个网站的内容被多次采集和索引。 网页消重就是指去除网页集合中转载网页（即文本内容基本相同）的过程。

该模块的基本思想：

为每个文档计算出一组指纹（fingerpint），这些指纹可以是网页内容中的一系列字符串的hash值或者MD5散列值，若两个文档拥有一定数量的相同指纹，则认为两个文档的内容重叠性较高，即二者是内容转载的。

算法的基本流程：

分析网页文档时，提取并记录网页中出现的关键词，同时根据公式赋予每个关键词一个权值，这些关键词的权值构成一个向量空间，可以用来表示网页。

将网页中权重最大的前N个关键词按字母进行排序后再拼接成一个字符串，记为Concatenate(sort(T))，用MD5对这个字符串产生散列值MD5(Concatenate(sort(T)))。

若两个网页的散列值相同，则认为二者是相互转载的。在实际程序运行期间，每当需要分析一个新的文档时，提取文档的前N个关键词，并按上述方法产生MD5散列值，将该散列值与之前分析完的所有文档进行比较，当这个新的文档的MD5散列值已经出现过时，说明这个文档时重复文档，删掉即可。

（4）中文分词模块：中文与英文不同，英文词与词之间有天然的分隔符，中文词汇大多是连续的，因此需要进行自动分词工作。该模块采用正向最大匹配的算法进行分词，用Trie树保存词典。

该模块的主要功能：

目前的中文检索系统中大多支持基于词的检索，因此需要对文本进行自动的词语切分，该过程也就是中文分词。

该模块的实现：

目前网络上有很多的开源分词工具IKAnalyzer、ICTCLAS、Paoding等等，本实验中采用自己设计的分词方法进行分词。

本实验采用正向最大匹配的算法进行分词。

算法的基本思想：

正向最大匹配算法的基本思想：从左到右将待分词的文本中的几个连续字符与词表匹配，如果匹配上则找到一个词。当下一个扫描不是词表中的词或某个词的前缀，则结束。继续分析后面的文本。

用Trie树保存词典。Trie树也称为前缀树，用Trie树保存词典能将文本的所有可能分词找出，无论该词有多长。Trie树还适用于查找单词前缀，如查找所有以“中华民”开头的单词，包括“中华民国”、“中华民族”等。

Trie树的结构如下图3-3：

Trie树的最坏的情况下搜索的时间代价是O(h)，h为Trie树的层数。

（1）每个结点都是词语的一个汉字。

（2）结点中的指针指向了该汉字在某一个词中的下一个汉字。这些指针存放在以汉字为key的hash结构中。

（3）结点中的“#”表示当前结点中的汉字是从根节点到该汉字结点所组成的词的最后一个字。

正向最大匹配的具体实现过程为：

首先：读取保存文本内容的文件。

设置起始位置startPosition，startPosition用于保存分词的开始位置，依次遍历文本中的每一个字符，先初始化Tocken为空，令position为startPosition的位置，当Trie树包含position位置的字符letter时，根据指针获得该字符letter对应的节点node，判断该node的结尾标识是否为true，为true说明找到一个分词，found设置为true，继续遍历下一个position对应的字符，当遍历到的字符不是某个词的前缀时，停止遍历。

判断found是否为true，若为true，则将这次遍历找到的最长的词保存下来，并将startPosition后移该词的长度个位置，若found为false，则说明没有找到一个分词，将startPosition后移一个位置。当startPosition超出文本的长度时，算法结束。

分完词的文件保存在file/wordFiles/目录下。

该过程的流程图如下图所示。

（5）倒排索引模块：该模块是网页预处理的核心部分，采用基于增量的倒排索引结构保存倒排文件，便于倒排文件的更新等操作。

倒排索引概念：

倒排索引的索引的对象是文档或文档集合中的单词，存储这些单词在一个文档或者一组文档中的存储位置，是对文档或文档集合的一种最常用的索引机制。

倒排文件的组成部分：

倒排文件一般包括两个部分：词汇表（vocabulary）和记录表（posting list）。词汇表是文档或者文档集合中所有不同单词的集合。对于词汇表中的每一单词，其在文档中出现的文档编号列表的集合构成记录表。

本实验采用的索引文件结构：

传统的静态信息检索系统由于文档集合相对稳定，索引一旦建立很少进行更新，需要更新时要重新建立整个检索文件。由于搜索引擎的索引结构需要支持高效的更新功能。因此，本实验中，采用一种增量索引结构。在建立倒排索引时，每个词项的记录表以连接块的形式存放于倒排索引文件中。

本次实验的索引结构如下图3-6所示：

该索引结构分为三个文件：

词项文件：该文件保存三个值的集合，第一个保存文档集合中出现的所有词项，用Term表示，第二个值为该词项对应的IDF值，即词项的反文档频率。该值的计算过程将在后面进行论述。第三个值是该词项对应的记录表在记录表文件中的位置（类型为long的一个偏移量）。

记录表文件：记录表中存放posting list集合，每个posting list按块存储，存储的格式如图中所示：首先是词项对应的文档集合的个数，接下来是每个文档的记录，包括文档的编号、文档中该词项出现的次数、最后一个是指向位置文件的指针，该指针保存指向位置文件的偏移量。

块的最后是一个指向下一块的指针，该指针保存指向记录表中该词项对应的另一个posting list块的位置。

位置文件：该文件保存位置信息，同样是按块进行存储。每个块中首先是位置的个数，然后是具体的位置列表。

每当新的一批文档集合需要插入该索引结构时，首先将这批文档集合在内存中建立索引结构，然后更新该索引结构。

该模块的实现：

该模块主要有一下几个类：

MFile类：用于保存文档信息，包括文档的编号、文档对应的URL、文档的标题、文档的摘要、文档的大小以及用于相关性排序的文档权重等属性。

Word类：用于保存新来的一批文档中的词项信息，包括该词的文本内容、词的权重(即IDF值)、出现该词的文档列表等信息。

Vocabulary类：用于保存新来的一批文档中所有的词汇表，包括所有词汇，用HashMap保存。

DWord类：用于保存从硬盘中读取的词汇信息，包括该词的文本内容、出现过该词的文档数目、该词的权重(即IDF值)、该词在索引文件中的偏移量等信息。

DVocabulary类：该类用于保存从硬盘中读取的词汇表信息，包括所有词汇，用HashMap保存。

Index类：该类用于建立索引结构。

该模块的类图如下图3-7所示：

建立索引结构的过程：

首先，将整个词项文件读入内存（由于该文件并不大，因此可以直接放在内存里，供后续步骤使用），每个词项包括该词的文本信息、权重和该词对应的记录表中对应的偏移量，用DWord对象保存该词项，并将该DWord对象保存到新建的DVocabulary对象中，读完后DVocabulary对象保存的就是所有的词项信息。

分别读取记录表文件和位置文件的文件尾位置。

遍历所有分好词的文件，新建MFile对象，并设置该对象的标题、文件编号等信息。遍历该文件中所有的分词，调用vocabulary对象的add方法，若该词不存在，则新建Word对象（该词文本、MFile对象和位置号为构造函数的参数）；若该词已经存在，则将该文件对象和位置号保存到已有的word对象中。当遍历完所有分好词的文件后，vocabulary对象中即保存了新来的这批文档中的词项信息。

接着遍历vocabulary对象中所有的Word对象，根据该Word对象查找dVoabulary对象中是否出现过该词。

如果没有出现过该词，则新建DWord对象，设置该对象的文本、对应的文档数（即该批文档的数目）、对应的记录表的偏移量（即当前记录表的文件尾位置）。将DWord对象添加到dVoabulary对象中。定位到记录表的文件尾位置，首先写入该词对应的文档数，然后依次将文件号、指向位置文件的指针写入记录文件。将nextPointer位置写入0，表明该块与另外一块相连。

如果该词在词项文件中出现过，则首先更新对应的DWord对象的文件数，即在原来的值上加上新来的这批文档中所包含该词的文件数。然后根据DWord对象的offset属性找到该词在记录表中第一个记录块，循环遍历这些相连的记录块，直到找到最后一个记录块的nextPointer指针，此时该指针的值为0，将该nextPointer指针设置为记录表文件尾位置。然后定位到记录表的文件尾位置，同样首先将该词对应的文件数写到该文件中，然后依次将文件号和该词在文件中位置的个数写入记录文件，并且将位置列表写入位置文件。

当处理完这批文档后，需要更新词项文件中的内容。遍历dVoabulary对象中的所有DWord对象，重新计算该词项的IDF值。该IDF值为词项的反文档频率，计算公式为log2(N/DF)，N为所有的文档总数，DF为包含该词项的文档数量。如果包含该词项的文档越多，则说明该词在区分文档内容的能力上却低，盖茨向的IDF也就越小。计算完权重后，将所有的词项信息重新写回到词项信息文件中。

建立索引的过程即结束。

该过程的流程图如下图3-8所示。

（6）相关性排序模块：该模块采用空间向量模型对检索出来文档进行相关性排序，并将结果反馈给用户。

相关性排序概念：

用户在进行信息检索时，希望获得与其需求密切相关的检索结果，因此信息检索系统的核心问题是：当用给定查询后，对文档集中的每一个与用户查询相关程度进行判断。也就是对所有相关文档按照相关度由大到小的排序过程。

本实验使用的相关性模型：

三种经典的模型：布尔模型、空间向量模型和概率模型等。本实验采用的是空间向量模型（好吧，真正的搜索引擎应该pagelink之类的算法，这里用最简单的，作为示例）。在空间向量模型中，文档和查询均被看成由索引项构成的向量。

计算网页与查询的相关性。即计算查询词与文本索引项构成的两个向量的夹角。计算公式如下图3-9所示。

其中dik是文档di中词项k的权重，qk是查询时Q中词项k的权重。

计算相关度的流程为：

首先创建Dvocabulary对象，读取保存所有词项信息的文件index.tl，将每个词项信息保存到DWord对象中，包括词项的文本、权重和该词项对应的记录表中的偏移量。将该DWord对象保存到Dvocabulary对象中，Dvocabulary对象中即保存了所有的词项信息。

读取保存所有文件信息的文件docinfo.txt，以便于根据用户输入选择网页的ID快速找到相应网页的URL，标题和摘要等。然后等待用户输入。

当用户输入完成后，获取用户查询的文本。

对用户查询的文本进行分词，得到查询词的列表。

遍历所有的用户查询词，根据该词从DVocabulary中得到对应的Dword对象。根据DWord对象中的offset值读取记录表文件，若有多块记录表，则根据nextPointer依次读取每个块，从而从记录表中得到该词相关的文件集合。

将各个词对应的文件集合进行集合的交操作，得到的文件包含所有的查询词。

对每个相关文档用空间向量模型计算该文档与查询的相关度。

根据文档号从文档信息中得到公式中dik*dik的值。

计算dik*qk和qk*qk的值，从而求出两个向量的夹角的值。

当求出所有相关文档的相关度后，按照相关度的值对这些文档进行排序，并将排序结果展示给用户。可以通过强制设定某个阈值，控制被检索出来的文档的数量。检索结果可以被用于相关反馈中，以便对原始的查询式进行修正。

搜索结果如下图所示。

参考：

刘挺，秦兵，张宇，车万翔. 信息检索系统导论.

邱哲，符滔滔，王学松. 开发自己的搜索引擎.

李晓明，闫宏飞，王继民. 搜索引擎-原理、技术与系统.

王冬，左万利. 一种增量倒排索引结构的设计与实现.

今天的文章设计一个检索系统_举例说明什么是事实检索[通俗易懂]分享到此就结束了，感谢您的阅读。