递归⤵动态规划⤴和语言 parsing🌲

2024-01-07 日 15:08 2024-05-11 六 17:42

修改历史

  • [2024-05-11 六 16:13] 只保留 LL parser combinator 的函数式实现

本文梳理递归、动态规划和语言解析的基础知识,尝试回答或者仅仅只是引出以下几个维度的问题:

  • 递归、动态规划是如何应用在语言解析里的,比如传统自然语言处理中的 CKY 算法和编程语言解析中的 LL1 递归下降算法,语言的哪种抽象层上出现了递归模式,从而可以使用递归或者动态规划算法来分析它们?
  • Chomsky 从语言学/认知/哲学出发提出来的语言等级划分是如何 "工程化" 变成自然语言处理里的 CKY 算法, 又是如何变成形式语言里的 LL parser 或者 Parser Generator 的 ? 比如 2009 年在 stackoverflow 上就有一个类似问题 parsing - Chomsky Hierarchy and LL(*) parsers - Stack Overflow,但被接收的回答中只是说 LL parsers 处理的语法是 Chomsky 提出的 CFG 语法的一个子集,并没有更多的解释。
  • LL parser combinator 的函数式编程实现

这主要是编译原理中覆盖的基础知识,不过用自己的思路重新描述出来。

如果对动态规划和递归的概念已经比较熟悉,可以直接跳过前两章,直接从 现实场景:语法和语言解析 开始阅读,如果已经了解语言解析,但没有用函数式编程方式写过 parser combinator 可以跳到 LL 递归下降的函数式实现 一章,如果只想了解递归和动态规划,阅读前两章即可。

所见即所得的格子世界

我们先以一个 leetcode 类型的题目进行热身, 64. 最小路径和 - 力扣(LeetCode) 的题目是,给定一个包含 m x n 个格子的 grid ,如下

+--------------------+
|  1   |  3   |  1   |
|------+------+------|
|  1   |  5   |  1   |
|------+------+------|
|  4   |  2   |  9   |
+--------------------+

找出一条从左上角到右下角的移动路径(只能右移和下移),使得路径上数字总和是最小的,并返回这个总和。

自顶向下(top-down)、递归下降和目标驱动

对于该问题,可以采用所谓自顶向下的方法,"顶"(top level) 指的是目标和策略,是一种高层的规划。 这听上去还是有点抽象,在本题中,起点是左上角,目标是在右下角,那么"顶" 的关注对象就是最右下角的格子,由于题目不单单要求到达该目标,还要使得路径和最小,因此要额外考虑到达最右下角格子的"路径"。

注意,不要看到"路径"两个字就立刻陷入细节,去图中试探各种从左上到右下的所有可能,这违背了 top level 的思想,自顶向下核心是保持足够清晰去抵御陷入细节的诱惑,只关注最右下角的目标格子,并只考虑到达该目标的"局部路径",这只有两种可能: "从上方格子" 和 "从左侧格子" 。 并且要假定这两个方向都带有已经积累的最小路径和,只需要从中选择更小的即可。

这就像一个拥有上万名员工的公司的 CEO 大多数时候只需要关注直接向其汇报的几个助手提供的信息,而不需要关注每个员工的动态。

在这种"顶层思维"下,定义到达某个格子的路径最小和是 s(i,j), 本例中核心关注的是 s(2, 2), 它的值应该来自于当前格子的值,以及上方格子 s(1,2)和左侧格子的 s(2,1) 的最小值之和:

s(2,2) = grid[2][2]+min(s(1,2), s(2,1))

将这个式子一般化(抽象):

s(i,j) = grid[i][j]+min(s(i-1,j), s(i,j-1))

至此,top-level 的目标和策略基本就完成了,我们可以直接将其写成代码:

def min_path_sum(grid):

    m, n = len(grid), len(grid[0])

    def s(i, j): 
        # 递归停止条件待定
        return grid[i][j] + min(s(i-1, j), s(i, j-1))

    return s(m-1, n-1)

写代码时很快发现,我们还需要考虑递归的终点(最底层没有下属的员工),对应的到图中就是越界的情况,即 j-1 或者 i-i 小于 0 的情况。

一种做法是,在对 s(i-1,j) 取值的时候,检查 i-1 是否小于 0(也就是 -1), 如果小于 0 就不考虑,即 min(s(-1,j), s(i,j-1)) 应该返回 s(i,j-1), 这等价于把 s(-1,j) 设置为无穷大。但这种把越界视为无穷大的技巧会遇到额外边界情况,即在起点 i=0,j=0 的情况下 ,min(s(-1,j), s(i,-1)) 中两个元素都是无穷大,从而导致 s(0,0) 也是无穷大,这是会得到错误结果。因此还要额外地在 i,j 都等于 0 时直接返回 grid[0][0], 至此可以写出可执行的 top-down 代码了:

def min_path_sum(grid):

    m, n = len(grid), len(grid[0])

    def s(i, j): 
        if i == 0 and j == 0:
            return grid[i][j]
        if i < 0 or j < 0:
            return float("inf") 
        return grid[i][j] + min(s(i-1, j), s(i, j-1))

    return s(m-1, n-1)
min_path_sum(grid = [[1,2,3],[4,5,6]])
12

有了具体代码,就可以分析执行细节的问题,也就是算法复杂度。以上函数的问题在于,计算 s(i,j) 时,要计算 s(i-1, j) 和 s(i,j-1), 而 s(i-1, j) 要计算 s(i-2,j) 和 s(i-1,j-1), s(i,j-1) 要计算 s(i-1,j-1) , s(i,j-2), 这里 s(i-1,j-1) 被计算了两次,如下图所示(绘图基于 Show HN: Ascii_tree – A way to create beautiful ASCII trees):

                        +--------+
             +----------| s(i,j) |------------+
             |          +--------+            |
       +----------+                     +-----+----+
    +--| s(i-1,j) |--+              +---| s(i,j-1) |---+
    |  +----------+  |              |   +----------+   |
+---+----+     +=====+====+    +====+=====+      +-----+----+
|s(i-2,j)|     |s(i-1,j-1)|    |s(i-1,j-1)|      | s(i,j-1) |
+--------+     +==========+    +==========+      +----------+

如果继续展开,会有更多的项目被重复计算,因此我们需要一个缓存机制,在递归过程中,如果某个子问题已经被解决,那么直接从缓存里获取结果即可,这里用 python 中的 lru_cache 实现:

import functools
def min_path_sum_cache(grid):

    m, n = len(grid), len(grid[0])

    @functools.lru_cache(1000) #假设 m*n 最大 1000
    def s(i, j): # 用函数 s 记录 s[i][j]
        if i == 0 and j == 0:
            return grid[i][j]
        if i < 0 or j < 0:
            return float("inf") 
        return grid[i][j] + min(s(i-1, j), s(i, j-1))

    return s(m-1, n-1)
grid = [[1,3,1],[1,5,1],[4,2,9]]
min_path_sum_cache(grid)
15

注意分析复杂度并加上缓存的思考和用 top-down 思维分解问题很不一样,后者更像战争中的战略家,设定目标和方向,前者则是战术家,负责实现这些目标的细节,后勤等。

(理想的)自顶向下的思路的特点是:

  • 先聚焦到目标本身,把目标分解成更小的相似的目标,因此它可以认为是目标驱动的。
  • 由于只需要考虑一次分解而避免陷入细节(唯一的细节是边界条件),所以它常常是递归形式的
  • 递归是在目标分解这棵树上从上(大目标)逐渐向下(子目标)执行,因此又会用递归下降来修饰这类算法(尤其是在后文提到的语言解析应用中)
  • 在递归树中重复的部分可以通过缓存机制(memo)来快速跳过,缓存有一种把子树变成叶子节点的剪枝能力, 让子树立即返回一个值,减少不必要的重复递归(解重复的子问题)。

自底向上(bottom-up)、动态规划和数据驱动

自顶向下是从终点的目标状态开始考虑,那么自底向上就是从初始状态或者 base case 开始思考。

在最小路径和题目中,自底向上要从网格的左上角起点开始按照规则向外搜索,在 top-down 思考中,已经把大问题分解成了相似的小问题,因此 bottom-up 要解决的每一步小问题的策略和大问题又是一样的:

s[i][j] = grid[i][j]+min(s[i-1][j], s[i][j-1])

注意这里我们把 s 从上文中的函数调用形式 s(i,j) 写成了数组形式 s[i][j], 它大小和原 grid 一样,s[i][j] 记录了到达 grid[i][j] 的路径和最小值。

除此之外, bottom-up 还要额外考虑解决子目标的顺序问题,这样才能保证进入下一个任务时,该任务所依赖的子任务都已经解决了。

路径和例子中, s[0][0] 是第一个解决的子任务,这毋庸置疑,解决了它之后,就可以按规则向下或向右计算 s[1][0] 和 s[0][1], 先解决哪个并不是很重要。

+--------------------+
|  1  ->  3   |  1   |
|--v---+------+------|
|  1   |  5   |  1   |
|------+------+------|
|  4   |  2   |  9   |
+--------------------+

接着解决对角线上三个子问题:

+------+------+------+
|  1  ->  3  ->  1   |
|--v---+--v---+------+
|  1  ->  5   |  1   |
|--v---+------+------+
|  4   |  2   |  9   |
+------+------+------+

总结来看,bottom-up 思路是从格子图左上角向右下角斜向下推进:

  1. 第一轮解决 s[0][0]
  2. 第二轮解决 s[1][0], s[0][1] 两个问题,因为它们只依赖 s[0][0]
  3. 第三轮解决 s[2][0], s[1][1], s[0][2] 三个问题,其中 s[1][1] 同时依赖上一步解决的两个子问题
  4. 第四轮解决 s[2][1], s[1][2]
  5. 第五轮解决 s[2][2] 这个最终目标

    把后三步的问题处理顺序和依赖绘制成以下一棵"树", 其中 i,j 都等于 2 。 "树"打引号是因为这不是真正意义上的树,而是一个图,因为 s[i-1][j-1] 即 s[1][1] 只需要计算一次(如果把前两个步骤的图也画上去,会变成一个菱形),但这里我们还是称为树。

                   +--------+
             1 +---| s(i,j) |------+
               |   +--------+      |
               |                   |
         +-----+----+        +-----+----+ 5
    2 +--| s(i-1,j) |--+  +--| s(i,j-1) |---+
      |  +----------+  |  |  +----------+   │
      |              4 |  |6               7│
3 +---+----+       +==========+       +-----+----+
  |s(i-2,j)|       |s(i-1,j-1)|       | s(i,j-1) |
  +--------+       +==========+       +----------+

从第三步到第五步的过程,正是按层次从树的底部向上移动逐渐解决每个子节点对应的问题,这再次体现了自底向上的特点。另外,由于事先已经有意识地制定好了解决子问题的顺序,因此 s(i-1,j-1) 节点只会被解决一次,这和上一节带缓存的递归是一样的, 但递归的劣势在于函数调用的成本比内存取值高很多,比如调用函数需要入栈出栈等操作,可能其中有 10 条指令,但访问内存取出 s[i-1][j-1] 可能只要一条指令,那么相同问题下, bottom-up 方式效率就是 top-down 方式效率的 10 倍了。

然而具体实现中基本不会沿着这样的任务顺序去解决,因为对于方格图来说,沿斜向下方向对 i,j 进行更新的遍历顺序写起来要复杂一点,更常见的是先从左到右解决第一行:

+------+------+------+
|  1  ->  3  ->  1   |
|------+------+------+
|  1   |  5   |  1   |
|------+------+------+
|  4   |  2   |  9   |
+------+------+------+

然后第二行,第三行:

+------+------+------+
|  1  ->  3  ->  1   |
|------+------+------+
|  1  ->  5  ->  1   |
|------+------+------+
|  4   |  2   |  9   |
+------+------+------+

这样只要写两个 for 循环就行了:

for i in range(m):
    for j in range(n):
        ...

逐行遍历优于斜线遍历的原因完全来自语言接口的设计,如果语言提供了一个 diag 函数,能够从中不断返回沿对角线向下移动的 i,j ,那么没有理由拒绝斜向下扫描的方式,因为斜向下更符合问题分解顺序。

之所以从左到右逐行扫描是合理的,是因为题目性质规定只能向右和向下移动,因此从左到右边,从上到下的顺序符合子问题的依赖顺序,但不能从右到左或从下到上来逐一解决问题。

我们按逐行扫描写出动态规划代码:

def min_path_sum_dp(grid):

    m, n = len(grid), len(grid[0])
    s = [[0]*n for _ in range(m)]
    s[0][0] = grid[0][0]

    # 先更精细地解决第一行和第一列中的子问题
    for i in range(1, m):
        s[i][0] = grid[i][0] + s[i-1][0]

    for j in range(1, n):
        s[0][j] = grid[0][j] + s[0][j-1]

    # 多个 for 循环精细避免了边界条件判断
    for i in range(1, m):
        for j in range(1, n): 
            s[i][j] = min(s[i-1][j], s[i][j-1]) + grid[i][j] 

    return s[m-1][n-1]
min_path_sum_dp(grid)
15

自底向上也会称为数据驱动型算法,因为它是从最小的子问题开始解决的,每向前一步都是基于之前解决问题的数据的基础上去解决下一个已经规划好的小目标。

总的来看:对问题的思考上,top-down 和 bottom-up 的出发点是一样的,都是找到目标并且把目标分解成子目标, 只是在具体实现上,top-down 在分解完任务、考虑好极端的边界条件后以 CEO 的视角把问题交给了两个助手,自己只要等待目标是否达成(目标驱动),bottom-up 则在分解完任务后亲自去规划每个子任务的进度安排,跟进每个任务。规划子任务执行路径的行为是它与 top-down 方法的核心差异,这种特点也使得此类算法称为动态规划。

规划子任务的执行顺序是一项严肃的需要投入思考的事情,也是 bottom-up 思想相比 top-down 思想的额外付出,多一份的耕耘也给动态规划带来了效率上的收获,比如它可以在代码中避开或减少边界条件的检查,更好地利用内存中缓存连续性(缓存局部性),也减少了递归中函数调用的开销。然而,有些问题很难自底向上规划出一条明确的解决任务的路线,更多只能在递归(结合自动缓存)中自发地展现出问题解决的路线,比如汉诺塔问题。

自顶向下索要路径

假设在最小和路径问题基础上,要求算法能够返回路径和最小的路径,而不单单是最小的路径和。比如,下图中箭头指向的就是和最小的路径。

+------+------+------+
|  1  ->  3  ->  1   |
|------+------+--v---+
|  1   |  5   |  1   |
|------+------+--v---+
|  4   |  2   |  9   |
+------+------+------+

具体来说,就是要返回 [(0,0),(0,1),(0,2),(1,2),(2,2)]

我们还是先以自顶向下的思路,对于 CEO 它只需要向两个助手提要求:”请给我到达你们手里的和最小的路径以及对应的和“,然后 从中挑选最小的那个并把自己所在的位置拼接到路径上。因此这与之前的问题多出来的要求是每个 s(i,j) 函数不单要返回数值,还要返回一个列表记录路径。

可以把 min_path_sum_cache 改写成如下函数,核心就是对 s(i,j) 接口上的适应,并且要用 if else 形式去找到更小的路径和以及路径,而不是用 min 直接获得更小的路径和。

import functools
def min_path_cache(grid):

    m, n = len(grid), len(grid[0])

    @functools.lru_cache(1000) #假设 m*n 最大 1000
    def s(i, j): # 用函数 s 记录 s[i][j]
        if i == 0 and j == 0:
            return grid[i][j], [(0, 0)]
        if i < 0 or j < 0:
            return float("inf"), []
        value_left, path_left = s(i-1, j)
        value_right, path_right = s(i, j-1)
        if value_left < value_right:
            value = grid[i][j] + value_left
            path = path_left + [(i, j)]
        else:
            value = grid[i][j] + value_right
            path = path_right + [(i, j)]
        return value, path

    return s(m-1, n-1)
grid = [[1,3,1],[1,5,1],[4,2,9]]
print(min_path_cache(grid))
(15, [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)])

动态规划中记录路径

对于动态规划,在具体做每一个小问题的时候,思路仍然和 top-down 方式是一样的,每次解决一个问题,都对当前任务所依赖的两个子任务中路径和更小(最优)的那个做一个标记,当解决最后一个问题时,要沿着标记反向把路径找出来。可以把 s[i][j] 改成存储两个变量:路径和 value 以及指向最优子问题的标记(指针) prev

把 min_path_sum_dp 改写成 min_path_dp:

def min_path_dp(grid):

    m, n = len(grid), len(grid[0])
    s = [[[0, None] for _ in range(n)] for _ in range(m)]
    s[0][0][0] = grid[0][0]
    # s[0][0][1] is None

    for i in range(1, m):
        s[i][0][0] = grid[i][0] + s[i-1][0][0]
        s[i][0][1] = (i-1, 0)

    for j in range(1, n):
        s[0][j][0] = grid[0][j] + s[0][j-1][0]
        s[0][j][1] = (0, j-1)

    for i in range(1, m):
        for j in range(1, n): 
            value_up, _ = s[i-1][j] # 不需要知道 prev 变量
            value_left, _ = s[i][j-1]
            if value_left < value_up:
                s[i][j][0] = value_left + grid[i][j] 
                s[i][j][1] = (i, j-1)
            else:
                s[i][j][0] = value_up + grid[i][j]
                s[i][j][1] = (i-1, j)

    path = []
    end = (m-1, n-1)
    while end:
        path.append(end)
        i, j = end
        end = s[i][j][1]
    return s[m-1][n-1][0], path[::-1]
print(min_path_dp(grid))
(15, [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)])

注意这里用了 value_left 和 value_up ,它表示的是 grid 里左侧和上方的位置,而上节递归中的 value_left, 和 value_right 表示的是递归树里左节点和右节点,它们和 grid 上的物理位置方向是无关的。

子字符串问题:抽象后的格子世界

上一节中,我们直接是在一个具体的格子世界(grid)里讨论自顶向下或自底向上的算法设计,这个例子的好处在于,可以比较直观地看到子问题的分解情况(路径只能来自左侧和上方),这类问题是自带可视化效果的。本节则例举直观上看和 grid 完全无关,但对问题抽象之后却变成了格子世界问题。计算机科学里的美妙现象之一就是,只要找到恰当的抽象层级,很多问题都有相同的结构,选择停留在哪个抽象层进行思考是很重要的。

本节还是以 leetcode 中题目为例,516. 最长回文子序列 - 力扣(LeetCode) 的问题如下:

给你一个字符串 s ,找出其中最长的回文子序列的长度。

子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

.

前文说过,无论是递归还是动态规划方式,第一步都是一样的: 找到目标然后分解成更小的相似的目标。在这个问题中,问题分解的动作是”删除字符“,一个明显的相似点在于,对非空字符串删除一个字符之后还是字符串,但这还不够,因此要考虑,删除某个字符后的序列的最长回文问题和原问题有什么关系?

一次过于复杂的分解

假设当前字符串 s, 长度是 n, 那么一种做法是,作为 CEO, 你找到 n 个助手,告诉他们,请你们分别把第 i 个字符删除,然后告诉我剩下的长度为 n-1 的各字符串的最长回文子序列长度是多少?然而这种做法会让自己变得困难:即便你拿到助手返回的 n 个数字,也无法根据这些数字计算出大目标的结果,因为问题中要求满足 "回文" 性质,光拿到助手告诉你的数字而没有能够判断回文的结构信息是无法完成最后一步决策的。

举个例子,如果你把手上的 "aba" 分给三个助手,他们分别拿到了 "ba","aa","ab", 然后返回了结果 0,2,0, 如果光看这三个数字,无法得到最后的结果 3.

你需要对删除字符的位置信息保持关注,比如第二个人返回了 2, 而你是把最中间的 b 删除了给他的,最中间意味着 b 不可能和其他额外的字符组成回文,它自身就是回文,因此你知道手上的 "aba" 回文子序列长度至少是 2+1. 支撑这个决策的关键是你记住了当前助手返回的结果是基于自己删除了最中间的字符后的字符串这个信息。

但这仍然不够,如果你手上的是 abba ,删除了 s[1], 即第一个 b 后得到 aba 交给了某个助手,返回了结果 3, 这时候你还需要考虑把 s[1] 加入之后是如何影响最长回文的,因此你继续要求助手额外返回它们发现的回文子序列的下标,比如 [0,1,2], 然后你根据删除的那个字符的下标去修正这个下标序列,变成 [0,2,3], 接着把 s[1] 的下标 1 拿出来,加入到这个下标序列,得到 [0,1,2,3], 检查一次这是否是回文,结果确实是回文,因此你返回了 [0,1,2,3]

问题在于,这还不够,因为最长回文子序列可能有多个,比如 abab, 其中 aba 和 bab 都是最长回文子序列,因此每次可能要返回多个结果,这使得你向助理索要的信息越来越多,助理的工作量越来越高,而由于每个人处理的问题是相似的(递归性),因此实际自己的工作量也越来越高,每个人都很累,结果还解决不了问题 …

针对"回文"性质的子问题分解

上一轮失败的原因在于,分解成子问题时少了一点对回文性质的思考,你期望用一种不带"先验"信息的暴力分解方式:遍历式地对字符串每个字符进行删除,但这导致在回收信息和整理决策的时候付出巨大代价。

实际上,不需要找 n 个助手来解决问题,而是最多只需要三个,这种分解来自于一个关键的问题: "第一个字符和最后一个字符是否相同"

  • 这个问题完全来自于回文性质的驱动,在字符串长度大于 2 的情况下,如果一个字符串的第一个字符和最后一个字符不同,那么这两个字符不可能同时出现在最长的回文子序列中, 这意味着要找到最长的回文子序列,只需要考虑以下两种情况之一:去掉第一个字符的子字符串 s[1:], 或去掉最后一个字符的子字符串 s[:-1]。
  • 如果一个字符串的第一个字符和最后一个字符相同,那么有可能这两个字符会在最终的最长回文子序列中, 因此你还需要额外找一个助手去解决 s[1:-1] 这个子问题,同时汇总 s[:-1] 和 s[1:]. 注意,有些情况下我们甚至可以不考虑 s[:-1] 和 s[1:], 但直到讨论了有关歧义的内容后才会额外说明。

问题树的分解如下,其中中间的分支是按条件选择的:

             +--------+
             | s[i:j] |
             +--------+
                | | |
     +----------+ | +-----------+
     |            |             |
+---------+  +----+-----+  +---------+
|s[i+1:j] |  |s[i+1:j-1]|  |s[i:j-1] |
+---------+  +----------+  +---------+

注意这里为了更方便说明, s[i:j] 表示的是起点是 s[i] 终点是 s[j] 的字符串,而不是 python 里去掉 s[j] 后的字符串,当然也可以把 s[i:j] 看作是自定义的函数 s(i,j), 表示起点和终点分别是 s[i] 和 s[j] 的字符串的最长回文子序列长度。

在这个定义下,考虑到边界条件:

  • i==j 的时候,说明只有一个字符,因此最长回文长度是 1
  • 如果 i>j 那么是空串,返回长度应该就是 0; 注意 i>j 只有在字符串长度为 2, 且 s[0]==s[-1] 情况下才会发生,因此我们也可以结合 len(s)==2 以及 s[0]==s[-1] 来联合判断,不过以下第一个实现中还是用 i>j 分支表示。

我们可以写出如下代码,@lru_cache 不带参数意味着大小是一直可增长的:

from functools import lru_cache
def longestPalindromeSubseq(s: str) -> int:
    @lru_cache
    def sub(i, j):
        if i == j: return 1
        if i > j: return 0
        i_1 = sub(i+1, j)
        j_1 = sub(i, j-1)
        if s[i] == s[j]:
            return max(sub(i+1, j-1) + 2, i_1, j_1)
        return max(i_1, j_1)

    return sub(0, len(s) - 1)

longestPalindromeSubseq("abacab")
5

动态规划和格子的重现

有了以上带记忆的递归版本后,本节考虑这个问题的动态规划版本。前文说过,动态规划需要在递归的基础上额外投入一点思考,即对解决问题的路径的“规划”,从最小的子问题开始,按规划去逐个解决更大一点的问题。

比如给定例子 "abacab":

  • 要解决的最小子问题就是问 "a","b","a","c","a","b" 这些长度为 1 的子串的最长回文串长度,那么自然就是 1, 这个后文称为 unigram
  • 长度为 2 的子串是 "ab", "ba", "ac", "ca", "ab", 称为 bigram
  • 长度为 3 的子串称为 trigram
  • 依此类推,这个时候我们可以重新画出类似上一章路径和里的格子图:

    +-----+-----+-----+-----+-----+-----+-----+
    |     |     |     |     |     |     |     |
    |     |  a  |  b  |  a  |  c  |  a  |  b  |
    +-----+-----+-----+-----+-----+-----+-----+
    |     |     |     |     |     |     |     |
    | a   |    1|    2|    3|    4>    5|    6|
    +-----+-----+-----+-----+-----+--^--+-----+
    |     |     |     |     |     |     |     |
    | b   |    0|    1|    2|    3|    4|    5|
    +-----+-----+-----+-----+-----+-----+-----+
    |     |     |     |     |     |     |     |
    | a   |     |    0|    1|    2|    3|    4|
    +-----+-----+-----+-----+-----+-----+-----+
    |     |     |     |     |     |     |     |
    | c   |     |     |    0|    1|    2|    3|
    +-----+-----+-----+-----+-----+-----+-----+
    |     |     |     |     |     |     |     |
    | a   |     |     |     |    0|    1|    2|
    +-----+-----+-----+-----+-----+-----+-----+
    |     |     |     |     |     |     |     |
    | b   |     |     |     |     |    0|    1|
    +-----+-----+-----+-----+-----+-----+-----+
    

我们先解决对角线上标记为 1 的那些子问题,然后对角线上为 2 的子问题,而每个问题是直接依赖左侧和下侧格子的结果,此外还依赖左下格子(比上一章找路径的问题多出的额外依赖)

前文也分析过,i>j 会在字符串长度为 2, 且 s[0]==s[-1] 情况下发生,具体到图中,就是那些标记为 0 的斜线上的点会被访问,因此只需要对这些位置初始化为 0, 就可以很好地处理这种情况。

我们写出按对角线扫描的方式:

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for i in range(n-2, -1, -1):
        for j in range(i + 1, n):
            cand = max(dp[i+1][j], dp[i][j-1])
            if s[i] == s[j]:
                cand = max(dp[i+1][j-1] + 2, cand)
            dp[i][j] = cand

    return dp[0][-1]

longestPalindromeSubseq("abacab")
5

然而,正如上一章最小路径和问题中更加偏向按行扫描的方式进行规划,本例也可以考虑按行扫描而不是按对角线扫描,但由于依赖关系总体是从主对角线往右上方移动的,因此不能从上往下按行扫描,而是从下往上,对应到具体的场景里,对于 "abacab", 应该先解决最后一个 unigram "b", 然后解决倒数第二个 "a" 以及最后一个 bigram "ab", 依次向上扫描每一行

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    for i in range(n-1, -1, -1):
        dp[i][i] = 1
        for j in range(i+1, n):
            cand = max(dp[i+1][j], dp[i][j-1])
            if s[i] == s[j]:
                cand = max(dp[i+1][j-1] + 2, cand)
            dp[i][j] = cand

    return dp[0][-1]

longestPalindromeSubseq("abacab")
5

返回额外序列和歧义问题

接着考虑不单单要获得最长回文子序列长度,还要获得这个子序列的下标的情况,经过一点思考会发现,最长回文子序列可能是有多个的,比如 "abca" 包括 "aba" 和 "aca" 两个长度为 3 的回文子序列。而 "abaa" 包括 "aba","aaa" 这个两个,并且 "aba" 可以对应下标 [0,1,2] 和 [0,1,3] 两个子序列,因此如果问题改成

给你一个字符串 s ,找出其中最长的回文子序列。

那么这个问题对于不同的人是有不同结果的,因此这会导致"歧义"。可以把问题改成

给你一个字符串 s ,找出其中所有的最长的回文子序列,用序列下标方式返回。

对于自顶向下的递归方式:

  • 首先 sub 函数应该返回两个对象:最长回文子序列长度以及最长回文子序列集合。
  • 我们用 left,mid, right 区分以下三种子情况,并且分别比较它们返回结果中序列长度的部分,根据大小关系返回不同序列组合

                 +--------+
                 | s[i:j] |
                 +--------+
                    | | |
         +----------+ | +-----------+
         |            |             |
    +---------+  +----------+  +---------+
    |s[i+1:j] |  |s[i+1:j-1]|  |s[i:j-1] |
    +---------+  +----------+  +---------+
       left          mid         right
    

函数实现如下

from functools import lru_cache
def longestPalindromeSubseq(s: str) -> int:
    @lru_cache
    def sub(i, j):
        if i == j: return 1, [[i]]
        if i > j: return 0, []
        len_left, res_left = sub(i+1, j)
        len_right, res_right = sub(i, j-1)
        if len_left > len_right:
            len_cand, res_cand = len_left, res_left
        elif len_left < len_right:
            len_cand, res_cand = len_right, res_right
        else:
            len_cand = len_left
            res_cand = res_left + res_right
        if s[i] == s[j]:
            len_mid, res_mid = sub(i+1, j-1)
            if len_mid + 2 > len_cand:
                return len_mid + 2, [[i] + res + [j] for res in res_mid]
            elif len_mid + 2 == len_cand:
                return len_cand, [[i] + res + [j] for res in res_mid] + res_cand
        return len_cand, res_cand

    return sub(0, len(s) - 1)

print(longestPalindromeSubseq("abacab"))
print(longestPalindromeSubseq("abca"))
print(longestPalindromeSubseq("abaa"))
(5, [[1, 2, 3, 4, 5]])
(3, [[0, 2, 3], [0, 1, 3]])
(3, [[0, 2, 3], [0, 1, 3], [0, 1, 2]])

接着考虑动态规划方式,我们基于上一节中从下往上扫描的算法来修改,核心就是,在每个 grid 格子里,那些对最长回文子序列有贡献的格子做上标记,为了保持原本的 dp 数组接口不变,这里引入新的 mark 数组来记录 每个子问题里的符合要求的回文序列下标:

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    mark = [[[] for _ in range(n)] for _ in range(n)]
    for i in range(n-1, -1, -1):
        dp[i][i] = 1
        mark[i][i] = [[i]]
        for j in range(i+1, n):
            if dp[i+1][j] > dp[i][j-1]:
                cand = dp[i+1][j]
                mark[i][j] = mark[i+1][j]
            elif dp[i+1][j] < dp[i][j-1]:
                cand = dp[i][j-1]
                mark[i][j] = mark[i][j-1]
            else:
                cand = dp[i+1][j]
                mark[i][j] = mark[i+1][j] + mark[i][j-1]
            if s[i] == s[j]:
                if dp[i+1][j-1] + 2 > cand:
                    cand = dp[i+1][j-1] + 2
                    mark[i][j] = [[i] + x + [j] for x in mark[i+1][j-1]]
                elif dp[i+1][j-1] + 2 == cand:
                    mark[i][j].extend([[i] + x + [j] for x in mark[i+1][j-1]])
            dp[i][j] = cand

    return dp[0][-1], mark[0][-1]

print(longestPalindromeSubseq("abacab"))
print(longestPalindromeSubseq("abca"))
print(longestPalindromeSubseq("abaa"))
(5, [[1, 2, 3, 4, 5]])
(3, [[0, 2, 3], [0, 1, 3]])
(3, [[0, 1, 2], [0, 2, 3], [0, 1, 3]])

不考虑歧义和路径的优化技巧

这部分完全是一些算法优化技巧,可以跳过

现在我们再回到最初的问题,即只返回回文的长度,而不考虑所有子序列。实际上当 s[i] == s[j] 的时候,dp[i+1][j-1] + 2 就是唯一结果。

原因可以引用 参考 leetcode 里某用户回答:

以 dp[i+1][j]为例,设 dp[i+1][j]中的回文子串最大值为 m。

若回文子串中不包含 s[j],那么 dp[i+1][j]=dp[i+1][j-1],那 dp[i+1][j-1]+2 肯定大于 dp[i+1][j]。

若回文子串中包含 s[j],在 dp[i+1][j]中的最大回文串中,我们掐头去尾,删除 s[j]和某个等于 s[j]数,寻找内部 dp[i+1][j-1]中最大回文子串,其最大值为 m-2,即 dp[i+1][j-1]=m-2=dp[i+1][j]-2。等式两边同时加上 2,就有 dp[i+1][j-1]+2=dp[i+1][j]。

综上所述 dp[i+1][j-1]+2>=dp[i+1][j]。

@尚小锋

from functools import lru_cache
def longestPalindromeSubseq(s: str) -> int:
    @lru_cache
    def sub(i, j):
        if i == j: return 1
        if i > j: return 0
        if s[i] == s[j]:
            return max(sub(i+1, j-1) + 2, sub(i+1, j), sub(i, j-1))
        return max(sub(i+1, j), sub(i, j-1))

    return sub(0, len(s) - 1)

longestPalindromeSubseq("abacab")
5

动态规划形式:

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    for i in range(n-1, -1, -1):
        dp[i][i] = 1
        for j in range(i+1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])

    return dp[0][-1]

longestPalindromeSubseq("abacab")
5

现实场景:语法和语言解析

Chomsky: 对语言的描述和分类

上文都是在讨论 leetcode 里的玩具模型,它能够让我在一个理想环境中看待算法本身,本节则把注意力转移回到现实中的问题 – 语言的解析,但在真正进入算法前,还需要介绍一点理论背景。

在计算机科学中,没有特别说明时,语言指的就是符合某种规则的字符串的集合。比如说所有的回文就组成了一种语言(生活在回文星球的人可能说的就是回文),因为所有的回文 s 都符合以下规则:

def is_palindrome(s):
    return s == s[::-1]

print(is_palindrome(""),is_palindrome("a"),is_palindrome("aba"))
True True True

这种描述语言的规则一般称为语法(语言的法则),Chomsky 在 1960 年代根据描述语言规则的复杂性对语言进行了划分,这里我用一个类比来说明对语言如何进行划分以及划分的动机。

首先,对某种事物进行精确分类的样板是在数学之中,比如关于整数就有非常多不同的划分:自然数,偶数,奇数,完全平方数,素数等等

对于这些数可以提出至少两个需求:

  • 判定需求:给定一个数,判断它是不是某个类型的数,比如是不是平方数
  • 生成需求:请生成 1000 到 2000 之间的所有素数

这些判断和生成的需求会对应不同的难度,比如判断某个数是否是素数就比判断某个数是否是偶数更难。然而即便判断素数更难,但我们知道,判定是否为素数这个算法是存在的,因为素数的定义有一种 “分解”性质:判断 n 是否为素数,只需要找比 n 小的数(且大于 1 的正数)作为除数去除 n 就可以,“比 n 小的大于 1 的整数”这个性质使得问题是可控的(就像 top-down 方法里针对的问题是可以往更小的方向分解的)。

另外,对于偶数,判定规则和生成规则的难度是类似的,都一样简单,比如可以根据 n 是否可以被 2 整除来判断 n 是否为偶数,也可以在给定一个范围 [a,b] 后,如果 a 是偶数,那么就用 x=a, x+=2 的算法来不断生成偶数,直到这个值超过 b 。 但对于素数,判定算法和生成算法则不太一样,标准的判定算法以上已经提到,但生成素数则还有筛选法等各种基于判定算法的变种,这里主要是突出,有些数的分类中,判定和生成可能很不一样。

数学里还有一个叫做 3n+1 的猜想(也叫 Collatz 猜想,奇偶归一猜想,冰雹猜想等等,参见 考拉兹猜想 - 维基百科,自由的百科全书), 它说的是,给定任何一个数 n,如果这个数是偶数,那么把这个数重新赋值成 n/2, 如果是奇数,那么重新赋值成 n=3n+1, 如果依次迭代下去,最终 n 等于 1, 那么就称它为 Collatz 数,这个猜想是说:所有正整数都是 Collatz 数。

然而,之所以这是一个猜想,是因为目前为止它还是未解之谜,也就是说,给定任意一个数,我们不一定能确认它是否为 Collatz 数,同样的,我们也无法找到一个可靠的算法(一定会停止),生成所有的 Collatz 数。相比来说,我们很容易写出一个算法找出所有素数(尽管效率很低并且会永远执行下去,但我们知道它返回都是素数,并且不会有遗漏),而无法找出所有 Collatz 数的一个很宽泛但也有用的解释是: collatz 数产生或判断的规则中,不单单有朝着数字减小的方向(n/2),也有增大的方向(3*n+1) ,数字增大的方向可能导致算法永远无法回到一个 basecase(也就是 n=1),而判断素数的规则里只涉及比 n 小的数。

现在类比回到语言,如下 5 是数字,而字符串就是语言

5
"abcba" # 语言

对于一个语言,我们也有两个需求:

  • 判定:这是否是回文、英文、中文
  • 生成:生成所有长度为 4 的英文回文,生成诗歌

Chomsky 的贡献之一是,他发现自然语言的句法结构可以通过生成规则来描述,并且试图通过分析生成规则的复杂性从而理解语言的复杂性,正如可以通过研究数的判定/生成规则来研究数的性质。(其思想被吸收到计算机科学后,人们发展出可以通过分析生成规则来获得判定的方法,也就是后文要讲的语言解析相关的技术)

用一个例子说明基于句法结构的生成规则和其他规则的差别,我们可以定义一种语言,看到 a 之后生成 c, 看到 c 之后生成 b, 看到 b 之后生成 a, 我们可以用以下方式返回生成该语言中特定长度的句子的函数

def abc_rule(n):
    def _rule(cur_char):
        sentence = ""
        for i in range(n):
            sentence += cur_char
            if cur_char == "a":
                cur_char = "c"
            elif cur_char == "c":
                cur_char = "b"
            elif cur_char == "b":
                cur_char = "a"
            else:
                return ""
        return sentence
    return _rule

因此如果第一个字符是 a 就得到以下句子:

abc_rule(10)("a")
acbacbacba

如果第一个字符是 b:

abc_rule(10)("b")
bacbacbacb

如果是其他字符则返回空串:

abc_rule(10)("x")
''

以上这种生成规则是基于字符序列之间的关系或者状态来定义的,它看上去是水平方向的,是扁平的:规则是针对字符实例来描述的,不太具有结构性。

当我们说"公司的结构"时,很多时候实际是在谈论这个公司对职位等级的划分,句法的结构也是如此,给定一个句子,我们不单单看到一个一个的词,还会看到他们的标签(某个员工的职位),它们组成的团体的标签(组、部),因此当要组建一个开发团队时,我们可能先考虑到的是找到某个开发过类似产品的部门,从里面找一个产品经理,三四个开发,一两个测试,然后再根据这个层级的规划,去找根据职位找到对应的人选。

句法结构的生成规则也是如此:我们想表达某个句子的时候,先是想到了这应该有个主体、一个动作以及宾语,然后再替换成具体的表达某个对象的词。

这种做法实际非常反直觉,因为人在造句的时候似乎不会用"公司管理" 中分层派发任务的办法,却更像上文提到的基于字之间关系而生成的。 但问题在于,Chomsky 之前也没有人能提出一套比较有说服力的理论解释人是如何掌握和使用语言的,Chomsky 的贡献就在于,这套很不明显的规则被他表达了出来,并且他认为这是大脑潜意识里生成语言时所遵循的结构,从而把语言学、认知科学、教育学、哲学、人类学(比如他还认为人类可能在十万到五万年前因为基因突变,导致了递归枚举能力,来源: 尼克|乔姆斯基 vs ChatGPT_上海书评_澎湃新闻-The Paper )等领域都串起来了,而这套精确的语法定义在计算机科学里又被进一步发展和应用。

(注:如今 chatgpt 的预训练方式和 Chomsky 理论是有冲突的,chatgpt 完全就是基于前文提到的字符实例的前后关系来进行句子生成的,即根据上文的词预测下一个词,从训练手段来看,这是纯粹扁平而无结构的,但 gpt 目前无法形成一套解释性理论来反驳 Chomsky)

因此,假设有一套以下的语法规则:

S -> NP VP (一个句子由名词短语和动词短语组成)
NP -> Det N (名词短语由限定词和名词组成)
NP -> N (名词短语也可以直接是名词)
VP -> V NP (动词短语由动词和名词短语组成)

按照 Chomsky 的理论, 我说话时潜意识是这样的:一个句子由名词短语和动词短语组成,名词短语只能是名词或者限定词加名词,动词短语只能是动词接一个名词短语。而由于当前所看到的景象,动词、冠词、名词的生成规则几乎被限定如下(可能我眼前看到了小猫和苍蝇):

V -> 追
Det -> 一只
N -> 苍蝇 
N -> 小猫 

因此我不需要有意识地去组织句子或思考,大脑对语言结构本身的理解就促使我说出了一句 "小猫追一只苍蝇”,而这是符合语法的。

反过来,当看到 "小猫追一只苍蝇" 时,可以构建出一棵语法解析树:

          +--------+
    +-----|   S    |--------+
    |     +--------+        |
+--------+            +-----------+
|   NP   |        +---|     VP    |---+
+--------+        |   +-----------+   |
    |             |                   |    
+---+----+   +---------+          +-------+
|   N    |   |    V    |       +--|  NP   |---+
+--------+   +---------+       |  +-------+   |
    |             |         +------+       +-----+
    |             |         | Det  |       |  N  |
    |             |         +------+       +-----+
    |             |            |              |
+-------+     +-------+     +------+       +-----+
| 小猫   |     |  追   |     | 一只  |       | 苍蝇 |
+-------+     +-------+     +------+       +-----+

注意这种生成规则是天然地从抽象层级向下不断递归发展的过程(递归下降)。

而如果我们从下往上看,最底层是具体的词,向上一层是这些词的词性,再上一层是对词性级别按照规则的组合,最终组成了一个句子 S。

CFG 和 Chomsky 语言层次

以上例子中给出的语法被称为上下文无关文法(context free grammar, CFG),它是 Chomsky 对语法结构划分的类别结果之一,被称为 Chomsky 2 型文法,它的核心特点在于:

  • 同时右边任意位置都允许出现左边已经出现过的变量(即允许递归定义)
    • 如果右侧不允许递归定义,但可以用记号表示某些重复,比如

      username : [a-z]+[0-9]+
      

      这里 [a-z]+ 表示这部分单词只由小写字母组成,可以重复任意多次,例如 abca,同样 [0-9]+ 表示可以由任意数字组成,因此 abca121 就是合法的 username.

      这种语言右侧不能有左侧已经定义过的符号,而只有终结字符,但给予了 "终结符号" 一些组合自由度,比如重复,拼接,这被称为正则语言或 Chomsky 3-型语言。

  • 生成规则的左边只有一个变量,也就是说生成规则一定是扩展性质的规则,而不会缩减。
    • 比如 VP -> V NP 这说明不管在什么场景下,动词短语标签都可以展开成一个动词连接一个名词短语, 这是上下文无关的核心意义。
    • 如下是一个反例:

      aXb : aXXb
      

      符号 X 只有在左右分别是 a 和 b 的时候才能扩展,这是上下文有关的(被称为 1-型语言)。

    • 再比如:

      xxxxx : -
      

      假设右侧 - 表示空白,这条规则类似五子棋,只要五个连在一起就消除,这也是上下文有关的。

    • 如果在规则中出现:

      VP VP-> VP
      

      那么这说明一个句子在生成的过程中,它的描述长度可能会缩减,因此当在反推这个语言的结构时,发现其中有一部分是 VP(比如动词短语"追苍蝇"), 而查看规则后发现 VP 竟然是可以根据两个 VP 缩减而来,因此 "追苍蝇" 这句话的语言结构可能有任意多的 VP (只不过都被这个规则消解了)。

      因此该语言结构可能有无限多种,变得复杂,这可以类比到 3n+1 猜想。这种语法对应的语言称为 0 型文法,

这种语法描述的字符串就像是整数分类里的素数,足够复杂,但却是可控的(可以递归到 basecase)。

四种语言分类如下,数值越大,限制越强,表达能力越弱:

Chomsky hierarchy:

/-------------------------------------------\
|                                           |
|     Recursively enumerable languages      | Type 0: γ->α
|                                           |
|   /-----------------------------------\   | <- recursive language(type 0.5)
|   |                                   |   |
|   |    Context-sensitive languages    |   | Type 1: αAβ->αγβ
|   |                                   |   |
|   |   /---------------------------\   |   |
|   |   |                           |   |   |
|   |   |  Context-free languages   |   |   | Type 2: A->α
|   |   |                           |   |   |
|   |   |   /-------------------\   |   |   |
|   |   |   | Regular languages |   |   |   | Type 3: A->aB|a
|   |   |   \-------------------/   |   |   |
|   |   \---------------------------/   |   |
|   \-----------------------------------/   |
\-------------------------------------------/
α: terminal
A,B: non-terminal
α,β,γ: string of terminals and/or non-terminals

注:图片基于 The true power of regular expressions, 对这些语言的更多介绍也可参考该链接。

以上链接文章中还解释了为什么正则表达式也可以识别编程语言,因为编程语言中的正则表达式(记为 reg)不是语言理论里的描述的标准正则语言(3 型语言)所对应的表达式,文章中提到,编程语言正则库基本可以匹配所有 CFG 甚至递归可枚举语言(加上 backtrack)。但用 reg 去解析 CFG 无法方便地获得语义树、错误信息解析等等,因此需要根据实际需求来使用。

文中还提到 context-sensitive grammar 和 non-contracting grammar 等价,这对于上文提到的关于 3n+1 猜想的类比算是一种支持。

对语法的描述之 BNF 范式

上一节中,我们介绍了语法,用来描述某一类字符串,其中引入了一个语法例子:

S -> NP VP 
NP -> Det N 
NP -> N 
VP -> V NP 

V -> 追
Det -> 一只
N -> 苍蝇 
N -> 小猫 

要注意的是,以上代码也是一串字符串,因此它也是某种语言,具有某种规则,比如每行有一个箭头,箭头左边只有一个变量,右边有多个,从左到右的箭头表示左边的变量可以被右边的变量组合替换掉,这种描述语法的语言可以称为元语法,或者叫做范式。语言的有趣和混乱就来自于描述语言的对象也是语言,而这可以无限递归下去,不过在实现上,必须找到一个递归的终点,而一般到范式层就算是终点了。

可以很容易用另外一种形式来描述相同的语法,比如最简单的,把箭头改成冒号:

S   : NP VP 
NP  : Det N 
NP  : N 
VP  : V NP 

V   : 追
Det : 一只
N   : 苍蝇 
N   : 小猫 

对于最后两条规则,即名词可以被"苍蝇"替换,也可以被 "小猫" 替换,这是一个集合,因此可以写成:

N   :{"苍蝇","小猫" }

这种精简后的语法称为巴科斯范式(Backus-Naur Form,BNF),标准的 BNF 范式如下

S   ::= NP VP 
NP  ::= Det N 
NP  ::= N 
VP  ::= V NP 

V   ::= 追
Det ::= 一只
N   ::= 苍蝇 | 小猫

也就是说生成符号用 ::= 表示,而集合关系用 | 表示,但实际用这些符号并不重要,BNF 范式的核心是其结构,从左到右生成,并且右侧支持集合这种表示,比如以下是用 python 列表对以上语言的 BNF 文法表示:

simple_grammar = [
  ("S " , ["NP", "VP"]) ,
  ("NP" , ["Det", "N"]) ,
  ("NP" , ["N"] ),
  ("VP" , ["V", "NP"] ),
  ("V"   , "追"),
  ("Det" , "一只"),
  ("N " , {"苍蝇", "小猫"}),
]

接着,可以看到,以上有两类很不一样的符号,一组是 "NP", "VP", "S" 这样的结构性描述变量,比如 S 是对句子的标签,NP 是对短语的标签,另一组如 "V", "Det","N" 是对词的标签,而 "追", "一只", "苍蝇", "小猫" 这些是具体的词库。

对于最后三条规则,类似于替换的终点(递归树的叶子节点),因为一旦执行到这些规则,至少在该分支下就无法继续替换了

simple_grammar_lexicon = [
  ("V"   , "追"),
  ("Det" , "一只"),
  ("N " , {"苍蝇", "小猫"}),
]

这部分规则称为 POS category, 它描述了所有可能的用词以及这些用词的语法标签(动词、名词形容词等), 也称 lexicon 。甚至严格来说,这部分不是语法,因为它没有描述语言组件之间组合的规则,而只是各个词的可能类别。

simple_grammar 的另一部分如下,这里描述的纯粹是句子的组成规则,规则的两边都是抽象变量,它是递归树里非叶子节点部分,也称为 CFG rules 。

simple_grammar_cfg_rules = [
  ("S " , ["NP", "VP"]) ,
  ("NP" , ["Det", "N"]) ,
  ("NP" , ["N"] ),
  ("VP" , ["V", "NP"] ),
]

对 rules 和对 lexicon 的区分可以带来实践上的灵活性, 比如有些场景下只需要分析词库,那么只需要 lexicon,但如果要进一步做句法分析,则需要把 cfg rules 也带上。

回文的 CFG 表示

假设字符串只由英文小写字母和数字组成,那么回文可以用以下 CFG 文法描述

S -> aSa | bSb | cSc | ... | zSz | 0S0 | 1S1 | ... | 9S9
S -> - | a | b | c | ... | z | 0 | 1 | ... | 9

"-" 表示 S 可以是空的。

其他 CFG 范式举例

除了 BNF 范式,还有其他范式可以描述 CFG 语法,比如 Grammatical Framework, 其一个例子如下(来自 Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning - ACL Anthology Appendix B):

abstract Food = {
flags startcat = Comment ;
cat
Comment ; Item ; Kind ; Quality ;
fun
Pred : Item -> Quality -> Comment ;
This , That : Kind -> Item ;
Mod : Quality -> Kind -> Kind ;
Wine , Cheese , Fish : Kind ;
Very : Quality -> Quality ;
Fresh , Warm , Italian , Expensive , Delicious , Boring : Quality ;
}

GPT 对以上例子的解释是:

  • 先定义这种抽象语法的名称: Food
  • 开始类别(flags startcat = Comment):这指定了语法的起始类别或起始符号,即“Comment”。这意味着生成的句子或结构将从“Comment”类别开始。
  • 类别(cat):这里定义了语法中使用的不同类别(或符号)。包括“Comment”(评论)、“Item”(项目)、“Kind”(种类)和“Quality”(质量)。
  • 函数(fun):这部分定义了语法的函数,用于构建句子或短语,类似 BNF 里的 CFG rules, 但这里生成方向总体是从右边到左边。
    • Pred : Item -> Quality -> Comment:这个函数表示一个“Item”(项目)和一个“Quality”(质量)可以结合生成一个“Comment”(评论)。
    • This, That : Kind -> Item:这表示“这个”或“那个”某种“Kind”(种类)可以表示一个“Item”(项目)。
    • Mod : Quality -> Kind -> Kind:这表示一个“Quality”(质量)可以修饰一个“Kind”(种类),生成一个新的“Kind”。
    • Wine, Cheese, Fish : Kind:这定义了具体的“Kind”(种类),即“Wine”(葡萄酒)、“Cheese”(奶酪)、“Fish”(鱼)。
    • Very : Quality -> Quality:这表示“Very”(非常)可以用来加强一个“Quality”(质量)。
    • Fresh, Warm, Italian:这些是定义的“Quality”(质量)属性,如“Fresh”(新鲜的)、“Warm”(温暖的)、“Italian”(意大利的)。

语言解析里的动态规划: CKY

CKY 的格子世界

现在假设有以下 CFG 语法(该例子基于 Probabilistic CKY Algorithm):

cfg_rules = [
  ["S" , ["NP", "VP"]],
  ["NP" , ["Det", "N"]],
  ["VP" , ["V", "NP"]],
]
  
lexicon = [
  ["V" , "includes"] ,
  ["V" , "price"],
  ["Det" , "the"],
  ["Det" , "a"],
  ["N" , "price"]
]

现在希望设计一个算法,能够给定一个通过该语法规则所生成的句子,比如 "The price includes a facemsk" 返回这个句子的语法构成,它可以是解析树的一种表达式。比如手动解析的话, "The price" 应该是名词短语,它由冠词 The 和名词 price 组成,includes a facemask 是动词短语,它由动词 includes 和 a facemask 名词短语组成,而后者又继续由冠词和名词构成,因此这句话和 "小猫追一只苍蝇" 的解析树是很像的,只是第一个名词短语是冠词加名词,而不是一个名词,它的解析树如下:


                   +--------+
             +-----|   S    |--------+
             |     +--------+        |
         +--------+            +-----------+
  +------|   NP   |        +---|     VP    |---+
  |      +--------+        |   +-----------+   |
  |          |             |                   |    
+-----+  +---+----+   +---------+          +-------+
| Det |  |   N    |   |    V    |       +--|  NP   |---+
+-----+  +--------+   +---------+       |  +-------+   |
  |         |             |         +------+       +-----+
  |         |             |         | Det  |       |  N  |
  |         |             |         +------+       +-----+
  |         |             |            |              |
+-----+ +-------+    +---------+    +------+      +--------+
| the | | price |    |includes |    |   a  |      |facemask|
+-----+ +-------+    +---------+    +------+      +--------+

有许多表示这种树的方法,比如嵌套的方式(只给出 includes a facemask 部分)

(VP (V includes) (NP (Det a) (N facemask)))

也可以返回一个树的表征,比如返回 root 对象,其中包括子树 NP, VP 对象的索引

本节用 CKY 算法来解决这个问题,CKY 是三个科学家的名字,因此有时候也叫 CYK.

CKY 的思路的展开和前文中寻找最长回文子序列的 grid 非常类似,从最短的子串开始,在长度这个维度上逐渐增加并分步解析。 解析实际就是在做抽象,比如说,当你知道熊猫是一种动物的时候,再看到熊猫时说这是动物,这就是抽象的过程。

在字符串解析中,第一步抽象也就是对每个词(长度为 1 的字符串)找到它的词性标签, 标记在对角线上,因为对角线表示的就是 s[i:i+1] 这个词。

         The         price     includes     a     facemask

         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
The      |         |         |         |         |         |
         |     Det |        2|       3 |        4|        5|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
price    |         |         |         |         |         |
         |         |     N/V |        2|        3|        4|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
includes |         |         |         |         |         |
         |         |         |       V |        2|        3|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
a        |         |         |         |         |         |
         |         |         |         |     Det |        2|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
facemask |         |         |         |         |         |
         |         |         |         |         |       N |
         +---------+---------+---------+---------+---------+

注意 price 一词可以是动词也可以是名词,因此两种可能都要标上。

接着考虑长度为 2 的序列,也就是以下 bigram 是什么语法结构

from pprint import pprint
s = "The price includes a facemask".split()
pprint([s[i:i+2] for i in range(len(s)-1)])
[['The', 'price'], ['price', 'includes'], ['includes', 'a'], ['a', 'facemask']]

这里的核心在于,由于在文法中区分了 Grammar rule 和 lexicon , 因此我们不需要从具体的 string pair (比如 "the price","price include")来分类,而只需要根据上一步解析的词的词性的组合进行分类,比如当考虑 "The price" 是属于什么语法类别时,只需要对 Det N 组合以及 Det V 组合进行分类,从语法规则里逆向匹配发现 Det N 有语法标签的 NP, 而 Det V 则没有语法标签,因此对于 The price, 只有 NP 这个语法标签,我们写在第 1 行第二列:

         The         price     includes     a     facemask

         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
The      |         |         |         |         |         |
         |     Det | ->  NP  |        3|        4|        5|
         +---------+---------+---------+---------+---------+
         |         |     ↑   |         |         |         |
price    |         |         |         |         |         |
         |         |     N/V |        2|        3|        4|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
includes |         |         |         |         |         |
         |         |         |       V |        2|        3|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
a        |         |         |         |         |         |
         |         |         |         |     Det |        2|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
facemask |         |         |         |         |         |
         |         |         |         |         |       N |
         +---------+---------+---------+---------+---------+

从 grid 操作上看,我们就是从当前格子的左边和下方读取标签,然后组合起来,再到语法表中去进行匹配,找到合适的分类。 用这种方式可以把所有 bigram 都进行语法分类,如果没有分类,则保留表示长度的数字,得到如下结果

         The         price     includes     a     facemask

         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
The      |         |         |         |         |         |
         |     Det | ->  NP  |        3|        4|        5|
         +---------+---------+---------+---------+---------+
         |         |     ↑   |         |         |         |
price    |         |         |         |         |         |
         |         |     N/V |        2|        3|        4|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
includes |         |         |         |         |         |
         |         |         |       V |        2|        3|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
a        |         |         |         |         |         |
         |         |         |         |     Det | ->    NP|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |       ↑ |
facemask |         |         |         |         |         |
         |         |         |         |         |       N |
         +---------+---------+---------+---------+---------+

接着考虑 trigram, 也就是长度为 3 的子序列,如下

s = "The price includes a facemask".split()
pprint([s[i:i+3] for i in range(len(s)-2)])
[['The', 'price', 'includes'],
 ['price', 'includes', 'a'],
 ['includes', 'a', 'facemask']]

从这里开始,格子操作和回文判断有所不同了,我们不能继续取左边的格子和下方的格子拼接起来,比如,假设 grid[0][2] 表示的是 "The price includes" 子字符串的语法分类,如果从它左侧格子 grid[0][1] 和下方格子 grid[1][2] 进行判断的话,就相当于认为 "The price includes" 是根据 "The price" 和 "price includes" 这两个子串拼接起来的,但事实上是 "The price includes" 的子串分解有两种情况:

  1. "The price" + "includes": 对应的是 grid[0][1] 和 grid[2][2]
  2. "The" + "price includes": 对应的是 grid[0][0] 和 grid[1][2]

对于第二种分解情况,如下图所示:

         The         price     includes     a     facemask

         +---------+---------+---------+---------+---------+
         |        ------------->       |         |         |
The      |         |         |         |         |         |
         |     Det |     NP  |      ↑ 3|        4|        5|
         +---------+---------+------|--+---------+---------+
         |         |         |      |  |         |         |
price    |         |         |         |         |         |
         |         |     N/V |        2|        3|        4|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
includes |         |         |         |         |         |
         |         |         |       V |        2|        3|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
a        |         |         |         |         |         |
         |         |         |         |     Det |       NP|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
facemask |         |         |         |         |         |
         |         |         |         |         |       N |
         +---------+---------+---------+---------+---------+

这里由于 grid[1][2] 没有语法标签,因此组合后的子串也没有语法标签

接着看 grid[0][2] 的另一个依赖,它要求对 NP V 组合找到标签,结果也没有:

         The         price     includes     a     facemask

         +---------+---------+---------+---------+---------+
         |         |      ----->       |         |         |
The      |         |         |         |         |         |
         |     Det |     NP  |      ↑ 3|        4|        5|
         +---------+---------+------|--+---------+---------+
         |         |         |      |  |         |         |
price    |         |         |      |  |         |         |
         |         |     N/V |      | 2|        3|        4|
         +---------+---------+------|--+---------+---------+
         |         |         |      |  |         |         |
includes |         |         |         |         |         |
         |         |         |       V |        2|        3|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
a        |         |         |         |         |         |
         |         |         |         |     Det |       NP|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
facemask |         |         |         |         |         |
         |         |         |         |         |       N |
         +---------+---------+---------+---------+---------+

用更精确的语言来描述就是, s[i][j] 的依赖是 s[i][j-k] 以及 s[i+(len-k)][j], 这里 len 就是当前处理的子串长度,此时 3, 按这个方式填补完长度为 3 的子序列对应的其他格子,只有 grid[2][4] 也就死 includes a facemask 才有对应的有效标签

         The         price     includes     a     facemask

         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
The      |         |         |         |         |         |
         |     Det |     NP  |        3|        4|        5|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
price    |         |         |         |         |         |
         |         |     N/V |        2|        3|        4|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
includes |         |         |       ----------------> VP  |
         |         |         |       V |        2|      ↑ 3|
         +---------+---------+---------+---------+------|--+
         |         |         |         |         |      |  |
a        |         |         |         |         |         |
         |         |         |         |     Det |       NP|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
facemask |         |         |         |         |         |
         |         |         |         |         |       N |
         +---------+---------+---------+---------+---------+

同理,对长度为 4 的子串寻找标签,那么 len 就是 4. 它包括两个子句 "The price includes a" 和 "price includes a facemask", 按照前文提到方法,检查各种组合发现都没有语法标签存在。

最后进入到长度为 5 的字符串,这就是句子本身,可以发现 grid[0][4] 从 grid[0][1] (对应 NP) 和 grid[2][4] (对应 VP) 上能够找到一个语法标签,即 S, 如下:

         The         price     includes     a     facemask

         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
The      |         |       ------------------------> S     |
         |     Det |     NP  |        3|        4|   ↑    5|
         +---------+---------+---------+---------+---|-----+
         |         |         |         |         |   |     |
price    |         |         |         |         |   |     |
         |         |     N/V |        2|        3|   |    4|
         +---------+---------+---------+---------+---|-----+
         |         |         |         |         |   |     |
includes |         |         |         |         |     VP  |
         |         |         |       V |        2|        3|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
a        |         |         |         |         |         |
         |         |         |         |     Det |       NP|
         +---------+---------+---------+---------+---------+
         |         |         |         |         |         |
facemask |         |         |         |         |         |
         |         |         |         |         |       N |
         +---------+---------+---------+---------+---------+

格子性质和 CNF 形式:递归分支数量问题

以上例子中,我们之所以可以只从格子的左侧和下方两个方向作为依赖,是因为给出的 CFG rules 规则中,右侧的数组长度都是 2:

cfg_rules = [
  ["S" , ["NP", "VP"]],
  ["NP" , ["Det", "N"]],
  ["VP" , ["V", "NP"]],
]

比如 "S" : ["NP", "VP"] 表示对于一个句子可以切成两个子串,左子串的标签是 NP, 对应格子的左边,右子串的标签是 VP 对应格子的下方。

问题在于,是否所有 CFG 规则都能写成这种形式呢? Chomsky 证明可以把所有 CFG rules 都写成右侧只有两个变量的情况,这种形式称为 CNF 形式(Chomsky Normal Form), 它要求所有规则必须是以下两种形式之一:

A -> BC(其中A、B和C是非终结符,B和C不能是开始符号)
A -> a(其中A是非终结符,a是终结符)

注意第二条也可以扩展到右侧可以是多个终结符的集合。

证明方法是,考虑所有生成规则的形式,对这些形式构建对应的转换规则,将其转为 CNF 形式:

  • 消除右侧大于 2 个变量的情况

    A->BCD
    

    可以引入一个额外的语法标签 I

    A->BI
    I->CD
    

    对于右侧有更多的情况,只需要引入更多层级的规则。

  • 消除混合右部(非终结符和终结符混合出现)的产生式。

    A->Ba
    

    这里 B 是变量(非终结符号或语法标签),a 是具体的词 这时候可以对 a 引入单独的一个语法标签 I:

    I->a
    A->BI
    

    对于更多混合的情况,比如 A->BCdef, 则结合本条规则和上一条规则

  • 消除右侧只有一个变量的情况

    A -> B
    

    注意我们不能引入一个表示空字符串的非停止符号 E,比如 A->BE, 这种情况没有意义,因为在格子世界中,相当于要去检查一个空串的标签,也就是类似 grid[-1][2] 的元素,这没有什么意义。

    消除方法是,根据前两条规则,实际上对于 B 它要么是生成两个非终结符,如 B->CD, 要么是生成终结符如 B->b, 因此 B 的展开规则已经是 CNF 了,因此只需要把 B 替换成 CNF 替换的结果之后就变成

    A -> CD
    //or
    A -> b
    

所以 CNF 形式实际是于抽象的格子世界形式上的对齐,另一方面它使得递归形式很规范,递归的树是一棵二叉树。

自然语言的歧义和语法概率化

首先回忆一下 回文里歧义的例子,比如 abaa 里有三个子序列都是回文:

print(longestPalindromeSubseq("abaa"))
(3, [[0, 1, 2], [0, 2, 3], [0, 1, 3]])

对应到语法解析中,歧义就是给定一个句子,算法解析出了不止一棵的解析树,而放在句子本身,就是不同的人对这个句子有不同的理解。 然而这个说法还是宽泛了,自然语言中歧义有很多种,包括词的歧义,比如 I went to the bank, 这里 bank 可以是银行也可以是河岸,这句话本身就不是上下文无关的,因此 CKY 或任何解析 CFG 的算法都无法处理。

而我们本节讨论的是自然语言里歧义的某个子集,首先这些句子基本能够被上下文无关文法描述,因此可以被 CKY 算法解析,但解析之后还是有语法结构上的歧义,比如一个经常拿来说明结构性歧义的例子

One morning I shot an elephant in my pajamas.

Groucho Marx, Animal Crackers, 1930

这里 I shot an elephant in my pajamas 的 in my pajamas 可以和 an elephant 组合成一个名词短语,表示穿着睡裤的大象,也可以和 shot an elephant 组合成一个动词短语,表示我穿着睡裤射击了一头大象(这里还有歧义,比如也可以解释成我在睡裤里射击了大象,但这是语法结构无法区分的)。

这种介词可以跟随不同对象而发生的歧义在英文里不少见,因此还有一个专门的名字来描述: PP-attachment 歧义。

GPT 对这个段子的解释

这句话出自 Groucho Marx 在 1930 年电影《动物饼干》中的一句幽默台词。它运用了英语中的语言游戏,通过模糊"在我睡衣里"这个状语的指代对象,制造了一个荒谬的幻想:大象穿着人的睡衣。实际上,这句话是在开玩笑,指的是射击大象的事件发生在穿着睡衣的时候,但字面上却好像是大象穿着睡衣。这是典型的幽默风格,通过语言的双关和歧义制造笑点。

人类在读到有歧义句子时,可能会说,我觉得它应该更倾向于这种意思 …, 也就是说人类会通过概率性地比较来试图消除歧义,把这中想法放到算法里就是概率话的 CKY, 这里的核心就是对返回的解析树赋予一个概率,如何赋予?这里做法是,对每个生成规则附加一个概率,动态规划中每次找到一个合并规则时,就把这个概率附加进去。用 I shot an elephant in my pajamas. 的例子来说明,

imp_cfg_rules = [
  ["S" , (1, ["Pronoun", "VP"])],
  ["VP" ,(0.6, ["V", "NP"])],
  ["NP" ,(0.6, ["Det", "Nominal"])],
  ["NP" ,(0.4, ["Det", "N"])],
  ["Nominal", (1, ["N", "PP"])],
  ["VP" ,(0.4, ["VP", "PP"])]
]

imp_lexicon = [
    ["Pronoun" , (0.3, "I")],
    ["V" , (0.2, "shot")],
    ["V" , (0.5, "like")],
    ["Det" , (0.4, "the")],
    ["Det" , (0.2, "an")],
    ["PP" , (1, "in my pajamas")], 
    ["N" , (1, "elephant")]
]

这里把 "in my pajamas" 看作一个符号,后文有时候直接简称为 imp

统计一个句子有多少解释的递归算法

就好比前文中 leetcode 题要求造出一个字符串有多少回文子序列,本节则给定一个字符串用 CKY 算法找出该句子在某个语法规则下有多少种解释。

我们不考虑分词,而是把分词结果作为算法输入,那么输入的就是:

pajamas = ["I", "shot", "an", "elephant", "in my pajamas"]

定义递归函数 s(i,j) 表示句子 sent[i:j+1] 可能包含的解释数量,但有这个统计值还不够,我们每一步子问题分解过程中,还需要知道子句子的语法标签,可以定义 g(i,j) 表示 sent[i:j+1] 的语法标签,比如可以是 "V", "Det" 也可以是 None

那么可以写出递归的表达式:

g(i,j) = sum([rule(g(i,k), g(k+1,j)) for k in range(i, j)])
s(i,j) = len(g(i, j))

rule([a,c], [b]) 会先对两个参数做笛卡儿积,比如得到 [a,b], [c,b], 然后分别去 grammar rules 中找生成规则是这些结果的变量名,返回所有结果,如果没有,则返回 []

base case 中,如果 g(i,i+1) 则是从 lexicon 里搜索到的 POS 集合,只需要计算函数 g

编写这个算法:

from functools import lru_cache
from itertools import product
def cky_num(s: str) -> int:
    @lru_cache
    def g(i, j):
        if i == j: return pos(s[i])
        res = sum([rule(g(i,k), g(k+1, j)) for k in range(i, j)], [])
        return [x for x in res if x]

    return g(0, len(s) - 1)

def pos(token):
    return [p for p,(prob, tok) in imp_lexicon if tok == token]

def rule(tags1, tags2):
    res = []
    for t1, t2 in product(tags1, tags2):
        x = [pos for pos,(prob, toks) in imp_cfg_rules if toks == [t1,t2]]
        res.extend(x)
    return res

print([pos(x) for x in pajamas])
print(rule(["Det"], ["N"]), rule(["Det"], ["Nominal"]))
print(cky_num(pajamas))
[['Pronoun'], ['V'], ['Det'], ['N'], ['PP']]
['NP'] ['NP']
['S', 'S']

这里看到,这句话有两种不同的语法结构,也就对应两种解释

返回所有解析树的 CKY 算法递归实现

现在继续扩展,不单单要给出解释的数量,还要给出这些解释所对应的语法树以及该语法树下解释的概率。

对于递归情况,可以把每个阶段的解析树返回,而不单单返回树的根节点,这里我们用嵌套列表来表示树:

from functools import lru_cache
from itertools import product
cky_trees = cky_num

def pos(token):
    return [[p] for p,(prob, tok) in imp_lexicon if tok == token]

def rule(tags1, tags2):
    res = []
    for t1, t2 in product(tags1, tags2):
        x = [[pos, t1, t2] for pos,(prob, toks) in imp_cfg_rules if toks == [t1[0],t2[0]]]
        res.extend(x)
    return res

print([pos(x) for x in pajamas])
pprint(cky_trees(pajamas))
[[['Pronoun']], [['V']], [['Det']], [['N']], [['PP']]]
[['S', ['Pronoun'], ['VP', ['V'], ['NP', ['Det'], ['Nominal', ['N'], ['PP']]]]],
 ['S', ['Pronoun'], ['VP', ['VP', ['V'], ['NP', ['Det'], ['N']]], ['PP']]]]

注意这里只修改了 pos 返回结果的部分

return [p for p,(prob, tok) in imp_lexicon if tok == token]
# 改成
return [[p] for p,(prob, tok) in imp_lexicon if tok == token]

rule 函数中

x = [pos for pos,(prob, toks) in imp_cfg_rules if toks == [t1,t2]]
# 改成
x = [[pos, t1, t2] for pos,(prob, toks) in imp_cfg_rules if toks == [t1[0],t2[0]]]

接着把概率也加进去:

def pos(token):
    return [[p, prob] for p,(prob, tok) in imp_lexicon if tok == token]

def rule(tags1, tags2):
    res = []
    for t1, t2 in product(tags1, tags2):
        x = [[pos, prob*t1[1]*t2[1], t1, t2] for pos,(prob, toks) in imp_cfg_rules if toks == [t1[0],t2[0]]]
        res.extend(x)
    return res

cky_prob_trees = cky_num
print([pos(x) for x in pajamas])
pprint(cky_prob_trees(pajamas))
[[['Pronoun', 0.3]], [['V', 0.2]], [['Det', 0.2]], [['N', 1]], [['PP', 1]]]
[['S',
  0.00432,
  ['Pronoun', 0.3],
  ['VP',
   0.0144,
   ['V', 0.2],
   ['NP', 0.12, ['Det', 0.2], ['Nominal', 1, ['N', 1], ['PP', 1]]]]],
 ['S',
  0.001152,
  ['Pronoun', 0.3],
  ['VP',
   0.0038400000000000005,
   ['VP',
    0.009600000000000001,
    ['V', 0.2],
    ['NP', 0.08000000000000002, ['Det', 0.2], ['N', 1]]],
   ['PP', 1]]]]

至于 cfg_rules 和 lexicons 里概率从何而来,这就是统计学习的知识,本文不展开,如有兴趣可以阅读 https://web.stanford.edu/~jurafsky/slp3/17.pdf, 对本章以及上一章里提到的关于语法的知识的更详细描述也可参考此书。

理论到工程:算法复杂度、解析语法和左递归问题

可以把以上算法改写成动态规划形式,把递归函数 g(i,j) 用 grid 二维数组表示,然后通过回溯的方式来重建解析树,这能提高实际应用中的计算效率。

由于修改方式几乎和回文问题的一样,并且本章已经详细描述了子问题分解过程,这里不再实现具体算法。但通过动态规划对应的格子操作可以看出,CKY 算法的时间复杂度是 O(n^3), 因为先要遍历格子的所有上三角部分,这就是 n^2 了,而每个格子里需要遍历 n 种切分方式,总共是 n^3。

要知道这是在解析 CNF 文法描述的语言上的结果,而所有的 CFG 语言都可以用 CNF 来描述,这意味着,对所有 Context Free 语言的解析,最差也是 O(n^3) ,这实际算是个好消息 。

因为前文提到,Chomsky 原本是从理论上分析人类语言,划分成了四类,其中包括 CFG, 它具有递归和上下文无关性质。

尽管自然语言本身不是上下文无关的,但由于 CFG 语法相对简单灵活的性质,我们可以构造出多项式复杂度的通用的解析算法 – CKY, 对于更复杂的语法,比如 0 型语法,解析的复杂度会更高,对于更简单的语言,比如正则,表达能力又太弱了。

因此 CFG 在理论表达和工程上的一个权衡结果,它能比较近似地解决一些自然语言分析的问题。 比如它一方面可以捕捉自然语言中可能存在的 "歧义" 问题,另一方面,计算语言学的研究者提出概率化的 CKY 算法,通过对不同解析树打分的方式,又可以进行消歧(正如人类也有这种能力)。

不过,这些工作本质还是在对人类语言这种依靠演化而出现的客观事物进行科学建模,我们需要充分尊重自然语言对象的属性,并设计出那些效率能过被接受的算法。

但当计算机科学家的目的不是用它去解释客观对象的原理,而是为了解决具体问题或创造解决其他问题的工具(造轮子),因此这里出现了大量的权衡和偏好选择。就像牛顿进行科学发现找到了精简的三条定律,但后世人们用牛顿定律创造的事物不计其数,Chmosky 就称自己是在对语言学进行科学化,牛顿力学是科学化的样板。

计算机科学可以在 CFG 的语法范畴里任意设计自己的语言,比如取它的某个规则子集,从而避免歧义(也就避免引入概率手段),用奥卡姆剃刀原则使得语句足够精简,加入比 CNF 更强的限制性的规则(CNF 和通用 CFG 语法是等价的)以使得 那个抽象的格子世界具有更多的结构性,从而不需要一个一个地去扫描解析,以此把复杂度降到线性级别。

这里又要回到之前讨论过的"生成文法" 的概念,Chomsky 是从人类语言之谜的角度来解释语言是如何构成或产生的,而不是从语言解析的角度,但计算机科学家更关注解析,因为编译器或解释器需要从编程语言中读出语义从而去实现程序员的意图,因此计算机科学家可以从解析的角度重新设计 CFG 语言的文法,比如 PEG 语法就是面向解析的文法。(可参考 N 倍效率神器,使用 PEG 生成自己的解析器 - 知乎

另外,这里的解析在那个年代实际是把 CFG 这种比较高层的带递归的语言结构朝着底层的机器语言的方向解释,因为在 Chomsky 提出生成文法(1950s)之前就有了理想的图灵机(1936)和实体的 ENIAC (1946),人们可以用机器码比如打孔卡片来编程,但还无法想象能够用更自然地语言来编写程序,Chomsky 的理论被计算机科学家引入后,我们不单单可以跟随着机器的结构(比如纸带和读写头)来设计和编写指令,还可以谈论这些指令本身的结构,并且说明这些结构和哪些更高层的语言性质(比如递归)的等价性等,这实际是从机器结构本身的限制中跳脱出来,我们可以针对语言或指令本身来做更多的设计,以此设计出编译器。

把一个类似科学发现的对象 – CFG 根据人们的应用场景进行工程优化,这基本引出了整个编程语言、编译原理子领域:

  • 比如就复杂度而言,可以试图设计一种不需要遍历 n^2 级别数量的格子去进行解析的语言。不遍历 n^2 格子意味着什么?在复杂度级别中,n^2 的下一个等级一般是 nlogn, 比如把冒泡排序优化成归并排序,那么是否可以遍历 nlogn 个格子?这意味着我们要在每一行或者每一列进行二分搜索,或者对 bigram, trigram 进行二分。
  • 还可以考虑到体系结构方面的优化,比如能否设计一种可以更高效并行解析的语法。
  • 除了优化语法本身,还可以在解析中引入一些启发性或预测性手段,比如预测分析表(predictive parsing table)可以在某些情况下实现更快的解析,引入更高效的数据结构也是一种优化方式。

后文主要介绍 LL 递归下降解析器的实现, "LL"这个名字意味着从左到右(Left-to-right)读取输入,构建最左派生(Leftmost derivation)的解析树,这是从解析的角度所提出来的需求,它最终会导致更严格、更具确定性的生成文法,它是前文讨论的几乎没有任何限制的 CFG 文法的一个子集。

过渡从 CKY 算法到 LL 解析器,本质上是从一种对广泛文法适用但效率较低的方法转向一种对特定文法高效但适用范围较窄的方法。这种过渡涉及到:

  • 简化文法:将复杂或含糊的语法规则转化为更简单、更明确的规则,以适应 LL 解析器的要求。

    比如不要求是 CNF 格式,而是可以把终结符和非终结符混用,比如:

    list     : '[' elements ']' ;
    

    这样算法要解析一个 list 的时候,第一步只需检查对象第一个字符是不是 '[', 如果不是,直接就可以报错,而不需要动态规划式地检查每一个字符和子字符串。

  • 消除左递归:LL 解析器不能处理左递归的文法规则,因此需要将这些规则转换为右递归或其他形式。

    比如前文 pajamas 例子语法中(如下),出现了 ["VP" ,(0.4, ["VP", "PP"])], 也就是 VP-> VP PP , 这是一种左递归定义,也就是右侧第一个变量也可以出现在左侧。由于 LL 解析是根据规则从左到右递归解析的,于是当它要解析 VP 结构的时候,马上会遇到右侧第一个 VP, 于是又去解析 VP 结构,从而陷入无限递归。

    imp_cfg_rules = [
      ["S" , (1, ["Pronoun", "VP"])],
      ["VP" ,(0.6, ["V", "NP"])],
      ["NP" ,(0.6, ["Det", "Nominal"])],
      ["NP" ,(0.4, ["Det", "N"])],
      ["Nominal", (1, ["N", "PP"])],
      ["VP" ,(0.4, ["VP", "PP"])]
    ]
    

    当然,如果用动态规划的方式,可以避免无限递归,也就可以不用消除左递归,以此构造其他的解析器,比如 LR parser, 这是一种设计上的选择。本文只关注 LL parser

通过这样的过渡,可以实现在特定应用领域内的高效语言解析,同时牺牲了对更广泛语法的通用性,这种权衡在语言设计和解析工具的开发中是常见的。

LL 递归下降的函数式实现

这部分来自 https://twitter.com/GrantSlatton/status/1739010735324184583/photo/1

从更抽象(或称通用、一般化、广义)的视角来看, parsing 实际就是输入序列,将其中部分子序列进行处理转换成另外一种形式(上文提到树结构是一种典型形式),然后返回该形式以及剩下的序列。

写成伪代码就是:

def parser(s):
    # 读取 s 中部分子串
    return result, remain

以上接口可以提供了 parsing 的高层的视角,接着向下一层,确定更具体规则,比如从左到右解析的场景:

def parser(arguments):
    def inner(s):
        return result, s
    return inner

从这个角度看,在递归树上任何一个节点的过程都可以看作一个 parser, 比如解析一个空格,一个特定字母或数字,这些 parser 可以组合起来解析更大的对象,比如多个解析数字的 parser 用 for 循环组合起来就可以解析一个数字字符串,继续组合可以解析数组、字典等等,由于这种组合性,他们都被称为 parser combinator.

低层 parser combinator

我们先构造那些只解析一个字符的 parser, 比如只识别 a 或者数字,为了避免对识别没给字符都首先一个这样的 parser, 可以构建一个通用的工厂函数,输入对象识别条件,返回一个根据该条件对字符串拆解的 parser:

def satisfy(predicate):
    def inner(s):
        head, tail = s[0], s[1:]
        if predicate(head):
            return head, tail
        raise Exception('Predicate not satisfied')
    return inner

这样,可以用 satisfy 构建出一个识别任何字符的 parser:

def any_char(s):
    return satisfy(lambda x: True)(s)

print(any_char("abc"))
print(any_char("bc"))
print(any_char("c"))
('a', 'bc')
('b', 'c')
('c', '')

接着构建出识别给定某些集合里词(或字符)的 parser, 比如对上文提到的 leicon ("N " , {"苍蝇", "小猫"}) 的解析

def one_of(chars):
    return satisfy(lambda x: x in chars)

print(one_of(["小猫","苍蝇"])(["小猫","追", "一只", "苍蝇"]))
('小猫', ['追', '一只', '苍蝇'])

以此构建出只识别特定字符的 char 的组合子

def char(c):
    return one_of(c)

print(char("a")("ab"))
('a', 'b')

识别不在某个集合里的 parser:

def none_of(chars):
    return satisfy(lambda x: x not in chars)

print(none_of("abc")("xyz"))
('x', 'yz')

解释型 parser

以上只是识别一个字符或元素,为了能够识别更多,比如多个字符组成的词,或者多个元素组成的子序列,可以连续应用多次 parser:

def series(*parsers):
    def inner(s):
        result = []
        for p in parsers:
            x, s = p(s)
            result.append(x)
        return result, s
    return inner

def string(x):
    return series(*map(char, x))

print(string("abc")("abcde"))
(['a', 'b', 'c'], 'de')

到目前为止,我们只是在根据条件识别并拆分序列或字符串,还没有对识别出的部分进行任何的解释,而当谈到解释时,就涉及到语义了,比如要说清楚当前解析的目的是什么,因为可能对于语法上完全相同的对象,在不同语言下解释结果完全不同,以下例子目的是解析 json 格式的文件。

首先解析 null 字符串,解释成 python 中的 None:

def json_null(s):
    _, s = string('null')(s)
    return None, s

print(json_null("null"))
(None, '')

json_null 也是一个 parser, 它只能解析 null, 遇到其他情况则会报错,我们可以不要这么严格,比如可以先去识别当前是不是 null, 如果不是,并不要直接报错,而是继续调用其他解析器去解析,因此引入一个 branch 工具,它可以传入多个解析器,一个一个轮番去解析,直到成功为止。

def branch(*parsers):
    def inner(s):
        for p in parsers:
            try:
                return p(s)
            except:
                pass
        raise Exception("No parser succeeded")
    return inner

这样,就可以识别 bool 值,因为 bool 只有 true 和 false 两种,因此传入两个解析器给 branch 即可:

def json_bool(s):
    def true(s):
        _, s = string('true')(s)
        return True, s

    def false(s):
        _, s = string('false')(s)
        return False, s

    return branch(true, false)(s)

print(json_bool("true,"), json_bool("false."))
(True, ',') (False, '.')

数字和字符串 parser

为了能够识别拥有连续的相同模式的序列,需要一种重复解析的能力,以下 many 函数只接受一个 parser, 但它贪婪地不断重复解析,直到解析失败。

def many(parser):
    def inner(s):
        result  = []
        try:
            while True:
                x, s = parser(s)
                result.append(x)
        except:
            pass
        return result, s
    return inner

这样就可以解析数字了,因为它们是连续的相同类型的字符序列

def json_number(s):
    number_chars, s = many(one_of('0123456789.'))(s)
    number = ''.join(number_chars)
    return float(number), s

print(json_number("123abc"))
(123.0, 'abc')

同时可以解析字符串, 字符串的特殊性在于要考虑转义字符,比如 "\"hello\"" 要解释成 "hello", 也就是说,在每一步解析的时候,应该先查看是否是转义字符,如果是那么只需要获得转义字符后的那个字符,如果不是,则解析任何字符(除了引号本身),因此这里逻辑稍微复杂一点:

def json_string(s):
    _, s = char('"')(s)

    def escaped_char(s):
        _, s = char('\\')(s)
        c, s = any_char(s)
        return c, s

    contents, s = many(branch(escaped_char, none_of('"')))(s)

    _, s = char('"')(s)

    return ''.join(contents), s

print(json_string('"hello \\"John"'))
('hello "John', '')

注意以上要加两个转义,如果只有一个 python 会自己转义

'"hello \"John"'
"hello "John"

这样识别出来的就只有 hello

print(json_string('"hello \"John"'))
('hello ', 'John"')

array 和 object parser

要处理 json 里的 array, 首先主要是要忽略空格,比如以下 python 里的 list 和 json array 类似,中间可以有任意多空格、tab 或换行符

print([1,    2,
       3])
[1, 2, 3]
def whitespace(s):
    return many(one_of(' \n\t'))(s)

为了匹配元素和分隔符交替出现的模式(但分隔符比元素个数要少一个),我们再引入一个工厂函数,用来构造组合子

def interspersed(parser, separator):
    def inner(s):
        result = []
        try:
            while True:
                # 读取到第一个元素后读取分隔符
                if result:
                    _, s = separator(s)
                x, s = parser(s)
                result.append(x)
        except:
            pass
        return result, s
    return inner

注意这里和 many 的区别就在于只有读取了第一个元素之后才会读取 (分隔符,元素) 重复出现模式

def many(parser):
    def inner(s):
        result  = []
        try:
            while True:
                x, s = parser(s)
                result.append(x)
        except:
            pass
        return result, s
    return inner

这样就可以实现 json 里的 array 和对象的读取了:

def json_array(s):
    _, s = series(char('['), whitespace)(s)
    separator = series(whitespace, char(','), whitespace)

    result, s = interspersed(json_value, separator)(s)
    _, s = series(whitespace, char(']'))(s)
    return result, s

def json_object(s):
    _, s = series(char('{'), whitespace)(s)

    def kv_pair(s):
        k, s = json_string(s)
        _, s = series(whitespace, char(':'), whitespace)(s)
        v, s = json_value(s)
        return (k, v), s

    separator = series(whitespace, char(','), whitespace)
    result, s = interspersed(kv_pair, separator)(s)

    _, s = series(whitespace, char('}'))(s)

    return dict(result), s

def json_value(s):
    return branch(json_null, json_bool, json_number, json_string, json_array, json_object)(s)

注意 json_value 函数中出现了 json_array 和 json_object,而后两者实现中又调用了 json_value, 这是递归。

branch(json_null, json_bool, json_number, json_string, json_array, json_object)(s)

这一句是典型的 top-down 自顶向下的思路,因为它只是把 json 看作以上的 null, bool,number,string, array,object 几种类型之一,要解析 json, 那么只需要解析到其中任何一个即可。加上其中的递归性质,这个解析器就称为递归下降解析器,它是模块化的,像堆积木一样整合起来,因此被称为 parser combinator, 它又是函数式的,因为每个 parser combinator 大多是闭包的形式。

另外,以上 branch 函数是如何写出来的?如果要用 BNF 格式书写 json 文件的文法(grammar),那么其中可能包括:

JSON_VALUE : NULL|BOOL|NUMBER|STRING|ARRAY|OBJECT
NUMBER: [0-9\.]+
BOOL: false|true
NULL: null
...

而第一条文法可以直接写成以上代码,这种文法和代码实现的一一对应关系如此明确,以至于可以再编写一个程序,这个程序读取文法并直接生成一段解析该语言的 parser 的代码,这种工具被称为 Parser Generator, 下一章还会提到此概念。

另外,如果文法中有:

NAME : NAME string

那么对 name 的 parser combinator 可能定义是

def name(s):
    return series(name, json_string)(s)

这会导致陷入无限递归,这就是左递归问题,LL parser 需要避免这种文法,大部分情况下,交换一下文法里右侧对象的顺序即可。

NAME : string NAME
def name(s):
    return series(json_string, name)(s)

这样先执行了 json_string 后,s 会被消耗部分,因此再调用 name 就不会无限递归了。

最后,如果额外考虑 json 对象的合法性,那么最终 json 的 parser 如下:

def json(s):
    result, s = json_value(s)
    _, s = whitespace(s)
    assert s == '', f'did not consume entire string: {s}'
    return result
test = '{ "a": 1.23, "b": [1, false, null], "c": {"d": {"e": false}}}'
expected = {'a': 1.23, 'b': [1, False, None], 'c': {'d': {'e': False}}}

assert json(test) == expected

总结

本文比较长,但实际只谈论了递归、动态规划和语言解析里的基础概念和算法,另外 ascii 图片占据了许多篇幅。总的来说,本文是想以"垂直"的视角来梳理语言解析(parsing)中涉及到的核心概念,包括递归、动态规划、Chomsky 分层、CFG 、LL parsing 等。

  • 本文先从简单的方格世界里的递归和动态规划说起,接着引申到回文子序列问题, 该问题在抽象层面也是一个方格世界,而自然语言中 CKY parsing 算法同样也是伪装了的方格问题。
  • 在引入 CKY 前先介绍了 Chomsky 对形式语言的分类(主要关注 Context Free Grammar ) 、CNF 标准形式以及该形式和 格子世界的天然联系(binary 性质),然而 CNF 并不会对 CFG 语法有本质的改变,在面对自然语言这种演化而成的客观对象面前,我们更多只能用最通用的 CKY 算法去解析它,因为自然语言可能包含了 CFG 文法里蕴含的所有属性,甚至超出了 CFG 所能描述的范围,我们不能为了算法实现上的优化而简单忽略这些属性。

    但从语言设计的角度,编程语言的句法可以只取 CFG 的子集,精心选择一些新的语法约束以提升解析该语言的算法的效率,这就引出了 LL 递归下降算法以及它所处理的文法。

  • 本文的最后展示了递归下降 parser combinator 的函数式实现。
radioLinkPopups

如对本文有任何疑问,欢迎通过 github issue 邮件 metaescape at foxmail dot com 进行反馈