一个 Java 搜索引擎的实现--网页预处理（2）

look_w

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

1 2 3 4 5 6 7 8 9 10 11 12

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. 标签过滤

1 2 3 4 5 6 7 8 9 10 11

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 列表即可。