析取程序合成：一种通过示例编程的健壮方法( 二 ) 摘要通过示例编程（PBE）系统

我们考虑来自 Web 提取领域的另一个示例。在这个领域中，用户的提取任务可能是从结构化 HTML 文档中提取特定数据字段，例如从包含航班行程的电子邮件中提取航班号。在现有的用于 Web 提取的 PBE 系统中，用户可以通过在几封电子邮件中提供所需字段的示例来执行此任务，然后系统将基于这些语言合成节点选择表达式作为 XPath 或 CSS 选择器，以提取 HTML DOM 中的节点。例如，假设所需字段的用户示例是以下的 SPAN 元素节点：
BA052挑战在于选择示例节点的哪些属性要包括或排除在节点选择逻辑中，因为不知道这些属性中的哪些会在其他输入中发生变化。例如，在上述情况下，我们可以在选择逻辑“颜色为灰色”（P1）， “类别为 c1”（P2）或更严格的两个属性“颜色为灰色且类别为 c1”之间进行选择（P3）。排名方案通常选择保守，并选择最具体的逻辑，但是这些逻辑往往会施加太多约束并过度拟合，因此无法在新输入上返回任何结果。选择更通用的逻辑具有丢失重要属性和识别不正确节点的陷阱。
因此，我们再次观察到，使用分离方法在合成程序中维护一组这些不同的可能逻辑，并且仅在执行时有新输入可用时才在它们之间进行选择将是有益的。例如，程序可以首先尝试最具体的逻辑，如果该程序无法返回任何结果，则可以尝试使用限制性较小的逻辑。但是，这种情况下的另一个问题是，可能的逻辑集随着节点可能具有的属性数量呈指数增长，因为谓词的可能合取对应于所有可能的子集。就学习算法的性能以及所学习程序的大小和执行时间而言，将所有这些可能性包括在析取程序中都是不可行的。在这项工作中，我们描述了一种计算最大值（最具体）的技术以及一组满足示例提取并同时覆盖示例节点的所有属性的最小（最小限制性）程序的技术。我们展示了如何通过合成算法选择覆盖所有观察到的特性的这些候选对象作为有效析取函数，以产生有效且健壮的析取程序。
我们的析取合成方法背后的核心思想是，通过在最终程序中保持多个析取关系，将最佳程序的选择过程从合成阶段的排名转移到程序本身的语义上。我们在实现此想法时面临的主要挑战是确定要包含哪些析取物的技术，以及在执行时决定析取物之间选择的选择机制的性质。这些设计选择以正确性和程序性能为目标。尽管文本和 Web 应用程序域的析取方法已经有了具体实现，在这项工作中，我们还提出了一个通用框架，在该框架中可以扩展任意 DSL 和综合算法以支持析取程序的学习，并且制定了所需的组件。
在下一部分中，我们将从 DSL 的一般形式开始，并介绍基于标准正则表达式和 CSS 选择器语言的文本和 Web 域的具体 DSL 。然后，我们描述了支持析取程序的任意 DSL 所需的扩展，并通过对文本和 Web DSL 进行析取式扩展来说明这一点。在接下来的部分中，我们将描述通用合成算法以及该算法针对特定 DSL 的特定于域的组件的实现，然后我们将使用从产品团队获得的一组提取方案对我们的技术进行评估。我们通过考虑可以从单个示例中学习到正确程序的场景的数量来说明鲁棒性的提高，并说明从非析取案例到析取案例，如何将其从 59.6％提高到 93.6％。我们最后讨论了相关工作和结论。
文章插图
文本提取：图 2 显示了用于文本操作的 DSL ，它基于 Flash 填充语言，使用正则表达式进行字符串处理。
文章插图
文章插图
Web 提取：图 3 显示了用于从 HTML 文档提取节点的 DSL 。在这种情况下，输入 inp 是整个 HTML 文档的 DOM 树，任何完整程序的输出 n 都是该树中的特定节点，例如引言中所述的提取任务，在航班行程中包含航班号的节点。
文章插图
文章插图
文章插图
文章插图
文章插图