关于动态规划:搞事代码找茬

最近老是想起陈芝麻烂谷子的事件，阐明工龄所剩无几了。

又是在那边远的 2009 年，那个“杯具”曾经不是杯具的年头，度厂办个算法较量，办出了点儿杯具的滋味。

较量的名字叫“百度之星”，那些年在校园里影响力还蛮大的（如同当初还是），大略赛制就是通过初赛、复赛、决赛这么几轮，选出几个社会主义四有青年 ~~瓜分奖金~~。值得一提的是，头两年（05、06）冠军都被楼教主承包了。

为什么说有点杯具的滋味呢，因为那年的初赛完结当前，度厂搞了个骚操作，把所有参赛选手提交的代码导出来，打了个包，发在贴吧里。

于是贴吧忽然就炸了。

要晓得初赛是网络赛，各个学校的 ACM（或 OI）集训队的队员们很可能都是凑在机房一起参加，毕竟毛主席教诲咱们人多力量大嘛。

所以这就有点意思了：如果同一个题，两份代码长得很像，阐明相互剽窃概率就很大。

问题是参赛人数有点多，两两比照这 O(n^2) 的工夫复杂度，靠人肉有点儿吃不消；但这么大一个瓜，光看不吃又有点惋惜了。

那么这瓜到底该怎么吃呢？

还好，作为一个比赛战五渣的我，通过初赛的能力没有，搞事件的能力还是有一点的。

为了比照两份代码的类似度，那我首先得找到一个指标。

作为一个长于舞弊思考的社会主义三无青年，我预计作弊者在拿到弊友代码后不会间接提交，至多会做些更换变量名之类操作；但比赛工夫紧迫，大概率来不及批改整体框架。

那么，只有我能算出批改的水平，就能判断类似度了：假如两份代码长度别离是 m、n，批改了 x 个字符，咱们大抵能够把 100% - x / ((m + n) / 2) 当成类似度（没被批改的字符占比）。

但如何计算这批改的水平呢？毕竟批改前后代码长度很可能不同，不适宜通过逐字比拟来找到差异。

既然间接解决两段代码有点辣手，那无妨先考虑一下简略的 case。

比如说要将字符串 “a” 改成 “b”，这个简略，只有改一个字符就行。

又比如说要将字符串 “a” 改成 “ab”，这个也简略，只有增加一个字符就行。

再比如说要将字符串 “ab” 改成 “b”，这个仍然简略，只有删除一个字符就行。

如果我能算出将一段字符串通过增加、删除、批改三种操作批改成另一个字符串的 起码操作次数，应该就能把这瓜给吃了。

如同是找到了方向，然而要怎么实现呢？

既然间接解决两段代码还是有点辣手，那无妨再考虑一下略微简单一点的 case，比方把字符串 X = “baidu” 变成 Y = “bytedance”。

首先，因为 X[0] 和 Y[0] 雷同，咱们能够把问题简化成：将 “aidu” 变成 “ytedance”，即 X[1..4] => Y[1..8]（前面简记为 X[1:] => Y[1:]）。

接着，X[1] = ‘a’, Y[1] = ‘y’，如上一节所说，这时候咱们有三种抉择：

增加：给 X 增加 ‘y’，当成 “byaidu”，于是问题简化为将 “aidu” 变成 “tedance”，即 X[1:] => Y[2:]；（留神，咱们在这里把该操作当成一个思维试验就好，不须要真的批改 X，所以这里 “aidu” 对应 X[1:] 而不是 X[2:]）
删除：从 X 中删掉 ‘a’，当成 “bidu”，问题简化为将 “idu” 变成 ytedance”，即 X[2:] => Y[1:]；
批改：把 X 这个 ‘a’ 改成 ‘y’，当成 ‘”byidu”，问题简化为将 “idu” 变成 “tedance”，即 X[2:] => Y[2:]；

这三种操作中，后续须要的批改次数起码的那个，再加上 1，就是咱们把 X[1:] 改成 Y[1:] 所需的起码次数。

依此类推，如果咱们将 X[i:] 变成 Y[j:] 须要 f(i, j) 次操作，由上可失去这样一个公式：

if X[i] == Y[j]:
  f(i, j) = f(i + 1, j + 1)
else:
  f(i, j) = 1 + min(f(i, j + 1),    #增加
    f(i + 1, j),    #删除
    f(i + 1, j + 1) #批改
  )

也就是说，咱们能够用子问题的最优解来推导出问题的最优解，如果用不说人话的形式，就叫做该问题存在 最优子结构。

这么一看，代码是不是跃然纸上了？

啰嗦了这么多，不能忘了大佬的教诲：

说干就干，把下面推导的公式落地成代码，so easy：

def change(x, y):
  def f(i, j):
    if x[i] == y[j]:
      return f(i + 1, j + 1)
    else:
      return 1 + min(f(i, j + 1),
        f(i + 1, j),
        f(i + 1, j + 1)
      )
  return f(0, 0)
    
print change("baidu", "bytedance")

而后跑起来一看：

$ python change.py 
Traceback (most recent call last):
  File "change.py", line 13, in <module>
    print change("baidu", "bytedance")
    ... #省略一大段
  File "change.py", line 3, in f
    if x[i] == y[j]:
IndexError: string index out of range

“index out of range”，越界了 —— 显然，这里漏掉了递归的终止条件。

不过这个简略：如果 X 越界了，阐明这时 i == len(X)，那么 Y 还剩几个字符，咱们都加上就行，即还须要 len(Y) – j 次操作；或者 Y 越界了，阐明 j == len(Y)，咱们把 X 剩下的几个字符删掉，即 len(X) – i 次操作。

于是代码变成了：

def change(x, y):
  def f(i, j):
    if i == len(x):
      return len(y) - j
    if j == len(y):
      return len(x) - i

    if x[i] == y[j]:
      return f(i + 1, j + 1)
    else:
      return 1 + min(f(i, j + 1),
        f(i + 1, j),
        f(i + 1, j + 1)
      )
  return f(0, 0)

print change("baidu", "bytedance")

跑起来成果杠杠的，马上就失去了 7，算得没故障。

只惋惜这代码还没法用 —— 别说跑那些参赛代码，就连长度为 16 的两个字符串都跑不出后果……

略微剖析一下咱们就会发现，它居然是指数工夫复杂度的：

不过仔细观察上图（不认真也没关系，我给红色高亮了），咱们能够发现，为了计算 f(i, j)，咱们须要计算 f(i + 1, j + 1)；而且它也被用于计算 f(i, j + 1) 和 f(i + 1, j)。

这意味着这个问题存在 重复子问题 ，相似于咱们用 f(i) = f(i – 1) + f(i – 2) 计算 ~~飞波纳妾~~ fibonacci 数列。

因而咱们齐全能够将 f(i, j) 存下来、防止反复计算，就像这样：

def change(x, y):
  cache = {}
  def f(i, j):
    if i == len(x):
      return len(y) - j
    if j == len(y):
      return len(x) - i

    if (i, j) not in cache:
      if x[i] == y[j]:
        ans = f(i + 1, j + 1)
      else:
        ans = 1 + min(f(i, j + 1),
          f(i + 1, j),
          f(i + 1, j + 1)
        )
      cache[(i, j)] = ans

    return cache[(i, j)]

  return f(0, 0)

注：实际上这里也能够间接用一个二维数组 f[i][j] 来保留 f(i, j)，对 C/C++ 来说实现会更容易，读写效率也更高。

优化当前，因为每个 f(i, j) 只须要计算 1 次、并且能够在常数工夫里实现（因为子问题曾经计算好了），咱们将工夫复杂度降到了 O(m * n)，从而能够在短时间内计算出后果了。

在这个问题里，还有一个很重要的个性是，咱们在计算 f(i, j) 的时候，并不关怀从 f(0, 0) 到 f(i, j) 的推导过程，或者说从 f(0, 0) 推导到 f(i, j) 的过程对后续计算 f(i, j) 没有任何影响。用不说人话的形式，这就叫做 无后效性。

留神，无后效性并不是对所有问题都成立的。

比方在一个 N * N 的迷宫里寻找从坐标 (1, 1) 走到 (N, N) 的一条门路，咱们在应用 BFS 或 DFS 搜寻时须要将路过的坐标做好标记，防止再次走到，因而从 (1, 1) 到 (x, y) 的门路是会影响从 (x, y) 到 (N, N) 的门路，不满足无后效性。

汇总一下后面提到的这个问题的几个特点：

最优子结构
重复子问题
无后效性

—— 这不就是规范的 动静布局 问题嘛！对应的，第 5 节咱们推导出的公式，就是这个动静布局问题的 状态转移方程 了！

因为满足这几个个性，咱们实际上可用迭代的形式，从 f(m, n) 倒推出 f(0, 0)，这样能够应用循环而不是递归，进一步提高代码的运行效率。

另外，对于同一个动静布局问题，状态转移方程也能够不止有一种写法，比方咱们能够定义 g(i, j) 为将 X[1..i] 变为 Y[1..j] 的最小操作次数，于是：

if X[i] == Y[j]:
  g(i, j) = g(i - 1, j - 1)
else:
  g(i, j) = 1 + min(g(i, j - 1),
    g(i - 1, j),
    g(i + 1, j + 1)
  )

基于这一版状态转移方程，咱们就能够从 f(0, 0) 开始逐渐计算出 f(m, n)。

具体代码就不在这里贴了，感兴趣的同学能够本人写写看，留神边界值的解决就好。

实际上，这个算法叫做 编辑间隔 ，英文名 Levenshtein distance，是一个和普京同名、姓 Levenshtein 的战斗民族大佬在 1965 年提出的算法；该算法经典到 php 的规范库里居然蕴含了一个 levenshtein 函数（ ~~可见 php 的作者真是太闲了~~）。

还没完，在谋求性能和成果的路上咱们还能走得更远，依据代码自身的个性，咱们还有一些优化能够做。

比如说代码的正文是能够先删掉再比拟。

比如说代码里的字符串也能够删掉再比拟。

比如说代码里的空格，貌似也不影响咱们的类似度比照。

通过这样的操作，咱们能够大幅缩短了须要比照的代码长度，对于 O(m*n) 的算法而言，这个改善是很可观的。

此外，过后下场切瓜的另一位瓜友将这个思路推到了极致：既然咱们认为代码的整体框架不变、扭转的只是变量名这些货色，那咱们间接把所有字母、数字、空格等字符全删除，只留下标点符号来代表代码的框架，不是更香吗？

这样咱们既晋升了计算的效率，又进一步晋升了计算的成果。

值得一提的是，该瓜友用的不是编辑间隔，而是另一个经典的动静布局算法“最长公共子序列（LCS）”。

啰嗦了这么多，终于能够写总结了：

计算两个文本的类似度，能够应用编辑间隔或者最长公共子序列算法；这两个都是典型的动静布局算法；
动静布局问题须要满足最优子结构、重复子问题、无后效性；
要解决动静布局问题，先定义状态，推导状态本义方程，再编码；能够用递归也能够用迭代，前者实现简略，后者运行更快；
搞事件要思考结果，本不应该把参赛账号名也间接公开，后果是那次较量有些人体面上有点不难看；不过年老时谁没犯点错呢，除了本人谁又还记得呢？

最初，“编辑间隔”是个 LeetCode 的原题（No. 72，传送门），；“最长公共子序列”也是个 LeetCode 的原题（No. 1143，传送门），感兴趣的同学也别错过。

都看到这儿了，帮忙点个“赞”或分享给你的小伙伴吧，感激~

举荐浏览：

程序员面试指北：面试官视角
又是面试题？对，合并有序序列。
踩坑记：go 服务内存暴涨
TCP：学得越多越不懂
UTF-8：一些如同没什么用的冷常识
(译) C程序员该晓得的内存常识 (1)

关于动态规划:搞事代码找茬

– 1 –

– 2 –

– 3 –

– 4 –

– 5 –

– 6 –

– 7 –

– 8 –

– 9 –

– a –

– b –

欢送关注