结构化数据提取：包装器生成及数据区域挖掘详解

### 结构化数据提取：包装器生成及数据区域挖掘详解 #### 1. 引言 在数据提取的过程中，构建 DOM 树是众多数据提取算法的必要步骤，而从单列表页面提取扁平数据记录则是数据提取中的一个重要问题。本文将详细介绍构建 DOM 树的方法以及从单列表页面提取扁平数据记录的具体流程。 #### 2. 构建 DOM 树的方法 构建 DOM 树（也称为标签树）有两种常见方法，下面分别进行介绍。 ##### 2.1 仅使用标签构建 大多数 HTML 标签是成对出现的，包括开始标签和结束标签，标签对之间还可能嵌套其他标签对，形成嵌套结构。利用页面的 HTML 代码构建 DOM 树时，每个标签对是一个节点，其内部嵌套的标签对是该节点的子节点。构建过程需要完成以下两个任务： 1. **HTML 代码清理**：有些标签虽然有结束标签，但并非必需（如 `<li>`、`<hr>` 和 `<p>`），因此需要插入额外的结束标签以确保所有标签平衡。同时，还需要修复格式错误的标签，这类错误标签通常是跨越不同嵌套块的结束标签，如 `<tr> … <td> … </tr> … </td>`，如果存在多层嵌套，修复起来会比较困难。可以使用开源程序来清理 HTML 页面，例如 `tidy`（可从 http://tidy.sourceforge.net/ 获取）。 2. **树构建**：按照页面中 HTML 标签的嵌套块来构建 DOM 树，这一过程相对简单，在此不再赘述。 这种方法适用于大多数页面，但对于一些格式错误严重的标签，即使使用 `tidy` 程序也可能无法修复，从而导致构建的 DOM 树出现错误，影响后续的数据提取。 ##### 2.2 使用标签和视觉线索构建 该方法不通过分析 HTML 代码来修复错误，而是利用渲染或视觉信息（即标签在屏幕上的渲染位置）来推断标签之间的结构关系并构建 DOM 树。由于 Web 浏览器（如 Internet Explorer）的渲染引擎具有较高的容错能力，这种方法能够更稳健地构建树。只要浏览器能够正确渲染页面，就可以正确构建其标签树。 具体步骤如下： 1. 通过调用浏览器（如 Internet Explorer）的渲染引擎，找到每个 HTML 元素矩形的四个边界。 2. 按照开始标签的顺序进行包含检查来构建树。包含检查是指检查一个矩形是否包含在另一个矩形内。 下面通过一个示例来说明该过程。假设有如下 HTML 代码： ```html 1 <table> 2 <tr> 3 <td> data1 <td> 4 </td>data2 </td> 5 <tr> 6 <td> data3 </td> 7 <td> data4 8 </tr> 9 </table> ``` 代码中存在三个错误：第 3 行的结束标签 `</td>` 放在了第 4 行的开始标签之后，第 5 行的结束标签 `</tr>` 和第 7 行的结束标签 `</td>` 缺失。但该 HTML 片段可以在浏览器中正确渲染，每个 HTML 元素的边界坐标如下： | 元素 | 左 | 右 | 上 | 下 | | ---- | ---- | ---- | ---- | ---- | | table | 100 | 300 | 200 | 400 | | tr | 100 | 300 | 200 | 300 | | tr | 100 | 200 | 200 | 300 | | td | 200 | 300 | 200 | 300 | | td | 100 | 300 | 300 | 400 | | td | 100 | 200 | 300 | 400 | | td | 200 | 300 | 300 | 400 | 利用这些视觉信息，可以轻松构建出相应的树。 #### 3. 从单列表页面提取扁平数据记录 在构建好页面的 DOM 树后，就可以进行数据提取任务了。对于包含多个列表且每个列表包含多个数据记录（至少两个）的单列表页面，需要完成以下三个任务： 1. **识别每个列表（数据区域）**：挖掘页面中所有的数据区域。 2. **分割每个列表或数据区域中的数据记录**。 3. **对齐数据记录中的数据项**：为每个数据区域生成数据表和正则表达式模式。 ##### 3.1 关于数据记录的两个观察 数据记录在每个列表（或数据区域）中使用相同的 HTML 标记编码。找到数据记录及其隐藏的模式意味着找到重复的模式并进行对齐，字符串或树匹配/比较是自然的技术。但问题在于效率，因为数据记录可以从页面的任何位置开始，长度也不确定，尝试所有可能性是不现实的。实际上，一组数据记录通常不会有完全相同的标签字符串或数据项，因为存在缺失或可选项。基于 DOM 树结构的两个重要观察有助于解决这个问题： 1. **观察 1**：一组描述相似对象的数据记录通常会在页面的连续区域中呈现，并使用相似的 HTML 标签进行格式化。这样的区域代表一个列表或数据区域。例如，在某个页面中，两本书的信息会在一个连续区域中呈现。 2. **观察 2**：一个区域中的数据记录列表由同一个父节点的一些子树组成。数据记录不太可能在一个子树的中间开始，在另一个子树的中间结束，而是从一个子树的开始处开始，在同一个或后续子树的结束处结束。 第二个观察使得设计一个高效的算法来识别数据记录成为可能，因为它限制了数据记录在 DOM 树中可能开始和结束的标签。 ##### 3.2 挖掘数据区域 挖掘数据区域的第一步是找到 Web 页面中包含数据记录列表（集合实例）的每个数据区域。直接找到数据区域（或其中的单个数据记录）比较困难，因此首先挖掘广义节点，相邻的广义节点序列形成一个数据区域，然后从每个数据区域中识别实际的数据记录。 下面使用 DOM（标签）树来定义广义节点和数据区域： - **广义节点**：长度为 r 的广义节点（节点组合）由 DOM 树中的 r（r ≥ 1）个节点组成，这些节点具有以下两个属性： 1. 节点都有相同的父节点。 2. 节点是相邻的。 引入广义节点是为了处理数据记录包含在多个兄弟