Bash - show suggestions
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 it by making a huge case
out of all the possible transposed letters ... but it will take forever and seems really messy ...
case $1 in
"statsu")
suggestion="status"
;;
"satsus")
suggestion="status"
;;
...
esac
How can I reproduce this behavior in my own program?
(related question here , but it is about setting up git ITSELF to print this post)
source to share
(I don't know if this is how git
, but it will work). There is a concept called edit distance that can be used to measure how close two lines are to each other. In this case, you must calculate the edit distance between the input ( statsu
) and each of the possible matches ( status
, commit
, rebase
etc.), and then offer the one who has the minimum edit distance.
The Wagner-Fischer algorithm can be easily, albeit inefficiently, implemented recursively, but it should be fast enough for short strings to 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 nearest suggestion, you can 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?"
source to share