网页正文抽取:基于行的Hash值模板算法

做搜索引擎,内容分析是一个核心环节,而要做内容分析,获得有效的内容——即网页的正文抽取是相当复杂的一个步骤。常见的正文抽取算法有基于DOM树的模板匹配法和基于内容密度算法,前者虽然精确,一旦网页的DOM结构发生改变就失效,后者结合机器学习能够对大量的网页快速自动抽取,能够满足搜索引擎的索引分类需求,但依然很难达到用户阅读级别的要求。

我在做Web挖掘时写过一种基于行的Hash值计算出模板的正文抽取算法,在精确度和自动化两方面都能兼顾。主要思路是获得整个网页的文本内容后,计算出每行的Hash值,与模板库中的模板进行匹配,如果能够匹配到模板,就进行正文抽取,如果无法匹配,则与样本库中的样本进行匹配,在样本匹配如能满足,计算出模板重新投取,如果找不到匹配的样本,则直接将整个文档的Hash值写入样本库等待下一个样本与它进行比较。

Untitled (4)

取得网页文本

有很多开源工具可以获取网页的文本,原理都是基于DOM树或XML路径解析。JSoup简洁精悍,Apache Tika比较全面,这里介绍Tika的获取方法,BodyContentHandler,它用于取出HTML中<body />节点的内容。

ContentHandler handler = new BodyContentHandler(outStream);
parser.parse(inStream, handler, metadata, context);
String text = handler.toString();

计算Hash模板

从Tika获取的内容默认是使用\n进行分行,可以使用Java的getHashCode()获取每行的Hash值。设计一个存储Hash模板的矩阵结构ArrayList<ArrayList<Integer>>,为了便于计算,我们需要一个正序排列的Hash值数组作为头部模板,一个倒序排列的Hash值数组作为尾部模板。

public class HashTemplete {

  private ArrayList<ArrayList<Integer>> templates = new ArrayList<ArrayList<Integer>>();
  private ArrayList<ArrayList<Integer>> docs = new ArrayList<ArrayList<Integer>>();
  private int minY = 3;

  public int compare (ArrayList<Integer> hashDoc) {
    int x = compare(hashDoc, templates);
    ArrayList<Integer> template = null;

    if (x == -1) {
      x = compare(hashDoc, docs);
      if (x > -1) {
        template = intersect(hashDoc, docs[x]);
        templates.add(template);
      } else {
        docs.add(hashDoc);
      }
    } else {
      template = templates[x];
    }

    return template != null ? template.size() : 0;
  }

  private int compare (ArrayList<Integer> target, ArrayList<ArrayList<Integer>> sources) {
    int x = -1, y = 0;

    for (int i = 0; i < sources.size(); i++) {
      for (int j = 0; j < sources[i].size(); j++) {
        if (j == target.size() || sources[i][j] != target[j]) break;
      }
      if (j > y) {
        x = i;
        y = j;
      }
    }

    return y < minY ? -1 : x;
  }
}

minY的作用是指定最小的模板匹配深度,避免数据计算在具体应用上的偏差。最后在存储模板时,还可以加入URL规则库,将模板按照URL键写入,这样在第一步就可以对目标网页进行快迅过滤。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>