在前文中, 我们谈到了定义在半环上的动态规划及其适用范围, 以及动态规划在图模型中的一些应用。本文我们将沿着这个思路继续探索, 并把目光从图模型转向树结构. 我们首先提出以下几个问题:
Problem 1.1
试判定一个字符串是否属于一个上下文无关文法生成的语言.
Problem 1.2
给定一个字符串和一个随机上下文无关文法 (PCFG) , 则按照 PCFG 中的某个生成方式生成该字符串会有一个概率 p . 试求 p 的最大值.
本文将对上述问题展开讨论. 在涉及分析树的内容之前, 我们先对前文的内容做一个小小的总结, 之后我们解决上述的两个问题. 除此之外, 我们还将提及一个数据库系统中的查询模型. 笔者的研究不涉及数据库领域的很多内容, 对这个模型的理解也比较粗浅, 在这里只是提供一个树结构上的算法思路.
Problem 2.1
现在有一个数据库系统, 其中不同的机器存储不同的数据. 试设计一个查询系统, 使得用户可以在最短的时间内查询到特定的数据被存储在哪个机器.
Problem 2.2
弱化Problem 2.1的需求. 现在我们查询特定的数据后, 允许得到一个机器的列表, 只要列表中存在一个机器存有我们所需的数据即可. 试优化这个查询系统.
Problem 1.1
试判定一个字符串是否属于一个上下文无关文法生成的语言.
Problem 1.2
给定一个字符串和一个随机上下文无关文法 (PCFG) , 则按照 PCFG 中的某个生成方式生成该字符串会有一个概率 p . 试求 p 的最大值.
本文将对上述问题展开讨论. 在涉及分析树的内容之前, 我们先对前文的内容做一个小小的总结, 之后我们解决上述的两个问题. 除此之外, 我们还将提及一个数据库系统中的查询模型. 笔者的研究不涉及数据库领域的很多内容, 对这个模型的理解也比较粗浅, 在这里只是提供一个树结构上的算法思路.
Problem 2.1
现在有一个数据库系统, 其中不同的机器存储不同的数据. 试设计一个查询系统, 使得用户可以在最短的时间内查询到特定的数据被存储在哪个机器.
Problem 2.2
弱化Problem 2.1的需求. 现在我们查询特定的数据后, 允许得到一个机器的列表, 只要列表中存在一个机器存有我们所需的数据即可. 试优化这个查询系统.
超图(Hypergraph)
我们已经在“ 舞动在半环上的 ‘动态规划’ ” 和 “从动态规划到 ‘k最优Dijkstra算法’ ”两篇文章中详细地探讨了动态规划在半环上的定义及适用范围, 以及动态规划的一些应用. 现在我们把之前谈及的几个算法按照模型的结构做一个简单的分类.
第一类是基于列表结构的动态规划, 主要的例子有最长公共子序列 (LCS) 等. 在这种结构下我们可以非常清晰地看到拓扑顺序, 在其上设计一个状态转移(状态合并)的方法即可. 我们再举几个典型的问题, 供大家思考. 注意在设计算法时, 要保证状态合并前后单调性仍然保持.
Problem 3.1.1
试求两个字符串的最长公共上升子序列 (LICS) .
Problem 3.1.2
给定三个字符串, 试求前两个字符串的最长公共子序列, 要求该子序列 s 不含第三个字符串作为 s 的子序列. (LCS w/o. subseq)
Problem 3.2.1
试求一个数组中连续 k 个数的和的最大值.
Problem 3.2.2
试求一个矩阵中行列连续的子矩阵中数的和的最大值.
第二类是基于复合链式模型的动态规划, 主要包括维特比 (Viterbi) 算法适用的一些问题, 主要包括求最优链的问题. 这类问题中不同的链有一些公共的节点, 但是整个空间仍然保持拓扑结构, 因此可以使用 Viterbi 算法按照拓扑层次求解. 从路径的角度来讲, 任意一个没有前驱的节点都可以作为起点, 任意一个没有后继的节点都可以作为终点. 这是一个典型的交错链表.
第三类是基于图模型的动态规划, 主要包括计算最短路径 (第 k 短路径) 和最小生成树的一些算法. 注意这类问题的本质有所区别. 一部分是定义在优幂等半环上的问题 ("事情总是会变得越来越差"), 另一部分模型不具有优幂等的属性, 因此设计状态转移时会略微复杂一些, 以保证状态合并不改变单调性. 有负权边的最短路径问题属于后者.
现在我们继续扩展, 给出超图的定义. 一个超图 (hypergraph) 的节点和图的节点类似, 超图的边 (hyperedge) 是多个节点的集合. 也就是说, 在图中每条边只连接两个节点, 图是一种特殊的超图. 在有向超图中, 每条边的节点被严格划分为两类, 一类点是这条超图边的起点, 另一类点是终点.
举一个例子, 一个典型的有向超图中每条超图边都有一些起点和一个终点. 在这个超图中, 我们仍然可以求一个点集到另一个点集的"最短路径". 如果这个超图本身满足严格的拓扑结构, 我们可以把维特比算法在这个超图上做一个拓展, 用广义维特比算法 (Generalized Viterbi Algorithm) 来求解这个问题. 这一点是比较好理解的.
当上述超图不满足拓扑结构时, 我们仍然可以把图模型中的一些算法引申过来. 打个比方, Dijkstra 算法把图中的节点分为两个类, 起初第一类只有起点 s , 根据其可达的最近节点不断拓展而得到终点 t . 在超图中我们用相同的方法, 从起点集开始探索其可达的最近节点, 直到得到终点集中的一个节点终止. 这种把 Dijkstra 算法拓展到超图模型的情形叫做 Knuth 算法. 类似地, k 最优 Dijkstra 算法可以拓展为 k 最优Knuth 算法.
事实上, 这个典型的有向超图是超图中应用最广泛的例子. 我们用一个非常直观的问题来解释它.
第一类是基于列表结构的动态规划, 主要的例子有最长公共子序列 (LCS) 等. 在这种结构下我们可以非常清晰地看到拓扑顺序, 在其上设计一个状态转移(状态合并)的方法即可. 我们再举几个典型的问题, 供大家思考. 注意在设计算法时, 要保证状态合并前后单调性仍然保持.
Problem 3.1.1
试求两个字符串的最长公共上升子序列 (LICS) .
Problem 3.1.2
给定三个字符串, 试求前两个字符串的最长公共子序列, 要求该子序列 s 不含第三个字符串作为 s 的子序列. (LCS w/o. subseq)
Problem 3.2.1
试求一个数组中连续 k 个数的和的最大值.
Problem 3.2.2
试求一个矩阵中行列连续的子矩阵中数的和的最大值.
第二类是基于复合链式模型的动态规划, 主要包括维特比 (Viterbi) 算法适用的一些问题, 主要包括求最优链的问题. 这类问题中不同的链有一些公共的节点, 但是整个空间仍然保持拓扑结构, 因此可以使用 Viterbi 算法按照拓扑层次求解. 从路径的角度来讲, 任意一个没有前驱的节点都可以作为起点, 任意一个没有后继的节点都可以作为终点. 这是一个典型的交错链表.
第三类是基于图模型的动态规划, 主要包括计算最短路径 (第 k 短路径) 和最小生成树的一些算法. 注意这类问题的本质有所区别. 一部分是定义在优幂等半环上的问题 ("事情总是会变得越来越差"), 另一部分模型不具有优幂等的属性, 因此设计状态转移时会略微复杂一些, 以保证状态合并不改变单调性. 有负权边的最短路径问题属于后者.
现在我们继续扩展, 给出超图的定义. 一个超图 (hypergraph) 的节点和图的节点类似, 超图的边 (hyperedge) 是多个节点的集合. 也就是说, 在图中每条边只连接两个节点, 图是一种特殊的超图. 在有向超图中, 每条边的节点被严格划分为两类, 一类点是这条超图边的起点, 另一类点是终点.
举一个例子, 一个典型的有向超图中每条超图边都有一些起点和一个终点. 在这个超图中, 我们仍然可以求一个点集到另一个点集的"最短路径". 如果这个超图本身满足严格的拓扑结构, 我们可以把维特比算法在这个超图上做一个拓展, 用广义维特比算法 (Generalized Viterbi Algorithm) 来求解这个问题. 这一点是比较好理解的.
当上述超图不满足拓扑结构时, 我们仍然可以把图模型中的一些算法引申过来. 打个比方, Dijkstra 算法把图中的节点分为两个类, 起初第一类只有起点 s , 根据其可达的最近节点不断拓展而得到终点 t . 在超图中我们用相同的方法, 从起点集开始探索其可达的最近节点, 直到得到终点集中的一个节点终止. 这种把 Dijkstra 算法拓展到超图模型的情形叫做 Knuth 算法. 类似地, k 最优 Dijkstra 算法可以拓展为 k 最优Knuth 算法.
事实上, 这个典型的有向超图是超图中应用最广泛的例子. 我们用一个非常直观的问题来解释它.
派生树(Derivation Tree)
我们在很多领域会涉及到一些基本的推导 (deduction) 或者证明 (proof) . 从给定的条件(condition) 或者规则 (rule) 出发, 推出我们所需要的结论. 打个比方, 我们现在有如下的三条规则:
\begin{aligned} r_1 &: A \to B \\ r_2 &: Bt \to v \\ r_3 &: \frac{t_1 \to t_1'}{t_1t_2 \to t_1't_2} \end{aligned}
那么我们可以通过一个简单的推导过程来推导式子"AC". 我们采用竖式写法来表示其推导过程 (deduction) , 用树形结构来表示其派生过程 (derivation) . 其中, 派生树 (derivation tree) 又被称之为证明树 (proof tree).
Deduction: \begin{aligned} & A \to B \ (r_1) \cr \Rightarrow & AC \to BC \ (r_3) \ * \cr & Bt \to v \ (r_2) \cr \Rightarrow & BC \to v \cr \Rightarrow & AC \to v (*) \cr \end{aligned} Derivation: $$ \Large \frac{\frac{(r_3), (r_1)A \to B}{AC \to BC}, (r_2)Bt \to v}{AC \to v}$$
现在我们思考一个很直观的问题. 为什么这个推导过程会产生一个树形结构的派生树, 而不是链式结构?事实上我们在竖式中也看到了, 很多步骤推导需要借助其他步骤的结论, 因此竖式推导也并不是一个链式结构.
这是因为, 绝大多数的推理过程, 都存在"多个条件推出一个式子"的中间过程. 这个过程的产生源于两个方面. 第一, 很多推理系统中存在一些规则, 支持由多个条件推出一个式子, 比如上述规则中的 r3, 就只能结合另一个条件 t1 -> t1' 来一起使用; 另一方面, 我们需要用多对一的方式来实现推理的传递性, 比如上式中我们推出了 AC -> BC, BC -> v, 我们需要一个"二对一"的方法来把这两条规则结合成一条规则.
这样的话, 推理结构就很自然地形成了一个超图结构. 考虑我们前述的典型超图模型, 每条边都可以有一个或者很多个起点和一个终点. 派生树在超图模型中的每一个节点是一个式子 (term), 每一条超图边表示推理的方向. 推理系统的应用非常广泛, 我在之后的文章里面会提到.
这是因为, 绝大多数的推理过程, 都存在"多个条件推出一个式子"的中间过程. 这个过程的产生源于两个方面. 第一, 很多推理系统中存在一些规则, 支持由多个条件推出一个式子, 比如上述规则中的 r3, 就只能结合另一个条件 t1 -> t1' 来一起使用; 另一方面, 我们需要用多对一的方式来实现推理的传递性, 比如上式中我们推出了 AC -> BC, BC -> v, 我们需要一个"二对一"的方法来把这两条规则结合成一条规则.
这样的话, 推理结构就很自然地形成了一个超图结构. 考虑我们前述的典型超图模型, 每条边都可以有一个或者很多个起点和一个终点. 派生树在超图模型中的每一个节点是一个式子 (term), 每一条超图边表示推理的方向. 推理系统的应用非常广泛, 我在之后的文章里面会提到.
上下文无关(Context Free)
我们现在试图关注另一个推理系统. 注意到, 上面的推理系统中每一个节点是一个式子, 而超图边只代表推理的方向, 超图边的本身并没有实际意义. 那么, 一个很自然的想法就是, 如果我们使用了规则 A -> B 的话, 能否做一个建模, 使得我们可以用一条边来连接 A 和 B 呢?
答案是否定的. 注意上面的例子. 我们可以用规则 r1 来推导出 A -> B, 但是在 AC 这样一个式子中, 必须借助 r3 这样一条规则才能够推导出 BC. 加入我们现在的式子是 CA, 那么根据上文的推理系统是无法退出 CB 的. 换而言之, 如果有上下文限制, 那么子串的推导规则就不能用在母串中. 上下文限制决定了在这个规则系统中无法用节点来表示字符单位, 超图边来承接规则.
一般的推理系统中需要设计一些诸如 r3 的规则来帮助一些子规则运用到上下文环境中. 一般地, 这样的规则称为一致性规则 (congruence rule), 而诸如 r1, r2 这类直接的推导规则叫做计算性规则 (computation rule).
根据上面的分析我们可以得知, 对于上下文无关的规则系统, 我们可以用一套更直观的超图结构来表示它: 每一个节点是当前字符单位, 我们称之为符号(symbol), 每一个超图边代表了一个规则. 在上下文无关环境中没有一致性规则, 只有计算性规则, 每个计算性规则都可以被超图结构中的超图边所表示. 上下文无关的推理系统尽管是广义推理系统的子集, 但是应用却非常非常的广泛. 数学算式, 绝大多数编程语言和其它非自然语言, 都是在上下文无关环境中构建出来的.
答案是否定的. 注意上面的例子. 我们可以用规则 r1 来推导出 A -> B, 但是在 AC 这样一个式子中, 必须借助 r3 这样一条规则才能够推导出 BC. 加入我们现在的式子是 CA, 那么根据上文的推理系统是无法退出 CB 的. 换而言之, 如果有上下文限制, 那么子串的推导规则就不能用在母串中. 上下文限制决定了在这个规则系统中无法用节点来表示字符单位, 超图边来承接规则.
一般的推理系统中需要设计一些诸如 r3 的规则来帮助一些子规则运用到上下文环境中. 一般地, 这样的规则称为一致性规则 (congruence rule), 而诸如 r1, r2 这类直接的推导规则叫做计算性规则 (computation rule).
根据上面的分析我们可以得知, 对于上下文无关的规则系统, 我们可以用一套更直观的超图结构来表示它: 每一个节点是当前字符单位, 我们称之为符号(symbol), 每一个超图边代表了一个规则. 在上下文无关环境中没有一致性规则, 只有计算性规则, 每个计算性规则都可以被超图结构中的超图边所表示. 上下文无关的推理系统尽管是广义推理系统的子集, 但是应用却非常非常的广泛. 数学算式, 绝大多数编程语言和其它非自然语言, 都是在上下文无关环境中构建出来的.
语言 (language) 是由文法 (Grammar) 定义的. 文法类似于一套推理系统, 但是更侧重在字符串上的定义. 一套文法可以生成句型 (sentential form) , 句子 (sentence), 从而生成语言.
而字符串的每一个字符属于一个字母表(alphabet), 因此文法都是定义在字母表上的.
文法 (Grammar) 是定义在一个字母表 A 上的集合 G = {Vt, Vn, S, P}. 其中 Vt 是终结符号 (terminal symbol) 的集合, Vn 是非终结符号 (non-terminal symbol) 的集合, S 是开始符号 (start symbol) 的集合, P 是规则(产生式)的集合 (production) .
语言学家 Avram Noam Chomsky 在1956年提出了一个形式文法的分类谱系, 把文法分成四种类型.
0型文法是没有任何限制的文法, 可以生成可枚举的语言;
1型文法是上下文相关文法 (Context Sensitive Grammar), 它的规则形如 aAb -> aA'b, 依照上下文可以从 A 推出 A';
2型文法是上下文无关文法 (Context Free Grammar), 在该文法中箭头左边只能有一个非终结符号, 任何规则都不需要依赖上下文即可应用;
3型文法是正则文法 (Regular Grammar), 它的规则形如 A -> a 或 A -> aB, 箭头右边只能向一个方向进行单链递归.
此外, 和图灵机一样, 文法还有很多变种, 包括随机文法 (Probabilistic Grammar) . 在随机文法中每一个产生式都有一个概率. 随机文法通常用来找到一个字符串对应的最大概率的产生方式.
我们在本文中讨论的是上下文无关文法 (CFG) 和随机上下文无关文法 (PCFG).
分析树(Parse Tree)
我们定义了上下文无关环境和其对应的超图模型, 那么根据这个模型我们会推出不同于派生树的一个树形结构, 我们称之为分析树(parse tree). 在分析树中, 每一个点代表一个符号, 包括终结符号和非终结符号; 每一条超图边由若干个符号指向一个非终结符号, 如 A -> aBb 这样的规则在分析树上表现为 a, B, b 三个顶点用一个超图边指向 A. 注意上下文无关环境中一个字符串中的不同字符分属于不同的顶点, 这是分析树的一个特点.
现在有这样一个问题. 我们描述的分析树是一个树形结构, 但却不是一个二叉树. 事实上, 几乎所有的上下文无关文法都可以对规则进行一些整理, 使得它们的规则只有 A -> BC (一个非终结符号分成两个非终结符号, 我们称这样的规则为二对一规则, binary rule) 和 A -> a (一个非终结符号变成一个终结符号, 我们称之为一对一规则, unary rule) 两种形式. 我们称这样的文法为 Chomsky 范式 (Chomsky Normal Form).
现在有这样一个问题. 我们描述的分析树是一个树形结构, 但却不是一个二叉树. 事实上, 几乎所有的上下文无关文法都可以对规则进行一些整理, 使得它们的规则只有 A -> BC (一个非终结符号分成两个非终结符号, 我们称这样的规则为二对一规则, binary rule) 和 A -> a (一个非终结符号变成一个终结符号, 我们称之为一对一规则, unary rule) 两种形式. 我们称这样的文法为 Chomsky 范式 (Chomsky Normal Form).
考虑到实际应用中会出现诸如 A -> B 的规则, 我们也可以把它算进 Chomsky 范式的一种规则, 无伤大雅. 本质上, Chomsky 范式只是保证了两点比较好的分析树的性质:
叶子节点全是终结符号, 非叶子节点全是非终结符号;
所有的超图边均有一个或者两个起点, 使得整个树的结构是一个准二叉树结构.
另外, 我们提到几乎所有的上下文无关文法都可以转化为 CNF. 事实上, 只要该 CFG 不含空串规则, 就一定能转化为 CNF.
现在我们整理出了一个很漂亮的超图结构. 我们知道, 给定一个文法, 我们可以任意地去让它派生出各种不同的字符串; 那么, 给定一个字符串, 我们如何判断它是否属于这个文法生成的语言呢? 这是我们在 Problem 1.1 中提出的问题, 结合 Problem 1.2, 我们介绍一些分析算法 (parsing algorithm), 来回答这个问题.
CKY算法(CKY Algorithm)
为了了解给定的字符串与一个文法的关系, 我们通常会根据文法来尝试地对该字符串构造分析树, 这种方法叫做分析 (parsing). 构造分析树所使用的算法统称为分析算法 (parsing algorithm).
首先我们来看一下 Chomsky 范式的性质. 首先, 一个长度为 n 的字符串中的每一个字符, 在分析树的最下层总会通过一个一对一规则转化成共计 n 个非终结符号. 其次, 这 n 个非终结符号一定会通过 n-1 个 二对一规则来结合成开始符号. 如果非终结符号间存在一对一规则, 我们则需要对单一的非终结符号的自迭代.
考虑一个字符串s[1, n]在 Chomsky 文法下的某一个分析树. 在分析树的顶端是一个开始符号 S . 如果n>1, 那么 S 一定会分两个非终结符号 A 和 B, 它们分别是 s[1,j] 和 s[j+1, n] 的子树根. (严格来说这两个子树不是分析树因为树根不是开始符号 , 我们暂且称其为分析子树) 此外, 由于文法的二义性, s[i, j] 可能会归结为不同的非终结符号, 于是我们需要在它的子树根上枚举可能被归结的非终结符号.
一般地, 对一个字符串 s[1, n] 可以进行一个自底向上的分析算法. 我们以子串 s[i, j] 的长度为顺序. 首先对于s[i, i], 我们只需把终结符号用一对一规则转成非终结符号; 其次, 对于s[i, j], 假定长度比其小的s[i', j']已经分析完毕, 那么我们可以枚举其所有的断点 k , 通过搜索是否存在二对一规则结合 s[i,k] 和 s[k+1, j] 来找到s[i, j] 的可能非终结符号.
当我们所求的不是所有分析树, 而是一个分析树或者概率最高的分析树 (对于PCFG而言), 我们就可以在上述模型中加入合并策略, 从而进行动态规划. 考虑到s[i, k] 和 s[k+1, j] 归结到 s[i, j] 这一过程, 我们不需要知道两个分析子树的内部情况, 只需要知道它们可能的非终结符号(及其概率)即可. 因此, 归结 s[i, j] 时, 我们可以合并相同的非终结符号即可. 这种运用了动态规划的分析算法叫做 CKY 算法(CKY algorithm), 又称 CYK 算法.
首先我们来看一下 Chomsky 范式的性质. 首先, 一个长度为 n 的字符串中的每一个字符, 在分析树的最下层总会通过一个一对一规则转化成共计 n 个非终结符号. 其次, 这 n 个非终结符号一定会通过 n-1 个 二对一规则来结合成开始符号. 如果非终结符号间存在一对一规则, 我们则需要对单一的非终结符号的自迭代.
考虑一个字符串s[1, n]在 Chomsky 文法下的某一个分析树. 在分析树的顶端是一个开始符号 S . 如果n>1, 那么 S 一定会分两个非终结符号 A 和 B, 它们分别是 s[1,j] 和 s[j+1, n] 的子树根. (严格来说这两个子树不是分析树因为树根不是开始符号 , 我们暂且称其为分析子树) 此外, 由于文法的二义性, s[i, j] 可能会归结为不同的非终结符号, 于是我们需要在它的子树根上枚举可能被归结的非终结符号.
一般地, 对一个字符串 s[1, n] 可以进行一个自底向上的分析算法. 我们以子串 s[i, j] 的长度为顺序. 首先对于s[i, i], 我们只需把终结符号用一对一规则转成非终结符号; 其次, 对于s[i, j], 假定长度比其小的s[i', j']已经分析完毕, 那么我们可以枚举其所有的断点 k , 通过搜索是否存在二对一规则结合 s[i,k] 和 s[k+1, j] 来找到s[i, j] 的可能非终结符号.
当我们所求的不是所有分析树, 而是一个分析树或者概率最高的分析树 (对于PCFG而言), 我们就可以在上述模型中加入合并策略, 从而进行动态规划. 考虑到s[i, k] 和 s[k+1, j] 归结到 s[i, j] 这一过程, 我们不需要知道两个分析子树的内部情况, 只需要知道它们可能的非终结符号(及其概率)即可. 因此, 归结 s[i, j] 时, 我们可以合并相同的非终结符号即可. 这种运用了动态规划的分析算法叫做 CKY 算法(CKY algorithm), 又称 CYK 算法.
CKY 算法, 又称 CYK 算法, CKY 分析算法 (CKY parsing algorithm), 是Cocke, Younger, Kasami三人于1965年合作研究出来的分析算法. 该算法可以适用于一切CFG, 用来判断一个字符串是否属于一个 CFG; 以及一切 PCFG, 用来寻找一个字符串在该 PCFG 下的最大概率.
CKY 算法的描述非常简单. 按照子串长度从小到大枚举每一个子串(共计 O(n^2) 个子串), 对于每一个子串s[i, j] 而言, 枚举所有的断点( O(n) )和所有的规则( O(R), R是规则的个数 ), 来更新 s[i, j] 的子树根上的非终结符号(及其概率). CKY算法的时间复杂度是 O(R*n^3).
我们用CKY算法可以直接回答 Problem 1.2.
Answer 1.2
使用 CKY 算法对该字符串进行分析, 可得最大概率及其对应的分析树.
对于Problem 1.1, 我们考虑到 CKY 算法的复杂度较高. 有一种特殊的上下文无关文法 -- 无二义性文法, 在无二义性文法中一个字符串最多只有一个分析树. 无二义性文法更加规范一些, 可以采用时间复杂度很低的分析方法, 在编译领域有广泛运用. 比较典型的有 LR 分析器, LALR 分析器等. 此处不再赘述.
Answer 1.1
考虑该上下文无关文法是否属于一些更规范的文法, 如 LR(k) 文法等. 如是, 则可以用该文法对应的低时间复杂度的分析器. 否则, 一切上下文无关文法都可以采用 CKY 算法来分析.
我们用CKY算法可以直接回答 Problem 1.2.
Answer 1.2
使用 CKY 算法对该字符串进行分析, 可得最大概率及其对应的分析树.
对于Problem 1.1, 我们考虑到 CKY 算法的复杂度较高. 有一种特殊的上下文无关文法 -- 无二义性文法, 在无二义性文法中一个字符串最多只有一个分析树. 无二义性文法更加规范一些, 可以采用时间复杂度很低的分析方法, 在编译领域有广泛运用. 比较典型的有 LR 分析器, LALR 分析器等. 此处不再赘述.
Answer 1.1
考虑该上下文无关文法是否属于一些更规范的文法, 如 LR(k) 文法等. 如是, 则可以用该文法对应的低时间复杂度的分析器. 否则, 一切上下文无关文法都可以采用 CKY 算法来分析.
树(Tree)
我们在前面讲了两个典型的超图模型的应用实例. 现在我们用典型的超图模型把树结构定义一下.
树 (tree) 是一个具有拓扑结构的超图,它的每一个超图边都只有一个终点, 且每一个节点至多被一个超图边所指向. 树中存在一个唯一的拓扑顺序最靠后的节点, 我们称之为树根. 特殊地, 如果每一个超图边均有两个起点, 则我们称之为二叉树.
注意树在有向图上的定义. 两个定义的区别在于图认为一个父亲与 k 个儿子的关系是用 k 条边表示的, 每条边只表示一个简单的父子关系; 而超图把一个父亲和其所有的儿子用一个超图边来表示. 两个定义是相通的.
特殊地, 二叉树 (binary tree) 所对应的超图的每条边有至多两个起点和一个终点. 在 Chomsky 文法之下每一个分析树都是二叉树.
树 (tree) 是一个具有拓扑结构的超图,它的每一个超图边都只有一个终点, 且每一个节点至多被一个超图边所指向. 树中存在一个唯一的拓扑顺序最靠后的节点, 我们称之为树根. 特殊地, 如果每一个超图边均有两个起点, 则我们称之为二叉树.
注意树在有向图上的定义. 两个定义的区别在于图认为一个父亲与 k 个儿子的关系是用 k 条边表示的, 每条边只表示一个简单的父子关系; 而超图把一个父亲和其所有的儿子用一个超图边来表示. 两个定义是相通的.
特殊地, 二叉树 (binary tree) 所对应的超图的每条边有至多两个起点和一个终点. 在 Chomsky 文法之下每一个分析树都是二叉树.
在分析 (parsing) 的领域中 hypergraph 的运用非常的广泛. 有兴趣的读者可以参阅UC Berkeley 的 Dan Klein 与 Stanford University 的 Chris Manning 合作的文章 "Parsing and Hypergraphs".
我在前文提及的文章"Advanced Dynamic Programming in Semiring and Hypergraph Framework" 中也对超图上的动态规划方法进行了一个总结.
树结构有一个天然的"合并"过程, 我们可以把它看做是 n 个叶子经过一系列超图边合并到一个根节点的过程. 因此, 自底向上地在树结构上运用动态规划方法是一个一般化的方法. Problem 2.2 是一个数据库上的查询优化问题. 我仿照上述的一般化方法提出了一个优化策略, 跟某大牛做过一些讨论, 因此想把它写出来.
线段树(Segment Tree)
我们不妨用二叉搜索树来实现 Problem 2.1中的查询系统. 如果将每一个非叶子节点采用区间表示的话, 那么我们就得到了一个线段树.
线段树(segment tree)是一种数据结构, 它是基于区间的二叉搜索树. 对于一个父亲节点所表示的区间[a, b], 存在一个该区间中的数 c, 使得两个儿子节点分别表示 [a, c] 和 [c, b]. 一般来说 c 会取 a 和 b 的平均值.
Answer 2.1
对每一个数据的查询字串 (key) 进行一个编码, 并采用线段树来实现这个查询系统. 在这个查询系统中, 除了叶子节点以外的部分与线段树类似, 叶子节点则分别存储该对应的数据所在的机器编号.
现在我们考虑对这个查询系统做一个优化. 考虑在一个实际的数据库系统中, 由于查询系统只能存储在一个主机上, 而成千上万的查询都需要通过这个主机来得到其数据所在的机器. 那么, 我们希望并非每一个查询都要搜索到线段树的底部, 从而来减少主机的负担.
一个可行的办法就是, 考虑到数据存储在不同的机器上, 对不同机器做查找的过程是可以并行的. 那么我们便尝试对这个二叉搜索树进行一个比较浅的查找, 使得我们可以得到 k 个机器的一个集合, 其中我们所要的数据一定存在某个机器上. 拿到这个集合之后, 我们便可以分别向这 k 个机器去获取数据, 这样的话便可以通过较低的查询代价和较高的获取代价来得到我们所要的数据.
我们提出了一种预处理+启发式搜索的方法来解决这个问题.
Answer 2.2
对于这个查询系统, 我们在每一个非叶子节点上记录一个集合, 代表以该叶子节点为根的子树中所有的数据所在的机器的集合. 如下即是初始化, 查询和维护操作.
初始化: 自底向上进行一次动态规划. 默认叶子节点表示的机器即为该节点的集合. 对于一个超图边, 合并两个起点的集合从而得到终点所在的集合. 我们可以规定一个深度 d, 并只对深度不低于 d 的节点进行初始化. (考虑到深度过低的节点集合中的元素比较密集)
查询: 采用一个启发式搜索的方法, 对该线段树自顶向上进行查找. 可以通过当前所在节点的集合的势, 以及当前所在节点的深度, 甚至查询系统的繁忙程度来决定搜索深度, 只要深度不小于 d 即可. 查找停止之后, 便对该集合的所有机器获取数据, 这样必有一个机器会给出所需数据.
维护: 对于数据插入, 数据删除, 数据修改, 只需要进行一个 O(D) (D 为树的深度)的操作, 更新其所有祖先的集合即可. 对于数据插入和修改, 如果看到一个祖先早已有其所在机器则停止; 对于数据删除, 则需要更新每一个祖先的同时查看其另一个儿子.
注意到, 这个方法在预处理中也用到了一些动态规划的思想. 总体来说, 树结构的自底向上的动态规划, 其对节点和超图边的访问顺序大体上是相似的.
线段树(segment tree)是一种数据结构, 它是基于区间的二叉搜索树. 对于一个父亲节点所表示的区间[a, b], 存在一个该区间中的数 c, 使得两个儿子节点分别表示 [a, c] 和 [c, b]. 一般来说 c 会取 a 和 b 的平均值.
Answer 2.1
对每一个数据的查询字串 (key) 进行一个编码, 并采用线段树来实现这个查询系统. 在这个查询系统中, 除了叶子节点以外的部分与线段树类似, 叶子节点则分别存储该对应的数据所在的机器编号.
现在我们考虑对这个查询系统做一个优化. 考虑在一个实际的数据库系统中, 由于查询系统只能存储在一个主机上, 而成千上万的查询都需要通过这个主机来得到其数据所在的机器. 那么, 我们希望并非每一个查询都要搜索到线段树的底部, 从而来减少主机的负担.
一个可行的办法就是, 考虑到数据存储在不同的机器上, 对不同机器做查找的过程是可以并行的. 那么我们便尝试对这个二叉搜索树进行一个比较浅的查找, 使得我们可以得到 k 个机器的一个集合, 其中我们所要的数据一定存在某个机器上. 拿到这个集合之后, 我们便可以分别向这 k 个机器去获取数据, 这样的话便可以通过较低的查询代价和较高的获取代价来得到我们所要的数据.
我们提出了一种预处理+启发式搜索的方法来解决这个问题.
Answer 2.2
对于这个查询系统, 我们在每一个非叶子节点上记录一个集合, 代表以该叶子节点为根的子树中所有的数据所在的机器的集合. 如下即是初始化, 查询和维护操作.
初始化: 自底向上进行一次动态规划. 默认叶子节点表示的机器即为该节点的集合. 对于一个超图边, 合并两个起点的集合从而得到终点所在的集合. 我们可以规定一个深度 d, 并只对深度不低于 d 的节点进行初始化. (考虑到深度过低的节点集合中的元素比较密集)
查询: 采用一个启发式搜索的方法, 对该线段树自顶向上进行查找. 可以通过当前所在节点的集合的势, 以及当前所在节点的深度, 甚至查询系统的繁忙程度来决定搜索深度, 只要深度不小于 d 即可. 查找停止之后, 便对该集合的所有机器获取数据, 这样必有一个机器会给出所需数据.
维护: 对于数据插入, 数据删除, 数据修改, 只需要进行一个 O(D) (D 为树的深度)的操作, 更新其所有祖先的集合即可. 对于数据插入和修改, 如果看到一个祖先早已有其所在机器则停止; 对于数据删除, 则需要更新每一个祖先的同时查看其另一个儿子.
注意到, 这个方法在预处理中也用到了一些动态规划的思想. 总体来说, 树结构的自底向上的动态规划, 其对节点和超图边的访问顺序大体上是相似的.