Bash - 显示建议

Question

使用 Git，当我输入如下内容时:

$ git statsu

我明白了...

git: 'statsu' is not a git command. See 'git --help'.

Did you mean this?
    status

我如何使用 Bash 复制它？

---

当然，我可以通过制作一个包含所有可能转置字母的巨大 case 来做到这一点……但这会花很长时间，而且看起来真的很脏……

case $1 in
  "statsu")
    suggestion="status"
  ;;
  "satsus")
    suggestion="status"
  ;;
  ...
esac

如何在我自己的程序中复制这种行为？

(相关问题 here，但这是在讨论配置 git ITSELF 以打印此消息)

Answer 1

(我不知道 git 是否正是这样做的，但它会起作用)。有一个概念叫edit distance它可以用来衡量两个字符串彼此之间的距离。在这种情况下，您将计算输入 (statsu) 和每个可能的匹配项(status、commit、rebase 等)，然后建议产生最小编辑距离的那个。

Wagner-Fischer 算法虽然效率低下，但可以很容易地以递归方式实现，但对于将要针对您的用例进行比较的短字符串，它应该足够快。

# Warning: not tested, but should be close
# return (cost) is in variable wf_cost
wagner_fischer () {
    local t0 t1 t2
    if [[ -z $1 ]]; then
        # Base case 1: first string is empty
        wf_cost=${#2}
    elif [[ -z $2 ]]; then
        # Base case 2: second string is empty
        wf_cost=${#1}
    elif [[ ${1:0:1} == ${2:0:1} ]]; then
        # Strings have identical first characters, recurse on the
        # rest of each string
        wagner_fischer "${1:1}" "${2:1}"
    else
        # Strings have differing first characters; recurse on
        # the rest of each string, but add 1 to the result to accommodate
        # the initial difference.
        #
        # Pick lowest cost of possible operations:
        wagner_fischer "${1:1}" "$2"     # deletion case
        t0=$wf_cost
        wagner_fischer "${1}" "${2:1}"   # insertion case
        t1=$wf_cost
        (( t0 < t1 )) && t1=$t0
        wagner_fischer "${1:1}" "${2:1}" # substitution case
        t2=$wf_cost
        (( t1 < t2 )) && t1=$t2
        (( wf_cost=t1 + 1))
    fi
}

要找到最接近的建议，您可以像这样使用上面的函数:

min_cost=65535  # "Infinity"
for choice in status rebase commit; do
    wagner_fischer "$input" "$choice"
    if (( wf_cost < min_cost )); then
        min_cost=$wf_cost
        suggestion=$choice
    fi
done
echo "You typed $input, did you mean $suggestion?"