C++博客 :: 首页 :: 新随笔 ::  ::  :: 管理

一个 Java 搜索引擎的实现，第 2 部分: 网页预处理

Posted on 2011-04-16 20:36 Kevin_Zhang 阅读(693) 评论(0)  编辑 收藏 引用 所属分类: 搜索引擎
在 上一部分 中，您了解到如何编写一个 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 列表即可。
回页首
小结
网页的预处理是搜索引擎的核心部分，建立索引网页库是为了网页数据更方便的从原始网页库中获取，而抽取正文信息是后续操作的基础。从分词开始就正式涉及到搜索引擎中文本数据的处理，分词的好坏以及效率很大程度上决定着搜索引擎的精确性，是非常需要关注的一点，而倒排索引时根据分词的结果建立的一个“词组——对应网页列表”映射，倒排索引是网页搜索的最关键数据结构，搜索引擎执行的速度与倒排索引的建立以及倒排索引的搜索方式息息相关。
回页首
后续内容
在本系列的第三部分中，您将了解到如何从创建网页，从网页中输入查询信息通过倒排索引的搜索完成结果的返回，并且完成网页排名的功能。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理