Approximate matching on strings

These are used if dealing with imprecise user inputs. The goal is to find entries that are approximately similar but not exactly the same.

Personal use case

I want to implement a search algorithm that helps users navigate my post note application quicker. I already distinguish between some important information like title, description, and tags from each individual note and can easily put them into a map.json which ought to be used as a mini database.

Implementing a fuzzy search algorithm

Now we can take a look at how we would implement such an algorithm, but we first need to decide which one we want to implement. There are a couple of decent options, each with their respect up- and downsides, I will take a look at two of them:

1. Levenshtein Distance

   • Pros:
     • Simple to understand and implement
     • Accurate for typo detection
   • Cons:
     • Slower on large data
     • Doesn’t handle sound-based similarity

2. Soundex / Metaphone

   • Pros:
     • Very fast and efficient
     • Simple phonetic matching
   • Cons:
     • Not typo-tolerant
     • Limited to English pronunciation

For this example I will go with the Levenshtein Distance algorithm.

Levenshtein Distance

In general terms the Levenshtein distance is a number that indicates how different two strings are. The smaller the number, the closer these two strings match. If you wanted to be more precise you could say, it's the number of symbols which have to be replaced, swapped or deleted until these two strings match exactly.

The steps needed to calculate the distance can be expressed as a recursive function which looks like this:

Let a = a_1 a_2 ... a_m and b = b_1 b_2 ... b_n be two strings. Define distance matrix D of size (m+1)\times(n+1), where: D(i, j) = \begin{cases} i & \text{if } j = 0 \\ j & \text{if } i = 0 \\ \min \left\{ \begin{array}{l} D(i-1, j) + 1 \\ D(i, j-1) + 1 \\ D(i-1, j-1) + \delta(a_i, b_j) \end{array} \right. & \text{otherwise} \end{cases}

where the cost function \delta(a_i, b_j) is defined as: \delta(a_i, b_j) = \begin{cases} 0 & \text{if } a_i = b_j \\ 1 & \text{if } a_i \ne b_j \end{cases}

Before we start calculating the difference we should check if the two strings we want to compare already match, if that's the case we can skip the calculation and assert that the distance is 1, since both Strings are already identical.

If that's not the case, we need to calculate the distance manually. One way to calculate the distance would be to transform each string into a vector, such that “Ford Prefect” would become ["f", "o", "r", "d", " ", "p", "r", "e", "f", "e", "c", "t"].

After that we can start calculating our matrix. To illustrate how this is done, we compare "Ford Prefect" with "Ford Perfect", since the first part already matches, we only need to compare the last part, which would look something like this:

The resulting distance is 2 (the number in the bottom right corner).

Particle Example

I got sidetrack earlier talking about my Post Notes Project, which is currently my main use for this algorithm.

I've implemented the search algorithm there so you can quickly search through all of my notes. The somewhat finished approach I've gone with looks like this:

 class NormalizedDistance {
        inner;

        constructor(distance, lengthA, lengthB) {
            const maxLength = Math.max(lengthA, lengthB);
            this.inner = maxLength === 0 ? 1 : 1 - distance / maxLength;
        }
    }

    class LevenshteinDistance {
        lengthA;
        lengthB;
        inner;

        constructor(a, b) {
            this.lengthA = a.length;
            this.lengthB = b.length;

            const matrix = Array.from({ length: a.length + 1 }, () => []);

            for (let i = 0; i <= a.length; i++) matrix[i][0] = i;
            for (let j = 0; j <= b.length; j++) matrix[0][j] = j;

            for (let i = 1; i <= a.length; i++) {
                for (let j = 1; j <= b.length; j++) {
                    const cost = a[i - 1] === b[j - 1] ? 0 : 1;
                    matrix[i][j] = Math.min(
                        matrix[i - 1][j] + 1,
                        matrix[i][j - 1] + 1,
                        matrix[i - 1][j - 1] + cost
                    );
                }
            }

            this.inner = matrix.pop().pop();
        }

        normalize() {
            return new NormalizedDistance(this.inner, this.lengthA, this.lengthB);
        }
    }

You may have noticed that I normalize the result so that I get a reliable result even if the length of both strings differ widely. The current implementation is by far not perfect, but I'm currently short on time, and it's better to be done then to strive for perfection and never finish the project.

I still want to revisit this issue and refine the search a bit. Maybe try out a more functional approach to save space, or look into different concepts like tokenization.AC