Bash - show suggestions

Question

using Git, when I type something like this:

$ git statsu

I get...

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

Did you mean this?
    status

How can I replicate this using Bash?

---

I could, of course, do this by making a huge case of all possible transposed letters... but that would take forever, and seems really dirty...

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

How can I replicate this behavior in my own program?

(related question here, but that is talking about configuring git ITSELF to print this message)

Answer 1

(I don't know if this is how git does it exactly, but it would work). There is a concept called edit distance which can be used to measure how close two strings are to each other. In this case, you would compute the edit distance between the input (statsu) and each of the possible matches (status, commit, rebase, etc), then suggest the one with that produced the smallest edit distance.

The Wagner-Fischer algorithm can be easily, although inefficiently, implemented recursively, but it should be fast enough for the short strings that would be compared for your use case.

# 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
}

To find the closest suggestion, you could use the above function like this:

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?"