如何实现 git 命令行的联想功能

码农生涯离不开 git ，无论是编码开发，版本控制，还是持续集成，代码审查， git 无疑是有效跟踪项目进展的利器，而 git 命令行更是必不可少的工具。我之前也尝试过一些带界面的 git 工具，然而都没有命令行来的顺手，按钮太多，界面太复杂，反而容易搞不清楚一些简单的操作应该如何下手。

命令行用的多了，难免有手滑输错命令的时候，这个时候屏幕上就会提示

 ~ » git stats
git: 'stats' is not a git command. See 'git --help'.

The most similar command is
	status

当年第一次用 git 的时候还是小惊喜了一下，因为之前接触的其他工具不是直接提示命令找不到，就是直接输出一大段 help 界面，对用户很不友好，所以 git 能直接把最接近的子命令输出到屏幕上还是很方便的。

那么这个贴心的小功能是如何实现的呢？很自然地想到，要想办法定义两个字符串之间的“相似程度”，换句话说，要找到一个度量衡，来量化两个字符串之间的不同程度为多大，然后遍历一遍 git 的子命令，找出不同程度最小的那个返回即可。这个度量衡早在 1965 年前苏联数学家 Vladimir Levenshtein 就已经给出了定义，因此命名为 Levenshtein Distance （莱文斯坦距离）。内容很简单，相似程度可以用两个字符串的编辑距离来量化，即给出字符串甲和字符串乙，只通过添加一位字母，删除一位字母，或者替换一位字母的操作，最少经过多少次操作能把字符串甲变成字符串乙。

举个例子，字符串 kitten 和 sitten 的编辑距离是多少？显然是 1 ，因为把首位字母替换为 s 即可成为后者。再来一个，字符串 abd 和 abcd 的编辑距离也是 1 ，因为只需要添加一个字母 c 就得到了后者。但是字符串有很多，复杂的情况无穷无尽，比如说 September 和 October 的编辑距离就不容易一眼看出来，所以需要一个算法来帮我们计算这个结果。

先考虑最简单的情况，当一个字符串为空的时候，编辑距离自然是另一个字符串的长度，因为只需要通过简单的添加操作，就能把一个空字符串变成另一个字符串，或者通过简单的删除操作，就能把一个非空字符串变成空字符串。

然后是比较复杂的情况，当两个字符串都不为空的时候，应该如何得到它们的编辑距离？我们先假设两个字符串的子串的编辑距离已知，这样我们就可以很容易地得出这两个字符串的编辑距离。具体说来，假如两个字符串分别命名为 str1 和 str2 ，已知下列子串的编辑距离（为说明方便，我这里的子串用 Python 的语法来表示）

• str1[:-1] -> str2[:-1]
• str1[:-1] -> str2
• str1 -> str2[:-1]

已知第一种情况下的编辑距离，我们只需要比较 str1 和 str2 的最后一位字母，如果相同的话， str1 和 str2 的编辑距离其实与 str1[:-1] 和 str2[:-1] 的编辑距离是一样的，因为我们不需要对最后一位字母做任何操作。如果最后一位字母不相同的话，我们只需要在第一种情况的基础上做一次替换，就能得到 str2 了，所以这时 str1 和 str2 的编辑距离为 str1[:-1] 和 str2[:-1] 的编辑距离加一。

已知 str1[:-1] -> str2 的编辑距离， str1 到 str1[:-1] 的距离显然是 1 ，只要删除最后一位字母就行了，所以 str1 到 str2 的编辑距离为 str1[:-1] -> str2 加一，具体操作为 str1 -> str1[:-1] -> str2 。数学家嘛，总是喜欢把一个未知的问题转化成一个已知的问题来解决。

同样地，已知 str1 -> str2[:-1] 的距离，只需要给 str2[:-1] 添加最后一位字母，就得到了 str1 -> str2 的编辑距离。

最后，从上述三种情况得到的编辑距离中取最小，就是我们想要的答案。

但问题还没完，上述三种情况的编辑距离我们是“假设”它们已知了，而实际情况中我们是无法直接得到它们的编辑距离的。考虑一下一开始提过的“最简单的情况”，基于它们，一步步向复杂的情况推进，我们很容易地就得到了所有情况的编辑距离。

于是，这个算法就有了形式化的定义。记字符串 a 与 b 的编辑距离为 leva,b(∣a∣,∣b∣)lev_{a,b}(|a|, |b|)leva,b​(∣a∣,∣b∣)其中 |a| 和 |b| 分别表示 a 与 b 的长度，可以得到推导公式

这个公式是用递归的形式定义的，但工程实现的时候我一般会倾向于避免这种方式，防止在输入过长的时候爆栈，这里可以用矩阵来存储 lev(i,j) 的值。以维基百科上的 sitting 和 kitten 的编辑距离为例，可以得到下面一个矩阵，右下角的 3 即为它们的编辑距离。

Python 编码实现如下

def levenshtein_distance(str1, str2):
    rows = len(str1)
    cols = len(str2)
    lev = [[0 for _ in range(cols+1)] for _ in range(rows+1)]
    for i in range(rows+1):
        lev[i][0] = i
    for j in range(cols+1):
        lev[0][j] = j

    for i in range(1, rows+1):
        for j in range(1, cols+1):
            lev[i][j] = min(
                lev[i-1][j] + 1,
                lev[i][j-1] + 1,
                lev[i-1][j-1] + (0 if str1[i-1] == str2[j-1] else 1)
            )

    return lev[rows][cols]

这个算法的时间复杂度和空间复杂度都为 O(M*N) ， M 和 N 分别代表两个字符串的长度。

回到 git 命令行， git 的子命令不过只有二十几个，最长的也不过 8 个字母，所以当遇到无法识别的命令时，一一计算输入的子命令和已有的子命令之间的编辑距离，就能快速找到最相近的一个并返回到屏幕上。当然了， git 也不会胡乱推荐，如果输入的子命令太过于奇葩，令编辑距离过大， git 是什么话也不会说的。

 ~ » git abcdefg
git: 'abcdefg' is not a git command. See 'git --help'.

• https://en.wikipedia.org/wiki/Levenshtein_distance

文章的脚注信息由WordPress的wp-posturl插件自动生成