英语原文共 21 页，剩余内容已隐藏，支付完成后下载完整资料

在领域专用语言中对生成语法分析和积优化的动态规划

Georg Sauthoff¹, Robert Giegerich²

¹(Universitauml;t Bielefeld, Technische Fakultauml;t, 33501 Bielefeld, Germany)

²(b Universitauml;t Bielefeld, Technische Fakultauml;t and Center of Biotechnology, 33501 Bielefeld, Germany)

摘 要：动态规划算法传统上是用一组矩阵递归来表示的，这是一种低层次的抽象，使得动态规划的设计具有新颖性。算法很困难，调试也很麻烦。BellmansGap是一种声明性的特定于领域的语言，它支持对序列数据进行动态编程。它实现了动态编程的代数风格并允许通过将所谓的生成语法与评估代数相结合来指定算法。代数上的积允许从已经存在的给定的，不修改测试组件。贝尔曼的差距扩大了前一个代数动态规划的几个概念，如“交错”产品运作与多道输入分析。为了从代数规范生成有效的命令式代码，需要对生成语法和评估代数进行广泛的分析。本文概述了对所需的分析进行了详细介绍。使用“realworld”应用程序进行的测量显示了生成的代码的质量。

关键词：代数动态规划 特定于域的语言 规则树语法 编译器优化 RNA结构预测

1 引 言

动态规划算法设计中的挑战

动态规划（DP）是一种成熟的编程技术，适用于多种组合方法。优化或枚举问题。它的根源可以追溯到理查德贝尔曼的工作[1]，当时数学“程序”仍然由一个人执行。今天，它是许多计算机科学教科书的主题。教育的在许多介绍性文本中都有这样的例子：字符串编辑距离、矩阵链乘法、背包问题、具有最佳预期访问时间的二进制搜索树、El Mamun的商队或Fibonacci数字。因为它们很简单，这些例子问题可以用一个整体的方式很好地解释。一个具有两种或三种情况区分的单一递推关系足以描述问题分解、解决方案候选项的评分和选择。一个最优解。在实施过程中，有必要将子问题的解决方案制成表格，以便日后重复使用；问题分解逻辑中的自顶向下递归让位给了由forloops控制的自下而上的计算。如果在最佳分数后面的解决方案候选也很感兴趣，则需要对回溯进行编码。讨论Bellman的最优性原理非正式地描述了可以用动态编程处理的问题的范围。

这种简单性是欺骗的原因有几个：

1. 在实际的应用场景中，我们可能会有数十个，有时是数百个重复发生，并且在问题分解中需要区分一组更大的情况。由于空间原因，所有这些重复出现的表格都是禁止的，问题是哪些需要（不需要）表格，同时保持最佳的渐进效率。这就引出了一个NP完全问题[2]，这个问题在小教科书例子的研究中是不可见的。
2. 通常，在不同的评分方案或目标函数下分析相同的搜索空间，或者对修改后的搜索空间应用相同的评分。当在传统的for循环中进行编码时，搜索空间结构和候选评估的紧密纠缠是程序员工作效率的主要障碍。
3. 动态编程重现的调试实现，其中案例分析被编码成几十个下标计算，是一个非常困难的任务。（例如）（i 1，j）而不是（i，jminus;1）的微小错误可能偶尔会导致错误（次优）答案，并且很可能在很长一段时间内被忽视。
4. 回溯最优分数后的解决方案的代码在生成和调试时都很繁琐。更重要的是，当所有共同最优或某些接近最优的解（达到一个阈值）都要生成时。
5. 当使用诸如隐马尔可夫模型（hmms）或随机上下文无关文法（scfgs）[3]等随机模型时，必须确保案例分析以非模糊的方式覆盖搜索空间。这个问题是正式的不可判定的（4），并且没有支持“GracMARWORD”，这个属性对于算法设计者来说是很难建立的。

总之，虽然DP的基本思想很容易理解，但对于大型的现实问题，支持是可取的，这有助于在更抽象的层次上指定问题，并避免处理实现细节。

生物序列分析中的动态规划

生物信息学是一个动态规划普遍存在、模型复杂、数据量大的领域。动态规划的一个核心问题是蛋白质、DNA和RNA序列的比较。这个问题存在于许多变体中（不同评分方案和GAP模型下的全局比对和局部比对），将一个序列与一个轮廓对齐，预测基因的内含子/外显子结构，评估质谱数据，重建重复序列的重复历史，所谓的小卫星，等等。蛋白质序列家族或结构（非编码）RNA分别通过HMMS和SCFGS建模。我们对动态规划的兴趣来自于RNA二级结构预测领域，在那里我们创建了许多最先进的工具[5]，我们将在本研究中用于效率测量。

以前支持动态编程的方法

由于在生物序列分析中的多种应用，该领域引入了两种早期的方法来支持序列数据上动态规划算法的设计和实现。炸药系统[6]模型作为状态转换与相关计分函数重复出现。多次重复会导致一个状态的几个子字段。C代码是从状态转换表自动生成的。

接下来的工作是电报系统[7]，为动态编程提供了一个面向对象的模板库，力求更大的灵活性。它包括一些从函数编程中得到启发的特性，例如绑定到用户指定函数的模型参数。然而，这些想法尚未达到稳定的实施状态。具有类似目标的纯函数方法导致了用于表示动态编程算法的组合语言[8]，该组合语言后来发展为下面描述的代数方法。

伯德和德摩尔将动态规划（对于单一的递推）作为一种关系演算。Stagingdp[10]提供了另一个组合程序库来支持动态编程。Morihata利用动态编程的成分，最近研究了从na_ve枚举和选择样式规范中自动派生高效算法[11]。

在上述设置中，输入序列的问题分解可以看作是一个相对简单的、无上下文的解析问题。在自然语言处理社区中，对更一般的语法类的更复杂的解析算法的发展有着浓厚的兴趣。这是由Dyna语言[12]支持的，该语言最初基于数据日志样式的前向链接方案，允许程序员专注于解析算法的逻辑，而不是它们的实现。Dyna语言最近的升级远远超出了这个范围，我们将在下面回到它。

不幸的是，在上述所有情况下，必须说，这些方法在创建者手中都很有效，但抽象性的收益似乎不足以让其他人证明采用新方法的设置成本，而且这些方法没有找到更广泛的用途。

代数动态规划（ADP）[13]是从[8]中基于Haskell的组合语言发展而来的一门独立于语言的形式主义。它是一种声明性方法，与前面提到的方法相比，它实现了搜索空间分解、候选评分和制表问题的完美分离。它的第一个实现是在Haskell中嵌入的特定于域的语言。为了提高效率，开发了一个将Haskell嵌入式ADP代码转换为C的编译器[14,15]，并逐步增加了越来越多的优化。

作为一个概念框架，ADP可以看作是半环解析框架的简化和扩展。[16，17]。半环是具有两个运算的数据类型，它是相联的和交换的，是相联的和分布的。主要的简化是双重的：虽然半环框架允许解析器从循环派生计算无限和，但ADP忽略无限和，禁止循环语法。虽然半环解析允许人们表达和研究许多不同的解析技术，但是我们的方法（到目前为止）只支持两种形式的解析。

随着我们的框架在下面的发展，扩展和进一步的差异将变得清晰；主要的扩展和进一步的差异如下：在ADP中，单个操作被分解成一系列（抽象）函数，由许多排序数据类型的签名指定。这些函数不限于二进制。目标函数是在多组值上定义的，必须遵守贝尔曼原理，对于所有其他函数，这是简单半环情况下的分布要求。半环解析中的上下文无关语法被一个（规则的）树语法所取代，该树语法作为其生成语言生成与上下文无关语法相同的上下文无关语言。但是，解析不会生成派生树，而是实际表示搜索空间中的解决方案候选的树，表示为从签名函数构建的公式。它们独立于产生它们的语法；不同的语法可以构造相同的搜索空间。

这从概念上将解析与搜索空间评估分离。候选树从未明确构建。在实现中，这两个阶段合并在一起，但源代码中没有。这允许我们定义不同类型的独立于语法的评价代数、代数上的积等。这是一个软件技术优势，因为相同的代数可以用于不同的语法，并且一个语法可以使用多个代数或其积。由于这样的模块化，支持组件的再使用。除了这些概念上的变化之外，还有许多语用扩展，这些扩展是由我们的应用场景驱动的，例如语法规则的句法和语义谓词、多道输入和空间优化，这些优化只针对语法的一个子集非终结符。

来自Haskell的Ex-bedding ADP

最初，haskell嵌入的ADP实现允许我们在相对较短的时间内开发出几种新的生物信息学工具，但这种方法在其他人手中却没有用处。主要的障碍似乎是haskell回忆ADP代码的语法，这是生物信息学家在他们大多数人看来厌恶的。除了关注用户接受度之外，现有的编译器很难从ADP理论中扩展到新的概念，ADP理论是在其使用的最初几年中发展起来的。这促使从头开始重新实现，包括扩展。其结果是贝尔曼的GAP编程系统，以其基本核心概念命名，即贝尔曼的最优性原理、语法、代数和积。

Bellman的GAP系统在其目前的状态下是经过十年的研究和开发动态编程领域特定语言的经验的结果。虽然本文主要讨论将dp算法的声明性规范转化为有效代码所需的特定于域的优化，但我们将以Bellmans Gap为例，对特定于域的语言开发进行进一步的研究。

BellmanGAP系统概述

行李员的GAP系统最近才推出[20]。读者对GAP-L语言的外观和感觉感兴趣，并对与Bellmans Gap有关的程序开发的介绍性示例有兴趣，请参阅该文章，因为本论文的贡献集中在编译问题上，扩展了在[21]中的贡献。

BellmanGAP由以下组件组成：

• GAP-L-声明语言，具有C/Java风格的语法，允许一个代数风格指定动态编程算法，
• GAP-L语义，根据语法、代数和产品定义GAP-L程序的含义，
• GAP-C编译器，它将GAP-L程序翻译成C ，
• GAP-M-A用于再利用的模块库，主要用于生物序列分析领域。
• gap-pages——一组教育网页，在其gap-l版本中显示动态编程的简单示例。

本文主要研究了从特定领域语言GAP-L到命令式代码的编译过程中出现的优化问题。这些问题与常见的编译器优化非常不同，后者通常在执行时间中处理常量因子。例如，在这里，编译器负责以最佳可能的渐进效率实现GAP-L程序，并生成大量包含通用DP技术的代码。我们在第2节中简要介绍了代数动态规划的背景知识。我们将在第3节中描述语法分析和基于它的优化。第4节讨论代数产品的优化实现。最后，第5节通过使用GAP-L重新实现的生物信息学应用程序进行测量来证明生成的代码的质量。第6节将讨论Bellman的GAP作为特定领域语言的发展，并概述未来的一些研究问题。

2 贝尔曼间隙代数动态规划

2.1 语法

代数动态规划的一种新的Java形式的具体语法的设计是贝尔曼间隙发展中的一个主要问题。然而在本文中，由于缺乏空间，我们没有描述gap-l的具体语法，因为bellman gap程序背后的语义概念足以解释我们的语法分析技术。读者对GAP-L程序的具体外观感兴趣，请参阅[20,22]。这里，我们将使用一个图形符号作为示例。在本节中，我们首先回顾了[13]之后ADP的基本定义，继续进行Bellmans Gap中的扩展，并提供一个玩具应用示例，稍后将使用和扩展。

2.2 语义

基本概念 让A表示要分析的字符串或序列的字母表。A上的签名sum;是一个数据类型占位符（sort）X和一组函数符号。每个函数符号的返回类型是x，每个参数都是x或a类型。tsum;表示签名sum;描述的术语语言，tsum;（v）表示集合v中变量的术语语言。一个代数或解释I是由x的载波集Xi给出的数学结构，并且在这个集合上操作函数Fi，并且在A上，根据它的签名，在每个F*中给出一个数学结构。用代数I解释一个术语t*t，表示I（t）并在Xi中产生一个值。

符号sum;上的正则树语法G定义为元组（sum;V，A，Z，P），其中V是非终结集，A是字母表，Zisin;V是公理，P是生成集。每一个作品都是形式的

v → t with v isin; V , t isin; TSigma;(V ) (1)

树语法G生成的语言是一组树

L(G) = t isin; TSigma; Z rArr;lowast; t (2)

其中，？是→的反身、传递闭包。通过构造，l（g）tsum;-其元素在构造时被视为树，在评估时被视为公式。

来自a的符号驻留在这些树的叶子上。符号Y表示屈服函数，类型为Tsum;→A。定义为y（a）=a，其中aisin;a和y（f（x1，hellip;，xn））=y（x1）hellip;hellip;y（xn），对于sum;和n 0中的f。树语法G的生成语言ly（g）定义为

Ly(G) = y(t) t isin; L(G) (3)

搜索空间结构。树语法在我们的上下文中被称为生成语法，因为我们面临一种特殊的解析问题：给定xisin;a，我们构造搜索空间s（x）=t tisin;l（g），y（t）=x。这个计算y的倒数的过程叫做收益解析。yield解析器的工作本质上类似于一个不依赖上下文的解析器2，它返回的树不是解析树，而是tsum;的元素——s（x）中的候选解决方案。BellmansGap的用户不需要关心收益解析是如何工作的。

候选人评估和选择。评价代数E是一个sum;-代数，用一个目标函数He:[Xe]→[Xe]进行扩充，其中方括号表示多集（理论上，在实践中列出）。目标函数他通常被称为选择函数，例如，当它在多个候选值集上最大化或最小化时。但是，在应用程序中，总结、枚举或抽样也是目标。GAP-L包括一种简单的语言，用于在数字和字符

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[20275]，资料为PDF文档或Word文档，PDF文档可免费转换为Word