Git

如何实现 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 的编辑距离为:
1.png

其中 |a| 和 |b| 分别表示 a 与 b 的长度,可以得到推导公式:
2.png

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

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://old-panda.com/2020/05/ ... ance/

0 个评论

要回复文章请先登录注册