原文地址：http://www.cppblog.com/zzfmars/archive/2011/04/16/144356.html和http://www.cppblog.com/zzfmars/archive/2011/04/16/144357.html

第一部分：网络爬虫

自己动手写一个搜索引擎，想想这有多 cool：在界面上输入关键词，点击搜索，得到自己想要的结果；那么它还可以做什么呢？也许是自己的网站需要一个站内搜索功能，抑或是对于硬盘中文档的搜索 —— 最重要的是，是不是觉得众多 IT 公司都在向你招手呢？如果你心动了，那么，Let's Go！
这里首先要说明使用 Java 语言而不是 C/C++ 等其它语言的原因，因为 Java 中提供了对于网络编程众多的基础包和类，比如 URL 类、InetAddress 类、正则表达式，这为我们的搜索引擎实现提供了良好的基础，使我们可以专注于搜索引擎本身的实现，而不需要因为这些基础类的实现而分心。
这个分三部分的系列将逐步说明如何设计和实现一个搜索引擎。在第一部分中，您将首先学习搜索引擎的工作原理，同时了解其体系结构，之后将讲解如何实现搜索引擎的第一部分，网络爬虫模块，即完成网页搜集功能。在系列的第二部分中，将介绍预处理模块，即如何处理收集来的网页，整理、分词以及索引的建立都在这部分之中。在系列的第三部分中，将介绍信息查询服务的实现，主要是查询界面的建立、查询结果的返回以及快照的实现。
dySE 的整体结构
在开始学习搜索引擎的模块实现之前，您需要了解 dySE 的整体结构以及数据传输的流程。事实上，搜索引擎的三个部分是相互独立的，三个部分分别工作，主要的关系体现在前一部分得到的数据结果为后一部分提供原始数据。三者的关系如下图所示：

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

图 2. 搜索引擎整体结构
 
爬虫从 Internet 中爬取众多的网页作为原始网页库存储于本地，然后网页分析器抽取网页中的主题内容交给分词器进行分词，得到的结果用索引器建立正排和倒排索引，这样就得到了索引数据库，用户查询时，在通过分词器切割输入的查询词组并通过检索器在索引数据库中进行查询，得到的结果返回给用户。
无论搜索引擎的规模大小，其主要结构都是由这几部分构成的，并没有大的差别，搜索引擎的好坏主要是决定于各部分的内部实现。
有了上述的对与搜索引擎的整体了解，我们来学习 dySE 中爬虫模块的具体设计和实现。
回页首
Spider 的设计
网页收集的过程如同图的遍历，其中网页就作为图中的节点，而网页中的超链接则作为图中的边，通过某网页的超链接 得到其他网页的地址，从而可以进一步的进行网页收集；图的遍历分为广度优先和深度优先两种方法，网页的收集过程也是如此。综上，Spider 收集网页的过程如下：从初始 URL 集合获得目标网页地址，通过网络连接接收网页数据，将获得的网页数据添加到网页库中并且分析该网页中的其他 URL 链接，放入未访问 URL 集合用于网页收集。下图表示了这个过程：

图 3. Spider 工作流程
 
回页首
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 关键词，从而达到线程的安全访问。
回页首
小结
Spider 是整个搜索引擎的基础，为后续的操作提供原始网页资料，所以了解 Spider 的编写以及网页库的组成结构为后续预处理模块打下基础。同时 Spider 稍加修改之后也可以单独用于某类具体信息的搜集，比如某个网站的图片爬取等。
回页首
后续内容
在本系列的第 2 部分中，您将了解到爬虫获取的网页库如何被预处理模块逐步提取内容信息，通过分词并建成倒排索引；而在第 3 部分中，您将了解到，如何编写网页来提供查询服务，并且如何显示的返回的结果和完成快照的功能。

第二部分：网页预处理

在 上一部分 中，您了解到如何编写一个 spider 程序来进行网页的爬取，作为 spider 的爬取结果，我们获得了一个按照一定格式存储的原始网页库，原始网页库也是我们第二部分网页预处理的数据基础。网页预处理的主要目标是将原始网页通过一步步的数据处理变成可方便搜索的数据形式。下面就让我们逐步介绍网页预处理的设计和实现。
预处理模块的整体结构
预处理模块的整体结构如下：

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

清单 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，配合 SQL-Front 软件可以轻松进行图形界面的操作。我们用一个表来记录这些信息，表的内容如下：url、content、offset、raws。URL 是某条记录对应的 URL，因为索引数据库建立之后，我们是通过 URL 来确定需要的网页的；raws 和 offset 分别表示网页库名和偏移值，这两个属性唯一确定了某条记录，content 是网页内容的摘要，网页的数据量一般较大，把网页的全部内容放入数据库中显得不是很实际，所以我们将网页内容的 MD5 摘要放入到 content 属性中，该属性相当于一个校验码，在实际运用中，当我们根据 URL 获得某个网页信息是，可以将获得的网页做 MD5 摘要然后与 content 中的值做一个匹配，如果一样则网页获取成功，如果不一样，则说明网页获取出现问题。
这里简单介绍一下 mySql 的安装以及与 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 摘要算法有些疑惑，这是什么？这有什么用？ 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，我们知道其功能，能使用就可以，具体的每个步骤的意义不需要深入理解。
回页首
正文信息抽取
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;// 返回文本字符串    
 }

通过一系列的标签过滤，我们可以得到网页的正文内容，就可以用于下一步的分词了。
回页首
分词
中文分词是指将一个汉字序列切分成一个一个单独的词，从而达到计算机可以自动识别的效果。中文分词主要有三种方法：第一种基于字符串匹配，第二种基于语义理解，第三种基于统计。由于第二和第三种的实现需要大量的数据来支持，所以我们采用的是基于字符串匹配的方法。
基于字符串匹配的方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配。常用的几种机械分词方法如下：
正向减字最大匹配法（由左到右的方向）；
逆向减字最大匹配法（由右到左的方向）；
最少切分（使每一句中切出的词数最小）；
双向最大减字匹配法（进行由左到右、由右到左两次扫描）；
我们采用其中的正向最大匹配法。算法描述如下：输入值为一个中文语句 S，以及最大匹配词 n
取 S 中前 n 个字，根据词典对其进行匹配，若匹配成功，转 3，否则转 2；
n = n – 1：如果 n 为 1，转 3；否则转 1；
将 S 中的前 n 个字作为分词结果的一部分，S 除去前 n 个字，若 S 为空，转 4；否则，转 1；
算法结束。
需要说明的是，在第三步的起始，n 如果不为 1，则意味着有匹配到的词；而如果 n 为 1，我们默认 1 个字是应该进入分词结果的，所以第三步可以将前 n 个字作为一个词而分割开来。还有需要注意的是对于停用词的过滤，停用词即汉语中“的，了，和，么”等字词，在搜索引擎中是忽略的，所以对于分词后的结果，我们需要在用停用词列表进行一下停用词过滤。
您也许有疑问，如何获得分词字典或者是停用词字典。停用词字典比较好办，由于中文停用词数量有限，可以从网上获得停用词列表，从而自己建一个停用词字典；然而对于分词字典，虽然网上有许多知名的汉字分词软件，但是很少有分词的字典提供，这里我们提供一些在 dySE 中使用的分词字典给您。在程序使用过程中，分词字典可以放入一个集合中，这样就可以比较方便的进行比对工作。
分词的结果对于搜索的精准性有着至关重要的影响，好的分词策略经常是由若干个简单算法拼接而成的，所以您也可以试着实现双向最大减字匹配法来提高分词的准确率。而如果遇到歧义词组，可以通过字典中附带的词频来决定哪种分词的结果更好。
回页首
倒排索引
这个章节我们为您讲解预处理模块的最后两个步骤，索引的建立和倒排索引的建立。有了分词的结果，我们就可以获得一个正向的索引，即某个网页以及其对应的分词结果。如下图所示：

图 2. 正向索引
 

图 3. 倒排索引
 
在本文的开头，我们建立了索引网页库，用于通过 URL 可以直接定位到原始网页库中该 URL 对应的数据的位置；而现在的正向索引，我们可以通过某个网页的 URL 得到该网页的分词信息。获得正向索引看似对于我们的即将进行的查询操作没有什么实际的帮助，因为查询服务是通过关键词来获得网页信息，而正向索引并不能通过分词结果反查网页信息。其实，我们建立正向索引的目的就是通过翻转的操作建立倒排索引。所谓倒排就是相对于正向索引中网页——分词结果的映射方式，采用分词——对应的网页这种映射方式。与图 2 相对应的倒排索引如上图 3 所示。
接下来我们分析如何从正向索引来得到倒排索引。算法过程如下：
对于网页 i，获取其分词列表 List；
对于 List 中的每个词组，查看倒排索引中是否含有这个词组，如果没有，将这个词组插入倒排索引的索引项，并将网页 i 加到其索引值中；如果倒排索引中已经含有这个词组，直接将网页 i 加到其索引值中；
如果还有网页尚未分析，转 1；否则，结束
建立倒排索引的算法不难实现，主要是其中数据结构的选用，在 dySE 中，正向索引和倒排索引都是采用 HashMap 来存储，映射中正向索引的键是采用网页 URL 对应的字符串，而倒排索引是采用分词词组，映射中的值，前者是一个分词列表，后者是一个 URL 的字符串列表。这里可以采用一个优化，分别建立两个表，按照标号存储分词列表和 URL 列表，这样，索引中的值就可以使用整型变量列表来节省空间。
回页首
初步实验
到目前为止，虽然我们还没有正式的查询输入界面以及结果返回页面，但这丝毫不影响我们来对我们的搜索引擎进行初步的实验。在倒排索引建立以后，我们在程序中获得一个倒排索引的实例，然后定义一个搜索的字符串，直接在倒排索引中遍历这个字符串，然后返回该词组所指向的倒排索引中的 URL 列表即可。
回页首
小结
网页的预处理是搜索引擎的核心部分，建立索引网页库是为了网页数据更方便的从原始网页库中获取，而抽取正文信息是后续操作的基础。从分词开始就正式涉及到搜索引擎中文本数据的处理，分词的好坏以及效率很大程度上决定着搜索引擎的精确性，是非常需要关注的一点，而倒排索引时根据分词的结果建立的一个“词组——对应网页列表”映射，倒排索引是网页搜索的最关键数据结构，搜索引擎执行的速度与倒排索引的建立以及倒排索引的搜索方式息息相关。
回页首
后续内容
在本系列的第三部分中，您将了解到如何从创建网页，从网页中输入查询信息通过倒排索引的搜索完成结果的返回，并且完成网页排名的功能。