Career Catalogue
← All writing

Implementing Fuzzy Search with Levenshtein Distance

2 min read

Vladimir Levenshtein, a Soviet mathematician, developed the concept of edit distance in 1965 whilst working at the Keldysh Institute of Applied Mathematics. His work was originally aimed at correcting errors in binary codes transmitted through noisy communication channels, where bits could be deleted, inserted, or substituted during transmission. This mathematical foundation eventually became a cornerstone for modern string matching, providing a way to quantify the similarity between two sequences.

Exact string matching is often insufficient for production search systems because it fails to account for user typos or character variations. Implementing a fuzzy search mechanism allows the system to return relevant results based on string similarity rather than binary equality.

The Levenshtein Distance Algorithm

Levenshtein distance, or edit distance, is a metric used to measure the difference between two sequences. It represents the minimum number of single-character edits required to transform one string into another.

The allowed operations are:

  1. Insertion: Adding a character.
  2. Deletion: Removing a character.
  3. Substitution: Replacing one character with another.

Application in Bioinformatics

In the field of genetics, this algorithm is fundamental to DNA sequence alignment. By treating the four nucleotide bases (A, C, G, T) as characters in a string, researchers use edit distance to identify mutations. Substitutions represent point mutations, whilst insertions and deletions (indels) account for bases added or lost during replication. Identifying the minimum number of edits allows scientists to determine the evolutionary distance between species or locate specific genetic disorders. Surprisingly, though, we aren’t using it to map the human genome, we just want to make sure the search bar works when someone forgets how to spell “plumber.”

Application in Search Systems

In a search context, the Levenshtein distance is typically used alongside a predefined threshold. For example, a maximum edit distance of 2 is often sufficient to catch common typing errors without introducing excessive noise into the results.

  1. Preprocessing: Strings are normalised (lowercased, whitespace trimmed) before calculation.
  2. Filtering: The algorithm runs against a candidate set of results to identify those within the acceptable distance threshold.
  3. Ranking: Results are sorted by distance, where a lower distance indicates a higher relevance.

Using this algorithm provides a more robust search interface that accounts for human error and improves result discoverability.