How similar are two strings ? Levenshtein edit distance

The test macro below uses the accompanying subroutine:

Levenshtein edit distance between two strings

  • Comparison of two identical strings has the value 0.
  • As strings become less similar, the Levenshtein edit distance value increases.

Sample output:

Edit distances:

3 between: "kitten" and "sitting"
3 between: "sitting" and "kitten"
8 between: "rosettacode" and "raisethysword"
8 between: "raisethysword" and "rosettacode"
3 between: "similar" and "simulate"
1 between: "amble" and "ample"
0 between: "ample" and "ample"

SimilarityOfStringsSubroutineAndTest.kmmacros (9,1 Ko)

See also: String Fuzzy Comparison Function Macro (v11.0.3) - Macro Library - Keyboard Maestro Discourse


Levenshtein function in subroutine:

Expand disclosure triangle to view JS source
return (() => {
    "use strict";

    // @Rob Trew 2024
    // Updated from a draft previously contributed to
    // Rosetta Code

    const main = () =>
        levenshtein(
            kmvar.local_String_A
        )(
            kmvar.local_String_B
        );

    // ------------ LEVENSHTEIN EDIT DISTANCE ------------

    // levenshtein :: String -> String -> Int
    const levenshtein = sa =>
        // The Levenshtein edit distance
        // between two given strings.
        sb => {
            const cs = [...sa];
            const go = (ns, c) => {
                const calc = z => tpl => {
                    const [c1, x, y] = tpl;

                    return Math.min(
                        1 + y,
                        1 + z,
                        x + (
                            c1 === c
                                ? 0
                                : 1
                        )
                    );
                };
                const [n, ...ns1] = ns;

                return scanl(calc)(1 + n)(
                    zip3(cs)(ns)(ns1)
                );
            };

            return last(
                [...sb].reduce(
                    go,
                    enumFromTo(0)(cs.length)
                )
            );
        };


    // ---------------- GENERIC FUNCTIONS ----------------

    // enumFromTo :: Int -> Int -> [Int]
    const enumFromTo = m =>
        n => Array.from({
            length: 1 + n - m
        }, (_, i) => m + i);


    // last :: [a] -> a
    const last = xs => {
        // The last item of a list.
        const n = xs.length;

        return 0 < n
            ? xs[n - 1]
            : null;
    };


    // scanl :: (b -> a -> b) -> b -> [a] -> [b]
    const scanl = f =>
        // The series of interim values arising
        // from a catamorphism. Parallel to foldl.
        startValue => xs =>
            xs.reduce(
                (a, x) => {
                    const v = f(a[0])(x);

                    return [v, a[1].concat(v)];
                }, [startValue, [startValue]]
            )[1];


    // zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
    const zip3 = xs =>
        ys => zs => xs.slice(
            0,
            Math.min(...[xs, ys, zs].map(x => x.length))
        )
        .map((x, i) => [x, ys[i], zs[i]]);


    // MAIN ---
    return JSON.stringify(main());
})();
4 Likes