利用高级栈机器提取HTML文档结构

### 利用高级栈机器提取HTML文档结构 #### 1. 引言 在万维网（WWW 或 Web）发展的早期，用户主要依赖网页浏览器提供的超链接，通过鼠标点击的导航方式来获取感兴趣的信息。然而，这种方式很快让用户迷失在网络空间中。此后，网页设计师和用户一直在寻找更好的替代方法。目前，从网络中检索信息主要有两种方法：一是使用索引服务器的关键字搜索方法；二是使用 Web 查询语言，包括类似 SQL 的查询语言和类似 Datalog 的查询语言。 为了更好地理解这个问题，我们需要明确三种类型的数据，即非结构化数据、结构化数据和半结构化数据。非结构化数据通常存储在可执行文件、不包含格式代码的纯文本文件和音频文件等文件中；结构化数据的典型例子是关系数据库模型中的表；半结构化数据则介于这两种极端类型的数据之间，例如包含格式代码的文本文件（如 DTgX 和 HTML 文件），以及需要严格内部结构但部分结构组件可以省略的文件（如 BIBTf^X 文件、Unix 环境文件等）。 网络上的信息是各种异构数据的集合，主要是 HTML 文档，还包括图像、声音和视频片段等其他类型的数据。HTML 规范是在网络上发布信息最广泛使用的范例，但它并不要求 HTML 文档具有统一的结构，例如一个 HTML 文档中出现的元素可能在其他 HTML 文档中缺失。因此，我们将 HTML 文档 H 视为其中嵌入的半结构化数据的文本表示。 使用半结构化数据的一个好处是其在数据表示上具有灵活性。然而，目前还缺乏半结构化数据的理论，也没有关于半结构化数据的通用标准定义。在本文中，如果一个有限的数据对象集合 {o1, o2, ..., on} 满足以下条件，我们就将其视为半结构化数据 D： - D 的结构不规则或不完整； - D 的模式与 {o1, o2, ..., on} 之间的区别模糊，并且模式可能会动态变化； - o i（1 < i < n）不具有类型敏感性。 本文提出了一种提取万维网 HTML 文档 H 中嵌入的半结构化数据结构的方法。假设 H 符合 HTML 规范，并由给定的 URL 引用（还可以从 H 中指定的超链接进一步获取其他 URL）。我们首先提出了一种半结构化数据的图形数据模型，即半结构化数据图（SDG），然后介绍了一种工具——高级栈机器（HSM），用于提取 H 中嵌入的结构。 本文的主要贡献有三点： - 扩展了数据库组件之间依赖关系的概念，以捕捉 HTML 文档中嵌入的半结构化数据的结构。 - 使用 Java 语言环境设计并实现了一个简单的自动机 HSM，用于根据 URL 构建 HTML 文档的 SDG。由于 HSM 基于下推自动机构建，因此使用栈实现相对容易，无需考虑像图灵机那样的复杂功能，如重读或替换输入，也无需假设无限的辅助内存。 - HSM 可以根据用户的需求轻松配置，用户只需提供一个配置文件，其中包含用户选择要包含在 HTML 文档 H 的 SDG 中的 HTML 元素列表。编写配置文件不需要额外的命令及其语法知识。 #### 2. 数据模型 我们的半结构化数据数据模型 SDG 基于数据库对象之间的依赖关系概念。 ##### 2.1 对象的定义 一个集合 S 中的对象 o 是一个三元组（标签，值，标识符），其中： - 标签是对 o 的文本描述（即字符串）； - 值是一个有限的有序字符串集合。如果值为空，则 o 称为自由对象；否则，o 称为绑定对象； - 标识符是一个非空字符串，用于唯一定义 S 中的 o。 在 SDG 中，对象的标识符和标签是静态的，而其值是动态的。此外，SDG 中对对象不严格执行类型约束，因此对象的值可以是任何类型。为了简单起见，我们假设对象的值是一个字符串集合，因为所有原子和复合类型（如整数、实数和布尔值）以及原子类型的对象集合都可以表示为字符串。 我们还定义了一些实用函数： - o.label() 和 o.value() 分别返回对象 o 的标签和值。 - 二元函数 con: S x S -> S，其中 S 是字符串集合，con(arg1, arg2) = arg1.arg2。 ##### 2.2 依赖关系的定义 如果 o1.value() := o2.value()，则称对象 o1 直接依赖于另一个对象 o2，记为 o1 <— o2。依赖关系是传递的，即如果 o1 <— o2 且 o2 <— o3，则 o1 <— o3，我们称 o1 间接依赖于 o3，记为 o1 <— o2 <— o3 或 o1 *— o3。如果 o <— o1, …, o <— on，则 o.value() = o1.value() ∪ … ∪ on.value()。 例如，给定以下对象及其数据值： - Location (Location; (free); Address, “Time Zone”) - Address (Address; (free); “Street Addr,” City, “Zip code”) - “Street Addr” (Street; (free); “11 E. Pine Lane”) - City (City; (free); Orem) - “Zip code” (ZipCode; (free); 84057) - “Time Zone” (TimeZone; (free); MST) - “11 E. Pine Lane” (“11 E. Pine Lane”; “11 E. Pine Lane”; - ) - Orem (Orem; Orem; - ) - 84057 (84057; 84057; - ) - MST (MST; “Mountain Standard Time”; - ) Address 的依赖约束为 Address <— “Street Addr” <— “11 E. Pine Lane”，Address <— City <— Orem，以及 Address <— “Zip code” <— 84057。因此，Address.value() = { “11 E. Pine Lane”, Orem, 84057 }。 ##### 2.3 长标签的定义 给定对象 o1, o2, ..., oN 之间的依赖关系，使得 o1 <— o2 <— … <— oN，对象 oi 的长标签 oi.Label()（1 < i < N）定义如下： - o1.Label() = o1.label()； - oi.Label() = con(oi - 1.Label(), oi.label())，2 < i < N。 例如，对于上述对象集合，根据定义可得： - Location.Label() = Location.label() = Location - Orem.Label() = (City.Label()).(Orem.label()) = (Address.Label()).(City.label()).Orem = (Location.Label()).(Address.label()).City.Orem = (Location.label()).Address.City.Orem = Location.Address.City.Orem - “Time Zone”.Label() = Location.TimeZone ##### 2.4 半结构化数据图（SDG）的定义 给定半结构化数据 D，其半结构化数据图 SDG 是一个三元组 (V, E, g)，它是一个有根的有向图，其中： - V 是一个有限的节点集合，V = {Vr} ∪ Vi ∪ Vl，其中 {Vr} ∩ Vi ∩ Vl = 0。Vr 是 SDG 的根节点，标签为 lD，作为 SDG 的入口点并表示 D；Vl 是一个有限的叶节点集合；Vi 是 SDG 中除 Vr 和 Vl 之外的有限内部节点集合。n ∈ (Vi ∪ Vl)，标签为 ‘o’，表示 D 中的一个对象 o。 - E 是一个有限的有向边集合。 - g: E -> V x V，使得 g(e) = (n1, n2) 当且仅当由 n1 ∈ ({Vr} ∪ Vi) 表示的对象依赖于由 n2 ∈ (Vi ∪ Vl) 表示的对象。 例如，考虑上述示例中的对象 Location，并假设半结构化数据 Info 由 Location 定义。根据 Location 及其相关对象的依赖约束，Info 的 SDG 如图 1 所示。 ##### 2.5 路径表达式的定义 给定 SDG 中对象 on 的长标签 (o1.label()).(…).(on.label())，对象 oi 和 oj（1 < i < j < N）之间的路径表达式 pe 是一个二元函数 pe: S x S -> S，使得 pe(oi, oi) = oi.label()，pe(oi, oj) = con(pe(oi, oj - 1), oj.label())，其中 S 是字符串集合，oi 表示 SDG 的根节点。 容易看出，pe(VR, o) = o.Label()，其中 Vr 是根节点，o ∈ (Vi ∪ Vl) 是相应 SDG 中的节点。 ##### 2.6 SDG 的词法表示 给定 SDG = ({Vr} ∪ Vi ∪ Vl, E, g)，对象 o ∈ ({Vr} ∪ Vi ∪ Vl) 的词法表示 L0 或词法 SDG 是 SDG 中以 o 为根的子图 S 的文本表示，使得 L0 = ∪vi {pe(o, oi)}，其中 oi 是 S 中的叶节点。 例如，对于 Info 的 SDG，有以下路径表达式和词法表示： - pe(Address, 84057) = con(pe(Address, “Zip code”), 84057.label()) = con(con(pe(Address, Address), “Zip Code”.label()), 84057) = con(con(Address.label(), ZipCode), 84057) = con(Address.ZipCode, 84057) = Address.ZipCode.84057 - pe(Address, Orem) = Address.City.Orem - LAddress = {Address.Street.“11 E. Pine Lane”} ∪ {Address.City.Orem} ∪ {Address.ZipCode.84057} = Address.{Street.“11 E. Pine Pine”, City.Orem, ZipCode.84057} - 词法 SDG of Info LInfo = Info.Location.{Address.{Street.“11 E. Pine Lane”, City.Orem, ZipCode.84057}, TimeZone.MST} 需要注意的是，给定 SDG = ({Vr} ∪ Vi ∪ Vl, E, g)，SDG 的词法表示为 ∪vi {pe(Vr, oi)} = ∪vi {oi.Label()}，其中 oi ∈ Vl。显然，SDG 的词法表示 L 不如 SDG 本身容易解释。为了解决这个问题，可以使用缩进和换行对 L 进行格式化。例如，Info 的格式化词法表示如下： ``` Info. Location.{ Address.{ Street.“11 E. Pine L ```