Levenshtein Distance and Excel

The Levenshtein Distance is a method of comparing two strings, via a recursive function that looks for 3 transformations, each one adds one to the total ‘distance’

This is very useful as a basic metric for comparing strings against a target. I’m aimimg to use it in my exploration of fuzzy string matching as a metric.

Transformations Overview

Insertions

If the source string has to add new characters to match the target string

Eg

You have to insert an “s” to the end of the source to reach the target, thus a distance of 1

Source “Sit” - Target “Sits” - Distance 1

Deletions

If the source string has to remove characters to match the target string

Eg

Removal of the “s” at the end of the source to match the target, thus a distance of 1

Source “Sits” - Target “Sit” - Distance 1

Replacement

Rather than a insertion or deletion, this looks for if the source string has to replace a character

Eg

Substitute the “K” and “e” for “S” and “s” respectively, thus a distance of 2

Source “Kite” - Target “Sits” - Distance 2

Excel & Power Query

When I was doing research for this project, I couldn’t find much viable information on how to implement this algorithm within excel. This was the intended software target due to the project requirements. I couldn’t use a macro, and the version I was working with couldn’t support the LAMBDA functions that other sources would reference, so I had to turn to Power Query and the M language.

M is functional, rather than object oriented which is what I am used to. So I first explored the syntax of the language, how to define recursive functions within the language, how to apply those functions to data. It was a significant shift in how to think through an algorithm as I couldn’t use my usual style. For example, using guarded if statements to early exit out of a function rather than nesting if statements were not possible in M, instead I had to sort of flip the function definition.

Fibonacci

This is a basic recursive implementation, where we take the ABSOLUTE of x (to prevent undefined behaviour with negative numbers) and then check against the base case. This has other names (guard clause, escape case, etc) but essentially it is how we tell the recursive function to stop and start moving back up the stack to the initial function call. In this case, if the input is less than 2 we can return either 0 or 1. If it is still larger than 1 then we add another recursive call.

The main problem with implementing this was that I initially started by trying to use the LAMBDA formula in sheet cell, with which I ran into compatibility issues across the excel versions that I have access to, as none of them had that feature. Next I tried to implement it as VBA macro, but I ran into a similar problem with that only the desktop version supported macros and the web version did not.

This is what led me to choose Power Query, which was compatible across all versions I had tested it on.

(x as number) as number =>
let
    x = Number.Abs(x)
    output = if x < 2 then
    let
        baseCase = if x = 0 then 0 else List.Max({x, 1})
        in
            baseCase
    else
        Fib(x -1) + Fib(x-2)
in
output

Crucial Rule: The function name query in your Power Query panel must be exactly Fib for the recursion step Fib(x - 1) + Fib(x - 2) to reference itself and execute properly.

Levenshtein Distance

Now onto the actual code for the algorithm, it’s only a few lines of code.

Like with the Fibonacci algorithm, I’ve had to tweak it from an implementation I found online in C++: https://www.geeksforgeeks.org/dsa/introduction-to-levenshtein-distance/

This was not a 1:1 conversion as Power Query functions is a declarative functional language with immutable variables, whereas C++ is more Object-Oriented and procedural with mutable variables.

Mutability basically refers to the ability to overwrite (or mutate) variables, since Power Query’s language - M - is immutable, there is no way to change a value, and instead I have to create a new one.

// LEVDISTANCE
(source as text, target as text, p as number, q as number) as number =>
let
    Distance = if p = 0 then q else if q = 0 then p else
        if (Text.ToList(source){p - 1} = Text.ToList(target){q - 1}) then LEVDISTANCE(source, target, p-1, q-1)
        else 
            1 + List.Min({
                LEVDISTANCE(source, target, p, q - 1), // Insertion
                LEVDISTANCE(source, target, p - 1, q), // Deletion
                LEVDISTANCE(source, target, p - 1, q - 1) // Replacem
                })
in
    Distance 

This by itself works well, but it is currently up to the user to input the length of the source (p) and the length of the target (q) when first calling the function. To make the usage of the function more clean, I also decided to add a wrapper that will invoke the recursion and return the result

// LEVDISTANCE_WRAPPER
(source as text, target as text) as number =>
let
    Output = LEVDISTANCE(source, target, Text.ToList(source), Text.ToList(target))
in
    Output