Fuzzy matching algorithms
8/3/2026, 5:29:23 PM · updated 8/3/2026, 5:47:27 PM · Source
A comprehensive guide to fuzzy string matching algorithms—including Levenshtein, Damerau-Levenshtein, Bitap, and n-gram—explaining how edit distance metrics work for approximate pattern matching across spell checkers, deduplication, plagiarism detection, bioinformatics, and more.
Fuzzy string matching is technique to find strings which have approximate matches. They are widely used in spell checkers, de-duplication of records, master data management, plagiarism detection, bioinformatics and DNA sequencing, spam filtering, content searches, similarity matches etc.
This article will cover a few algorithms — Levenshtein, Damerau-Levenshtein, Bitap and n-gram — which are implemented for such approximate string matchings. The detailed python implementation and codes are available in the Jupyter notebook in the GitHub repo.
(This was presented as a Women Who Code Data Science session in April 2022. The recording of the session is on YouTube.)
Introduction to fuzzy matching
String matching or fuzzy matching is a method to find strings which match a given pattern or string approximately. It identifies the likelihood or probability that two records are true match based on some parameters. In the example shown below, the algorithms try to match the 5 different variations to the given string ‘Microsoft Corporation’ and score each of them based on how close they match the true value.
Press enter or click to view image in full size
Example where string/fuzzy matching is used
Algorithms used
Most commonly used fuzzy matching algorithms involve calculating the edit distance metrics between the strings. Edit distance metric quantifies how dissimilar two strings are by counting the minimum number of operations required to transform one string into the other. Some of the well-known distance metrics are
- Levenshtein distance
- Damerau–Levenshtein distance
- Longest common subsequence
- Hamming distance
- Jaro distance
Bitap algorithm (shift-or, shift-and algorithm or Baeza-Yates–Gonnet algorithm) which tells whether a given text contains a substring which is “approximately equal” to a given pattern also makes use of Levenshtein distance. It is very efficient for relatively short pattern strings. The Bitap algorithm is the heart of the utility function agrep/grep in Unix systems.
n-gram algorithm uses a Markov model to predict the next item in a sequence of text. n-gram is a pattern of n characters (words, letters, symbols etc.) in some particular order. In text processing, the use of n-grams help capture some information related to the order of words.
The main difference between the Bitap and n-gram algorithms is that the former is an on-line method, while the latter is the off-line one. On-line algorithm do the search without an index and therefore their performance on large data is inefficient. The use of indexing in off-line techniques makes the search drastically faster and is widely used for text processing.
Other commonly used algorithms are Needleman–Wunsch algorithm, Smith–Waterman algorithm, BK Tree metric, Soundex or Metaphone (this is a phonetic algorithm).
Edit distance metrics — Levenshtein distance & Damerau-Levenshtein distance
The edit distance metric measures the number of edits needed to transform one word into another. Levenshtein distance is a popular method to calculate edit distance metric. The figures below show how the Levenshtein and Damerau-Levenshtein distances work and the difference between these two.
Press enter or click to view image in full size
Levenshtein and Damerau-Levenshtein distances
Press enter or click to view image in full size
Calculating Levenshtein and Damerau-Levenshtein distances
The math behind the algorithm is explained below
Press enter or click to view image in full size
Math behind calculating the Levenshtein distance
Levenshtein distance has the following properties:
- It is zero if and only if the strings are equal.
- It is at least the difference of the sizes of the two strings.
- It is at most the length of the longer string.
- Triangle inequality: The Levenshtein distance between two strings is no greater than the sum of their Levenshtein distances from a third string.
Implementation in python
Press enter or click to view image in full size
Bitap algorithm
This is an on-line method of searching (i.e., search without indexing) and uses Levenshtein distance to calculate approximate equality between the search string and the given pattern. Bitap algorithm uses bitwise operations on the bitmasks (a bitmask is the data used for bitwise operations, and multiple bits in a byte, word etc. can be set either on or off, or inverted from on to off or vice versa in a single bitwise operation using bitmasks) which are extremely fast. It performs best on patterns of short lengths due to the underlying data structures.
Get Madhurima Nath, PhD’s stories in your inbox
Join Medium for free to get updates from this writer.
Subscribe
Remember me for faster sign in
Example 1:
input text: womenwhocode, pattern: code
output: Pattern found at index: 8
_Example 2:
_input text: youareawesome, pattern: youareamazing
output: No Match
Implementation in python
Press enter or click to view image in full size
this is my python implementation of the code in GeekforGeeks for bitap seach
Press enter or click to view image in full size
this is my python implementation of the code in GeekforGeeks for bitap search
n-gram algorithm
This algorithm predicts next item in a sequence of text in form of a Markov model. It is an off-line search, i.e., the search is performed on the indices, making this much computationally efficient for large data. Currently, n-gram techniques are used in almost every Natural Language processing algorithms. n-gram is a set of values generated from a string by pairing sequentially occurring n characters/words. The goal is to compute probability of a sequence of characters/words or sentence.
Press enter or click to view image in full size
Math of n-gram algorithm
In this notebook, these algorithms are applied on a simple example to show the similarities/differences between these methods.
Learning map
Fuzzy Matching Algorithms — Learning Roadmap
Stage 1: Foundations
- Understand why approximate string matching matters (exact match is often insufficient in real-world data)
- Learn about edit distance metrics: Levenshtein, Damerau-Levenshtein, Hamming, Jaro-Winkler, longest common subsequence
- Grasp the difference between on-line (Bitap) and off-line (n-gram) search strategies
Stage 2: Core Algorithms & Mathematics
- Levenshtein Distance: Master dynamic programming approach — insertions, deletions, substitutions, with their cost matrix visualization
- Damerau-Levenshtein: Learn the transposition operation added to Levenshtein and why it matters for human typos
- Bitap (Shift-Or/Shift-And): Understand bitmask-based approximate matching for short patterns
- n-gram Matching: Study Markov model foundations and how character/word-level n-grams capture positional information
Stage 3: Python Implementation
- Implement each algorithm from scratch using matrices and bitwise operations
- Use difflib.SequenceMatcher (built-in) for quick prototyping
- Benchmark algorithms against each other on realistic data
Stage 4: Real-World Applications
- Build spell checkers with edit-distance thresholds
- Implement record de-duplication for master data management
- Apply to plagiarism detection and similarity search pipelines
- Explore bioinformatics applications (DNA sequence alignment variants like Needleman-Wunsch, Smith-Waterman)
Get hands-on — step by step
- Set up a Python environment (Python 3.9+ with numpy) and create a project folder for fuzzy matching experiments.
- Run pip install numpy to get the array operations needed for matrix-based implementations.
- Study Levenshtein distance by manually filling in its cost matrix — given s1='kitten' and s2='sitting', trace how each insertion/deletion/substitution builds the DP table step by step.
- Write a Python function that implements Levenshtein distance from scratch using a 2D array: initialize a (m+1)x(n+1) matrix with row/column indices as base costs, then fill it iteratively comparing each character pair.
- Copy and run the Damerau-Levenshtein implementation that adds a transposition cost to the Levenshtein logic — test it on strings like 'cafe' vs 'cafe' (identical) and 'abx' vs 'axy'.
- Implement the Bitap (shift-or) algorithm using Python's built-in integers as bitmasks: for each character in your alphabet, precompute a bitmask; then use bitwise OR and AND operations to slide a window over the text.
- Build an n-gram splitter function that takes a string and integer n, then returns all overlapping n-character sequences (e.g., 'hello' with n=2 yields ['he','el','ll','lo']). Compute similarity by comparing two lists of n-grams using Jaccard or cosine similarity.
- Compare all four algorithms on the same test cases: misspelled company names, near-duplicate records, and short pattern searches — record execution time and accuracy for each.
- Pick one real-world scenario from spell checking, deduplication, or plagiarism detection and build a minimal pipeline using your favorite algorithm from Steps 3-6.
Top 3 sources
- 1difflib — SequenceMatcher (Built-in Fuzzy Matching)
Python standard library module providing SequenceMatcher for computing similarity between sequences, built on an optimized Hunt-Szymanski algorithm. Zero dependencies and the fastest way to prototype fuzzy matching in Python.
https://docs.python.org/3/library/difflib.html
- 2The Sequence Alignment Primer - Levenshtein & Dynamic Programming
Comprehensive guide to sequence alignment algorithms (Levenshtein, Needleman-Wunsch, Smith-Waterman) with the mathematical foundations you need for understanding edit distance metrics — directly applicable to the fuzzy matching techniques in this article.
https://academic.oup.com/femsre/article/28/5/573/540557
- 3Hands-On Machine Learning by Aurélien Géron - NLP Chapter (Ch. 10)
O'Reilly's canonical practical ML text with a strong NLP chapter covering n-grams, embeddings, and similarity search at production scale — bridges the gap between textbook algorithms and real-world applications like deduplication and recommendation.
https://github.com/ageron/handson-ml2
Links are AI-suggested — worth a quick sanity check before diving in.