Data Highlighter

又是好久没有写 blog 了。现在确实没有上学的时候愿意折腾了,能用钱解决的问题,就不自己动手了。但是,很久不写 blog 这事呢,其实就是因为懒 _ (:3」∠) _。

这里带来的是
如何从 WEB 页面中提取信息
一文中提到的 data highlighter。但是由于开源需要重写代码,而我并不打算使用它,这里只给出 demo 和算法思路。

简介

Data Highlighter 其实是一种生成提取规则的方式:

Data Highlighter 的标注方式是:给一系列相似的页面,让用户标出(高亮)每个属性在页面中的位置。通过多个页面的标注信息,寻找每个属性的特征。当然了,这个特征可以是 xpath,也可以是上下文,也有可能是机器学习的特征向量。
Data Hightlighter 通过高亮 多个页面中相同属性 进行规则学习,省去了人为设置规则时的学习成本。实践表明,在单一页面模板下,标记2个页面就足以生成规则了。效率远大于手工设置规则。Google Data Highlighter 甚至对文字进行了切分,能在 英语 / 汉语普通话 / 粤语 xpath 相同的情况下,分别选出三种语言。是我目前见过的成熟度最高、通用性最好、最简便的数据抽取方式。

那我们通过例子介绍一下使用方式。首先打开 demo。这里列出了5个豆瓣电影的 sample 页面,点击 go 加载页面。将鼠标放在页面中,就会发现文字被高亮了,点击拖拽鼠标选择需要提取的文字,在弹出的菜单中选择属性名。


然后分别点击 gen_tpltest_all 就能看到生成的模板,以及提取效果了。

extraction sample

算法解析

点击 gen_tpl 就可以看到生成的模板了,tpl 字段的 key 为抽取的变量的名字,value 描述了一个 状态机

先看一个简单的例子,以下就是对 name 字段的模板,它描述了一个 s0 -> e0 的状态机。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
{
"need_more_sample": true,
"tips": {},
"tpl": {
"name": {
"states": {
"s0": {
"tag": "start",
"transitions": [
"e0"
],
"condition": {
"xpath": "/html/body/div/div/h1/span/textnode",
"features": {
"exclude": [],
"include": [
"ancestor::*[1][name()=\"span\" and @property='v:itemreviewed']"
]
}
}
},
"e0": {
"tag": "end",
"transitions": [],
"condition": {
"xpath": "/html/body/div/div/h1/span/textnode",
"features": {
"exclude": [
"following::*[position()=1 and name()=\"textnode\"]"
],
"include": [
"ancestor::*[1]/*[last()-0] = ancestor-or-self::*[1]"
]
}
}
}
},
"entrance_state": [
"s0"
],
"is_list": false,
"data_type": "TEXT"
}
}
}

直接跳到 tpl.name 部分,它有4个字段,is_listdata_type 描述了字段的类型,它们在字段定义的时候就已经指定了,没什么好说的。statesentrance_state 为状态机的描述部分。

entrance_state 表示状态机的入口为 s0

states 中描述了两个状态 s0e0s0.tag == start 表示这是一个开始状态,即标示字段提取的开头,e0.tag == end 为结束状态,即字段的结尾。s0.transitions == [e0] 表示从 s0 能够转移到 e0,而由于 e0.tag == end 已经结束了,所以就没有转移状态了。


在执行时,先序遍历 DOM 树,根据 condition 的条件进行状态转移。

s0.condition 表示进入开始条件为:xpath /html/body/div/div/h1/span/textnode 并且满足 ancestor::*[1][name()=\"span\" and @property='v:itemreviewed'](父元素的 name 为 span,property 属性为 “v:itemreviewed”) 这个特征。

而进入结束条件为 e0.condition: xpath /html/body/div/div/h1/span/textnode 并且满足 ancestor::*[1]/*[last()-0] = ancestor-or-self::*[1](最后一个元素),并排除满足 following::*[position()=1 and name()=\"textnode\"](右兄弟为 textnode,实际与 include 互斥)的元素。

简单地说,这个状态机描述了 属性 property='v:itemviewed' 的 span 的所有 textnode 孩子 这样一条规则。

而多状态的执行也是类似的,只不过它可能存在状态分支,或者在多个状态间循环。不过只要根据状态转移条件状态进行转移,再根据 tag 所标识的开始结束进行提取即可。

为什么要使用状态机在后面的小结讲解,我们暂且将整个状态机理解为「描述字段提取的开头和结尾」,每个状态就描述了开头结尾的特征。先来看看状态是如何描述「字段提取的开头和结尾」的。

状态条件的生成

算法的基本思路是寻找多个样本间相同的特征,并使得特征排除其他相似元素

每一个元素可以根据 id, class 属性,文字内容,位置,前 n 个元素的特征,祖先元素特征生成一组特征集合。对多个样本的特征取交,对需要排除的元素取差。

例如如果每次都选择第二个「豆瓣成员常用的标签」,就会生成

1
2
3
4
5
6
7
8
"features": {
"exclude": [
"preceding::*[position()=2 and name()=\"textnode\"]"
],
"include": [
"preceding::*[position()=2 and name()=\"a\"]"
]
}

如果每次都选择 2016 的标签,就会生成

1
2
3
4
5
6
"features": {
"exclude": [],
"include": [
"ancestor::*[1][contains(., '2016')]",
"contains(., '2016')"
]

通过特征集合的运算,算法能够通过样本,猜测出用户选择的意图。而这样的特征集合,可以不断地添加,以满足不同页面的需要。

需要特别说明的是,特征并不需要像 demo 中使用某种特定的选择器(xpath),由于模板执行时,可以再次为候选元素生成特征集合,对特征集合进行比较。实际上,你可以在特征集合中放入任何字符串,例如「第5元素」,「前一个字符为 answer,且值为 42」都是可以的。

状态机

不同于往常的选取一个元素(例如 pyspider 中的选择器),data highlighter 提供了

  1. 元素内文字选取
  2. 跨元素选取

的功能,这使得正常的「元素选择器」不再好使,取而代之的是一种定位开始和结束的规则。描述为状态机即:s0 -> e0

而 data highlighter 另一种需要支持的功能为列表选取:

就不能仅仅通过 s0 -> e0 这样开头结尾的模式进行描述了。它需要准确描述出整个列表的开头,结尾,分隔符等信息,需要通过一个类似

1
2
s0 -> e0 -> s1 -> e1 -> s2 -> e2
|------|

的状态机,s0 为整个列表的开头,s1 -> e1 为中间循环的组,e2 为 整个列表的结束。

而实际中,由于某些状态可以被合并,你可能会看到类似

1
2
3
s0 -> e0 -> s2 -> e1
|
s1

e0 和 e1 被合并了,即第一个元素的结束条件和中间元素的结束没有不同

的状态机

状态机的生成

虽然状态机看起来非常复杂,但是用程序处理起来却不难。首先为每一个样本(包括列表选取)生成一条 s0 -> e0 -> s1 -> e1 -> s2 -> e2 -> s3 -> e3 ... 的长链,然后尝试合并状态,然后将多个样本的链用同一规则合并。而不能合并的状态,就做个分支转移即可。

而状态能否合并,取决于它们有没有共同特征,就是这么简单。

总结

Data Highlighter 的算法设计,实际上是对元素特征选取的一种建模。通过设计合适的数据结构,使得多样本能够反映到模板中去。

这个算法是两年前设计的,现在看起来实际上问题蛮多的,例如:

  • 无法使用组合特征,即要求元素同时满足满足多个条件
  • 没有设计合理的泛化机制
  • 模板不可读

等,所以,我并不打算使用这个算法。

只不过,最近些年,看到很多数据提取的公司,特别是国内的数据提取平台,还在停留在非常初级的 css selector 或者 xpath 点选生成。希望这篇文章能抛砖引玉,提供一些新的思路,为数据抽取提供更易用有效的工具。

完。