DEPTA

Web Data Extraction Based on Partial Tree Alignment ———— 论文翻译

摘要

本文研究了从包含多个结构化数据记录的网页中提取数据的问题。目标是将这些数据记录进行分割，从中提取数据项/字段，并将数据放入数据库表中。这个问题已经被多位研究人员研究过。然而，现有的方法仍然存在一些严重的限制。第一类方法基于机器学习，需要对感兴趣的每个网站进行大量示例的人工标注。由于Web上存在大量的站点和页面，这个过程非常耗时。第二类算法基于自动模式发现。这些方法要么不准确，要么做出很多假设。本文提出了一种新的自动执行任务的方法。它包括两个步骤：（1）识别页面中的单个数据记录，（2）对识别出的数据记录进行对齐和提取数据项。对于第一步，我们提出了一种基于视觉信息的方法来分割数据记录，这比现有方法更准确。对于第二步，我们提出了一种基于树匹配的新颖部分对齐技术。部分对齐意味着我们仅对一对数据记录中可以确凿对齐（或匹配）的数据字段进行对齐，并不对其余的数据字段做出承诺。这种方法能够非常准确地对齐多个数据记录。使用来自不同领域的大量Web页面的实验结果表明，所提出的两步技术能够非常准确地分割数据记录，并从中对齐和提取数据。

1、介绍

结构化数据对象是Web上非常重要的一种信息类型。这些数据对象通常是来自底层数据库的记录，并以一些固定的模板显示在Web页面中。在本文中，我们也称它们为数据记录。在Web页面中挖掘数据记录是有用的，因为它们通常呈现它们所在页面的基本信息，例如产品和服务列表。提取这些结构化数据对象使得我们能够整合来自多个Web页面的数据/信息，提供增值服务，例如比较购物、元查询和搜索。图1展示了Web上一些示例数据记录。图1（A）显示了一个包含两本产品（图书）列表的Web页面段落。每本书的描述是一个数据记录。图1（B）显示了一个包含数据表的页面段落，其中每个数据记录是一个表行。我们的目标有两个：（1）自动识别页面中的这些数据记录，（2）自动对齐和提取数据记录中的数据项。

文献中报道了多种从Web页面中挖掘数据记录的方法。第一种方法是手动方法。通过观察Web页面及其源代码，程序员从页面中找出一些模式，然后编写程序来识别和提取所有的数据项/字段。这种方法在处理大量页面时不具有可扩展性。其他方法都具有一定程度的自动化。主要有两种算法，即包装器归纳和自动提取。在包装器归纳中[11, 19, 23, 25, 33]，从一组手动标注的页面或数据记录中学习一组提取规则。然后利用这些规则从类似页面中提取数据项。这种方法仍然需要大量的手动工作。在自动方法中，[12] [1]从包含类似数据记录的多个页面中找出模式或语法。然而，这种方法的一个主要限制是需要找到一组包含类似数据记录的初始页面，而这些页面必须通过手动或其他系统来找到。[20]提出了一种尝试探索当前页面背后的详细信息页面以提取数据记录的方法。然而，需要详细信息页面的需求也是一个严重的限制，因为许多数据记录并没有这样的背后页面（例如，图1（B））。此外，该方法假设详细页面已经存在，这在实践中是不现实的。由于典型Web页面中存在大量链接，自动识别指向详细信息页面的链接是一个非常棘手的任务。[8]提出了一种字符串匹配方法，但其结果不够强大，如[21]所示。大多数当前系统做出的另一个假设是，数据记录的相关信息包含在HTML代码的连续段中。然而，在一些Web页面中，一个对象的描述可能与其他对象的描述交织在一起。例如，HTML源代码中两个对象的描述可能按照以下顺序排列：对象1的部分1，对象2的部分1，对象1的部分2，对象2的部分2。因此，对象1和对象2的描述不是连续的。然而，当它们在浏览器上显示时，它们对于人类观看者来说是连续的。在第2节中，我们详细讨论了这些方法，并与我们提出的方法进行了比较。

本文提出了一个两步策略来解决这个问题。

1、首先，该方法通过对页面进行分割来识别每个数据记录，而无需提取其数据项。我们改进了先前用于此目的的技术MDR [21]。具体而言，新方法也利用视觉线索来寻找数据记录。视觉信息以两种方式帮助系统：

（i）它使系统能够识别分隔数据记录的间隙，这有助于正确分割数据记录，因为数据记录内的间隙（如果有）通常较小于数据记录之间的间隙。

（ii）所提出的系统通过分析HTML标签树或DOM树 [7] 来识别数据记录。构建标签树的一种简单方法是按照HTML代码中的嵌套标签结构进行处理。

然而，必须加入复杂的分析来处理HTML代码中的错误（例如，缺失或格式不正确的标签）。而视觉或显示信息可以在HTML代码被Web浏览器渲染后获得，它还包含有关标签的层次结构的信息。在这项工作中，我们不是分析HTML代码，而是利用视觉信息（即标签在屏幕上的位置）来推断标签之间的结构关系并构建标签树。由于Web浏览器的渲染引擎（例如Internet Explorer）具有较高的容错性，因此这种方法可以实现更强健的树结构构建。只要浏览器能够正确地渲染页面，就可以正确构建其标签树。

2、提出了一种新颖的部分树对齐方法，用于对齐并提取发现的数据记录中的相应数据项，并将数据项放入数据库表中。由于HTML代码的嵌套（或树状）组织方式，使用树对齐是自然而然的选择。根据我们的实验证明，这种新方法非常准确。
具体来说，在确定了所有的数据记录之后，每个数据记录的子树被重新排列成单一的树，因为每个数据记录可能包含在页面的原始标签树中的多个子树中，并且每个数据记录可能不是连续的。然后，使用我们的部分对齐方法对所有数据记录的标签树进行对齐。在部分对齐中，我们指的是对于每对树（或数据记录），我们仅对齐那些可以确定对齐的数据字段，并忽略那些无法对齐的部分，即不确定未对齐数据项的位置。过早地做出不确定的对齐决策可能会对后续涉及其他数据记录的对齐产生不良影响。这种方法在多个树的对齐中非常有效。

由此产生的对齐结果使我们能够从页面中提取所有数据记录的数据项。它还可以作为一个提取模式，用于从使用相同模板生成的其他带有数据记录的页面中提取数据项。

我们的两步方法被称为DEPTA（基于部分树对齐的数据提取），与所有现有方法非常不同，它不会做出现有方法所做的那些假设。只要一个页面包含至少两个数据记录，我们的系统就会自动找到它们（有关更多讨论，请参见第3.5节）。我们使用大量页面的实验结果表明，所提出的技术非常有效。

2、相关工作

与我们的相关工作在包装生成领域。包装是从网站或页面中提取数据并将其放入数据库的程序[1, 11, 12, 16, 18, 19, 22, 23, 25]。有两种主要的包装生成方法。

第一种方法是包装归纳，它使用有监督学习从一组手动标记的正负样本中学习数据提取规则。然而，手动标记数据是费力且耗时的工作。此外，对于不同的网站或甚至同一网站的不同页面，手动标记过程需要重复进行，因为它们遵循不同的模板/模式。示例包装归纳系统包括WIEN [19]，Softmealy [18]，Stalker [23]，WL2 [11]，[25]等。我们的技术不需要人工标记。它可以自动在页面中挖掘数据记录并从记录中提取数据。

第二种方法是自动提取。在[14]中，研究了自动识别数据记录边界的方法。该方法基于一组启发式规则，例如最高计数标签、重复标签和本体匹配。[5]提出了一些更多的启发式规则来执行任务，而不使用领域本体。然而，[21]表明这些方法产生了较差的结果。此外，这些方法不会从数据记录中提取数据。[8]提出了一种从页面的HTML标签字符串中找到模式的方法，然后使用这些模式提取数据项。该方法使用了Patricia树和序列对齐来找到非精确匹配。然而，[21]表明其性能也较弱。我们的新方法不使用标签字符串进行对齐，而是使用树，利用嵌套的树结构来进行更准确的数据提取。[13]还提供了一组启发式规则来找到单个产品信息，例如价格和其他信息。

在[1, 12, 34]中，提出了另外两种技术。然而，它们需要使用包含相似数据记录的同一网站的多个页面（假定这些页面已给出）来从页面中找到模式或语法来提取数据记录。假设可用的包含相似数据记录的多个页面是一个严重的限制。我们的方法适用于每个单独的页面。

[20]提出了另一种数据提取方法。其主要思想是利用当前页面后面的详细数据来识别数据记录。通常，包含多个数据记录的页面并不包含每个数据记录的完整信息。相反，通常使用链接指向包含产品详细描述的页面。因此，该技术适用于图1（A）中的示例，但不适用于图1（B）中的示例，因为图1（B）中的每个数据记录都没有指向详细页面的链接。此外，[20]中的方法假设详细页面已经存在（在他们的实验中，这些页面是手动确定的），这是不现实的。由于典型网页中存在大量链接，自动识别指向详细页面的正确链接并不是一项简单的任务。我们的技术适用于图1中的两种页面类型，因为它不需要任何详细页面。

大多数现有方法的另一个问题是它们假设数据记录的相关信息包含在HTML代码的连续段中。这并不总是正确的。这个问题在介绍部分已经讨论过。我们提出的方法能够处理这种情况，因为我们的记录分割方法能够识别出这样的数据记录。在[21]中，我们提出了MDR算法，它只识别数据记录，但不对数据记录进行对齐或提取数据项。因此，它只完成了我们任务的第一步。即使对于第一步，它也有两个主要缺点。(1)该算法利用Web页面的HTML标签树从页面中提取数据记录。然而，某些页面的HTML源代码中的错误标签使得构建正确的树变得困难，从而无法在这些页面中找到正确的数据记录。使用视觉（渲染）信息来构建我们的新系统中的树解决了这个问题。(2)单个数据记录可能由多个子树组成。由于噪声信息，MDR可能会找到错误的子树组合。在我们的新系统中，数据记录之间的视觉间隙有助于解决这个问题。请注意，视觉线索已在其他Web任务中使用，例如找到不同的语义块[29, 28]。

最后，在[27]中，树匹配被用于在新闻页面中找到主要内容。然而，他们的任务与我们的不同。

3、数据记录抽取

现在我们开始介绍我们提出的技术。本节重点介绍第一步：将Web页面分割为单个数据记录以识别它们。本节不涉及对数据记录进行对齐或提取数据项的工作，这将是下一节的主题。由于这一步是对我们先前的技术MDR [21]的改进，因此我们在下面简要概述MDR算法，并介绍在本工作中对MDR进行的改进。我们也将增强的算法称为MDR-2（MDR的第二个版本）。

3.1、MDR的基本思想

MDR算法基于对Web页面中数据记录的两个观察以及一个编辑距离字符串匹配算法[2]来查找数据记录。这两个观察是：

1、一组包含一组类似对象描述的数据记录通常以连续的区域形式呈现在页面上，并使用相似的HTML标签进行格式化。这样的区域被称为数据记录区域（或简称为数据区域）。例如，在图1（A）中，两本书在一个连续的区域中呈现。它们还使用几乎相同的HTML标签序列进行格式化。如果我们将页面的HTML标签视为一个长字符串，我们可以使用字符串匹配（例如，编辑距离[2]）来比较不同的子字符串，以找到表示相似数据记录的子字符串。这种方法的问题是计算量很大，因为数据记录可以从任何标签开始，也可以在任何标签结束。一组数据记录通常在其标签字符串方面长度不同，因为它们可能不包含完全相同的信息片段（参见图1（A））。下一个观察有助于解决这个问题。

2、 Web页面中HTML标签的嵌套结构自然形成一个标签树。例如，图2显示了一个示例标签树。在这个树中，每个数据记录被包裹在3个TR节点中，并且它们的子树位于相同的父节点TBODY下。两个数据记录位于两个虚线框中。我们的第二个观察是，一组相似的数据记录由相同父节点的一些子树组成。一个数据记录不太可能从一个子树的中间开始，在另一个子树的中间结束。相反，它从一个子树的开头开始，并在相同或后续的子树的结尾结束。例如，一个数据记录不太可能从TD*开始，并在TD＃结束（图2）。这个观察使得基于编辑距离字符串比较的高效算法能够识别数据记录，因为它限制了在标签树中可能起始和结束数据记录的标签范围。

实验结果表明，这些观察非常有效。我们绝不假设一个Web页面只有一个包含数据记录的数据区域。事实上，一个Web页面可能包含几个数据区域，不同的区域可能具有不同的数据记录。给定一个Web页面，算法分为三个步骤（我们还讨论了在我们当前工作中对MDR进行的改进）：

第一步：构建页面的HTML标签树。在新系统中，使用视觉（渲染）信息构建标签树。
第二步：使用标签树在页面中挖掘数据区域。数据区域是页面中包含一系列相似数据记录的区域。MDR首先挖掘数据区域，然后在这些区域内找到数据记录，而不是直接挖掘数据记录（这是困难的）。例如，在图2中，我们首先找到TBODY节点下方的单个数据区域。在我们的新系统中，再次使用视觉信息可以产生更好的结果。
第三步：从每个数据区域中识别数据记录。例如，在图2中，这一步在TBODY节点下方的数据区域中找到数据记录1和数据记录2。

对MDR算法的主要改进是利用视觉信息来帮助构建更健壮的树，并找到更准确的数据区域。我们下面对它们进行描述。

3.2、构建HTML标签树

在Web浏览器中，每个HTML元素（由起始标签、可选属性、可选嵌入的HTML内容和可能被省略的结束标签组成）都会被渲染为一个矩形。可以根据嵌套的矩形（由嵌套标签产生）构建标签树。具体细节如下：

通过调用浏览器的嵌入式解析和渲染引擎（如Internet Explorer），找到每个HTML元素的矩形的四个边界。
检测矩形之间的包含关系，即一个矩形是否被包含在另一个矩形内。可以根据包含关系构建树结构。

让我们用一个示例来说明这个过程。假设我们有图3左侧的HTML代码，其中是一个包含两行（tr）和每行两个单元格（td）的表格。浏览器的渲染引擎在图3右侧为每个HTML元素生成了边界坐标（以像素为单位）。

通过视觉信息，我们可以按照打开标签的顺序，并通过包含关系检查，构建出图4中的树结构。树构建算法非常直观，我们在这里不再详细讨论。

3.3、挖掘数据区域

该步骤会挖掘包含相似数据记录的页面中的每个数据区域。为了避免直接挖掘数据记录（这很困难），我们首先挖掘数据区域。通过比较单个节点（包括其子节点）的标签字符串和相邻多个节点的组合，我们可以找到每个数据区域。

我们使用图5中的人工标签树来解释。我们发现节点5和6相似（基于编辑距离）并形成标记为1的数据区域，节点8、9和10相似并形成标记为2的数据区域，节点对（14, 15）、（16, 17）和（18, 19）相似并形成标记为3的数据区域。为了避免同时使用单个节点和节点组合，我们使用广义节点的概念来表示每个相似的单个（标签）节点和每个（标签）节点组合。因此，一系列相邻的广义节点形成一个数据区域。图5中的每个阴影单个节点或节点组合都是一个广义节点。广义节点的概念捕捉了这样的情况：数据记录可能包含在几个兄弟标签节点中，而不是一个标签节点，并且数据记录在标签树中可能不是连续的，但广义节点是连续的（见下文）。

由于第3.1节的观察，为了识别数据区域中的广义节点并进行字符串比较，所需的比较次数并不多。我们只需要在父节点的子节点之间进行比较。识别数据区域的过程比较复杂，请参阅[21]了解更多细节。

在我们的新系统中，利用数据记录之间的间隙来消除虚假的节点组合。我们利用以下关于数据记录的视觉观察：

• 数据区域中两个数据记录之间的间隙应不小于数据记录内的任何间隙。例如，在图1（A）中，两个数据记录之间存在较大的间隙。

3.4、识别数据记录

在确定了所有的数据区域之后，我们从广义节点中识别数据记录。需要注意的是，每个广义节点（标签树中的单个节点或节点组合）可能不代表一个单独的数据记录。情况可能非常复杂。下面，我们只强调两种有趣的情况，其中数据记录不包含在HTML代码的连续段中，以展示我们系统的一些高级功能（详细信息请参阅[21]，以及其他更简单的情况）。

3.4.1、非连续的数据记录：情况1

在某些网页中，对象（数据记录）的描述不在HTML代码的连续段中。有两种主要情况。图6展示了第一种情况的示例。

在这个示例中，数据区域包含两个广义节点，每个广义节点包含两个标签节点（两行），这意味着这两个标签节点（行）彼此不相似。但是，每个标签节点具有相同数量的子节点，并且子节点彼此相似。一行列出了两个对象的名称，下一行列出了对象的其他信息，也是两个单元格。这导致HTML代码如下：name 1, name 2, description 1, description 2, name 3, name 4, description 3, description 4。

对于这种情况，广义节点中每个标签节点的相应子节点形成一个非连续的数据记录。这由图6底部的标签树进行说明，其中r表示行，n表示名称，d表示描述。G1和G2是广义节点。 (n1, d1), (n2, d2), (n3, d3)和(n4, d4)形成了四个数据记录。

3.4.2、非连续的数据记录：情况2

图7展示了第二种情况的示例，其中两个或更多数据区域形成多个数据记录。在这个示例中，第一行和第二行彼此不相似，但第一行形成一个数据区域，第二行形成另一个数据区域。每个数据区域包含两个（小）广义节点。

从图7的标签树中可以看出，这种情况与图6中的情况具有相同的结构。因此，可以应用类似的策略，即将每个数据区域的相应广义节点合并在一起形成非连续的数据记录。这个过程由图7中的标签树进行说明（G1、G2、g1和g2是广义节点）。

3.5、关于数据记录的重要说明

最后，需要强调的是，MDR或MDR-2并不知道哪些常规数据记录对用户有用。它仅仅找到了所有的数据记录。然而，在特定的应用中，用户通常只对特定类型的数据记录感兴趣，例如产品列表或数据表。可以设计简单的启发式方法来仅输出所需类型的数据记录。例如，在MDR（或MDR-2）中，可以选择仅基于一些指标（如图像、价格等）输出产品数据记录。

4、数据抽取

我们现在介绍数据提取的部分树对齐技术。关键任务是如何匹配所有数据记录中对应的数据项或字段。这包括两个子步骤：

为每个数据记录生成一个根标签树：在确定了所有数据记录后，每个数据记录的子树将重新排列为一棵单独的树。正如上文所示，每个数据记录可能包含在页面原始标签树的多个子树中，并且每个数据记录可能不是连续的。因此，这个子步骤是为了为每个数据记录组合成一棵单独的树（可能需要添加一个人工根节点）。由于这个过程相当简单，我们不再进一步讨论。
部分树对齐：每个数据区域中所有数据记录的标签树都使用我们的部分对齐方法进行对齐，该方法基于树匹配。需要注意的是，在匹配过程中，我们仅使用标签，不涉及数据项。接下来，我们首先简要介绍树编辑距离或树匹配，然后介绍本工作中使用的受限树匹配方法。之后，我们将讨论多重对齐，并介绍基于标签树对多个数据记录进行部分树对齐的方法。

在这里需要指出的是，字符串编辑距离在这一步骤中并不适用，因为字符串没有考虑树结构，而树结构对于确定数据项的正确对齐非常重要。由于两个字符串的多个对齐可能导致相同的编辑距离，字符串对齐可能会产生许多错误。而且，由于大多数用于形成数据记录的标签是tr和td，通过字符串匹配很难确定正确的对齐方式，因为有许多可能的对齐方式。然而，树匹配由于树结构约束，显著减少了可能的对齐方式数量。在我们的算法中，我们只使用一个简单的规则来解决存在多个可能的树对齐时的冲突。我们简单地选择最早出现在树中的可能子树对齐。这种方法在我们的实验中表现得非常好。因此，我们没有设计更复杂的冲突解决策略。

4.1、树编辑距离

类似于字符串编辑距离，两个树A和B之间的树编辑距离[31, 30]（我们只关注带标签的有序根树）是将A转换为B所需的最小操作集的相关成本。在经典的定义中，用于定义树编辑距离的操作集包括三种操作：节点删除、节点插入和节点替换。通常为每个操作分配一个成本。解决树编辑距离问题通常通过找到两个树之间的最小成本映射来辅助完成[30]。映射[30]的概念在正式定义上如下：

假设X是一棵树，X[i]是树X的第i个节点，根据树的前序遍历。树A的大小为n1，树B的大小为n2，映射M是一组有序对(i, j)，每个来自树的一个节点，对于所有的(i1, j1), (i2, j2) ∈ M，满足以下条件：

（1）i1 = i2当且仅当j1 = j2；
（2）如果A[i1]在A[i2]的左侧，那么B[j1]在B[j2]的左侧；
（3）如果A[i1]是A[i2]的祖先，那么B[j1]是B[j2]的祖先。

直观地说，该定义要求每个节点在映射中最多出现一次，并且保留了兄弟节点之间的顺序和节点之间的层次关系。图8展示了一个映射的示例。

已经提出了几种算法来解决找到将一棵树转换为另一棵树所需的最小操作集（即成本最小）的问题。所有的表述都具有二次以上的复杂性[10]。还证明了如果树没有顺序，问题是NP-complete的[36]。在[30]中，提出了一种基于动态规划的解决方案。该算法的复杂度为O(n1n2h1h2)，其中n1和n2是树的大小，h1和h2是树的高度。在[32][10]中，还提出了另外两个具有类似复杂度的算法。

4.2、简单树匹配

在上述一般设置中，映射可以跨越层级，例如树A中的节点a和树B中的节点a。还存在替换，例如A中的节点b和B中的节点h。在本工作中，我们使用了一种受限制的匹配算法[35]，该算法最初用于比较软件工程中的两个计算机程序，被称为简单树匹配（STM）。STM通过动态规划生成最大匹配来评估两个树的相似性，其复杂度为O(n1n2)，其中n1和n2分别为树A和B的大小。不允许进行节点替换和层级交叉。

设A和B为两棵树，i ∈ A，j ∈ B为A和B中的两个节点。树之间的匹配被定义为一个映射M，对于M中的每对(i, j)其中i和j为非根节点，有(parent(i), parent(j)) ∈ M。最大匹配是具有最大配对数的匹配。

设A = <RA, A1, A2,…, Am>和B = <RB, B1, B2,…, Bn>为两棵树，其中RA和RB为A和B的根节点，Ai和Bj分别为A和B的第i个和第j个一级子树。当RA和RB包含相同的符号时，A和B之间的最大匹配是MA,B+1，其中MA,B是<A1, A2,…, Am>和<B1, B2,…, Bn>之间的最大匹配。MA,B可以通过以下动态规划方案获得：

如果Am和Bn之间的最大匹配大于Am和Bi（1≤i<n）之间的任何最大匹配，则MA,B是<A1, A2,…, Am-1>和<B1, B2,…, Bn-1>之间的最大匹配加上Am和Bn之间的最大匹配。
否则，MA,B与<A1, A2,…, Am>和<B1, B2,…, Bn-1>之间的最大匹配相同，或者与<A1, A2,…, Am-1>和<B1, B2,…, Bn>之间的最大匹配相同。

在图9中的Simple_Tree_Matching算法中，首先比较A和B的根节点（第1行）。如果根节点包含不同的符号，则两棵树完全不匹配。如果根节点包含相同的符号，则递归地找到A和B的一级子树之间的最大匹配，并将其保存在W矩阵中（第8行）。基于W矩阵，应用动态规划方案来找到两棵树A和B之间最大匹配中的配对数。

算法伪代码: Simple_Tree_Matching(A, B)

if the roots of the two trees A and B contain distinct symbols 
  then return (0); 
else m:= the number of first-level sub-trees of A; 
  n:= the number of first-level sub-trees of B; 
  Initialization: M[i, 0]:= 0 for i = 0, …, m; 
                  M[0, j] := 0 for j = 0, …, n; 
  for i = 1 to m do 
    for j = 1 to n do 
      M[i,j]:=max(M[i,j-1], M[i-1, j], M[i-1, j-1]+W[i, j]); 
        where W[i,j] = Simple_Tree_Matching(Ai, Bj) 
    endfor; 
  endfor; 
  return (M[m, n]+1) 
endif

我们使用[35]中的一个例子来解释算法（图10）。为了找到树A和B之间的最大匹配，首先比较它们的根节点N1和N15。由于N1和N15包含相同的符号，返回M1-15[4,2]+1作为树A和B之间的最大匹配值（第11行）。M1-15矩阵是基于W1-15矩阵计算的，而W1-15矩阵中的每个条目，例如W1-15[i, j]，是树A和B的第i个和第j个一级子树之间的最大匹配，它是基于其M矩阵递归计算的。例如，通过构建矩阵(E)-(H)，递归计算出W1-15[4, 2]。所有相关的单元格都被阴影标记。M矩阵中的零列和零行是初始化。请注意，我们在M和W矩阵中都使用下标来指示它们所操作的节点。

在匹配过程（或匹配之后），我们可以回溯到M矩阵中，找到两个树中匹配/对齐的节点。当一个节点有多个匹配结果时，我们选择在树中出现最早的匹配。例如，在图11中，树A中的节点c可以匹配树B中的第一个节点c或最后一个节点c。我们选择树B中的第一个节点c。这种启发式方法是因为在Web页面中为了视觉效果，如果树A中的较早节点x与树B中的较晚节点y匹配，通常会有一些指示（标签）出现在x之前。根据我们的实验，这种启发式方法效果很好。

4.3、多对齐

由于页面中的每个数据区域都包含多个数据记录，我们需要对多个标签树进行对齐，以便在表的同一列中生成一个包含所有相应数据项/字段的单个数据库表。在这个数据表中，每一行代表一棵树（数据记录），每一列代表每个数据记录中的一个数据字段。存在几种现有算法可以执行多个序列/树的赋值。在[6]中，提出了一种使用多维动态规划的多重对齐方法。该方法是最优的，但其时间复杂度呈指数级增长，因此不适合实际使用。还提出了许多启发式方法[24, 17, 3]。在[8]中使用的居中字符串方法是一种特殊的启发式方法，用于多个序列的对齐，也可以用于树的对齐。在这种方法中，选择一个序列xc，使得（D(xi, xc)代表两个字符串的距离）的值最小。

$$
\sum_{k}^{i=0}D(x_i,x_c)
$$

然后，针对每对(xi, xc)，其中i ≠ c，执行一对一的对齐操作。假设有k个序列，且所有序列的长度为n，寻找中心序列的时间复杂度为O(k^2n^2)，而每一步的迭代一对一对齐操作的时间复杂度为O(n^2)。因此，总体的时间复杂度为O(k^2n^2)。类似地，我们可以找到一个中心树Tc，并将所有其他树与Tc对齐。这种技术存在两个主要缺点：首先，尽管该算法具有多项式时间复杂度，但对于包含许多数据记录或包含许多属性的数据记录的页面，其运行速度较慢。其次，如果中心树没有特定的数据项，那些包含相同数据项的其他数据记录将无法对齐。我们实施了这种方法，但结果很差。其他流行的多重对齐方法包括渐进对齐[17]和迭代对齐[3]。它们的工作原理类似于分级聚类，并且都需要提前进行O(k^2)的一对一匹配。对于我们的任务，我们可以做得更好，因为我们知道数据记录遵循某些预定义的模板。

4.4、部分树对齐

我们提出的方法通过逐步扩展种子（标签）树来对齐多个标签树。种子树记为Ts，最初选择具有最多数据字段的树作为种子树。需要注意的是，种子树类似于中心树，但不需要进行O(k^2)的一对一树匹配来选择。选择这棵种子树的原因很明确，因为这棵树更有可能与其他数据记录中的数据字段良好对齐。然后，对于每个Ti（i ≠ s），算法试图为Ti中的每个节点找到与Ts中的匹配节点。当找到节点ni的匹配时，在ni和ns之间创建一个链接，表示在种子树中的匹配。如果找不到节点ni的匹配，则算法尝试通过将ni插入到Ts中来扩展种子树。扩展后的种子树Ts随后用于后续匹配。需要注意的是，在匹配或对齐过程中不使用标签树节点中的数据项。

4.4.1、两棵树的部分树对齐

在介绍完对齐多个树的完整算法之前，让我们先讨论一下两个树的部分对齐的概念。如上所述，在Ts和Ti匹配之后，Ti中的一些节点可以与Ts中对应的节点对齐，因为它们互相匹配。对于那些未匹配的Ti中的节点，我们希望将它们插入到Ts中，因为它们可能包含可选的数据项。当从Ti中插入一个新节点ni到种子树Ts时，可能存在两种情况，取决于能否确定在Ts中唯一的位置来插入ni。事实上，我们不仅考虑单个节点ni，还可以一起考虑Ti中一组未匹配的连续兄弟节点nj…nm。不失一般性，我们假设nj…nm的父节点在Ts中有一个匹配，并且我们希望将nj…nm插入到Ts中的相同父节点下。只有当可以在Ts中唯一确定插入nj…nm的位置时，我们才会将它们插入到Ts中。否则，它们将不会被插入到Ts中，保持未对齐状态。因此，这种对齐是部分的。插入nj…nm的位置可以唯一确定在以下情况下：

如果nj…nm在Ti中有两个相邻的兄弟节点，一个在右侧，一个在左侧，它们与Ts中的两个连续兄弟节点匹配。图12(A)展示了这样的情况，其中给出了Ts的一部分和Ti的一部分。我们可以看到Ti中的节点c和节点d（连续的兄弟节点）可以插入到Ts的节点b和节点e之间，因为Ts和Ti中的节点b和节点e是匹配的。新的（扩展的）Ts也在图12(A)中显示。需要注意的是，节点a、b、c、d和e也可能有它们自己的子节点，但我们没有绘制它们以节省空间。以下所有情况都适用于此。
如果nj…nm在Ti中只有一个左侧相邻节点x，并且x与Ts中最右侧的节点x匹配，那么nj…nm可以插入到Ts中的节点x之后。图12(B)说明了这种情况。
如果nj…nm在Ti中只有一个右侧相邻节点x，并且它与Ts中最左侧的节点x匹配，那么nj…nm可以插入到Ts中的节点x之前。这种情况与上述情况类似。

否则，我们无法唯一确定Ti中未匹配节点插入Ts的位置。这在图12(C)中有所说明。在这种情况下，Ti中未匹配的节点x可以插入到Ts的两个位置之间，即节点a和节点b之间，或者节点b和节点e之间。在这种情况下，我们将不会将其插入到Ts中。

4.4.2、完整算法

图13给出了基于两个标签树部分对齐的多树对齐的完整算法。

我们在图14中使用一个简单的示例来解释算法。我们有三个示例树，它们都只有两个层级。

第1行和第2行（图13）基本上是找到具有最多数据项的树，这就是种子树。在图14中，种子树是第一棵树（我们省略了T1左侧的许多节点）。第3行进行一些初始化操作。第4行开始while循环，对每个未对齐的树与Ts进行对齐。第5行选择下一个未对齐的树，第6行进行树的匹配。第7行通过追踪第6行的矩阵结果找到所有匹配的节点对。这个过程类似于使用编辑距离对齐两个字符串。我们不会进一步讨论这个问题。注意，第5行和第6行可以集成在一起。为了简单起见，我们将它们分开展示。在图14中，Ts和T2产生一个匹配，即节点b。节点n、c、k和g未与Ts匹配。第8行进行检查。第9行尝试将它们插入Ts，这就是上面讨论的部分树对齐。在图14中，T2中的节点n、c、k和g都无法插入Ts，因为找不到唯一的位置。第14行将T2插入R，R是可能需要进一步处理的树的列表。在图14中，当将T3与Ts进行匹配时，所有未匹配的节点c、h和k都可以插入Ts。因此，T3将不会被插入R。第14-16行设置“flag = true”以指示找到了一些新的对齐/匹配，或者插入了一些未匹配的节点到Ts中。

第17-21行检查停止条件。“S = ∅ and flag = true”表示我们已经处理了S中的所有树，并且找到了一些新的对齐或插入操作。然后应该再次处理R中的树。在图14中，R中只有T2，它将与下一轮中的新Ts进行匹配。现在T2中的每个节点都可以匹配或插入。过程完成。第23行根据生成的对齐结果输出每个树的数据项。请注意，如果算法完成后仍然存在未匹配的节点和数据，那么每个未匹配的数据将占据单独的一列。表1显示了图14中树的数据表。我们使用“1”表示一个数据项。

该算法的复杂度在不考虑树匹配的情况下为O(k^2)，其中k是树的数量。然而，在实践中，我们几乎总是只需要遍历S一次（即R = ∅）。

应注意，生成的对齐结果Ts还可以用作从使用相同模板生成的其他页面中提取数据项的提取模式。

5、实验评估

本节评估了我们的系统DEPTA（基于部分树对齐的数据提取），该系统实现了提出的技术。评估分为两个部分：

数据记录提取（步骤1）：我们将DEPTA的第一步（也称为MDR-2）与我们现有的系统MDR进行比较，以确定数据记录。在这里，我们不将其与[5]和[8]中的方法进行比较，因为[21]表明MDR已经比它们更有效。
数据项/字段对齐和提取（步骤2）：这是DEPTA的第二步。[8]能够执行相同的任务。然而，正如[21]所示，它在找到正确的数据记录方面表现不佳，因此无法很好地提取数据项。我们不与[1][12]中的系统进行比较，因为它们需要多个页面，并且所有页面都包含类似的数据记录以从页面中提取模式。[20]中的技术需要页面背后的详细信息页面（待提取页面），在他们的实验中，这些详细信息页面是手动识别和下载的，这在实践中是不现实的。DEPTA更加通用。给定单个页面，它能够从中提取数据记录和数据项。

我们的实验结果如表2所示。

第1列：列出了每个站点的URL。在某些站点上尝试了多个页面（具有不同的数据记录格式）。我们在实验中使用的站点数量为49。使用的页面总数为72。我们的实验Web页面是随机收集的。由于大多数页面的URL较长，我们无法在此列出它们。我们将在我们的网站上发布所有测试页面的URL。

第2列和第4列：它们分别给出了MDR和MDR-2（DEPTA的步骤1）从每个站点的页面中提取的正确（Cor.）记录数。这些数据记录是页面中明显的记录（例如产品列表）。它们不包括导航区域，这些区域也可能具有规律的模式。请注意，尽管MDR-2框架能够处理嵌套的数据记录（记录中的记录），但在这项工作中我们没有明确处理此类数据记录，因为在记录列表中它们相对较少。我们将在未来添加这一点。提出的部分树对齐方法能够对齐嵌套记录中的数据项。

第3列和第5列：它们分别给出了MDR和MDR-2（DEPTA的步骤1）从每个站点的页面中错误提取的数据记录数。x/y表示提取结果中有x个是不正确的，y个是未提取的。

第6列和第7列：它们分别给出了DEPTA的第2步从每个站点的数据记录中提取的正确数据项和错误数据项的数量。具有错误对齐的提取的数据项也被视为错误。

表2的最后三行给出了每列的总计，以及每个系统的召回率和精确度。对于MDR和MDR-2（DEPTA的第1步），召回率和精确度是基于在所有页面中找到的正确数据记录总数和这些页面中实际数据记录的数量计算的。对于DEPTA的数据项提取，精确度和召回率的计算考虑了因DEPTA的第1步导致的20个丢失的数据记录。

我们可以看到，数据提取非常有效。几乎所有的错误都是由于数据记录提取引起的。我们还观察到，MDR-2的性能明显优于MDR。

6、结论和未来工作

在本文中，我们提出了一种从网页中提取结构化数据的新方法。尽管这个问题已经被几位研究人员研究过，但现有的技术要么不准确，要么做出了许多强假设。我们的方法不做这些假设，只需要页面包含多个数据记录，而对于包含数据记录的页面来说，这几乎总是成立的。我们的技术包括两个步骤：（1）在不提取数据记录中的每个数据字段的情况下识别数据记录，以及（2）对多个数据记录中的相应数据字段进行对齐，以从中提取数据并放入数据库表中。我们针对步骤（1）提出了一种基于视觉信息的增强方法，显著提高了我们之前算法的准确性。对于步骤（2），我们提出了一种新颖的部分树对齐技术，用于对齐多个数据记录的相应数据字段。使用大量网页的实证结果表明，这种新的两步技术能够非常准确地分割数据记录并从中提取数据。