如何实现 git 命令行的联想功能
命令行用的多了，难免有手滑输错命令的时候，这个时候屏幕上就会提示
:panda_face: ~ » 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 的编辑距离为 lev_{a,b}(|a|, |b|)
其中 |a| 和 |b| 分别表示 a 与 b 的长度，可以得到推导公式
lev_{a,b}(i, j)=\begin{cases}
\begin{array}{ll}
max(i, j) & if min(i, j)=0, \\
min
\begin{cases}
\begin{array}{ll}
lev_{a,b}(i-1,j) + 1 \\
lev_{a,b}(i,j-1) + 1 \\
lev_{a,b}(i-1,j-1) + 1_{a_i \ne b_j}
\end{array}
\end{cases} & otherwise.
\end{array}
\end{cases}
这个公式是用递归的形式定义的，但工程实现的时候我一般会倾向于避免这种方式，防止在输入过长的时候爆栈，这里可以用矩阵来存储 lev(i,j)
的值。以 维基百科
上的 sitting
和 kitten
的编辑距离为例，可以得到下面一个矩阵，右下角的 3 即为它们的编辑距离。
| k | i | t | t | e | n | ||
|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| s | 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| i | 2 | 2 | 1 | 2 | 3 | 4 | 5 |
| t | 3 | 3 | 2 | 1 | 2 | 3 | 4 |
| t | 4 | 4 | 3 | 2 | 1 | 2 | 3 |
| i | 5 | 5 | 4 | 3 | 2 | 2 | 3 |
| n | 6 | 6 | 5 | 4 | 3 | 3 | 2 |
| g | 7 | 7 | 6 | 5 | 4 | 4 | 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 是什么话也不会说的。
:panda_face: ~ » git abcdefg git: 'abcdefg' is not a git command. See 'git --help'.
参考资料
原创文章，转载请注明：转载自Panda Home
本文链接地址: 如何实现 git 命令行的联想功能
文章的脚注信息由WordPress的 wp-posturl插件
自动生成
About The Author
