Build a Fuzzy Search Engine from Scratch

Implement Levenshtein distance in Python to build a typo-tolerant search engine.

Introduction

30 Second Summary

Ever typed a misspelled word into a search bar and still found what you were looking for? That's fuzzy search, the same algorithm behind spell checkers, autocorrect, and Google's "Did you mean?" feature.

In this project, you will build a fuzzy search engine from scratch using Python. You'll implement the core matching algorithm yourself, then benchmark it against a production library called RapidFuzz.

What You'll Build

A command-line fuzzy search engine that searches through a dataset of world countries, tolerating typos and misspellings to return ranked matches.

By the end of this project, you'll have:

  • A working Levenshtein distance algorithm implemented from scratch that calculates edit distance between any two strings.
  • An interactive fuzzy search tool that finds approximate matches in a dataset of 20+ countries, handling typos and misspellings.
  • A side-by-side comparison showing how your hand-built algorithm performs against RapidFuzz, a production fuzzy matching library.
  • Secret Mission: Add "Did You Mean?" autocorrect suggestions that kick in when no exact match is found, plus highlight the differences between the query and the matched result.

Are there any prerequisites?

You should be comfortable with basic Python concepts like variables, functions, loops, lists, and dictionaries. No prior knowledge of algorithms or fuzzy matching is needed.

Before We Start

Every search engine you use handles typos gracefully. Type "Austrailia" into Google and it knows you meant "Australia." This magic is powered by fuzzy matching algorithms that measure how similar two strings are.

In this project, you'll build a fuzzy search engine from scratch using Python. You'll implement the Levenshtein distance algorithm, wrap it in a search tool, then compare your solution against a production library called RapidFuzz. First, let's get your environment ready.

In this step, get ready to:
  • Verify that Python 3.10 or later is installed on your machine.
  • Install the RapidFuzz library for later comparison.
  • Create your project folder and files in Cursor.
Verify Python and set up your editor

This project requires Python 3.10 or later. Let's confirm it's installed on your machine.

  • Press Cmd+Space (macOS) or the Windows key (Windows) to open your search bar.
  • Type Terminal (macOS) or Command Prompt (Windows) and press Enter to open it.
  • Check your Python version by running this command:
python --version

Using macOS?

On macOS, the python command may not exist. Try python3 --version instead. If both work, use whichever shows version 3.10 or higher.

✔️ I see version 3.10 or higher

You should see output like Python 3.10.x or higher (for example Python 3.14.5). You're good to go.

ⓧ I see an older version

If you see a version lower than 3.10 (for example Python 3.8.10), you need to install a newer version.

On macOS, the system Python is often outdated. The python3 command may point to an older version even after installing a new one. Download the latest Python from the link below, install it, then use python3.14 or the full path to the new binary.

  • Download the latest Python installer from https://www.python.org/downloads/.
  • Run the installer. On Windows, check Add Python to PATH during installation.
  • Close and reopen your terminal, then run python --version again to confirm.

ⓧ Command not found

Python is not installed on your machine yet. Let's install it now.

  • Go to https://www.python.org/downloads/ and download the latest Python installer for your operating system.
  • Run the installer. On Windows, make sure to check Add Python to PATH before clicking Install.
  • On macOS, double-click the downloaded .pkg file and follow the prompts.
  • Close and reopen your terminal, then run python --version (or python3 --version on macOS) to confirm you see 3.10 or higher.

Now let's open Cursor, your code editor for this project.

  • Press Cmd+Space (macOS) or the Windows key (Windows) to open your search bar.
  • Type Cursor and press Enter to open it.

What is Cursor?

Cursor is a code editor built on top of VS Code with AI features built in. If you don't have Cursor installed, you can download it from https://cursor.com. VS Code also works if you prefer it.

Next, create your project folder on the Desktop so it's easy to find.

  • Open Cursor's built-in terminal by pressing Ctrl+` (backtick key, same shortcut on macOS and Windows).
  • Move to your Desktop by running this command:
cd ~/Desktop
  • Create your project folder and move into it by running these commands:
mkdir fuzzy-search-engine
cd fuzzy-search-engine
  • Open this folder in Cursor by clicking File in the top menu bar.
  • Click Open Folder.
  • Select the fuzzy-search-engine folder on your Desktop, then click Open.

Don't see the folder?

Make sure you ran both the cd ~/Desktop and mkdir fuzzy-search-engine commands in the terminal. If you're on Windows and ~/Desktop doesn't work, try cd %USERPROFILE%\Desktop instead.

Help me find my project folder on my Desktop.

Install RapidFuzz and create files

You'll compare your hand-built algorithm against RapidFuzz later in the project. Let's install it now so it's ready when you need it.

  • In Cursor's terminal (open it with Ctrl+` if it's not visible), install RapidFuzz by running this command:
pip install rapidfuzz==3.14.5

What does this command do?

This installs rapidfuzz version 3.14.5 from PyPI. Pinning the version with ==3.14.5 ensures everyone working through this project gets identical behavior.

✔️ I see Successfully installed rapidfuzz

The install completed. You're ready to continue.

ⓧ I see an error

If pip is not recognized, try pip3 install rapidfuzz==3.14.5 instead. On macOS, pip3 is the standard command when Python was installed via the official installer.

Help me fix my pip install error.

Now let's create the five Python files you'll build throughout this project.

  • Create all five project files by running this command:
touch levenshtein.py fuzzy_search.py compare.py data.py main.py

On Windows?

The touch command may not exist in Command Prompt. Use this instead:

New-Item levenshtein.py, fuzzy_search.py, compare.py, data.py, main.py
  • Confirm the files exist by running:
ls

You should see levenshtein.py, fuzzy_search.py, compare.py, data.py, and main.py listed in the output.

Files not showing up?

Make sure your terminal is inside the fuzzy-search-engine folder. Run pwd (macOS) or cd (Windows) to check your current location. The path should end with fuzzy-search-engine.

Help me find where my files were created.

Your environment is ready. Next up, you'll implement the Levenshtein distance algorithm from scratch.

Set Up Your Project

Every search engine needs data to search through. Before you write any algorithms, you need a structured dataset that your fuzzy search engine can query.

In this step, you'll open your project in Cursor and create a dataset of 20 world countries with their capitals. This is the data your search engine will match against when handling misspelled queries.

In this step, get ready to:
  • Open the fuzzy-search-engine project folder in Cursor.
  • Build a dataset of 20 world countries and capitals for your search engine to query.
Open your project folder in Cursor

Your fuzzy-search-engine folder already exists on your Desktop with five empty files inside. You need to open it in Cursor so you can start editing.

  • In Cursor, click File in the top menu bar.
  • Click Open Folder.
  • Select the fuzzy-search-engine folder on your Desktop, then click Open.

You should see all five files listed in the Explorer sidebar on the left: compare.py, data.py, fuzzy_search.py, levenshtein.py, and main.py.

Create the country dataset

Your fuzzy search engine needs a collection of real data to search through. You'll create a list of dictionaries where each entry has a country name and its capital city.

  • Click on data.py in the Explorer sidebar to open it.
  • Paste the following country dataset into the file:
countries = [
    {"name": "Australia", "capital": "Canberra"},
    {"name": "Brazil", "capital": "Brasilia"},
    {"name": "Canada", "capital": "Ottawa"},
    {"name": "Denmark", "capital": "Copenhagen"},
    {"name": "Egypt", "capital": "Cairo"},
    {"name": "France", "capital": "Paris"},
    {"name": "Germany", "capital": "Berlin"},
    {"name": "Hungary", "capital": "Budapest"},
    {"name": "India", "capital": "New Delhi"},
    {"name": "Japan", "capital": "Tokyo"},
    {"name": "Kenya", "capital": "Nairobi"},
    {"name": "Lithuania", "capital": "Vilnius"},
    {"name": "Mexico", "capital": "Mexico City"},
    {"name": "Norway", "capital": "Oslo"},
    {"name": "Portugal", "capital": "Lisbon"},
    {"name": "Romania", "capital": "Bucharest"},
    {"name": "Spain", "capital": "Madrid"},
    {"name": "Thailand", "capital": "Bangkok"},
    {"name": "United States", "capital": "Washington D.C."},
    {"name": "Venezuela", "capital": "Caracas"},
]

What does this code do?

The countries variable holds a list of 20 dictionaries. Each dictionary represents one country with two keys: "name" for the country name and "capital" for its capital city.

When your fuzzy search engine receives a misspelled query like "Austrailia", it will compare that query against every "name" value in this list to find the closest match.

  • Save data.py.
  • Open Cursor's integrated terminal by pressing Ctrl+` (backtick) on both macOS and Windows.
  • Confirm the dataset loads correctly by running:
python -c "from data import countries; print(len(countries))"
  • You should see 20 printed in the terminal.

Seeing a ModuleNotFoundError?

Make sure your terminal is open inside the fuzzy-search-engine folder. If the terminal opened in a different directory, run cd ~/Desktop/fuzzy-search-engine first.

Also check that you saved data.py before running the command. Unsaved changes won't be picked up by Python.

Help me fix this ModuleNotFoundError

✔️ Awesome, I've got everything!

Great. Double check you've saved data.py and move on to the next step.

ⓧ I'd like to double check the full code

Here is the complete data.py file:

countries = [
    {"name": "Australia", "capital": "Canberra"},
    {"name": "Brazil", "capital": "Brasilia"},
    {"name": "Canada", "capital": "Ottawa"},
    {"name": "Denmark", "capital": "Copenhagen"},
    {"name": "Egypt", "capital": "Cairo"},
    {"name": "France", "capital": "Paris"},
    {"name": "Germany", "capital": "Berlin"},
    {"name": "Hungary", "capital": "Budapest"},
    {"name": "India", "capital": "New Delhi"},
    {"name": "Japan", "capital": "Tokyo"},
    {"name": "Kenya", "capital": "Nairobi"},
    {"name": "Lithuania", "capital": "Vilnius"},
    {"name": "Mexico", "capital": "Mexico City"},
    {"name": "Norway", "capital": "Oslo"},
    {"name": "Portugal", "capital": "Lisbon"},
    {"name": "Romania", "capital": "Bucharest"},
    {"name": "Spain", "capital": "Madrid"},
    {"name": "Thailand", "capital": "Bangkok"},
    {"name": "United States", "capital": "Washington D.C."},
    {"name": "Venezuela", "capital": "Caracas"},
]

Your dataset is ready to go. Next up, you'll implement the Levenshtein distance algorithm that measures how "close" a misspelled word is to each country name.

Implement the Levenshtein Distance Algorithm

Your project environment is ready with Python, RapidFuzz, and a dataset of 20 countries. Now it's time to build the core algorithm that makes fuzzy search possible.

The Levenshtein distance algorithm measures how different two strings are by counting the minimum number of single-character edits needed to transform one into the other. You'll implement this using dynamic programming, filling a matrix cell by cell until you reach the final answer in the bottom-right corner.

In this step, get ready to:
  • Build the Levenshtein distance function using a dynamic programming matrix.
  • Add a visualization function that prints the full matrix to the console.
  • Test the algorithm with multiple string pairs to verify correctness.
Build the dynamic programming matrix

The Levenshtein distance algorithm works by building a 2D matrix where each cell represents the minimum edits needed to transform a substring of the source into a substring of the target. The first row and column represent distances from an empty string, and each remaining cell is calculated from its three neighbours.

  • In Cursor, open levenshtein.py and add the levenshtein_distance function by pasting this code:
def levenshtein_distance(source, target):
    m = len(source)
    n = len(target)

    matrix = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        matrix[i][0] = i
    for j in range(n + 1):
        matrix[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if source[i - 1] == target[j - 1] else 1

            matrix[i][j] = min(
                matrix[i - 1][j] + 1,       # deletion
                matrix[i][j - 1] + 1,       # insertion
                matrix[i - 1][j - 1] + cost  # substitution
            )

    return matrix[m][n]

What does this code do?

This function creates a matrix of size (len(source) + 1) x (len(target) + 1). The extra row and column account for the empty string.

  • The first row and column are initialized with sequential integers (0, 1, 2, ...) because transforming any string to/from an empty string costs one edit per character.
  • Each remaining cell picks the cheapest option: delete a character (cell above + 1), insert a character (cell to the left + 1), or substitute (diagonal cell + 0 if characters match, + 1 if they don't).
  • The bottom-right cell holds the final answer: the minimum edit distance between the two full strings.

Why dynamic programming?

A brute-force approach would try every possible sequence of edits, which grows exponentially. Dynamic programming breaks the problem into overlapping subproblems (each cell depends on previously computed cells) and solves each one only once. This brings the time complexity down to O(m * n), where m and n are the string lengths.

  • Save levenshtein.py.
  • You won't see any output yet. The next function will visualize how this matrix gets filled.
Add a matrix visualization function

Seeing the matrix printed out makes the algorithm click. This function recalculates the matrix and prints it row by row with headers, so you can trace how the algorithm arrives at each cell's value.

  • Below the levenshtein_distance function in levenshtein.py, add the print_matrix function:
def print_matrix(source, target):
    m = len(source)
    n = len(target)

    matrix = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        matrix[i][0] = i
    for j in range(n + 1):
        matrix[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if source[i - 1] == target[j - 1] else 1
            matrix[i][j] = min(
                matrix[i - 1][j] + 1,
                matrix[i][j - 1] + 1,
                matrix[i - 1][j - 1] + cost
            )

    # Print header
    header = ["", ""] + list(target)
    print("".join(c.rjust(3) for c in header))

    # Print rows
    for i in range(m + 1):
        label = "" if i == 0 else source[i - 1]
        row = [label] + [str(v) for v in matrix[i]]
        print("".join(c.rjust(3) for c in row))

    print(f"\nLevenshtein distance: {matrix[m][n]}")
    return matrix[m][n]

What does this code do?

This function builds the same matrix as levenshtein_distance, but also prints it in a readable grid format.

  • The header row shows each character of the target string, so you can read across to see how costs change.
  • Each subsequent row is labeled with a character from the source string.
  • The final line prints the distance (the value in the bottom-right cell) so you can quickly read the result.
  • Save levenshtein.py.
  • You won't see output yet. The next chunk adds test code that calls both functions.
Test with multiple examples

Now you'll add a test block that runs automatically when you execute the file. This calls both functions with known string pairs so you can verify the algorithm produces correct distances.

  • At the bottom of levenshtein.py, add the test block:
if __name__ == "__main__":
    print("=== Levenshtein Distance Examples ===\n")

    print('--- "kitten" vs "sitting" ---')
    print_matrix("kitten", "sitting")

    print('\n--- "cat" vs "hat" ---')
    d1 = levenshtein_distance("cat", "hat")
    print(f"Distance: {d1}")

    print('\n--- "saturday" vs "sunday" ---')
    d2 = levenshtein_distance("saturday", "sunday")
    print(f"Distance: {d2}")

    print('\n--- "australia" vs "austrailia" ---')
    d3 = levenshtein_distance("australia", "austrailia")
    print(f"Distance: {d3}")

What does this code do?

The if __name__ == "__main__": guard means this code only runs when you execute the file directly. It won't run when other files import the levenshtein_distance function later.

  • The first test uses print_matrix to show the full grid for "kitten" vs "sitting" (expected distance: 3).
  • The remaining tests use levenshtein_distance directly and print just the result for quick verification.
  • Save levenshtein.py.
  • Run the file by executing this command in your terminal:
python levenshtein.py
  • You should see the full matrix for "kitten" vs "sitting" with a distance of 3, then three more results: "cat" vs "hat" = 1, "saturday" vs "sunday" = 3, and "australia" vs "austrailia" = 1.

Seeing an error or wrong distances?

  • If you see IndentationError, check that all lines inside the function body are indented with 4 spaces. Mixing tabs and spaces causes this.
  • If you see NameError: name 'print_matrix' is not defined, make sure the print_matrix function is defined above the if __name__ block, not below it.
  • If the distances are wrong, double check that the cost variable is 0 when characters match and 1 when they don't. Swapping these inverts the logic.

Why is my Levenshtein distance function returning incorrect values?

✔️ Awesome, I've got everything!

Great. Double check you've saved levenshtein.py and your distances match the expected values.

ⓧ I'd like to double check the full code

Here is the complete levenshtein.py file. Compare yours against it:

def levenshtein_distance(source, target):
    m = len(source)
    n = len(target)

    matrix = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        matrix[i][0] = i
    for j in range(n + 1):
        matrix[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if source[i - 1] == target[j - 1] else 1

            matrix[i][j] = min(
                matrix[i - 1][j] + 1,       # deletion
                matrix[i][j - 1] + 1,       # insertion
                matrix[i - 1][j - 1] + cost  # substitution
            )

    return matrix[m][n]


def print_matrix(source, target):
    m = len(source)
    n = len(target)

    matrix = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        matrix[i][0] = i
    for j in range(n + 1):
        matrix[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if source[i - 1] == target[j - 1] else 1
            matrix[i][j] = min(
                matrix[i - 1][j] + 1,
                matrix[i][j - 1] + 1,
                matrix[i - 1][j - 1] + cost
            )

    # Print header
    header = ["", ""] + list(target)
    print("".join(c.rjust(3) for c in header))

    # Print rows
    for i in range(m + 1):
        label = "" if i == 0 else source[i - 1]
        row = [label] + [str(v) for v in matrix[i]]
        print("".join(c.rjust(3) for c in row))

    print(f"\nLevenshtein distance: {matrix[m][n]}")
    return matrix[m][n]


if __name__ == "__main__":
    print("=== Levenshtein Distance Examples ===\n")

    print('--- "kitten" vs "sitting" ---')
    print_matrix("kitten", "sitting")

    print('\n--- "cat" vs "hat" ---')
    d1 = levenshtein_distance("cat", "hat")
    print(f"Distance: {d1}")

    print('\n--- "saturday" vs "sunday" ---')
    d2 = levenshtein_distance("saturday", "sunday")
    print(f"Distance: {d2}")

    print('\n--- "australia" vs "austrailia" ---')
    d3 = levenshtein_distance("australia", "austrailia")
    print(f"Distance: {d3}")

Your Levenshtein distance algorithm is working and verified. Next up, you'll build a fuzzy search module that uses this function to find approximate matches in your countries dataset.

Build the Fuzzy Search Module

Your Levenshtein distance algorithm is working. You've verified it produces correct edit distances for several test cases.

Now you'll wrap that algorithm in a practical search function. The function will loop through your entire country dataset, calculate the distance for each entry, and return only the closest matches ranked by similarity.

In this step, get ready to:
  • Build a fuzzy_search function that calculates edit distances against your country dataset.
  • Normalize raw distances into similarity scores between 0 and 1.
  • Test the search with intentional typos like "Austrailia" and "Brazl".
Create the search function

The search function needs to compare a user's query against every country in the dataset. For each comparison, it calculates the edit distance, filters out anything too far away, and returns the best matches.

  • In Cursor, open fuzzy_search.py and paste the following code:
from levenshtein import levenshtein_distance
from data import countries


def fuzzy_search(query, dataset, threshold=3, key="name", limit=5):
    query_lower = query.lower()

    results = []

    for item in dataset:
        value = item[key].lower()
        distance = levenshtein_distance(query_lower, value)

        if distance <= threshold:
            max_len = max(len(query_lower), len(value))
            score = 1 - (distance / max_len)

            results.append({
                "item": item,
                "distance": distance,
                "score": score,
            })

    results.sort(key=lambda r: r["score"], reverse=True)

    return results[:limit]

What does this code do?

  • The function imports levenshtein_distance from the module you built in the previous step.
  • It lowercases both the query and each dataset value so that comparisons are case-insensitive.
  • The threshold parameter controls how many edits are tolerated. Only results within this distance are kept.
  • Results are sorted by score (highest similarity first) and capped at limit entries.
  • Save fuzzy_search.py.
  • You won't see output yet. The next substep adds test code to verify the search works.

Seeing an import error?

Make sure levenshtein.py and data.py are in the same folder as fuzzy_search.py. Python looks for imports in the same directory first.

Check that levenshtein.py is named exactly right. A typo in the filename means Python can't find the module.

help me fix an import error in fuzzy_search.py

Understand scoring and ranking

The raw edit distance tells you how many changes are needed, but it doesn't account for string length. A distance of 3 means something very different for a 4-letter word versus a 15-letter word.

How does the similarity score work?

The formula 1 - (distance / max_len) normalizes the distance into a value between 0 and 1. A score of 1.0 means a perfect match (zero edits). A score of 0.0 means the strings are completely different.

Dividing by the longer string's length ensures that short and long strings are compared fairly. "Brazl" vs "Brazil" (distance 1, max length 6) scores 0.83. "Untied States" vs "United States" (distance 2, max length 13) scores 0.85.

What does the threshold control?

The threshold parameter is a hard cutoff on edit distance. With threshold=3, any country name requiring more than 3 edits is excluded entirely. A lower threshold is stricter (fewer results). A higher threshold is more forgiving (more results, but noisier).

Test the search with typos

Time to prove the search works. You'll add a test block that runs common misspellings through your function and prints ranked results.

  • Add the following test block at the bottom of fuzzy_search.py, below the fuzzy_search function:
if __name__ == "__main__":
    print("=== Fuzzy Search Tests ===\n")

    test_queries = ["Austrailia", "Brazl", "Frence", "Untied States"]

    for query in test_queries:
        print(f'Query: "{query}"')
        print("-" * 40)

        results = fuzzy_search(query, countries, threshold=3)

        if not results:
            print("  No matches found.")
        else:
            for result in results:
                name = result["item"]["name"]
                capital = result["item"]["capital"]
                score = result["score"] * 100
                dist = result["distance"]
                print(f"  {name} ({capital}) - Score: {score:.1f}% | Distance: {dist}")

        print()

What does this test block do?

  • The if __name__ == "__main__": guard ensures this code only runs when you execute the file directly, not when another module imports it.
  • It runs four intentionally misspelled queries through your fuzzy_search function and prints each match with its country name, capital, similarity score (as a percentage), and edit distance.
  • Save fuzzy_search.py.
  • Run the search tests by running this command in your terminal:
python fuzzy_search.py
  • You should see ranked results for each query. "Austrailia" should match Australia with a high similarity score. "Brazl" should match Brazil. "Frence" should match France. "Untied States" should match United States.

Not seeing any matches?

If you see "No matches found" for every query, check that your data.py file contains the full list of 20 countries. An empty or incomplete list means nothing is close enough to match.

If you see a NameError or ImportError, confirm the import line at the top of your file says from data import countries and that your terminal is inside the fuzzy-search-engine folder.

help me debug my fuzzy search output

Experiment with threshold values

Try changing threshold=3 to threshold=1 in the test block and re-running. You'll see fewer matches because only single-edit typos qualify. Set it back to 3 when you're done experimenting.

✔️ Awesome, I've got everything!

Great. Double check you've saved your file before moving on.

ⓧ I'd like to double check the full code

Here's the complete fuzzy_search.py file for comparison:

from levenshtein import levenshtein_distance
from data import countries


def fuzzy_search(query, dataset, threshold=3, key="name", limit=5):
    query_lower = query.lower()

    results = []

    for item in dataset:
        value = item[key].lower()
        distance = levenshtein_distance(query_lower, value)

        if distance <= threshold:
            max_len = max(len(query_lower), len(value))
            score = 1 - (distance / max_len)

            results.append({
                "item": item,
                "distance": distance,
                "score": score,
            })

    results.sort(key=lambda r: r["score"], reverse=True)

    return results[:limit]


if __name__ == "__main__":
    print("=== Fuzzy Search Tests ===\n")

    test_queries = ["Austrailia", "Brazl", "Frence", "Untied States"]

    for query in test_queries:
        print(f'Query: "{query}"')
        print("-" * 40)

        results = fuzzy_search(query, countries, threshold=3)

        if not results:
            print("  No matches found.")
        else:
            for result in results:
                name = result["item"]["name"]
                capital = result["item"]["capital"]
                score = result["score"] * 100
                dist = result["distance"]
                print(f"  {name} ({capital}) - Score: {score:.1f}% | Distance: {dist}")

        print()

Your fuzzy search module is finding matches through typos. Next up, you'll pit your hand-built algorithm against RapidFuzz, a production library, and see how they compare on the same queries.

Compare with RapidFuzz

Your fuzzy search engine works. It finds matches, ranks them by similarity, and handles typos gracefully. But how does it stack up against a production library?

In this step, you'll run your hand-built Levenshtein algorithm alongside RapidFuzz, a high-performance fuzzy matching library written in C++. Seeing the same queries processed by both approaches will show you exactly where a pure Python implementation trades off against a compiled, optimized library.

In this step, get ready to:
  • Set up RapidFuzz to search the same country dataset.
  • Run both algorithms side-by-side on identical typo queries.
  • Print a summary table comparing features and trade-offs.
Set up RapidFuzz with the same dataset

RapidFuzz needs a flat list of strings to search through, not a list of dictionaries. You'll extract just the country names into a choices list so RapidFuzz can process them.

  • In Cursor, open compare.py and add the imports and setup code:
from rapidfuzz import fuzz, process, utils
from data import countries
from fuzzy_search import fuzzy_search

# Prepare choices for RapidFuzz
choices = [c["name"] for c in countries]

test_queries = ["Austrailia", "Brazl", "Frence", "Japn", "Canad"]

What does this code do?

You import three modules from RapidFuzz: fuzz (scoring functions), process (batch matching utilities), and utils (preprocessing helpers).

The choices list extracts just the country names from your dataset. RapidFuzz's process.extract() expects a simple list of strings to search through, not dictionaries.

  • You won't see a change yet. The next chunk uses this setup to run both algorithms.
Run a side-by-side comparison

Now you'll loop through each test query and run it through both your algorithm and RapidFuzz. This puts the results next to each other so you can compare scoring approaches directly.

  • Add the comparison loop below your test_queries list in compare.py:
print("=== Fuzzy Search Comparison ===")
print("Your Algorithm (Levenshtein) vs RapidFuzz (Optimized C++)\n")
print("=" * 60)

for query in test_queries:
    print(f'\nQuery: "{query}"')
    print("-" * 60)

    # Your algorithm
    my_results = fuzzy_search(query, countries, threshold=3, limit=3)

    print("\n  Your Algorithm (Levenshtein Distance):")
    if not my_results:
        print("    No matches")
    else:
        for r in my_results:
            name = r["item"]["name"]
            score = r["score"] * 100
            dist = r["distance"]
            print(f"    {name} - Similarity: {score:.1f}% (edit distance: {dist})")

    # RapidFuzz
    rf_results = process.extract(
        query, choices, scorer=fuzz.WRatio,
        processor=utils.default_process, limit=3
    )

    print("\n  RapidFuzz (WRatio scorer):")
    if not rf_results:
        print("    No matches")
    else:
        for match, score, index in rf_results:
            print(f"    {match} - Score: {score:.1f}%")

What does this code do?

For each misspelled query, the loop runs two searches back-to-back.

Your algorithm uses fuzzy_search() with a threshold of 3 and returns the top 3 matches with similarity percentages and raw edit distances.

RapidFuzz uses process.extract() with the fuzz.WRatio scorer (a weighted combination of multiple matching strategies) and utils.default_process for automatic case normalization. It returns tuples of (match, score, index).

Why use utils.default_process?

Since RapidFuzz 3.0.0, strings are not preprocessed by default. Without processor=utils.default_process, RapidFuzz treats uppercase and lowercase as different characters. Your algorithm handles this manually with .lower().

  • You won't run the script yet. The next chunk adds a summary table that completes the comparison.
Print the summary table

The raw results show what each algorithm returns. A feature comparison table makes the trade-offs between your implementation and RapidFuzz explicit at a glance.

  • Add the summary table at the bottom of compare.py, after the for loop:
print("\n" + "=" * 60)
print("\n=== Summary ===\n")
print("| Feature                | Your Algorithm       | RapidFuzz            |")
print("|------------------------|----------------------|----------------------|")
print("| Algorithm              | Levenshtein (DP)     | Levenshtein + Indel  |")
print("| Implementation         | Pure Python          | C++ with Python bind |")
print("| Speed                  | Slower (interpreted) | Very fast (compiled) |")
print("| Multiple scorers       | No (edit distance)   | Yes (ratio, partial) |")
print("| Batch processing       | Manual loop          | process.extract()    |")
print("| Preprocessing          | Manual lowercasing   | utils.default_process|")
print("| Best for               | Learning / simple    | Production apps      |")

What does this table show?

Your algorithm is pure Python and uses a single scoring method (edit distance). RapidFuzz is backed by compiled C++ code, offers multiple scoring strategies (ratio, partial ratio, token sort), and includes batch utilities like process.extract() that search entire collections in one call.

Your implementation is excellent for learning how fuzzy matching works under the hood. RapidFuzz is what you'd reach for in a production application where speed and features matter.

  • Save compare.py.
  • Run the comparison script by entering this in your terminal:
python compare.py
  • You should see each test query followed by your algorithm's results (with similarity percentages and edit distances) and RapidFuzz's results (with WRatio scores). At the bottom, the summary table compares features side-by-side.

Seeing a ModuleNotFoundError?

If the error mentions rapidfuzz, the library may not be installed in the Python environment your terminal is using. Run pip install rapidfuzz==3.14.5 again and make sure you're using the same python that pip installed to.

If the error mentions levenshtein or fuzzy_search, make sure you're running the command from inside your fuzzy-search-engine folder where all your .py files live.

Still stuck? Help me debug why python compare.py is throwing a ModuleNotFoundError.

✔️ Awesome, I've got everything!

Great. Double check you've saved your file before moving on.

ⓧ I'd like to double check the full code

from rapidfuzz import fuzz, process, utils
from data import countries
from fuzzy_search import fuzzy_search

# Prepare choices for RapidFuzz
choices = [c["name"] for c in countries]

test_queries = ["Austrailia", "Brazl", "Frence", "Japn", "Canad"]

print("=== Fuzzy Search Comparison ===")
print("Your Algorithm (Levenshtein) vs RapidFuzz (Optimized C++)\n")
print("=" * 60)

for query in test_queries:
    print(f'\nQuery: "{query}"')
    print("-" * 60)

    # Your algorithm
    my_results = fuzzy_search(query, countries, threshold=3, limit=3)

    print("\n  Your Algorithm (Levenshtein Distance):")
    if not my_results:
        print("    No matches")
    else:
        for r in my_results:
            name = r["item"]["name"]
            score = r["score"] * 100
            dist = r["distance"]
            print(f"    {name} - Similarity: {score:.1f}% (edit distance: {dist})")

    # RapidFuzz
    rf_results = process.extract(
        query, choices, scorer=fuzz.WRatio,
        processor=utils.default_process, limit=3
    )

    print("\n  RapidFuzz (WRatio scorer):")
    if not rf_results:
        print("    No matches")
    else:
        for match, score, index in rf_results:
            print(f"    {match} - Score: {score:.1f}%")

print("\n" + "=" * 60)
print("\n=== Summary ===\n")
print("| Feature                | Your Algorithm       | RapidFuzz            |")
print("|------------------------|----------------------|----------------------|")
print("| Algorithm              | Levenshtein (DP)     | Levenshtein + Indel  |")
print("| Implementation         | Pure Python          | C++ with Python bind |")
print("| Speed                  | Slower (interpreted) | Very fast (compiled) |")
print("| Multiple scorers       | No (edit distance)   | Yes (ratio, partial) |")
print("| Batch processing       | Manual loop          | process.extract()    |")
print("| Preprocessing          | Manual lowercasing   | utils.default_process|")
print("| Best for               | Learning / simple    | Production apps      |")

You've seen exactly how your hand-built algorithm stacks up against a production library. Next, you'll bring everything together into an interactive CLI where you can type any query and see live fuzzy search results.

Build the Interactive CLI Search

You've already compared your algorithm against RapidFuzz and seen how both approaches handle misspelled queries. Now it's time to give your fuzzy search engine a proper interface.

In this step, you'll build an interactive command-line tool that lets anyone type a country name and instantly see ranked matches. You'll add colour-coded output so high-confidence results stand out from weaker ones at a glance.

In this step, get ready to:
  • Create an interactive search loop that accepts user input and exits on "quit".
  • Format results with colour-coded similarity scores and a friendly fallback message.
Create the interactive prompt

Your search modules work, but right now you have to edit Python files to test different queries. An interactive prompt lets you type queries in real-time and see results instantly.

  • In Cursor, open main.py from the Explorer sidebar.
  • Add the following imports and ANSI colour constants at the top of the file:
from fuzzy_search import fuzzy_search
from data import countries

# ANSI escape codes for coloured terminal output
GREEN = "\033[32m"
YELLOW = "\033[33m"
RED = "\033[31m"
RESET = "\033[0m"
BOLD = "\033[1m"

What are ANSI escape codes?

ANSI escape codes are special character sequences that tell your terminal to change text colour, make it bold, or reset formatting. They start with \033[ followed by a number code.

The RESET code turns off all formatting so your colours don't bleed into the next line of output.

  • Below the constants, add the main() function that creates the interactive loop:
def main():
    print(f"{BOLD}=== Fuzzy Search Engine ==={RESET}")
    print("Search for any country by name. Typos are welcome!")
    print('Type "quit" to exit.\n')

    while True:
        try:
            query = input(f"{BOLD}Search: {RESET}").strip()
        except (EOFError, KeyboardInterrupt):
            print("\nGoodbye!")
            break

        if query.lower() == "quit":
            print("\nGoodbye!")
            break

        if not query:
            continue

        results = fuzzy_search(query, countries, threshold=3, limit=5)
        display_results(query, results)


if __name__ == "__main__":
    main()

What does this code do?

  • while True creates an infinite loop that keeps prompting for input until the user types "quit" or presses Ctrl+C.
  • The try/except block catches keyboard interrupts (Ctrl+C) so the program exits gracefully instead of showing a traceback.
  • Each query runs through fuzzy_search() with a threshold of 3 edits and a limit of 5 results, then passes the matches to display_results() for formatting.

You won't see a change yet. The display_results() function doesn't exist yet, so running the file would raise a NameError. You'll build it in the next substep.

Format the output nicely

Raw numbers aren't helpful if you can't tell good results from weak ones at a glance. You'll add a colour helper and a display function that formats each match as a numbered, colour-coded entry.

  • In main.py, add the following two functions between the ANSI constants and the main() function:
def get_color(score):
    if score >= 0.8:
        return GREEN
    if score >= 0.6:
        return YELLOW
    return RED


def display_results(query, results):
    if not results:
        print(f"\n{RED}  No matches found. Try a different spelling.{RESET}\n")
        return

    print(f'\n{BOLD}  Results for "{query}":{RESET}\n')

    for i, result in enumerate(results, 1):
        item = result["item"]
        score = result["score"]
        distance = result["distance"]
        color = get_color(score)
        pct = score * 100

        print(f"  {color}{i}. {item['name']}{RESET} (capital: {item['capital']})")
        print(f"     Similarity: {color}{pct:.1f}%{RESET} | Edit distance: {distance}")

    print()

What does this code do?

  • get_color() picks a colour based on the similarity score. Green means 80%+ match, yellow means 60-79%, and red means below 60%.
  • display_results() handles two cases. When no matches exist within the threshold, it prints a red "No matches found" message. Otherwise, it loops through results and prints each one with its rank, country name, capital, similarity percentage, and edit distance.
  • enumerate(results, 1) gives each result a number starting at 1 instead of 0, so the output reads naturally as a ranked list.
  • Save main.py.
  • Launch the interactive search by running this command in your terminal:
python main.py
  • You should see a bold "=== Fuzzy Search Engine ===" header followed by a Search: prompt.
  • Type Austrailia and press Enter. You should see "Australia" appear in green with a high similarity score.
  • Try xyzzy to see the red "No matches found" fallback.
  • Type quit to exit the interactive loop.

Not seeing colours in your terminal?

  • If you see raw escape codes like \033[32m instead of green text, your terminal may not support ANSI codes. On Windows, use Windows Terminal or PowerShell instead of the older cmd.exe.
  • If you get a NameError for display_results, make sure the get_color() and display_results() functions appear ABOVE the main() function in the file.
  • Check that your imports at the top match exactly: from fuzzy_search import fuzzy_search and from data import countries.

Still stuck? Help me debug why my main.py interactive search isn't working

✔️ Awesome, I've got everything!

Great. Double check you've saved your file.

ⓧ I'd like to double check the full code

from fuzzy_search import fuzzy_search
from data import countries

GREEN = "\033[32m"
YELLOW = "\033[33m"
RED = "\033[31m"
RESET = "\033[0m"
BOLD = "\033[1m"


def get_color(score):
    if score >= 0.8:
        return GREEN
    if score >= 0.6:
        return YELLOW
    return RED


def display_results(query, results):
    if not results:
        print(f"\n{RED}  No matches found. Try a different spelling.{RESET}\n")
        return

    print(f'\n{BOLD}  Results for "{query}":{RESET}\n')

    for i, result in enumerate(results, 1):
        item = result["item"]
        score = result["score"]
        distance = result["distance"]
        color = get_color(score)
        pct = score * 100

        print(f"  {color}{i}. {item['name']}{RESET} (capital: {item['capital']})")
        print(f"     Similarity: {color}{pct:.1f}%{RESET} | Edit distance: {distance}")

    print()


def main():
    print(f"{BOLD}=== Fuzzy Search Engine ==={RESET}")
    print("Search for any country by name. Typos are welcome!")
    print('Type "quit" to exit.\n')

    while True:
        try:
            query = input(f"{BOLD}Search: {RESET}").strip()
        except (EOFError, KeyboardInterrupt):
            print("\nGoodbye!")
            break

        if query.lower() == "quit":
            print("\nGoodbye!")
            break

        if not query:
            continue

        results = fuzzy_search(query, countries, threshold=3, limit=5)
        display_results(query, results)


if __name__ == "__main__":
    main()

Your fuzzy search engine is fully operational. You've gone from a raw algorithm to a polished interactive tool that handles typos gracefully. Next up, you'll push this even further with autocorrect suggestions in the Secret Mission.

Secret mission

Add "Did You Mean?" Autocorrect

Your fuzzy search finds matches, but real search engines go further. They proactively suggest corrections before showing results. In this mission, you'll add a "Did you mean?" system that highlights exactly which characters differ between the query and the suggestion.

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your files around for further experimentation, or delete them to free up space.

Resources you used:

  • The fuzzy-search-engine project folder (local files).
  • The rapidfuzz Python package (installed via pip).

Keep everything running

No action needed. Choose this if you want to keep experimenting with your fuzzy search engine or extend it further.

  • Your project files stay in the fuzzy-search-engine folder.
  • The rapidfuzz package stays installed in your Python environment.

Pause - I'll come back to this later

There are no running processes or background services to pause. Your files will be exactly as you left them whenever you come back.

  • Close the project in Cursor to free up memory.

Delete - I don't want to use this again

Remove all project files and the installed package to start completely fresh.

  • Delete the project folder by running this command in your terminal:
rm -rf ~/Desktop/fuzzy-search-engine

On Windows, run this instead:

rmdir /s /q "$HOME\Desktop\fuzzy-search-engine"
  • Uninstall the RapidFuzz package by running:
pip uninstall rapidfuzz -y

Nice Work!

Nice Work!

You just built a fuzzy search engine from the ground up. You now understand exactly how tools like spell checkers and autocorrect work under the hood.

You've learned how to:

  • Implement the Levenshtein distance algorithm using dynamic programming, one of the most important string algorithms in computer science.
  • Build a practical fuzzy search tool that finds approximate matches in a dataset, tolerating typos and misspellings gracefully.
  • Compare your hand-built solution to RapidFuzz, understanding the trade-offs between learning-friendly implementations and production-grade C++ libraries.
  • Added "Did You Mean?" autocorrect suggestions with visual diff highlighting and a prefix bonus scoring system.

Ready to quiz yourself?