Introduction

One great feature that some of CLI applications and compilers recently gained is providing suggestions in the case of misspellings arguments or options. For instance, Python suggests possible method/fields names, like:

>>> 'lower'.is_upper()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'str' object has no attribute 'is_upper'. Did you mean: 'isupper'?

If we want to include similar feature in our program, then a quite obvious solution is to use Levenshtein distance. Its basic implementation is simple and short. If we want suggestion for larger corpus, we may use tries to speedup matching — see: Fast and Easy Levenshtein distance using a Trie by Steve Hanov.

Despite that, I was curious if simpler algorithm would do the job. We may assume that our users know what they are doing. Their inputs will be sane, with an exception of minor mistakes. Like omitting a single letter, swapping two adjacent letters or maybe hitting a wrong key from time to time.

The two additional assumptions I made: we search suggestions in small sets, and we use only ASCII letters (128 possible bytes).

Alternative approach

To estimate edit distance we use two histogram-based approaches:

1. byte histogram — exact histogram for each byte of a string,
2. bit histogram — mark in a bit-set which bytes from a string are present.

In the first case, histogram takes 128 bytes. Similarity is calculated as the sum of absolute values.

def diff1(h1, h2):
    s = 0
    for i in range(128):
        s += abs(h1[i] - h2[i])

    return s

In the second case histogram uses 128 bits = 16 bytes. Similarity uses Hamming distance — it is the number of 1 bits in the word calculated as a XOR of two corresponding words from histograms.

def diff2(h1, h2):
    # assume words are 64-bit numbers, thus we have 4-element arrays
    s = 0
    for i in range(4):
        d = h1[i] ^ h2[i]
        s += d.bit_count()

    return s

Let's assume a valid word "rebase" (the git command). And a misspelled sample is "revase" — the letter 'b' got replaced with the 'v'. The Levenshtein distance is 1.

h1("rebase") = [..., 1, 1, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, ...]
h2("revase") = [..., 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, ...]
                        ^                                                           ^

h1("rebase") = [... 0000000000001100000000000010011000000000000000000000000000000000 ...]
h2("revase") = [... 0000000001001100000000000010001000000000000000000000000000000000 ...]
                             ^                   ^

Evaluation

The two sets of words were tested:

• git commands (clone, init, add, mv, restore, rm, bisect, diff, grep, log, show, status, branch, commit, merge, rebase, reset, switch, tag, fetch, pull, push),
• Python's str methods (capitalize, casefold, center, count, encode, endswith, expandtabs, find, format, format_map, index, isalnum, isalpha, isascii, isdecimal, isdigit, isidentifier, islower, isnumeric, isprintable, isspace, istitle, isupper, join, ljust, lower, lstrip, maketrans, partition, removeprefix, removesuffix, replace, rfind, rindex, rjust, rpartition, rsplit, rstrip, split, splitlines, startswith, strip, swapcase, title, translate, upper, zfill).

Each word was taken and got modified in the following ways:

• remove i-th character,
• replace i-th with an ASCII letters,
• swap i-th and j-th characters,
• insert at i-th position an ASCII letter.

A hit is defined as a suggestion that yields the original word.

Source

All programs are available on Github.