dySE：一个 Java 搜索引擎的实现

忘是亡心i 2022-06-10 05:13 187阅读 0赞

本系列文章将逐步介绍 dySE 这个开源的[Java][] 小型[搜索引擎][Link 1]的实现过程。该搜索引擎分为三个模块：爬虫模块、预处理模块和搜索模块。其中详细阐述了: 多线程页面爬取、正文内容提取、文本提取、分词、索引建立、快照等功能的实现。本文将重点介绍 dySE 的整体结构和爬虫模块的设计与实现。

分三部分的系列将逐步说明如何设计和实现一个搜索引擎。在第一部分中，您将首先学习搜索引擎的工作原理，同时了解其体系结构，之后将讲解如何实现搜索引擎的第一部分，网络爬虫模块，即完成网页搜集功能。在系列的第二部分中，将介绍预处理模块，即如何处理收集来的网页，整理、分词以及索引的建立都在这部分之中。在系列的第三部分中，将介绍信息查询服务的实现，主要是查询界面的建立、查询结果的返回以及快照的实现。

# 第 1 部分: 网络爬虫 #

# 第 2 部分: 网页预处理 #

# 第 3 部分: 查询服务 #

# 网络爬虫 #

## dySE 的整体结构 ##

在开始学习搜索引擎的模块实现之前，您需要了解 dySE 的整体结构以及数据传输的流程。事实上，搜索引擎的三个部分是相互独立的，三个部分分别工作，主要的关系体现在前一部分得到的数据结果为后一部分提供原始数据。三者的关系如下图所示：

##### 图 1. 搜索引擎三段式工作流程 #####

![图 1. 搜索引擎三段式工作流程][1.]

在介绍搜索引擎的整体结构之前，我们借鉴《[计算机网络][Link 2]——自顶向下的方法描述因特网特色》一书的叙事方法，从普通用户使用搜索引擎的角度来介绍搜索引擎的具体工作流程。

自顶向下的方法描述搜索引擎执行过程：

*  用户通过浏览器提交查询的词或者短语 P，搜索引擎根据用户的查询返回匹配的网页信息列表 L；
 *  上述过程涉及到两个问题，如何匹配用户的查询以及网页信息列表从何而来，根据什么而排序？用户的查询 P 经过分词器被切割成小词组 <p1,p2 … pn> 并被剔除停用词 ( 的、了、啊等字 )，根据系统维护的一个倒排索引可以查询某个词 pi 在哪些网页中出现过，匹配那些 <p1,p2 … pn> 都出现的网页集即可作为初始结果，更进一步，返回的初始网页集通过计算与查询词的相关度从而得到网页排名，即 Page Rank，按照网页的排名顺序即可得到最终的网页列表；
 *  假设分词器和网页排名的计算公式都是既定的，那么倒排索引以及原始网页集从何而来？原始网页集在之前的数据流程的介绍中，可以得知是由爬虫 spider 爬取网页并且保存在本地的，而倒排索引，即词组到网页的映射表是建立在正排索引的基础上的，后者是分析了网页的内容并对其内容进行分词后，得到的网页到词组的映射表，将正排索引倒置即可得到倒排索引；
 *  网页的分析具体做什么呢？由于爬虫收集来的原始网页中包含很多信息，比如 html 表单以及一些垃圾信息比如广告，网页分析去除这些信息，并抽取其中的正文信息作为后续的基础数据。

在有了上述的分析之后，我们可以得到搜索引擎的整体结构如下图：

##### 图 2. 搜索引擎整体结构 #####

![图 2. 搜索引擎整体结构][2.]

爬虫从 Internet 中爬取众多的网页作为原始网页库存储于本地，然后网页分析器抽取网页中的主题内容交给分词器进行分词，得到的结果用索引器建立正排和倒排索引，这样就得到了索引[数据库][Link 3]，用户查询时，在通过分词器切割输入的查询词组并通过检索器在索引数据库中进行查询，得到的结果返回给用户。

无论搜索引擎的规模大小，其主要结构都是由这几部分构成的，并没有大的差别，搜索引擎的好坏主要是决定于各部分的内部实现。

有了上述的对与搜索引擎的整体了解，我们来学习 dySE 中爬虫模块的具体设计和实现。

[回页首][Link 4]

## Spider 的设计 ##

网页收集的过程如同图的遍历，其中网页就作为图中的节点，而网页中的超链接则作为图中的边，通过某网页的超链接 得到其他网页的地址，从而可以进一步的进行网页收集；图的遍历分为广度优先和深度优先两种方法，网页的收集过程也是如此。综上，Spider 收集网页的过程如下：从初始 URL 集合获得目标网页地址，通过网络连接接收网页数据，将获得的网页数据添加到网页库中并且分析该网页中的其他 URL 链接，放入未访问 URL 集合用于网页收集。下图表示了这个过程：

##### 图 3. Spider 工作流程 #####

![图 3. Spider 工作流程][3. Spider]

[回页首][Link 4]

## Spider 的具体实现 ##

### 网页收集器 Gather ###

网页收集器通过一个 URL 来获取该 URL 对应的网页数据，其实现主要是利用 Java 中的 URLConnection 类来打开 URL 对应页面的网络连接，然后通过 I/O 流读取其中的数据，BufferedReader 提供读取数据的缓冲区提高数据读取的效率以及其下定义的 readLine() 行读取函数。代码如下 ( 省略了异常处理部分 )：

##### 清单 1. 网页数据抓取 #####

URL url = new URL(“http://www.xxx.com”); 
    URLConnection conn = url.openConnection(); 
    BufferedReader reader = new BufferedReader(new InputStreamReader(conn.getInputStream())); 
    String line = null; 
    while((line = reader.readLine()) != null) 
        document.append(line + "\n");

使用 Java 语言的好处是不需要自己处理底层的连接操作，喜欢或者精通 Java 网络编程的读者也可以不用上述的方法，自己实现 URL 类及相关操作，这也是一种很好的锻炼。

### 网页处理 ###

收集到的单个网页，需要进行两种不同的处理，一种是放入网页库，作为后续处理的原始数据；另一种是被分析之后，抽取其中的 URL 连接，放入 URL 池等待对应网页的收集。

网页的保存需要按照一定的格式，以便以后数据的批量处理。这里介绍一种存储数据格式，该格式从北大天网的存储格式简化而来：

*  网页库由若干记录组成，每个记录包含一条网页数据信息，记录的存放为顺序添加；
 *  一条记录由数据头、数据、空行组成，顺序为：头部 + 空行 + 数据 + 空行；
 *  头部由若干属性组成，有：版本号，日期，IP 地址，数据长度，按照属性名和属性值的方式排列，中间加冒号，每个属性占用一行；
 *  数据即为网页数据。

需要说明的是，添加数据收集日期的原因，由于许多网站的内容都是动态变化的，比如一些大型门户网站的首页内容，这就意味着如果不是当天爬取的网页数据，很可能发生数据过期的问题，所以需要添加日期信息加以识别。

URL 的提取分为两步，第一步是 URL 识别，第二步再进行 URL 的整理，分两步走主要是因为有些网站的链接是采用相对路径，如果不整理会产生错误。URL 的识别主要是通过正则表达式来匹配，过程首先设定一个字符串作为匹配的字符串模式，然后在 Pattern 中编译后即可使用 Matcher 类来进行相应字符串的匹配。实现代码如下：

##### 清单 2. URL 识别 #####

public ArrayList<URL> urlDetector(String htmlDoc){
        final String patternString = "<[a|A]\\s+href=([^>]*\\s*>)";           
        Pattern pattern = Pattern.compile(patternString,Pattern.CASE_INSENSITIVE);   
        ArrayList<URL> allURLs = new ArrayList<URL>();
        Matcher matcher = pattern.matcher(htmlDoc);
        String tempURL;
        //初次匹配到的url是形如：<a href="http://bbs.life.xxx.com.cn/" target="_blank">
        //为此，需要进行下一步的处理，把真正的url抽取出来，
    	//可以对于前两个"之间的部分进行记录得到url
        while(matcher.find()){
            try {
                tempURL = matcher.group();            
                tempURL = tempURL.substring(tempURL.indexOf("\"")+1);        
                if(!tempURL.contains("\""))
                    continue;
                tempURL = tempURL.substring(0, tempURL.indexOf("\""));        
            } catch (MalformedURLException e) {
                e.printStackTrace();
            }
        }
        return allURLs;    
    }

按照“`<[a|A]\\s+href=([^>]*\\s*>)`”这个正则表达式可以匹配出 URL 所在的整个标签，形如“`<a href="http://bbs.life.xxx.com.cn/" target="_blank">`”，所以在循环获得整个标签之后，需要进一步提取出真正的 URL，我们可以通过截取标签中前两个引号中间的内容来获得这段内容。如此之后，我们可以得到一个初步的属于该网页的 URL 集合。

接下来我们进行第二步操作，URL 的整理，即对之前获得的整个页面中 URL 集合进行筛选和整合。整合主要是针对网页地址是相对链接的部分，由于我们可以很容易的获得当前网页的 URL，所以，相对链接只需要在当前网页的 URL 上添加相对链接的字段即可组成完整的 URL，从而完成整合。另一方面，在页面中包含的全面 URL 中，有一些网页比如广告网页是我们不想爬取的，或者不重要的，这里我们主要针对于页面中的广告进行一个简单处理。一般网站的广告连接都有相应的显示表达，比如连接中含有“ad”等表达时，可以将该链接的优先级降低，这样就可以一定程度的避免广告链接的爬取。

经过这两步操作时候，可以把该网页的收集到的 URL 放入 URL 池中，接下来我们处理爬虫的 URL 的派分问题。

### Dispatcher 分配器 ###

分配器管理 URL，负责保存着 URL 池并且在 Gather 取得某一个网页之后派分新的 URL，还要避免网页的重复收集。分配器采用设计模式中的单例模式编码，负责提供给 Gather 新的 URL，因为涉及到之后的多线程改写，所以单例模式显得尤为重要。

重复收集是指物理上存在的一个网页，在没有更新的前提下，被 Gather 重复访问，造成资源的浪费，主要原因是没有清楚的记录已经访问的 URL 而无法辨别。所以，Dispatcher 维护两个列表 ,“已访问表”，和“未访问表”。每个 URL 对应的页面被抓取之后，该 URL 放入已访问表中，而从该页面提取出来的 URL 则放入未访问表中；当 Gather 向 Dispatcher 请求 URL 的时候，先验证该 URL 是否在已访问表中，然后再给 Gather 进行作业。

### Spider 启动多个 Gather 线程 ###

现在 Internet 中的网页数量数以亿计，而单独的一个 Gather 来进行网页收集显然效率不足，所以我们需要利用多线程的方法来提高效率。Gather 的功能是收集网页，我们可以通过 Spider 类来开启多个 Gather 线程，从而达到多线程的目的。代码如下：

/** 
    * 启动线程 gather，然后开始收集网页资料
    */ 
    public void start() { 
        Dispatcher disp = Dispatcher.getInstance(); 
        for(int i = 0; i < gatherNum; i++){ 
            Thread gather = new Thread(new Gather(disp)); 
            gather.start(); 
        }
    }

在开启线程之后，网页收集器开始作业的运作，并在一个作业完成之后，向 Dispatcher 申请下一个作业，因为有了多线程的 Gather，为了避免线程不安全，需要对 Dispatcher 进行互斥访问，在其函数之中添加 synchronized 关键词，从而达到线程的安全访问。

# 网页预处理 #

## 预处理模块的整体结构 ##

预处理模块的整体结构如下：

##### 图 1. 预处理模块的整体结构 #####

![图 1. 预处理模块的整体结构][1. 1]

通过 spider 的收集，保存下来的网页信息具有较好的信息存储格式，但是还是有一个缺点，就是不能按照网页 URL 直接定位到所指向的网页。所以，在第一个流程中，需要先建立网页的索引，如此通过索引，我们可以很方便的从原始网页库中获得某个 URL 对应的页面信息。之后，我们处理网页数据，对于一个网页，首先需要提取其网页正文信息，其次对正文信息进行分词，之后再根据分词的情况建立索引和倒排索引，这样，网页的预处理也全部完成。可能读者对于其中的某些专业术语会有一些不明白之处，在后续详述各个流程的时候会给出相应的图或者例子来帮助大家理解。

--------------------

[回页首][Link 5]

## 建立索引网页库 ##

原始网页库是按照格式存储的，这对于网页的索引建立提供了方便，下图给出了一条网页信息记录：

##### 清单 1. 原始网页库中的一条网页记录 #####

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 
     xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx     // 之前的记录
    
     version:1.0                           // 记录头部
     url:http://ast.nlsde.buaa.edu.cn/ 
     date:Mon Apr 05 14:22:53 CST 2010 
     IP:218.241.236.72 
     length:3981 
    
     <!DOCTYPE ……                     // 记录数据部分
     <html> …… </html> 
    
     xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx     // 之后的记录
     xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

我们采用“网页库名—偏移”的信息对来定位库中的某条网页记录。由于数据量比较大，这些索引网页信息需要一种保存的方法，dySE 使用数据库来保存这些信息。数据库们采用[MySQL][Link 3]，配合 SQL-Front 软件可以轻松进行图形界面的操作。我们用一个表来记录这些信息，表的内容如下：url、content、offset、raws。URL 是某条记录对应的 URL，因为索引数据库建立之后，我们是通过 URL 来确定需要的网页的；raws 和 offset 分别表示网页库名和偏移值，这两个属性唯一确定了某条记录，content 是网页内容的摘要，网页的数据量一般较大，把网页的全部内容放入数据库中显得不是很实际，所以我们将网页内容的 MD5 摘要放入到 content 属性中，该属性相当于一个校验码，在实际运用中，当我们根据 URL 获得某个网页信息是，可以将获得的网页做 MD5 摘要然后与 content 中的值做一个匹配，如果一样则网页获取成功，如果不一样，则说明网页获取出现问题。

这里简单介绍一下 [ mysql][Link 3] 的安装以及与 Java 的连接：

*  安装 mySql，最好需要三个组件，mySql，mySql-front，mysql-connector-java-5.1.7-bin.jar，分别可以在网络中下载。注意：安装 mySql 与 mySql-front 的时候要版本对应，MySql5.0 + MySql-Front3.2 和 MySql5.1 + MySql-Front4.1，这个组合是不能乱的，可以根据相应的版本号来下载，否则会爆“‘ 10.000000 ’ ist kein gUltiger Integerwert ”的错误。
 *  导入 mysql-connector-java-5.1.7-bin.jar 到 eclipse 的项目中，打开 eclipse，右键点需要导入 jar 包的项 目名，选属性（properties)，再选 java 构建路径（java Build Path)，后在右侧点 (libraries)，选 add external JARs，之后选择你要导入的 jar 包确定。
 *  接着就可以用代码来测试与 mySql 的连接了，代码见本文附带的 testMySql.java 程序，这里限于篇幅就不在赘述。
 *  对于数据库的操作，我们最好进行一定的封装，以提供统一的数据库操作支持，而不需要在其他的类中显示的进行数据库连接操作，而且这样也就不需要建立大量的数据库连接从而造成资源的浪费，代码详见 DBConnection.java。主要提供的操作是：建立连接、执行 SQL 语句、返回操作结果。

介绍了数据库的相关操作时候，现在我们可以来完成网页索引库的建立过程。这里要说明的是，第一条记录的偏移是 0，所以在当前记录 record 处理之前，该记录的偏移是已经计算出来的，处理 record 的意义在于获得下一个记录在网页库中的偏移。假设当前 record 的偏移为 offset，定位于头部的第一条属性之前，我们通过读取记录的头部和记录的数据部分来得到该记录的长度 length，从而，offset+length 即为下一条记录的偏移值。读取头部和读取记录都是通过数据间的空行来标识的，其伪代码如下：

##### 清单 2. 索引网页库建立 #####

For each record in Raws do 
    begin 
        读取 record 的头部和数据，从头部中抽取 URL；
        计算头部和数据的长度，加到当前偏移值上得到新的偏移；
        从 record 中数据中计算其 MD5 摘要值；
        将数据插入数据库中，包括：URL、偏移、数据 MD5 摘要、Raws；
    end；

您可能会对 MD5 摘要[算法][Link 6]有些疑惑，这是什么？这有什么用？ Message Digest Algorithm MD5（中文名为消息摘要算法第五版）为计算机安全领域广泛使用的一种散列函数，用以提供消息的完整性保护。MD5 的典型应用是对一段信息 (Message) 产生一个 128 位的二进制信息摘要 (Message-Digest)，即为 32 位 16 进制数字串，以防止被篡改。对于我们来说，比如通过 MD5 计算，某个网页数据的摘要是 00902914CFE6CD1A959C31C076F49EA8，如果我们任意的改变这个网页中的数据，通过计算之后，该摘要就会改变，我们可以将信息的 MD5 摘要视作为该信息的指纹信息。所以，存储该摘要可以验证之后获取的网页信息是否与原始网页一致。

对 MD5 算法简要的叙述可以为：MD5 以 512 位分组来处理输入的信息，且每一分组又被划分为 16 个 32 位子分组，经过了一系列的处理后，算法的输出由四个 32 位分组组成，将这四个 32 位分组级联后将生成一个 128 位散列值。其中“一系列的处理”即为计算流程，MD5 的计算流程比较多，但是不难，同时也不难实现，您可以直接使用网上现有的 java 版本实现或者使用本教程提供的源码下载中的 MD5 类。对于 MD5，我们知道其功能，能使用就可以，具体的每个步骤的意义不需要深入理解。

--------------------

[回页首][Link 5]

## 正文信息抽取 ##

### PageGetter ###

在正文信息抽取之前，我们首先需要一个简单的工具类，该工具类可以取出数据库中的内容并且去原始网页集中获得网页信息，dySE 对于该功能的实现在 originalPageGetter.java 中，该类通过 URL 从数据库中获得该 URL 对应的网页数据的所在网页库名以及偏移，然后就可以根据偏移来读取该网页的数据内容，同样以原始网页集中各记录间的空行作为数据内容的结束标记，读取内容之后，通过 MD5 计算当前读取的内容的摘要，校验是否与之前的摘要一致。对于偏移的使用，BufferedReader 类提供一个 skip(int offset) 的函数，其作用是跳过文档中，从当前开始计算的 offset 个字符，用这个函数我们就可以定位到我们需要的记录。

##### 清单 3. 获取原始网页库中内容 #####

public String getContent(String fileName, int offset) 
     { 
         String content = ""; 
         try { 
             FileReader fileReader = new FileReader(fileName); 
             BufferedReader bfReader = new BufferedReader(fileReader); 
             bfReader.skip(offset); 
             readRawHead(bfReader); 
             content = readRawContent(bfReader);         
         } catch (Exception e) {e.printStackTrace();} 
         return content;     
     }

上述代码中，省略了 readRawHead 和 readRawContent 的实现，这些都是基本的 I/O 操作，详见所附源码。

### 正文抽取 ###

对于获得的单个网页数据，我们就可以进行下一步的处理，首先要做的就是正文内容的抽取，从而剔除网页中的标签内容，这一步的操作主要采用正则表达式来完成。我们用正则表达式来匹配 html 的标签，并且把匹配到的标签删除，最后，剩下的内容就是网页正文。限于篇幅，我们以过滤 script 标签为示例，其代码如下 :

##### 清单 4. 标签过滤 #####

public String html2Text(String inputString) {        
         String htmlStr = inputString; // 含 html 标签的字符串    
         Pattern p_script;    Matcher m_script;      
         try { 
                String regEx_script = "<script[^>]*?>[\\s\\S]*?</script>";
                p_script = Pattern.compile(regEx_script,Pattern.CASE_INSENSITIVE);    
                m_script = p_script.matcher(htmlStr);    
                htmlStr = m_script.replaceAll(""); // 过滤 script 标签    
         }catch(Exception e) {e.printStackTrace();} 
         return htmlStr;// 返回文本字符串    
     }

通过一系列的标签过滤，我们可以得到网页的正文内容，就可以用于下一步的分词了。

--------------------

[回页首][Link 5]

## 分词 ##

中文分词是指将一个汉字序列切分成一个一个单独的词，从而达到计算机可以自动识别的效果。中文分词主要有三种方法：第一种基于字符串匹配，第二种基于语义理解，第三种基于统计。由于第二和第三种的实现需要大量的数据来支持，所以我们采用的是基于字符串匹配的方法。

基于字符串匹配的方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配。常用的几种机械分词方法如下：

1.  正向减字最大匹配法（由左到右的方向）；
2.  逆向减字最大匹配法（由右到左的方向）；
3.  最少切分（使每一句中切出的词数最小）；
4.  双向最大减字匹配法（进行由左到右、由右到左两次扫描）；

我们采用其中的正向最大匹配法。算法描述如下：输入值为一个中文语句 S，以及最大匹配词 n

1.  取 S 中前 n 个字，根据词典对其进行匹配，若匹配成功，转 3，否则转 2；
2.  n = n – 1：如果 n 为 1，转 3；否则转 1；
3.  将 S 中的前 n 个字作为分词结果的一部分，S 除去前 n 个字，若 S 为空，转 4；否则，转 1；
4.  算法结束。

需要说明的是，在第三步的起始，n 如果不为 1，则意味着有匹配到的词；而如果 n 为 1，我们默认 1 个字是应该进入分词结果的，所以第三步可以将前 n 个字作为一个词而分割开来。还有需要注意的是对于停用词的过滤，停用词即汉语中“的，了，和，么”等字词，在搜索引擎中是忽略的，所以对于分词后的结果，我们需要在用停用词列表进行一下停用词过滤。

您也许有疑问，如何获得分词字典或者是停用词字典。停用词字典比较好办，由于中文停用词数量有限，可以从网上获得停用词列表，从而自己建一个停用词字典；然而对于分词字典，虽然网上有许多知名的汉字分词软件，但是很少有分词的字典提供，这里我们提供一些在 dySE 中使用的分词字典给您。在程序使用过程中，分词字典可以放入一个集合中，这样就可以比较方便的进行比对工作。

分词的结果对于搜索的精准性有着至关重要的影响，好的分词策略经常是由若干个简单算法拼接而成的，所以您也可以试着实现双向最大减字匹配法来提高分词的准确率。而如果遇到歧义词组，可以通过字典中附带的词频来决定哪种分词的结果更好。

--------------------

[回页首][Link 5]

## 倒排索引 ##

这个章节我们为您讲解预处理模块的最后两个步骤，索引的建立和倒排索引的建立。有了分词的结果，我们就可以获得一个正向的索引，即某个网页以及其对应的分词结果。如下图所示：

##### 图 2. 正向索引 #####

![图 2. 正向索引][1. 1]

##### 图 3. 倒排索引 #####

![图 3. 倒排索引][1. 1]

在本文的开头，我们建立了索引网页库，用于通过 URL 可以直接定位到原始网页库中该 URL 对应的数据的位置；而现在的正向索引，我们可以通过某个网页的 URL 得到该网页的分词信息。获得正向索引看似对于我们的即将进行的查询操作没有什么实际的帮助，因为查询服务是通过关键词来获得网页信息，而正向索引并不能通过分词结果反查网页信息。其实，我们建立正向索引的目的就是通过翻转的操作建立倒排索引。所谓倒排就是相对于正向索引中网页——分词结果的映射方式，采用分词——对应的网页这种映射方式。与图 2 相对应的倒排索引如上图 3 所示。

接下来我们分析如何从正向索引来得到倒排索引。算法过程如下：

1.  对于网页 i，获取其分词列表 List；
2.  对于 List 中的每个词组，查看倒排索引中是否含有这个词组，如果没有，将这个词组插入倒排索引的索引项，并将网页 i 加到其索引值中；如果倒排索引中已经含有这个词组，直接将网页 i 加到其索引值中；
3.  如果还有网页尚未分析，转 1；否则，结束

建立倒排索引的算法不难实现，主要是其中[数据结构][Link 6]的选用，在 dySE 中，正向索引和倒排索引都是采用 HashMap 来存储，映射中正向索引的键是采用网页 URL 对应的字符串，而倒排索引是采用分词词组，映射中的值，前者是一个分词列表，后者是一个 URL 的字符串列表。这里可以采用一个优化，分别建立两个表，按照标号存储分词列表和 URL 列表，这样，索引中的值就可以使用整型变量列表来节省空间。

# 查询服务 #

## 查询服务的整体结构 ##

查询服务的整体结构如下：

##### 图 1. 查询服务整体结构 #####

![图 1. 查询服务整体结构][1. 1]

在前面两部分的叙述中，我们有了放在文件中的原始网页库、放在数据库中的网页索引 ( 指示某个网页所在原始网页库的位置 )、倒排索引，以及一些小工具：分词器。在这些部件的基础上，我们开始搭建我们搜索引擎的界面并且实现信息的输入和输出。

以下的章节安排如下：首先我们完善后台服务，使得程序能够在控制台输入查询的情况下，在控制台中返回需要的结果信息，这些结果将在后续的部分中返回给网页进行显示；其次，我们搭建 Web 服务器，进行网页编程，使得查询服务与后台服务程序能够交互；最后我们介绍网页结果返回时的一些优化，比如网页排名的实现。

--------------------

[回页首][Link 7]

## 简单查询 ##

在第二部分预处理之后，我们现有的待用数据如下：原始网页库，网页索引，倒排索引，分词器。为了方便您对于后文的理解，我们再次说明这些资源的用途：原始网页库记录了爬虫获取的各个网页信息，按照一定的格式保留在本地；然而这些网页信息不便于随机的进行访问，所以我们通过网页索引记录某个网页在原始网页库中的位置，以方便查询；倒排索引是一个关键字和包含这个关键字的网页 URL 集合的映射，通过倒排索引可以方便的得到哪些网页包含确定的关键词；分词器的作用在于可以对用户输入的文字进行分词，因为用户可能会输入多个词组所以分词器在查询服务中也起着必不可少的作用。

简单的查询服务过程如下：对于用户的输入，首先进行分词，对于每个词组，搜索倒排索引获取包含该词组的网页 URL 信息， 找到各个分词对应的 URL 集合中共同的 URL，根据结果 URL 集合查询网页索引获得 URL 对应的网页信息，整合网页信息之后进行返回。

### 结果集合的生成 ###

在上述的过程中，分词和倒排索引的具体结构已经在第二部分预处理模块中提及，这里就不再赘述。分词结果集 (keywords) 在倒排索引中搜索结果的算法如下：

##### 清单 1. 结果检索算法 #####

结果集合，URLs 初始化为空
     For each keyword in keywords do 
     begin 
    获取 keyword 对应的倒排索引中的数据项：urls；
    合并 URLs 与 urls，保留两者的共同 url，如果 URLs 为空，则将 urls 赋值给 URLs；
     end；
     if(URLs 为空 ) return null；
     else return URLs；

由于可能会产生信息查询不到的情况，所以算法中追加了检索结果为空的判断，保证程序的健壮性。合并结果集合 URLs 和 keyword 对应的网页集合 urls 中相同的元素有许多种方法，简单的可以采用建立一个临时的集合，存储两者的公共 url，等到该次执行结束，将该临时集合中的值赋值给 URLs 即可。

如此我们得到了作为简单结果的 URL 集合，下一步我们要通过这个集合生成详细结果并且进行返回。我们可以使用其他的搜索引擎比如 google、百度等来了解一个网页结果具体需要包含哪些信息，下图是在 google 中搜索“中国教育”关键字的返回结果：

##### ![Figure xxx. Requires a heading][1. 1]  从图中可以看出，在第一行显示的是该网页的标题，并且是一个超级链接，第二行是正文内容的一个摘要，该摘要最好能够包含搜索的关键词，从而用户可以判断该网页与用户查询的相关度。最后一行显示的是该网页的 URL 以及网页快照的一个功能。快照功能是指收录的网页的纯文本备份，在网速很慢或者原始网页无法打开的情况下，可以使用快照功能查看该网页的文本内容，快照功能的实现我们将在本文的末尾提及。下面我们主要完成标题的提取、正文摘要的提取两个部分。  在第二部分中，我们介绍了如何通过原始网页库的文件名和文件内偏移进行某个 URL 对应的页面数据查询，所以这部分我们只是再简单的提及，通过数据库的查询，我们可以得到某个 URL 所对应的文件的所在位置，通过 BufferedReader 类中提供的 skip 函数可以完成偏移量的跳转从而直接开始读取所需要的页面信息。标题的获取比较直观，由于 html 中 <title></title> 标签对中的内容即对应该网页的标题，所以提取该标签即可，对于页面数据，我们可以用正则表达式来比配这个标签对，该匹配的正则表达式如下：title\[^>\]\*?>\[\\\\s\\\\S\]\*?</title>。正则表达式具体的匹配过程在第二部分中有示例，这里不再赘述。  正文摘要的生成主要有两种方法，一种是在 html 标签中提取 description 信息，网页的摘要信息会放在形如：<META content="关注搜索引擎…" name=description> 的标签中，仍旧通过正则表达式，我们可以匹配得到网页的摘要信息，这种方法比较常用，同时也很方便。第二种方法在网页正文的基础上生成，由于某些网页中可能不包含 description 标签，这样就需要在正文中抽取网页摘要，这种方法也是第一种方法的一个备用方法。网页正文可以通过去掉网页的 html 标签来获得。正文摘要的目标是使摘要能尽量多的在一段内容中显示更多与查询关键字相关的信息，为此，我们可以采用如下策略来进行摘要的生成：  首先，用户查询的关键字在摘要中最好能处于相邻位置。由于 URL 结果是在分词的基础上搜索生成的，所以 URL 对应页面包含的关键字可能也是分散的，例如，我们搜索“搜索引擎”关键字，如果一个页面上有如下两段文字：(1) 本文介绍搜索引擎的具体实现步骤…；(2) 警察通过搜索发现，汽车的引擎不翼而飞…。很显然，文本 (1) 更加适合做该关键字的摘要。  在提取的限定长度的摘要中，关键词的出现频率应该要比较高；  如果第一点不能达到，那么在摘要中，关键词之间的间隔应该要尽可能的小。  根据这些策略，我们就可以提取摘要的文字信息。  除了上述的两项信息，百度在搜索结果中还有网页的日期这一项，我们可以参照这点在结果中显示日期信息。由于我们在将网页格式化存储时包含了摘录该网页的时间，我们可以直接获取该日期显示在结果中。  为了更好的封装返回的结果，我们创建 Result 类来存储单个网页的返回信息，这其中主要包括了标题 (title)、正文动态摘要、日期、URL 四种数据。而查询的最终结果是返回一个 Result 的 List。  由于这些数据都是字符串类型，所以可以很容易的在控制台上进行显示并进行[测试][Link 8]，我们可以在控制台下测试如下： #####

##### 清单 2. 控制台下检索结果检测 #####

public static void main(String[] args) { 
     Scanner cin=new Scanner(System.in); 
     String keyword = cin.next();  //read the keyword from console 
     Response response = new Response(); 
     ArrayList<Result> results = response.getResponse(keyword); 
     System.out.println("返回结果如下："); 
     for(Result result : results){ 
     System.out.println(result.getTitle()); 
     System.out.println(result.getContent()); 
     System.out.println(result.getUrl() + "  " + result.getDate()); 
     } 
     }

在控制台输入“中国教育”返回的结果大致如下：

##### 图 2. 查询“中国教育”返回的结果 #####

![图 2. 查询“中国教育”返回的结果][1. 1]

--------------------

[回页首][Link 7]

## 搭建 Web 服务器提供查询服务 ##

一般的搜索引擎都是通过 Web 程序提供应用接口，从而提供服务，在本节我们介绍 Web 服务器的搭建提供查询服务。我们按照 Web 服务器的搭建、与后台查询模块的连接两个部分来进行叙述。

### Web 服务器搭建 ###

由于我们的后台 ( 即之前所述的倒排索引建立查询和结果返回等部分 ) 是用 Java 编写，所以很自然的，我们想到用 JSP([Java][]Server Page) 来提供查询服务，在这小节中，我们重点介绍如何搭建服务器提供 JSP 服务。

我们使用 Tomcat 作为 Web 应用服务器，Tomcat 是一个小型的开源轻量级应用服务器，是开发和调试 JSP 程序的很好选择。我们先来介绍 Tomcat 服务器的搭建过程：

*  下载 Tomcat6.0，参考地址：http://tomcat.apache.org/；
 *  Tomcat 是免安装的，所以解压到本地进行环境变量的配置即可使用；
 *  双击在 tomcat 的 bin 目录下的 startup.bat 文件，启动 tomcat 服务器；

### Web 页面编写 ###

有了服务器的支持，我们即可进行 Web 页面的编写，以提供查询服务的入口和结果返回页面。查看大部分搜索引擎的界面，无论是主界面还是搜索结果显示界面，其显示的内容都较为简单，所以 JSP 的页面开发环境您可以根据您的习惯和喜好自由选择，本文主要在 MyEclipse 中进行页面编写。

##### 清单 3. 查询服务入口 index.jsp #####

<%@ page language="java" import="java.util.*" pageEncoding="gb2312"%> 
     <% 
     String path = request.getContextPath(); 
     String basePath = request.getScheme()+"://"
     +request.getServerName()+":"
     +request.getServerPort()+path+"/"; 
     %> 
     <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> 
     <html> 
      <head> 
        <base href="<%=basePath%>"> 
            <title>dySE</title> 
              <style> 
     #search{ 
     width:78px; 
     height:28px; 
     font:14px "宋体"
     } 
     #textArea{ 
     width:300px; 
     height:30px; 
     font:14px "宋体"
     } 
     </style> 
      </head> 
      
      <body> 
     <p align="center"><img src="dySE-logo.jpg" /></p> 
     <form action="search.jsp" name="search" method="get" 
     enctype="application/x-www-form-urlencoded"> 
     <table border="0" height="30px" width="450px" align="center"> 
     <tr> 
     <td width ="66%"><input name="keyword" type="text" maxlength="100" 
     id="textArea"></td> 
     <td height="29" align="center"><input type="submit" value="搜索一下" 
     id = "search"></td> 
     </tr> 
     </table> 
     </form> 
      </body> 
     </html>

我们在 MyEclipse 中新建一个 WEB PROJECT，并新建一个 JSP 页面，命名为 index.jsp，MyEclipse 会自动生成基本的页面代码，我们编写的代码主要是两个部分，一部分是 <style></style> 标签对中的 CSS 样式，这部分指定了页面中关键字输入文本框和按钮的样式，这里就此略过。另一部分是 <body></body> 标签对中的代码，第一行居中显示 dySE 的 logo 图标，然后空行，之后就是一个表单，其中包括了一个含有文本输入框和按钮的表格—— <table> </table> 标签对中，在 form 标签中，设定了按下按钮的动作——转到 search.jsp 页面，其中的 enctype="application/x-www-form-urlencoded"指定了编码格式，如果没有指定，在搜索中文的时候会导致乱码。该代码显示结果如下：

##### 图 3. 搜索界面 #####

![图 3. 搜索界面][1. 1]

接下来我们编写搜索结果显示页面。

##### 清单 4. 查询结果显示 search.jsp #####

<%@ page language="java" import="java.util.*" pageEncoding="gb2312"%> 
     <jsp:directive.page import="core.query.Response" /> 
     <jsp:directive.page import="core.util.Result" /> 
    
     <% 
     String path = request.getContextPath(); 
     String basePath = request.getScheme()+"://"+request.getServerName()+":
     "+request.getServerPort()+path+"/"; 
     %> 
    
     <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> 
     <html> 
      <head> 
        <base href="<%=basePath%>"> 
        <title>Search Result</title> 
        <style> 
     #search{ 
     width:78px; 
     height:28px; 
     font:14px "宋体"
     } 
     #textArea{ 
     width:300px; 
     height:30px; 
     font:14px "宋体"
     } 
     </style> 
      </head> 
      
      <body> 
        <form action="search.jsp" name="search" method="get"> 
     <table border="0" height="30px" width="450px" align="center"> 
     <tr> 
     <td><img src="dySE-logo.jpg" /></td> 
     <td width ="66%"><input name="keyword" type="text" maxlength="100" id="textArea" ></td> 
     <td height="29" align="center"><input type="submit" value="搜索一下" id = "search"></td> 
     </tr> 
     </table> 
          </form> 
     <%  
     String keyword = new String(request.getParameter("keyword") .getBytes("
     ISO-8859-1"),"GB2312"); 
     Response resp = new Response(); 
     ArrayList<Result> results = resp.getResponse(keyword); 
     for(Result result : results) 
     { 
     %> 
     <h2><a href=<%=result.getUrl()%>><%=result.getTitle()%></a></h2> 
     <p><%=result.getContent()%><p> 
     <p><%=result.getUrl()%>     <%=result.getDate()%><p> 
     <%  
     } 
     %>  
     </body> 
     </html>

Search.jsp 在开头引入了 response 和 result 两个类，其后的代码与 index.jsp 有很大部分的相似之处，这里不再赘述，主要说明一下 <form></form> 标签对之后查询服务的调用以及返回的结果的显示方式。第一行先获取了用户在文本框内输入的查询关键字，为了防止编码问题，我们在获取结果时候加入编码格式。之后通过我们建立的 Response 类来进行结果的获得，通过传入搜索的关键字，Response 类在 getResponse 操作中对倒排索引进行查询，将查询的结果放入到结果列表中（算法可参见简单查询部分），操作返回的结果是一个 Result 类型的 List，遍历这个 List 并且按照一定的格式显示这些数据即可得到所需要的输出，输出的内容将按照一定的 html 格式进行设置。第一行建立一个超链接，链接的显示文字是 Result 类型中页面的 title 属性，链接的地址是对应的 url。第二行将页面的内容简介进行显示，并在第三行显示页面对应的 url 和页面的抓取日期。

##### 图 4. 搜索结果返回 #####

![图 4. 搜索结果返回][1. 1]

由于我们在试验过程中，主要爬取的是几大门户网站的网页，所以搜索“中国教育”并不会出来中国教育网之类的网站，但是，我们的结果返回了新浪和网易的教育频道，可见我们的搜索引擎是可以正确运行的。

--------------------

[回页首][Link 7]

## 网页排名 ##

到目前为止，我们的网页已经可以正确的返回所输入和查询的结果，但是还有一个问题需要我们考虑，那就是网页排名策略。网页排名简单来说就是搜索引擎对搜索某个关键字产生的结果网页集合的返回顺序，由于对于用户来说，用户感兴趣的网页最好能够排在前面来显示，从而减少用户筛选结果的开销。网页排名策略即是考评结果网页集合排列顺序的算法策略，最基本的策略要求就是使得与用户输入最相关的网页排在之前，那么如何确定网页内容与用户输入关键词的相关程度呢？

我们还是以搜索“中国教育”为例解释网页排名策略。我们知道，“中国教育”可以分为两个关键词：中国、教育。根据经验，我们知道，包含这两个词多的网页要比包含这两个词少的网页相关，所以我们可以统计网页中，包含的关键词的总数，从而简单的确定网页的相关性。但是，这样的方法有个问题，那就是长的网页比短的网页跟占优势，所以我们需要根据网页的长度，对关键词的次数进行归一化，也就是用关键词的次数除以网页的总字数，这个商叫做“关键词词频”(Term Frequency)，比如，某个 1000 词的网页中，中国出现了 10 词，教育出现了 3 次，那么两者的词频分别为 0.01 和 0.003，则其和 0.013 就是该网页与“中国教育”的相关度的一个简单度量。相关性的一个简单的度量。概括地讲，如果一个查询包含关键词 w1,w2,...,wn，它们在一个特定网页中的词频分别是 :TF1,TF2,...,TFn (TF: Term Frequency)。那么，这个查询和该网页的相关性就是：TF1+TF2+...+TFn。

进一步我们可以发现，“中国”这个词很普通，而“教育”是一个较为专业的词，所以后者在相关性排名中应该比前者重要，因此我们引入关键词的权重，以区分各个关键词之间的重要性。该权重应该具有如下特性：首先一个词预测主题能力越强，权重越大，反之则权重越小；其次，停用词的权重为 0。那么，这个权重如何确定呢？在信息检索中，使用最多的权重计算方法是“逆文本频率指数”(Inverse Document Frequency：IDF)。其公式为 log(D/DW), 其中，D 是全部网页数，而 DW 是关键词 W 在 DW 个网页中出现过。假设全部网页 D=10 亿，“教育”在 2 百万个网页中出现，则其权重 IDF=log(500)=6.2，同理若“中国”在 5 亿个网页中出现，则其权重为 IDF=log(2)=0.7。所以，我们网页相关性的计算公式也转变为：

TF1\*IDF1+TF2\*IDF2+...+TFn\*IDFn。

第三，既然搜索“中国教育”，那我们希望网页中“中国”和“教育”这两个词的出现位置是更多的是处于相邻位置，诸如“浅谈中国教育”的网页内容应该比“中国工人先进性教育”更符合我们的搜索目标。关于位置信息需要在倒排索引建立的过程中进行抽取，由于在第二部分的倒排索引中，为了方便理解，我们只是建立了最简单的倒排索引，而没有加入位置信息，所以这部分的策略我们将在后续的优化部分进行说明。

## 总结 ##

到现在为止，我们已经完成了 dySE 搜索引擎的实现过程讲解，我们按照搜索引擎中处理的三个模块进行分块介绍，从第一部分的网络爬虫获取原始网页库，到第二部分的预处理建立索引网页库、分词以及建立倒排索引，到此文中搭建 Web 服务器提供网络查询服务并且进行网页的排名。这其中爬虫是搜索引擎的基础，提供了原始数据集，而预处理是核心，提供后台的查询服务并且返回给前台 Web，而第三部分是与用户交互的接口，提供查询结果的输入和输出。三者互相依赖，互相配合完成搜索引擎的工作。

然而，目前我们还只是对各个模块进行了简单的实现和连接，一些优化方案和具体实现过程将在后续的优化章节中进行介绍。

以上就是我们为您呈现的搜索引擎的实现过程，项目的全部源代码您可以在 Google Code 中获得，网址是 : [https://github.com/thewarlocker/dynastySE/][https_github.com_thewarlocker_dynastySE]，欢迎您的评价并提出不足，衷心希望能对您有所启发和帮助，感谢您的阅读

本文作者：

[董 宇][Link 9]

[Java]: http://lib.csdn.net/base/java
[Link 1]: http://lib.csdn.net/base/searchengine
[1.]: /images/20220610/ee18befcf2bb4db5b7addfaac0072fcd.png
[Link 2]: http://lib.csdn.net/base/computernetworks
[2.]: /images/20220610/d4410f41aa074ebf921bec1c9f33edec.png
[Link 3]: http://lib.csdn.net/base/mysql
[Link 4]: http://www.ibm.com/developerworks/cn/java/j-lo-dyse1/index.html#ibm-pcon
[3. Spider]: /images/20220610/75fbce20e6e241aa801967855340336e.png
[1. 1]: 
[Link 5]: http://www.ibm.com/developerworks/cn/java/j-lo-dyse2/index.html#ibm-pcon
[Link 6]: http://lib.csdn.net/base/datastructure
[Link 7]: http://www.ibm.com/developerworks/cn/java/j-lo-dyse3/index.html#ibm-pcon
[Link 8]: http://lib.csdn.net/base/softwaretest
[https_github.com_thewarlocker_dynastySE]: http://code.google.com/p/dynasty-search-engine/
[Link 9]: http://www.ibm.com/developerworks/cn/java/j-lo-dyse2/index.html#authorN10022