搜索多层次XML文档：碎片化的案例

### 搜索多层次 XML 文档：碎片化的案例 #### 1. 引言 在使用 XML 对文本文档的属性进行编码时，往往需要使用多个标记层次结构，这就容易导致编码中的标记冲突。文本编码倡议（TEI）指南认识到了这个问题，并提出了一些在单个格式良好的 XML 文档中整合多个层次结构的方法。其中一种方法是标记碎片化，它通过将冲突的 XML 元素进行碎片化处理，以实现正确的嵌套，从而在单个 XML 文档中表示多层次标记。 然而，碎片化的 XML 文档使用传统的 XML 查询语言（如 XPath）进行查询变得困难。一些在常规 XML 文档中可以轻松用 XPath 表达的查询，在碎片化的 XML 中却无法实现。目前，还缺乏方便、一致且与领域无关的形式化方法和软件来查询这种碎片化的编码。 本文的主要贡献如下： - 为具有标记碎片化的 XML 文档正式定义多个层次结构。 - 为具有多个层次结构的碎片化 XML 文档计算 XPath 轴给出新的语义。 - 提出并实现计算具有碎片化的 XML 文档 XPath 轴的高效算法。 - 展示一些初步的实验结果。 #### 2. 文本编码中的重叠标记 重叠标记在许多文本编码任务中都会出现。例如，图 1 展示了一份 10 世纪古英语手稿的片段，以及该片段在三种不同标记层次结构（物理位置、句子结构和手稿状况）下的编码。这些层次结构的特征存在重叠，如 `<rstxt>`（恢复文本）与第 22 行的 `<w>` 重叠，单词 `ægþer` 被分割在第 22 行和第 23 行，单词 `spræce` 被分割在第 23 行和第 24 行。 TEI 指南提出了一些在单个文档中表示多层次标记的方法，本文关注其中的碎片化方法。碎片化的工作原理是：当两个元素的范围重叠时，将其中一个元素分割成若干部分，使得两个元素能够正确嵌套在同一个 XML 文档中。例如，将 `<w>spræce</w>` 分割成 `<w id="W1" next="W2">spræ</w>` 和 `<w id="W2" prev="W1">ce</w>`，通过 `id`、`prev` 和 `next` 属性形成一个双向链表来表示这些片段属于同一个单词。 然而，碎片化虽然解决了多层次标记在单个文档中的存储问题，但 TEI 指南并未解决碎片化数据的查询问题。以下面的查询为例： 查询：找出完全位于第 23 行的所有单词。 对于非碎片化的 XML 文档，对应的 XPath 查询为 `/descendant::line[@no="23"]/descendant::w`。但在碎片化的情况下，该查询返回的结果包含了单词的片段，并非完整的单词，因此需要重新表述查询：找出 `<line no="23">` 元素范围内的所有 `<w>` 元素，这些元素要么未被碎片化，要么其所有同级片段都在 `<line no="23">` 元素的范围内。这个查询无法用单个 XPath 1.0 查询表达，因为 XPath 1.0 在决定是否将一个节点包含在答案集中时，不依赖于其他节点的决策。不过，我们可以通过简单的步骤得到所需结果： 1. 搜索以 `<line no="23">` 为根的 DOM 子树。 2. 将每个未碎片化的 `<w>` 节点和所有构成单个单词的碎片化 `<w>` 节点包含在答案集中。可以在单次树遍历中，通过验证当发现一个 `<w ID="x" next="y">` 元素（第一个片段）时，匹配的 `<w ID ="z" prev="u">` 元素（最后一个片段）也在 `<line no="23">` 的范围内来确定。 这个例子表明，XPath 1.0 在 DOM 上的语义与碎片化 XML 的 DOM 树语义不兼容。接下来我们将解决这个问题。 #### 3. 背景 在介绍解决方法之前，我们先简要介绍文档对象模型（DOM）和 XPath 查询语言，以及本文使用的一些符号。 ##### 3.1 文档对象模型（DOM） 在 DOM 中，XML 文档被表示为一个带标签的无序树。我们用 `dom(d)` 表示文档 `d` 的 DOM 节点集，`root(d)` 表示文档 `d` 的根节点，`tags(d)` 表示文档 `d` 的节点标签集。本文只考虑 `dom(d)` 中的元素节点和文本节点。我们定义了以下函数： - `type(x)`：返回节点 `x` 的类型，即 “element” 或 “text”。 - `tag(x)`：对于元素节点返回其标签，对于文本节点返回 `null`。 - `x < y` 或 `y > x`：表示节点 `x` 在文档顺序上先于节点 `y`。 - `ancestorDOM(x)`：表示节点 `x` 在 DOM 中的祖先节点集。 - `scope(x)`：对于元素节点 `x`，表示从其开始标签到结束标签的文档内容区间。 ##### 3.2 XPath 查询语言 XPath 是一种用于定位 XML 文档部分内容的语言，它在 XQuery 中用于访问 XML 文档，也可以单独用于查询 XML 文档。XPath 使用节点树模型来表示 XML 文档，其主要语法结构是表达式，通过位置路径（一种特殊的表达式）来定位文档中的节点。位置路径由一个或多个步骤组成，每个步骤根据节点之间的关系（在步骤中指定）从当前上下文节点集中选择一组节点。步骤评估的节点集结果成为位置路径中下一个步骤的当前上下文节点集。XPath 的核心语法总结如下： - `locationPath := step1/step2/.../stepn` - `step := axis::node - test predicate*` - `predicate := [expression]` XPath 使用 13 个轴来定位文档中的节点，包括 `ancestor`、`ancestor - or - self`、`attribute`、`child`、`descendant`、`descendant - or - self`、`following`、`following - sibling`、`namespace`、`parent`、`preceding`、`preceding - sibling` 和 `self`。XPath 轴的正式语义在相关文档中有定义，轴评估得到的节点集会通过节点测试（基本上是节点类型测试或元素节点的名称测试）和表达式进行过滤，表达式可以是位置路径（如果结果节点集非空则评估为真），也可以是涉及 XPath 核心函数库中函数的布尔表达式。 ##### 3.3 具有碎片化的 XML 文档的多个层次结构 我们将 XML 文档的多个层次结构定义为节点名称（标签或元素）到有限标签集（层次结构名称）的映射。在任何多层次文档中，除根节点属于所有层次结构外，元素节点只属于一个层次结构，而文本节点属于所有层次结构。通常，每个层次结构包含一组特定的标记特征。 下面给出正式定义： - **定义 1（多层次结构）**：设 `H` 是一个标签集（字符串）。多层次结构是一个函数 `H : tags(d) → 2^H`，满足： - 如果 `x` 是根节点或 `type(x) = “text”`，则 `H(x) = H`。 - 如果 `x` 是元素节点且不是根节点，则 `H(x) = {a}`，其中 `a ∈ H`。 - **定义 2（碎片化表示）**：设 `H` 是标签集 `H` 上的多层次结构。设 `d1, .., d|H|`