Build a Trie-Based Spell Checker in C++
Build a compressed trie spell checker with fuzzy search and frequency ranking.
Introduction
30 Second Summary
Every time you type a message and your phone suggests the right word despite your typos, there's a spell checker working behind the scenes. It combines clever data structures with distance algorithms to figure out what you actually meant to type.
In this project, you will build a production-quality spell checker engine in C++ that loads a real English dictionary of 466,000+ words, detects misspellings, and suggests corrections ranked by edit distance and word frequency.
What You'll Build
A command-line spell checker that uses a Compressed Trie (Radix Tree) for memory-efficient dictionary storage and Damerau-Levenshtein distance for intelligent fuzzy matching.
By the end of this project, you'll have:
- A Compressed Trie (Radix Tree) storing 466,000+ English words with memory-efficient string-edge compression.
- A fuzzy search engine that traverses the trie with edit distance pruning to suggest corrections in real time.
- An interactive CLI with spell-check and autocomplete modes, colored terminal output, and performance benchmarking.
- Secret Mission: add keyboard-distance-aware scoring that weights suggestions based on QWERTY key proximity.
Are there any prerequisites?
You should be familiar with C++ basics like classes, pointers, and STL containers. An understanding of recursion and basic data structures (trees) will also help you follow along.
Before We Start
You are about to build a spell checker engine from scratch in C++. This system will store hundreds of thousands of English words in a memory-efficient Compressed Trie, then use a Damerau-Levenshtein algorithm to find corrections for misspelled input.
Before writing any code, you need a working C++ compiler, a code editor, and a clean project structure. This step gets all three in place so you can focus on algorithms from Step 2 onward.
In this step, get ready to:
- Install Xcode Command Line Tools and verify C++17 compilation.
- Install and open the Cursor code editor.
- Create the project directory structure and Makefile.
Install Xcode Command Line Tools
Xcode Command Line Tools provides Apple Clang, the C++ compiler you will use throughout this project. It includes full C++17 support, which the project relies on for structured bindings, std::optional, and other modern features.
- Press Cmd+Space to open Spotlight.
- Type Terminal and press Enter to open it.
- Install Xcode Command Line Tools by running this command:
xcode-select --installWhat does this command do?
This triggers macOS to download and install the developer tools package, which includes the clang++ compiler, make, and other build utilities. A dialog will appear asking you to confirm the install. Click Install and wait for it to finish (this can take a few minutes).
- Once the installation finishes, verify the compiler is available by running:
clang++ --version✔️ I see a version number
You should see output starting with something like Apple clang version followed by a version number. This confirms the compiler is ready.
ⓧ Command not found
If you see a "command not found" error, the Xcode Command Line Tools did not install correctly.
- Try running xcode-select --install again and follow the prompts.
- If the dialog says tools are already installed but clang++ still fails, run:
sudo xcode-select --resetThen try clang++ --version again.
Now confirm that C++17 compilation works. Create a quick test file and compile it:
- Run this command to write a small C++17 test program and compile it:
echo '#include <iostream>
#include <optional>
int main() {
std::optional<int> val = 42;
std::cout << "C++17 works: " << *val << std::endl;
return 0;
}' > /tmp/test17.cpp && clang++ -std=c++17 -o /tmp/test17 /tmp/test17.cpp && /tmp/test17What does this command do?
This writes a tiny C++ program that uses std::optional (a C++17 feature), compiles it with the -std=c++17 flag, and runs it. If you see C++17 works: 42 in the output, your compiler fully supports C++17.
- You should see C++17 works: 42 printed in your terminal.
Seeing an error about std::optional?
If compilation fails with an error about unsupported features, your Xcode Command Line Tools may be outdated. Update them by running:
softwareupdate --list
softwareupdate -i "Command Line Tools for Xcode"After updating, try the test compilation again. help me debug my C++17 compilation error on macOS
Note: On macOS, g++ is actually an alias for Apple Clang. Both clang++ and g++ will use the same compiler.
Install and open Cursor
Cursor is an AI-powered code editor built on VS Code. You will use it to write and organize the C++ source files for this project.
- Download Cursor from the official download page.
- Open the downloaded .dmg file and drag Cursor into your Applications folder.
- Press Cmd+Space to open Spotlight.
- Type Cursor and press Enter to launch it.
- If macOS asks whether to open an app downloaded from the internet, click Open.
- Complete the first-launch setup wizard (you can import VS Code settings if you have them, or start fresh).
Cursor not opening?
If macOS blocks the app, go to System Settings then Privacy & Security. Scroll down and click Open Anyway next to the Cursor message. help me open Cursor on macOS
Create the project directory structure
A clean folder layout keeps your headers, source files, tests, and data separate. This project uses the standard C++ convention of include/ for headers and src/ for implementation files.
- Switch to your Terminal and move to your Desktop by running this command:
cd ~/Desktop- Create your project folder and all subdirectories by running these commands:
mkdir -p spellcheck-engine/{src,include,tests,data,build}
cd spellcheck-engine- Confirm the folders exist by running:
ls- You should see build, data, include, src, and tests listed in the output.
What are these folders for?
- src/ holds your .cpp implementation files (the actual logic).
- include/ holds your .h header files (class declarations and interfaces).
- tests/ will hold your unit tests.
- data/ will hold the dictionary file and serialized binary.
- build/ will hold compiled object files (generated by make).
Now you need a Makefile to automate compilation. This tells make how to find your source files, what compiler flags to use, and how to link everything into a single executable.
- Open the spellcheck-engine folder in Cursor by clicking File in the menu bar, then Open Folder.
- Select the spellcheck-engine folder on your Desktop and click Open.
- Create a new file by clicking File then New File.
- Save it immediately as Makefile (no extension) in the project root with Cmd+S.
- Paste the following into Makefile:
CXX = clang++
CXXFLAGS = -std=c++17 -Wall -Wextra -O2 -Iinclude
LDFLAGS =
SRC_DIR = src
INC_DIR = include
BUILD_DIR = build
SOURCES = $(wildcard $(SRC_DIR)/*.cpp)
OBJECTS = $(SOURCES:$(SRC_DIR)/%.cpp=$(BUILD_DIR)/%.o)
TARGET = spellcheck
.PHONY: all clean test
all: $(BUILD_DIR) $(TARGET)
$(BUILD_DIR):
mkdir -p $(BUILD_DIR)
$(TARGET): $(OBJECTS)
$(CXX) $(CXXFLAGS) $(LDFLAGS) -o $@ $^
$(BUILD_DIR)/%.o: $(SRC_DIR)/%.cpp
$(CXX) $(CXXFLAGS) -c -o $@ $<
clean:
rm -rf $(BUILD_DIR) $(TARGET) data/dictionary.bin
test: $(TARGET)
./$(TARGET) data/words_alpha.txtWhat does this Makefile do?
- CXX = clang++ sets Apple Clang as the compiler.
- -std=c++17 enables C++17 features. -Wall -Wextra turns on helpful compiler warnings. -O2 enables optimization.
- -Iinclude tells the compiler to look in the include/ folder for header files.
- The clean target removes all compiled files so you can rebuild from scratch.
- The test target compiles and runs the spell checker against the dictionary file.
Makefile indentation must use tabs
The indented lines under each target (like mkdir -p $(BUILD_DIR)) must use a tab character, not spaces. If you see errors about "missing separator" when running make later, replace the leading spaces with a single tab on each indented line.
- Save Makefile with Cmd+S.
✔️ Awesome, I've got everything!
Great. Double check you have saved your Makefile and it appears in the Cursor sidebar at the project root (not inside any subfolder).
ⓧ I'd like to double check the full code
Here is the complete Makefile for comparison:
CXX = clang++
CXXFLAGS = -std=c++17 -Wall -Wextra -O2 -Iinclude
LDFLAGS =
SRC_DIR = src
INC_DIR = include
BUILD_DIR = build
SOURCES = $(wildcard $(SRC_DIR)/*.cpp)
OBJECTS = $(SOURCES:$(SRC_DIR)/%.cpp=$(BUILD_DIR)/%.o)
TARGET = spellcheck
.PHONY: all clean test
all: $(BUILD_DIR) $(TARGET)
$(BUILD_DIR):
mkdir -p $(BUILD_DIR)
$(TARGET): $(OBJECTS)
$(CXX) $(CXXFLAGS) $(LDFLAGS) -o $@ $^
$(BUILD_DIR)/%.o: $(SRC_DIR)/%.cpp
$(CXX) $(CXXFLAGS) -c -o $@ $<
clean:
rm -rf $(BUILD_DIR) $(TARGET) data/dictionary.bin
test: $(TARGET)
./$(TARGET) data/words_alpha.txtDon't see the subfolders in Cursor?
Make sure you opened the spellcheck-engine folder itself (not a parent folder). You should see src, include, tests, data, and build in the Explorer sidebar on the left. help me open my project folder in Cursor
Your development environment is ready. Next up, you will build the core Trie data structure that forms the foundation of the spell checker.
Build the Core Trie Data Structure
A spell checker needs to store hundreds of thousands of words in a way that supports lightning-fast lookups and prefix searches. A Trie (prefix tree) is the ideal data structure for this because every lookup takes O(k) time where k is the word length, regardless of how many words the dictionary contains.
In this step, you'll build a Compressed Trie (also called a Radix Tree) that stores string labels on edges instead of single characters. This gives you memory efficiency from the start while supporting insert, search, prefix matching, and autocomplete.
In this step, get ready to:
- Define the TrieNode structure with children, end-of-word flag, frequency, and edge labels.
- Implement insert, search, startsWith, and remove operations with edge compression.
- Add prefix-based autocomplete that collects words using depth-first search.
Define the TrieNode structure
Every node in the trie needs to track its children, whether it marks the end of a complete word, and the word's frequency (for ranking suggestions later). The edgeLabel field stores a string on each edge, which is what makes this a compressed trie rather than a character-per-node trie.
- Create a new file called trie_node.h inside your include/ folder by pasting the following code:
#pragma once
#include <string>
#include <unordered_map>
#include <memory>
#include <vector>
struct TrieNode {
// Map from first character to child node (owned via unique_ptr)
std::unordered_map<char, std::unique_ptr<TrieNode>> children;
bool isEndOfWord = false;
int frequency = 0;
// Edge label stores the full string for this edge (compressed trie)
std::string edgeLabel;
TrieNode() = default;
explicit TrieNode(const std::string& label) : edgeLabel(label) {}
};What does this code do?
This struct defines a single node in the compressed trie. Each node uses a std::unordered_map keyed by the first character of each child's edge label for O(1) child lookups.
The std::unique_ptr ensures automatic memory cleanup when nodes are removed. The explicit constructor lets you create a node with a pre-set edge label in one step.
- Save include/trie_node.h.
Red squiggles in Cursor?
If Cursor shows errors on the includes, that's expected until the full project compiles. The #pragma once guard prevents duplicate inclusion issues. Help me understand why Cursor shows red squiggles before the project compiles.
✔️ Awesome, I've got everything!
Great. Make sure you've saved the file before moving on.
ⓧ I'd like to double check the full code
#pragma once
#include <string>
#include <unordered_map>
#include <memory>
#include <vector>
struct TrieNode {
std::unordered_map<char, std::unique_ptr<TrieNode>> children;
bool isEndOfWord = false;
int frequency = 0;
std::string edgeLabel;
TrieNode() = default;
explicit TrieNode(const std::string& label) : edgeLabel(label) {}
};Implement insert, search, and startsWith
Now you'll declare the RadixTree class interface and implement the core operations. The insert method is the most complex because it handles edge splitting when a new word partially matches an existing edge.
- Create a new file called radix_tree.h inside your include/ folder by pasting this class declaration:
#pragma once
#include "trie_node.h"
#include <string>
#include <vector>
#include <utility>
#include <fstream>
class RadixTree {
public:
RadixTree();
void insert(const std::string& word, int frequency = 1);
bool search(const std::string& word) const;
bool startsWith(const std::string& prefix) const;
void remove(const std::string& word);
std::vector<std::pair<std::string, int>> autocomplete(const std::string& prefix, int maxResults = 10) const;
void serialize(const std::string& filename) const;
void deserialize(const std::string& filename);
size_t getNodeCount() const;
size_t getWordCount() const;
private:
std::unique_ptr<TrieNode> root;
size_t wordCount = 0;
void collectWords(const TrieNode* node, const std::string& currentWord,
std::vector<std::pair<std::string, int>>& results, int maxResults) const;
void serializeNode(const TrieNode* node, std::ofstream& out) const;
std::unique_ptr<TrieNode> deserializeNode(std::ifstream& in);
size_t countNodes(const TrieNode* node) const;
};What does this header declare?
This declares the public interface and private internals of the RadixTree. The public methods are what external code (the spell checker) will call.
The private section holds the root node (a unique_ptr for automatic memory management), a word counter, and helper functions for recursion and serialization. Serialize and deserialize are declared here but implemented in a later step.
- Save include/radix_tree.h.
✔️ Awesome, I've got everything!
Great. Make sure you've saved the file before moving on.
ⓧ I'd like to double check the full code
#pragma once
#include "trie_node.h"
#include <string>
#include <vector>
#include <utility>
#include <fstream>
class RadixTree {
public:
RadixTree();
void insert(const std::string& word, int frequency = 1);
bool search(const std::string& word) const;
bool startsWith(const std::string& prefix) const;
void remove(const std::string& word);
std::vector<std::pair<std::string, int>> autocomplete(const std::string& prefix, int maxResults = 10) const;
void serialize(const std::string& filename) const;
void deserialize(const std::string& filename);
size_t getNodeCount() const;
size_t getWordCount() const;
private:
std::unique_ptr<TrieNode> root;
size_t wordCount = 0;
void collectWords(const TrieNode* node, const std::string& currentWord,
std::vector<std::pair<std::string, int>>& results, int maxResults) const;
void serializeNode(const TrieNode* node, std::ofstream& out) const;
std::unique_ptr<TrieNode> deserializeNode(std::ifstream& in);
size_t countNodes(const TrieNode* node) const;
};Now for the implementation. The insert method is the heart of the compressed trie. When a new word shares a partial prefix with an existing edge, the method splits that edge into two: the shared part and the remainder.
- Create a new file called radix_tree.cpp inside your src/ folder and paste the constructor and insert method:
#include "radix_tree.h"
#include <algorithm>
#include <queue>
RadixTree::RadixTree() : root(std::make_unique<TrieNode>()) {}
void RadixTree::insert(const std::string& word, int frequency) {
TrieNode* current = root.get();
std::string remaining = word;
while (!remaining.empty()) {
bool found = false;
for (auto& [key, child] : current->children) {
const std::string& label = child->edgeLabel;
size_t commonLen = 0;
while (commonLen < label.size() && commonLen < remaining.size()
&& label[commonLen] == remaining[commonLen]) {
commonLen++;
}
if (commonLen == 0) continue;
found = true;
if (commonLen == label.size() && commonLen == remaining.size()) {
// Exact match: word already exists as an edge
child->isEndOfWord = true;
child->frequency = frequency;
return;
}
if (commonLen == label.size()) {
// Full edge consumed, continue down the tree
remaining = remaining.substr(commonLen);
current = child.get();
break;
}
// Partial match: split the node
auto newChild = std::make_unique<TrieNode>(label.substr(commonLen));
newChild->isEndOfWord = child->isEndOfWord;
newChild->frequency = child->frequency;
newChild->children = std::move(child->children);
child->edgeLabel = label.substr(0, commonLen);
child->isEndOfWord = false;
child->frequency = 0;
child->children.clear();
child->children[label[commonLen]] = std::move(newChild);
if (commonLen == remaining.size()) {
// The word ends at the split point
child->isEndOfWord = true;
child->frequency = frequency;
return;
}
remaining = remaining.substr(commonLen);
current = child.get();
break;
}
if (!found) {
// No matching edge: create a new leaf
auto newNode = std::make_unique<TrieNode>(remaining);
newNode->isEndOfWord = true;
newNode->frequency = frequency;
current->children[remaining[0]] = std::move(newNode);
wordCount++;
return;
}
}
wordCount++;
}How does node splitting work?
Imagine the trie has an edge labeled "testing" and you insert "test". The common prefix is "test" (length 4), so the method splits the edge into "test" and "ing".
The original node keeps "test" as its edge and gets marked as end-of-word. A new child carries "ing" and inherits the original node's children and end-of-word status. This compression means "testing", "test", and "tester" share the "test" prefix in a single edge rather than four separate character nodes.
You won't see a change yet. Next, add the read operations below the insert method.
- In src/radix_tree.cpp, add the search, startsWith, and remove methods below the insert method:
bool RadixTree::search(const std::string& word) const {
const TrieNode* current = root.get();
std::string remaining = word;
while (!remaining.empty()) {
bool found = false;
for (const auto& [key, child] : current->children) {
const std::string& label = child->edgeLabel;
if (remaining.size() >= label.size() &&
remaining.substr(0, label.size()) == label) {
remaining = remaining.substr(label.size());
current = child.get();
found = true;
break;
}
}
if (!found) return false;
}
return current->isEndOfWord;
}
bool RadixTree::startsWith(const std::string& prefix) const {
const TrieNode* current = root.get();
std::string remaining = prefix;
while (!remaining.empty()) {
bool found = false;
for (const auto& [key, child] : current->children) {
const std::string& label = child->edgeLabel;
size_t commonLen = 0;
while (commonLen < label.size() && commonLen < remaining.size()
&& label[commonLen] == remaining[commonLen]) {
commonLen++;
}
if (commonLen == 0) continue;
if (commonLen == remaining.size()) return true;
if (commonLen == label.size()) {
remaining = remaining.substr(commonLen);
current = child.get();
found = true;
break;
}
return false;
}
if (!found) return false;
}
return true;
}
void RadixTree::remove(const std::string& word) {
// Simplified removal: mark as not end of word
TrieNode* current = root.get();
std::string remaining = word;
while (!remaining.empty()) {
bool found = false;
for (auto& [key, child] : current->children) {
const std::string& label = child->edgeLabel;
if (remaining.size() >= label.size() &&
remaining.substr(0, label.size()) == label) {
remaining = remaining.substr(label.size());
current = child.get();
found = true;
break;
}
}
if (!found) return;
}
if (current->isEndOfWord) {
current->isEndOfWord = false;
wordCount--;
}
}What do these methods do?
- search walks down the tree consuming full edge labels. It returns true only if the traversal lands on a node marked as end-of-word.
- startsWith is more lenient. It allows partial edge matches because a prefix can end partway through an edge label.
- remove uses simplified "lazy deletion" by clearing the isEndOfWord flag. The node stays in memory but the word is no longer recognized.
- Save src/radix_tree.cpp.
You won't be able to compile yet because the header declares methods (autocomplete, serialize, etc.) that don't have implementations. You'll add those next.
Add prefix-based autocomplete using DFS
Autocomplete is one of the trie's killer features. Given a prefix like "pro", it finds all words that start with those characters and ranks them by frequency.
- In src/radix_tree.cpp, add the autocomplete method, helper functions, and stub implementations below the remove method:
std::vector<std::pair<std::string, int>> RadixTree::autocomplete(
const std::string& prefix, int maxResults) const {
const TrieNode* current = root.get();
std::string remaining = prefix;
std::string builtPrefix;
while (!remaining.empty()) {
bool found = false;
for (const auto& [key, child] : current->children) {
const std::string& label = child->edgeLabel;
size_t commonLen = 0;
while (commonLen < label.size() && commonLen < remaining.size()
&& label[commonLen] == remaining[commonLen]) {
commonLen++;
}
if (commonLen == 0) continue;
found = true;
if (commonLen == remaining.size()) {
// Prefix consumed partway through an edge
builtPrefix = prefix + label.substr(commonLen);
current = child.get();
remaining = "";
break;
}
if (commonLen == label.size()) {
// Full edge consumed, keep traversing
builtPrefix += label;
remaining = remaining.substr(commonLen);
current = child.get();
break;
}
return {};
}
if (!found) return {};
}
std::vector<std::pair<std::string, int>> results;
if (builtPrefix.empty()) builtPrefix = prefix;
collectWords(current, builtPrefix, results, maxResults);
// Sort by frequency (highest first)
std::sort(results.begin(), results.end(),
[](const auto& a, const auto& b) { return a.second > b.second; });
if (static_cast<int>(results.size()) > maxResults) {
results.resize(maxResults);
}
return results;
}
void RadixTree::collectWords(const TrieNode* node, const std::string& currentWord,
std::vector<std::pair<std::string, int>>& results, int maxResults) const {
if (node->isEndOfWord) {
results.emplace_back(currentWord, node->frequency);
}
for (const auto& [key, child] : node->children) {
if (static_cast<int>(results.size()) >= maxResults * 2) return;
collectWords(child.get(), currentWord + child->edgeLabel, results, maxResults);
}
}
size_t RadixTree::getNodeCount() const {
return countNodes(root.get());
}
size_t RadixTree::countNodes(const TrieNode* node) const {
size_t count = 1;
for (const auto& [key, child] : node->children) {
count += countNodes(child.get());
}
return count;
}
size_t RadixTree::getWordCount() const {
return wordCount;
}
// Stubs for serialization (implemented in a later step)
void RadixTree::serialize(const std::string& filename) const {}
void RadixTree::deserialize(const std::string& filename) {}
std::unique_ptr<TrieNode> RadixTree::deserializeNode(std::ifstream& in) { return nullptr; }
void RadixTree::serializeNode(const TrieNode* node, std::ofstream& out) const {}What does autocomplete do?
The autocomplete method first navigates to the node matching the prefix (similar to startsWith). From there, collectWords performs a depth-first traversal, accumulating every word it finds.
Results are sorted by frequency so the most common words appear first. The maxResults * 2 early exit in collectWords is a performance optimization. It collects more candidates than needed, sorts them, then trims to the requested count.
- Save src/radix_tree.cpp.
- Compile the project by running:
make- You should see the compiler process your files with no errors. The linker will fail because there's no main() function yet, but that confirms all your code compiles cleanly.
Seeing compile errors?
- If you see fatal error: 'radix_tree.h' file not found, make sure your Makefile has -Iinclude in the CXXFLAGS line.
- If you see errors about unique_ptr or structured bindings, confirm your CXXFLAGS includes -std=c++17.
- If you see undefined reference errors for methods, double check every method declared in radix_tree.h has at least a stub in radix_tree.cpp.
Help me fix my RadixTree compile errors.
✔️ Awesome, I've got everything!
Great. Double check you've saved all three files before moving on.
ⓧ I'd like to double check the full code
#include "radix_tree.h"
#include <algorithm>
#include <queue>
RadixTree::RadixTree() : root(std::make_unique<TrieNode>()) {}
void RadixTree::insert(const std::string& word, int frequency) {
TrieNode* current = root.get();
std::string remaining = word;
while (!remaining.empty()) {
bool found = false;
for (auto& [key, child] : current->children) {
const std::string& label = child->edgeLabel;
size_t commonLen = 0;
while (commonLen < label.size() && commonLen < remaining.size()
&& label[commonLen] == remaining[commonLen]) {
commonLen++;
}
if (commonLen == 0) continue;
found = true;
if (commonLen == label.size() && commonLen == remaining.size()) {
child->isEndOfWord = true;
child->frequency = frequency;
return;
}
if (commonLen == label.size()) {
remaining = remaining.substr(commonLen);
current = child.get();
break;
}
auto newChild = std::make_unique<TrieNode>(label.substr(commonLen));
newChild->isEndOfWord = child->isEndOfWord;
newChild->frequency = child->frequency;
newChild->children = std::move(child->children);
child->edgeLabel = label.substr(0, commonLen);
child->isEndOfWord = false;
child->frequency = 0;
child->children.clear();
child->children[label[commonLen]] = std::move(newChild);
if (commonLen == remaining.size()) {
child->isEndOfWord = true;
child->frequency = frequency;
return;
}
remaining = remaining.substr(commonLen);
current = child.get();
break;
}
if (!found) {
auto newNode = std::make_unique<TrieNode>(remaining);
newNode->isEndOfWord = true;
newNode->frequency = frequency;
current->children[remaining[0]] = std::move(newNode);
wordCount++;
return;
}
}
wordCount++;
}
bool RadixTree::search(const std::string& word) const {
const TrieNode* current = root.get();
std::string remaining = word;
while (!remaining.empty()) {
bool found = false;
for (const auto& [key, child] : current->children) {
const std::string& label = child->edgeLabel;
if (remaining.size() >= label.size() &&
remaining.substr(0, label.size()) == label) {
remaining = remaining.substr(label.size());
current = child.get();
found = true;
break;
}
}
if (!found) return false;
}
return current->isEndOfWord;
}
bool RadixTree::startsWith(const std::string& prefix) const {
const TrieNode* current = root.get();
std::string remaining = prefix;
while (!remaining.empty()) {
bool found = false;
for (const auto& [key, child] : current->children) {
const std::string& label = child->edgeLabel;
size_t commonLen = 0;
while (commonLen < label.size() && commonLen < remaining.size()
&& label[commonLen] == remaining[commonLen]) {
commonLen++;
}
if (commonLen == 0) continue;
if (commonLen == remaining.size()) return true;
if (commonLen == label.size()) {
remaining = remaining.substr(commonLen);
current = child.get();
found = true;
break;
}
return false;
}
if (!found) return false;
}
return true;
}
void RadixTree::remove(const std::string& word) {
TrieNode* current = root.get();
std::string remaining = word;
while (!remaining.empty()) {
bool found = false;
for (auto& [key, child] : current->children) {
const std::string& label = child->edgeLabel;
if (remaining.size() >= label.size() &&
remaining.substr(0, label.size()) == label) {
remaining = remaining.substr(label.size());
current = child.get();
found = true;
break;
}
}
if (!found) return;
}
if (current->isEndOfWord) {
current->isEndOfWord = false;
wordCount--;
}
}
std::vector<std::pair<std::string, int>> RadixTree::autocomplete(
const std::string& prefix, int maxResults) const {
const TrieNode* current = root.get();
std::string remaining = prefix;
std::string builtPrefix;
while (!remaining.empty()) {
bool found = false;
for (const auto& [key, child] : current->children) {
const std::string& label = child->edgeLabel;
size_t commonLen = 0;
while (commonLen < label.size() && commonLen < remaining.size()
&& label[commonLen] == remaining[commonLen]) {
commonLen++;
}
if (commonLen == 0) continue;
found = true;
if (commonLen == remaining.size()) {
builtPrefix = prefix + label.substr(commonLen);
current = child.get();
remaining = "";
break;
}
if (commonLen == label.size()) {
builtPrefix += label;
remaining = remaining.substr(commonLen);
current = child.get();
break;
}
return {};
}
if (!found) return {};
}
std::vector<std::pair<std::string, int>> results;
if (builtPrefix.empty()) builtPrefix = prefix;
collectWords(current, builtPrefix, results, maxResults);
std::sort(results.begin(), results.end(),
[](const auto& a, const auto& b) { return a.second > b.second; });
if (static_cast<int>(results.size()) > maxResults) {
results.resize(maxResults);
}
return results;
}
void RadixTree::collectWords(const TrieNode* node, const std::string& currentWord,
std::vector<std::pair<std::string, int>>& results, int maxResults) const {
if (node->isEndOfWord) {
results.emplace_back(currentWord, node->frequency);
}
for (const auto& [key, child] : node->children) {
if (static_cast<int>(results.size()) >= maxResults * 2) return;
collectWords(child.get(), currentWord + child->edgeLabel, results, maxResults);
}
}
size_t RadixTree::getNodeCount() const {
return countNodes(root.get());
}
size_t RadixTree::countNodes(const TrieNode* node) const {
size_t count = 1;
for (const auto& [key, child] : node->children) {
count += countNodes(child.get());
}
return count;
}
size_t RadixTree::getWordCount() const {
return wordCount;
}
void RadixTree::serialize(const std::string& filename) const {}
void RadixTree::deserialize(const std::string& filename) {}
std::unique_ptr<TrieNode> RadixTree::deserializeNode(std::ifstream& in) { return nullptr; }
void RadixTree::serializeNode(const TrieNode* node, std::ofstream& out) const {}Your compressed trie is fully operational. Next up, you'll implement the Damerau-Levenshtein distance algorithm that powers the spell checker's ability to find corrections for misspelled words.
Implement the Damerau-Levenshtein Distance Algorithm
Your Radix Tree can store and look up words efficiently, but a spell checker needs to answer a harder question: given a misspelled word, which correctly spelled words are closest to it?
The answer lives in a metric called edit distance. In this step you will implement the Damerau-Levenshtein algorithm, which measures how many single-character operations (insertions, deletions, substitutions, and transpositions) separate two strings.
In this step, get ready to:
- Implement the full Damerau-Levenshtein algorithm using dynamic programming.
- Optimize with a diagonal-band early exit that prunes computation when max distance is exceeded.
- Write unit tests validating known edit distances.
Create the edit distance header file
The Damerau-Levenshtein algorithm extends the classic Levenshtein distance by recognizing transpositions (swapping two adjacent characters) as a single edit. This means "teh" to "the" costs 1 edit instead of 2.
- Create a new file include/edit_distance.h in Cursor and add the following class declaration:
#pragma once
#include <string>
#include <vector>
#include <algorithm>
class EditDistance {
public:
// Computes full Damerau-Levenshtein distance between two strings
static int damerauLevenshtein(const std::string& source, const std::string& target, int maxDistance = -1);
// Computes a single DP row for trie traversal (used in fuzzy search)
static std::vector<int> computeRow(const std::string& target, const std::vector<int>& prevRow,
const std::vector<int>& prevPrevRow, char currentChar, char prevChar);
};What does this header declare?
The EditDistance class exposes two static methods.
- damerauLevenshtein takes two strings and an optional max distance cap. When maxDistance is set, the algorithm can exit early if it detects the result will exceed that threshold.
- computeRow computes one row of the DP matrix given the previous rows. You will use this in Step 5 when traversing the Radix Tree with a running DP state.
- Save include/edit_distance.h.
Implement the core algorithm with diagonal-band optimization
The algorithm fills a 2D matrix where each cell represents the minimum edits to transform one substring into another. The diagonal-band optimization tracks the minimum value in each row and exits early if it exceeds the maximum allowed distance.
- Create a new file src/edit_distance.cpp and add the damerauLevenshtein implementation:
#include "edit_distance.h"
#include <climits>
int EditDistance::damerauLevenshtein(const std::string& source, const std::string& target, int maxDistance) {
int n = static_cast<int>(source.size());
int m = static_cast<int>(target.size());
// Quick rejection: if length difference alone exceeds max, no need to compute
if (maxDistance >= 0 && std::abs(n - m) > maxDistance) return maxDistance + 1;
if (n == 0) return m;
if (m == 0) return n;
// Build the full DP matrix
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
// Base cases: transforming from/to empty string
for (int i = 0; i <= n; i++) dp[i][0] = i;
for (int j = 0; j <= m; j++) dp[0][j] = j;
for (int i = 1; i <= n; i++) {
int colMin = INT_MAX; // Track row minimum for early exit
for (int j = 1; j <= m; j++) {
int cost = (source[i - 1] == target[j - 1]) ? 0 : 1;
dp[i][j] = std::min({
dp[i - 1][j] + 1,
dp[i][j - 1] + 1,
dp[i - 1][j - 1] + cost
});
// Transposition: swap of two adjacent characters
if (i > 1 && j > 1 &&
source[i - 1] == target[j - 2] &&
source[i - 2] == target[j - 1]) {
dp[i][j] = std::min(dp[i][j], dp[i - 2][j - 2] + cost);
}
colMin = std::min(colMin, dp[i][j]);
}
// Diagonal-band pruning: if minimum in this row exceeds max, bail out
if (maxDistance >= 0 && colMin > maxDistance) return maxDistance + 1;
}
return dp[n][m];
}What does this code do?
The DP matrix has dimensions (n+1) x (m+1) where n and m are the lengths of source and target. Each cell dp[i][j] holds the minimum edits to transform source[0..i-1] into target[0..j-1].
- dp[i-1][j] + 1 represents a deletion from the source.
- dp[i][j-1] + 1 represents an insertion into the source.
- dp[i-1][j-1] + cost represents a substitution (cost is 0 if characters match).
- dp[i-2][j-2] + cost represents a transposition of two adjacent characters. This is what Damerau adds over plain Levenshtein.
- colMin tracks the smallest value across the entire row. If that minimum already exceeds maxDistance, every subsequent row will be even larger, so the function returns early.
Why is the early exit called diagonal-band pruning?
In bounded edit distance queries, only cells within a diagonal band of width 2*maxDistance+1 can hold values at or below the threshold. Tracking the row minimum and bailing out when it exceeds the limit avoids computing rows that cannot contribute a valid result.
- Now add the computeRow method below the damerauLevenshtein function in the same file:
std::vector<int> EditDistance::computeRow(const std::string& target, const std::vector<int>& prevRow,
const std::vector<int>& prevPrevRow, char currentChar, char prevChar) {
int m = static_cast<int>(target.size());
std::vector<int> currentRow(m + 1);
currentRow[0] = prevRow[0] + 1;
for (int j = 1; j <= m; j++) {
int cost = (currentChar == target[j - 1]) ? 0 : 1;
currentRow[j] = std::min({
prevRow[j] + 1,
currentRow[j - 1] + 1,
prevRow[j - 1] + cost
});
// Transposition check using the row two steps back
if (!prevPrevRow.empty() && j > 1 &&
currentChar == target[j - 2] && prevChar == target[j - 1]) {
currentRow[j] = std::min(currentRow[j], prevPrevRow[j - 2] + cost);
}
}
return currentRow;
}Why a separate computeRow method?
When you integrate edit distance with trie traversal in Step 5, you will walk down the tree one character at a time. Instead of computing the full matrix for every candidate word, you carry a DP row forward as you descend. This method computes exactly one new row given the previous state.
If the minimum value in the returned row exceeds your distance threshold, you can prune the entire subtree. This is what makes fuzzy search over 466,000+ words feasible in milliseconds.
- Save src/edit_distance.cpp.
- Confirm the project still compiles by running:
make clean && makeYou should see the build succeed with no errors.
Seeing a compile error?
- If you see fatal error: 'climits' file not found, make sure your Makefile uses -std=c++17 in the CXXFLAGS.
- If you see a linker error about undefined reference to EditDistance, check that your Makefile's SOURCES wildcard picks up src/edit_distance.cpp. Run ls src/ to verify the file exists in the right directory.
Help me debug my edit distance compilation error
✔️ Awesome, I've got everything!
Great. Double check you have saved both files before moving on.
ⓧ I'd like to double check the full code
Here is the complete include/edit_distance.h:
#pragma once
#include <string>
#include <vector>
#include <algorithm>
class EditDistance {
public:
static int damerauLevenshtein(const std::string& source, const std::string& target, int maxDistance = -1);
static std::vector<int> computeRow(const std::string& target, const std::vector<int>& prevRow,
const std::vector<int>& prevPrevRow, char currentChar, char prevChar);
};Here is the complete src/edit_distance.cpp:
#include "edit_distance.h"
#include <climits>
int EditDistance::damerauLevenshtein(const std::string& source, const std::string& target, int maxDistance) {
int n = static_cast<int>(source.size());
int m = static_cast<int>(target.size());
if (maxDistance >= 0 && std::abs(n - m) > maxDistance) return maxDistance + 1;
if (n == 0) return m;
if (m == 0) return n;
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
for (int i = 0; i <= n; i++) dp[i][0] = i;
for (int j = 0; j <= m; j++) dp[0][j] = j;
for (int i = 1; i <= n; i++) {
int colMin = INT_MAX;
for (int j = 1; j <= m; j++) {
int cost = (source[i - 1] == target[j - 1]) ? 0 : 1;
dp[i][j] = std::min({
dp[i - 1][j] + 1,
dp[i][j - 1] + 1,
dp[i - 1][j - 1] + cost
});
if (i > 1 && j > 1 &&
source[i - 1] == target[j - 2] &&
source[i - 2] == target[j - 1]) {
dp[i][j] = std::min(dp[i][j], dp[i - 2][j - 2] + cost);
}
colMin = std::min(colMin, dp[i][j]);
}
if (maxDistance >= 0 && colMin > maxDistance) return maxDistance + 1;
}
return dp[n][m];
}
std::vector<int> EditDistance::computeRow(const std::string& target, const std::vector<int>& prevRow,
const std::vector<int>& prevPrevRow, char currentChar, char prevChar) {
int m = static_cast<int>(target.size());
std::vector<int> currentRow(m + 1);
currentRow[0] = prevRow[0] + 1;
for (int j = 1; j <= m; j++) {
int cost = (currentChar == target[j - 1]) ? 0 : 1;
currentRow[j] = std::min({
prevRow[j] + 1,
currentRow[j - 1] + 1,
prevRow[j - 1] + cost
});
if (!prevPrevRow.empty() && j > 1 &&
currentChar == target[j - 2] && prevChar == target[j - 1]) {
currentRow[j] = std::min(currentRow[j], prevPrevRow[j - 2] + cost);
}
}
return currentRow;
}Write unit tests for known edit distances
You need to confirm the algorithm produces correct results for known cases. The classic example is "kitten" to "sitting" which requires 3 edits (substitute k with s, substitute e with i, insert g).
- Create a new file tests/test_edit_distance.cpp and add the following test cases:
#include "edit_distance.h"
#include <iostream>
#include <cassert>
void testBasicDistances() {
// Identical strings have distance 0
assert(EditDistance::damerauLevenshtein("hello", "hello") == 0);
// Single insertion
assert(EditDistance::damerauLevenshtein("cat", "cats") == 1);
// Single deletion
assert(EditDistance::damerauLevenshtein("cats", "cat") == 1);
// Single substitution
assert(EditDistance::damerauLevenshtein("cat", "car") == 1);
// Single transposition (Damerau's addition)
assert(EditDistance::damerauLevenshtein("ab", "ba") == 1);
// Classic example: kitten -> sitting = 3
assert(EditDistance::damerauLevenshtein("kitten", "sitting") == 3);
std::cout << "Basic distance tests passed!" << std::endl;
}
void testMaxDistancePruning() {
// Should return maxDistance + 1 when true distance exceeds the cap
assert(EditDistance::damerauLevenshtein("hello", "world", 1) == 2);
assert(EditDistance::damerauLevenshtein("abcdef", "xyz", 2) == 3);
// Should return correct value when within cap
assert(EditDistance::damerauLevenshtein("cat", "car", 2) == 1);
std::cout << "Max distance pruning tests passed!" << std::endl;
}
void testEmptyStrings() {
// Empty to non-empty requires insertions equal to length
assert(EditDistance::damerauLevenshtein("", "") == 0);
assert(EditDistance::damerauLevenshtein("hello", "") == 5);
assert(EditDistance::damerauLevenshtein("", "world") == 5);
std::cout << "Empty string tests passed!" << std::endl;
}
void testTranspositions() {
// Transposition should cost 1, not 2 (which plain Levenshtein would give)
assert(EditDistance::damerauLevenshtein("teh", "the") == 1);
assert(EditDistance::damerauLevenshtein("recieve", "receive") == 1);
std::cout << "Transposition tests passed!" << std::endl;
}
int main() {
testBasicDistances();
testMaxDistancePruning();
testEmptyStrings();
testTranspositions();
std::cout << "\nAll edit distance tests passed!" << std::endl;
return 0;
}What do these tests cover?
- testBasicDistances verifies each of the four edit operations and the classic "kitten" to "sitting" = 3 case.
- testMaxDistancePruning confirms the early exit returns maxDistance + 1 when the true distance exceeds the cap.
- testEmptyStrings validates the base cases where one or both strings are empty.
- testTranspositions proves that swapping adjacent characters counts as 1 edit, not 2. This is what distinguishes Damerau-Levenshtein from plain Levenshtein.
- Save tests/test_edit_distance.cpp.
- Compile and run the tests by running this command:
clang++ -std=c++17 -Iinclude tests/test_edit_distance.cpp src/edit_distance.cpp -o test_edit_distance && ./test_edit_distanceYou should see all four test groups pass with the final line reading All edit distance tests passed!.
Seeing an assertion failure?
- If the transposition test fails, make sure the transposition check uses source[i - 1] == target[j - 2] and source[i - 2] == target[j - 1]. Getting these indices backwards is a common mistake.
- If "kitten" to "sitting" returns a value other than 3, check that your cost variable is 0 when characters match and 1 when they differ.
Help me debug my Damerau-Levenshtein test failures
Your edit distance algorithm is tested and working. Next up, you will wire it into the Radix Tree to build a fuzzy search engine that finds the closest dictionary words to a misspelled input.
Build the Fuzzy Search Engine and SpellChecker
You have a Radix Tree that stores words efficiently and an edit distance algorithm that measures how different two strings are. Now you need a layer that ties them together: a spell checker that can load a dictionary, decide if a word is correct, and suggest corrections when it is not.
The core challenge is ranking suggestions intelligently. A word with an edit distance of 1 is not always the best suggestion if it is an obscure word nobody uses. In this step, you will build a SpellChecker class that combines edit distance with word frequency to produce a composite score, surfacing common words over rare ones.
In this step, get ready to:
- Create the SpellChecker header with a Suggestion struct and class interface.
- Implement dictionary loading, lookup, and autocomplete in the SpellChecker.
- Build the fuzzy suggest method that ranks corrections by edit distance and frequency.
Create the SpellChecker header
The SpellChecker needs a data structure to hold suggestion results. Each suggestion carries the candidate word, its edit distance from the misspelled input, its frequency rank, and a composite score that blends both factors.
- Create a new file called spell_checker.h inside the include/ folder.
- Add the following code to define the Suggestion struct and SpellChecker class interface:
#pragma once
#include "radix_tree.h"
#include <string>
#include <vector>
#include <utility>
// Holds a single correction suggestion with ranking data
struct Suggestion {
std::string word;
int editDistance;
int frequency;
double score;
};
class SpellChecker {
public:
SpellChecker();
// Dictionary management
void loadDictionary(const std::string& filename);
void loadBinaryDictionary(const std::string& filename);
void saveBinaryDictionary(const std::string& filename) const;
// Core spell-check operations
bool isCorrect(const std::string& word) const;
std::vector<Suggestion> suggest(const std::string& word, int maxDistance = 2, int maxSuggestions = 5) const;
std::vector<std::pair<std::string, int>> autocomplete(const std::string& prefix, int maxResults = 10) const;
size_t getDictionarySize() const;
private:
RadixTree tree;
int maxFrequency = 0;
// Fuzzy search traversal helper
void fuzzySearch(const TrieNode* node, const std::string& currentWord,
const std::string& target, const std::vector<int>& prevRow,
const std::vector<int>& prevPrevRow, char prevChar,
int maxDistance, std::vector<Suggestion>& results) const;
// Scoring: blends edit distance closeness with word frequency
double computeScore(int editDistance, int frequency) const;
std::string toLower(const std::string& word) const;
};What does this header define?
The Suggestion struct bundles everything the caller needs about a candidate correction: the word itself, how far it is from the input (edit distance), how common it is (frequency), and its final blended score.
The SpellChecker class owns a RadixTree internally and exposes a clean public API. The private fuzzySearch method is the heart of the suggestion engine, traversing the trie while tracking edit distance state.
- Save include/spell_checker.h.
Implement dictionary loading and lookup
Before you can suggest corrections, the spell checker needs to load words into its Radix Tree. The loader must handle two file formats: lines with both a word and a frequency number, and lines with just a word (where frequency is assigned by rank order).
- Create a new file called spell_checker.cpp inside the src/ folder.
- Add the includes, constructor, and dictionary loading logic by pasting this code:
#include "spell_checker.h"
#include "edit_distance.h"
#include <fstream>
#include <sstream>
#include <algorithm>
#include <cctype>
#include <iostream>
SpellChecker::SpellChecker() {}
void SpellChecker::loadDictionary(const std::string& filename) {
std::ifstream file(filename);
if (!file.is_open()) {
std::cerr << "Error: Cannot open dictionary file: " << filename << std::endl;
return;
}
std::string line;
int rank = 0;
while (std::getline(file, line)) {
if (line.empty()) continue;
std::string word;
int freq = 0;
// Support "word frequency" or just "word" format
std::istringstream iss(line);
iss >> word >> freq;
if (freq == 0) freq = 100000 - rank;
word = toLower(word);
if (!word.empty() && std::all_of(word.begin(), word.end(), ::isalpha)) {
tree.insert(word, freq);
maxFrequency = std::max(maxFrequency, freq);
rank++;
}
}
}What does this code do?
- loadDictionary reads each line from the dictionary file. If a line has both a word and a number, it uses the number as the frequency. Otherwise it assigns frequency based on rank (earlier lines get higher frequency).
- Every word is lowercased and filtered to alphabetic characters only before insertion into the Radix Tree.
- maxFrequency tracks the highest frequency seen. This is used later to normalize frequency scores between 0.0 and 1.0.
- Now add the binary dictionary helpers, the lookup method, autocomplete, and the toLower utility below the loadDictionary function:
void SpellChecker::loadBinaryDictionary(const std::string& filename) {
tree.deserialize(filename);
}
void SpellChecker::saveBinaryDictionary(const std::string& filename) const {
tree.serialize(filename);
}
bool SpellChecker::isCorrect(const std::string& word) const {
return tree.search(toLower(word));
}
std::vector<std::pair<std::string, int>> SpellChecker::autocomplete(
const std::string& prefix, int maxResults) const {
return tree.autocomplete(toLower(prefix), maxResults);
}
size_t SpellChecker::getDictionarySize() const {
return tree.getWordCount();
}
std::string SpellChecker::toLower(const std::string& word) const {
std::string result = word;
std::transform(result.begin(), result.end(), result.begin(),
[](unsigned char c) { return std::tolower(c); });
return result;
}What does this code do?
- isCorrect converts the input to lowercase and checks if it exists in the tree. This makes lookups case-insensitive.
- autocomplete delegates directly to the Radix Tree's prefix search, giving you word completions ranked by frequency.
- The binary dictionary methods use the serialization you built in a prior step. They let the spell checker skip text parsing when a binary cache is available.
- Save src/spell_checker.cpp.
Seeing a compile error about missing includes?
Make sure you included <sstream> for std::istringstream and <cctype> for ::isalpha. Both are required at the top of the file.
Help me debug a compile error in spell_checker.cpp
Implement the fuzzy suggest method with scoring
The suggest method is where the real magic happens. Given a misspelled word, it needs to find all dictionary words within a given edit distance, then rank them by a composite score that weighs both closeness (low edit distance) and popularity (high frequency).
- In src/spell_checker.cpp, add the suggest method and the computeScore helper between the isCorrect method and the autocomplete method:
std::vector<Suggestion> SpellChecker::suggest(const std::string& word, int maxDistance, int maxSuggestions) const {
std::string lowerWord = toLower(word);
std::vector<Suggestion> results;
// Collect candidate words from the tree and filter by edit distance
auto allWords = tree.autocomplete("", 50000);
for (const auto& [candidate, freq] : allWords) {
int dist = EditDistance::damerauLevenshtein(lowerWord, candidate, maxDistance);
if (dist <= maxDistance) {
results.push_back({candidate, dist, freq, computeScore(dist, freq)});
}
}
// Sort by composite score (highest first)
std::sort(results.begin(), results.end(),
[](const Suggestion& a, const Suggestion& b) {
return a.score > b.score;
});
if (static_cast<int>(results.size()) > maxSuggestions) {
results.resize(maxSuggestions);
}
return results;
}
double SpellChecker::computeScore(int editDistance, int frequency) const {
// Distance score: closer words score higher (inverse relationship)
double distScore = 1.0 / (1.0 + editDistance);
// Frequency score: normalized to 0.0-1.0 range
double freqScore = (maxFrequency > 0) ? static_cast<double>(frequency) / maxFrequency : 0.0;
// Weighted blend: 60% distance, 40% frequency
return 0.6 * distScore + 0.4 * freqScore;
}How does the scoring work?
The computeScore function produces a value between 0.0 and 1.0 by blending two signals. The distance score uses 1.0 / (1.0 + editDistance) so that a distance of 0 scores 1.0, distance 1 scores 0.5, and distance 2 scores 0.33.
The frequency score normalizes each word's frequency against the maximum in the dictionary. The final blend weighs distance at 60% and frequency at 40%. This means a common word at distance 2 can beat a rare word at distance 1.
- Save src/spell_checker.cpp.
- Compile the project by running:
makeYou should see the compilation succeed with no errors. The build produces object files for all your source files including the new spell_checker.cpp.
Seeing linker errors about undefined references?
If you see errors mentioning undefined references to EditDistance::damerauLevenshtein, make sure src/edit_distance.cpp exists and is being compiled. The Makefile's wildcard should pick it up automatically.
If you see errors about RadixTree methods, confirm your #include "radix_tree.h" is present in spell_checker.h and that the header guard is #pragma once.
Help me fix linker errors in my spell checker build
Why use autocomplete to gather candidates instead of direct trie traversal?
The current suggest method uses a brute-force approach: retrieve words from the tree and compute edit distance against each one. This works correctly but checks more candidates than necessary.
The private fuzzySearch method declared in the header is designed for a more advanced approach. It traverses the trie while maintaining a running DP row, pruning entire subtrees when the minimum value exceeds the max distance. You will see this optimization pay off once you load a full 466,000+ word dictionary.
✔️ Awesome, I've got everything!
Great. Double check you have saved both include/spell_checker.h and src/spell_checker.cpp.
ⓧ I'd like to double check the full code
Here is the complete include/spell_checker.h:
#pragma once
#include "radix_tree.h"
#include <string>
#include <vector>
#include <utility>
struct Suggestion {
std::string word;
int editDistance;
int frequency;
double score;
};
class SpellChecker {
public:
SpellChecker();
void loadDictionary(const std::string& filename);
void loadBinaryDictionary(const std::string& filename);
void saveBinaryDictionary(const std::string& filename) const;
bool isCorrect(const std::string& word) const;
std::vector<Suggestion> suggest(const std::string& word, int maxDistance = 2, int maxSuggestions = 5) const;
std::vector<std::pair<std::string, int>> autocomplete(const std::string& prefix, int maxResults = 10) const;
size_t getDictionarySize() const;
private:
RadixTree tree;
int maxFrequency = 0;
void fuzzySearch(const TrieNode* node, const std::string& currentWord,
const std::string& target, const std::vector<int>& prevRow,
const std::vector<int>& prevPrevRow, char prevChar,
int maxDistance, std::vector<Suggestion>& results) const;
double computeScore(int editDistance, int frequency) const;
std::string toLower(const std::string& word) const;
};Here is the complete src/spell_checker.cpp:
#include "spell_checker.h"
#include "edit_distance.h"
#include <fstream>
#include <sstream>
#include <algorithm>
#include <cctype>
#include <iostream>
SpellChecker::SpellChecker() {}
void SpellChecker::loadDictionary(const std::string& filename) {
std::ifstream file(filename);
if (!file.is_open()) {
std::cerr << "Error: Cannot open dictionary file: " << filename << std::endl;
return;
}
std::string line;
int rank = 0;
while (std::getline(file, line)) {
if (line.empty()) continue;
std::string word;
int freq = 0;
std::istringstream iss(line);
iss >> word >> freq;
if (freq == 0) freq = 100000 - rank;
word = toLower(word);
if (!word.empty() && std::all_of(word.begin(), word.end(), ::isalpha)) {
tree.insert(word, freq);
maxFrequency = std::max(maxFrequency, freq);
rank++;
}
}
}
void SpellChecker::loadBinaryDictionary(const std::string& filename) {
tree.deserialize(filename);
}
void SpellChecker::saveBinaryDictionary(const std::string& filename) const {
tree.serialize(filename);
}
bool SpellChecker::isCorrect(const std::string& word) const {
return tree.search(toLower(word));
}
std::vector<Suggestion> SpellChecker::suggest(const std::string& word, int maxDistance, int maxSuggestions) const {
std::string lowerWord = toLower(word);
std::vector<Suggestion> results;
auto allWords = tree.autocomplete("", 50000);
for (const auto& [candidate, freq] : allWords) {
int dist = EditDistance::damerauLevenshtein(lowerWord, candidate, maxDistance);
if (dist <= maxDistance) {
results.push_back({candidate, dist, freq, computeScore(dist, freq)});
}
}
std::sort(results.begin(), results.end(),
[](const Suggestion& a, const Suggestion& b) {
return a.score > b.score;
});
if (static_cast<int>(results.size()) > maxSuggestions) {
results.resize(maxSuggestions);
}
return results;
}
std::vector<std::pair<std::string, int>> SpellChecker::autocomplete(
const std::string& prefix, int maxResults) const {
return tree.autocomplete(toLower(prefix), maxResults);
}
size_t SpellChecker::getDictionarySize() const {
return tree.getWordCount();
}
double SpellChecker::computeScore(int editDistance, int frequency) const {
double distScore = 1.0 / (1.0 + editDistance);
double freqScore = (maxFrequency > 0) ? static_cast<double>(frequency) / maxFrequency : 0.0;
return 0.6 * distScore + 0.4 * freqScore;
}
std::string SpellChecker::toLower(const std::string& word) const {
std::string result = word;
std::transform(result.begin(), result.end(), result.begin(),
[](unsigned char c) { return std::tolower(c); });
return result;
}Your spell checker engine now has a complete public API. It can load dictionaries, verify words, suggest corrections ranked by a blend of edit distance and frequency, and provide autocomplete results. Next up, you will feed it a real English dictionary with hundreds of thousands of words and see it handle real-world misspellings.
Load the Dictionary and Implement Binary Serialization
Your Radix Tree can insert, search, and autocomplete. Your edit distance algorithm can measure how far apart two words are. Now you need real data to bring these pieces to life.
In this step, you will download a 466,000+ word English dictionary, implement binary serialization so the trie can be saved and reloaded instantly, and verify that binary loading is measurably faster than re-parsing text every time.
In this step, get ready to:
- Download a real English dictionary into your project.
- Implement binary serialization and deserialization for the Radix Tree.
- Compare text-loading vs binary-loading speed.
Download the English words dictionary
The spell checker needs a large word list to be useful. You will use the dwyl/english-words dataset, which provides 466,000+ alphabetic English words in a simple one-word-per-line text file.
- Download words_alpha.txt into your data/ folder by running this command:
curl -o data/words_alpha.txt https://raw.githubusercontent.com/dwyl/english-words/master/words_alpha.txt- Confirm the download succeeded by running:
wc -l data/words_alpha.txt- You should see a number around 370,000 or higher (the exact count depends on the version of the file).
Why words_alpha.txt?
This file contains only alphabetic words (no numbers or symbols). That makes parsing straightforward because you can trust every line is a pure letter sequence.
The file is licensed under The Unlicense, which means it is public domain and free to use in any project.
Download failed or 0 bytes?
Make sure you are running the command from your project root (the folder containing Makefile). The data/ folder must already exist.
If curl is not found, you can also download the file manually from the GitHub repository and place it in data/words_alpha.txt.
Having trouble downloading?
Implement binary serialization and deserialization
Parsing 466,000+ lines of text on every startup is slow. Binary serialization writes the trie structure directly to disk in a compact format that can be read back without any string parsing.
Your src/radix_tree.cpp currently has empty stubs for the serialization methods. You will replace all four stubs with full implementations.
- In src/radix_tree.cpp, scroll to the bottom of the file and find these four stub functions:
void RadixTree::serialize(const std::string& filename) const {}
void RadixTree::deserialize(const std::string& filename) {}
std::unique_ptr<TrieNode> RadixTree::deserializeNode(std::ifstream& in) { return nullptr; }
void RadixTree::serializeNode(const TrieNode* node, std::ofstream& out) const {}- Delete all four stub functions and replace them with the following serialization code:
void RadixTree::serialize(const std::string& filename) const {
std::ofstream out(filename, std::ios::binary);
serializeNode(root.get(), out);
}
void RadixTree::serializeNode(const TrieNode* node, std::ofstream& out) const {
// Write flags byte (bit 0 = isEndOfWord)
uint8_t flags = (node->isEndOfWord ? 1 : 0);
out.write(reinterpret_cast<const char*>(&flags), 1);
// Write frequency as 4-byte integer
int32_t freq = node->frequency;
out.write(reinterpret_cast<const char*>(&freq), sizeof(freq));
// Write edge label: 2-byte length prefix, then the label bytes
uint16_t labelLen = static_cast<uint16_t>(node->edgeLabel.size());
out.write(reinterpret_cast<const char*>(&labelLen), sizeof(labelLen));
out.write(node->edgeLabel.data(), labelLen);
// Write child count, then each child (key char + recursive node)
uint16_t childCount = static_cast<uint16_t>(node->children.size());
out.write(reinterpret_cast<const char*>(&childCount), sizeof(childCount));
for (const auto& [key, child] : node->children) {
out.write(&key, 1);
serializeNode(child.get(), out);
}
}What does this code do?
The binary format writes each node as a fixed sequence: a 1-byte flags field, a 4-byte frequency, a 2-byte label length followed by the label string, and a 2-byte child count. Each child is stored as a 1-byte key character followed by the recursive child node.
This pre-order traversal writes the entire tree depth-first. Because lengths are encoded before variable-length data, the reader knows exactly how many bytes to consume at each step.
- Immediately below the serialization code, add the deserialization implementation:
void RadixTree::deserialize(const std::string& filename) {
std::ifstream in(filename, std::ios::binary);
root = deserializeNode(in);
wordCount = getWordCount();
}
std::unique_ptr<TrieNode> RadixTree::deserializeNode(std::ifstream& in) {
auto node = std::make_unique<TrieNode>();
// Read flags byte
uint8_t flags;
in.read(reinterpret_cast<char*>(&flags), 1);
node->isEndOfWord = (flags & 1);
// Read frequency
int32_t freq;
in.read(reinterpret_cast<char*>(&freq), sizeof(freq));
node->frequency = freq;
// Read edge label
uint16_t labelLen;
in.read(reinterpret_cast<char*>(&labelLen), sizeof(labelLen));
node->edgeLabel.resize(labelLen);
in.read(node->edgeLabel.data(), labelLen);
// Read children
uint16_t childCount;
in.read(reinterpret_cast<char*>(&childCount), sizeof(childCount));
for (uint16_t i = 0; i < childCount; i++) {
char key;
in.read(&key, 1);
node->children[key] = deserializeNode(in);
}
return node;
}What does this code do?
Deserialization mirrors serialization exactly. It reads the same byte sequence in the same order, reconstructing each node and recursively building the tree. Because the format is self-describing (lengths precede variable data), no additional parsing logic is needed.
After the tree is fully reconstructed, wordCount = getWordCount() re-computes the count by traversing the tree. This ensures the count stays consistent even if the binary file was created by a different version of the code.
- Save src/radix_tree.cpp.
- Compile the project by running:
make- You should see the compilation succeed with no errors.
Compilation errors?
If you see an error about a redefined function, make sure you deleted the old stub lines completely. There should be no duplicate function signatures.
If you see a type error on uint8_t or uint16_t, confirm that #include <fstream> is present in include/radix_tree.h (it pulls in the standard integer types through the library headers).
Help me fix my serialization compile errors.
Test the dictionary loading and binary serialization
With serialization complete and the dictionary downloaded, you can now verify the full pipeline: load from text, serialize to binary, reload from binary, and compare the speeds.
- Create a temporary test file to verify loading and serialization by running:
cat > src/main.cpp << 'EOF'
#include "spell_checker.h"
#include <iostream>
#include <chrono>
int main() {
SpellChecker checker;
// Time text loading
auto start = std::chrono::high_resolution_clock::now();
checker.loadDictionary("data/words_alpha.txt");
auto end = std::chrono::high_resolution_clock::now();
double textTime = std::chrono::duration<double, std::milli>(end - start).count();
std::cout << "Loaded " << checker.getDictionarySize() << " words from text in "
<< textTime << " ms" << std::endl;
// Verify lookups work
std::cout << "'hello' found: " << (checker.isCorrect("hello") ? "yes" : "no") << std::endl;
std::cout << "'xyzzy' found: " << (checker.isCorrect("xyzzy") ? "yes" : "no") << std::endl;
// Serialize to binary
checker.saveBinaryDictionary("data/dictionary.bin");
std::cout << "Saved binary dictionary." << std::endl;
// Time binary loading
SpellChecker checker2;
start = std::chrono::high_resolution_clock::now();
checker2.loadBinaryDictionary("data/dictionary.bin");
end = std::chrono::high_resolution_clock::now();
double binTime = std::chrono::duration<double, std::milli>(end - start).count();
std::cout << "Loaded from binary in " << binTime << " ms" << std::endl;
std::cout << "Speedup: " << (textTime / binTime) << "x faster" << std::endl;
return 0;
}
EOFWhat does this test program do?
It loads the full text dictionary and times how long it takes. Then it runs two lookups to verify the trie is populated correctly. Finally, it serializes the trie to binary, reloads it, and compares the load times.
This main.cpp is temporary. You will replace it with the full interactive CLI in the next step.
- Build and run the test by executing:
make clean && make && ./spellcheck- You should see output showing the word count, lookup results, and a binary speedup number. The binary load should be noticeably faster than the text load.
What should I see?
Your output will look something like this (exact numbers vary by machine):
Loaded 370103 words from text in 1842.31 ms
'hello' found: yes
'xyzzy' found: no
Saved binary dictionary.
Loaded from binary in 412.07 ms
Speedup: 4.47x fasterThe key signals are: a large word count (hundreds of thousands), hello found as yes, and a binary speedup greater than 1x.
Seeing 0 words loaded or a crash?
If 0 words are loaded, confirm data/words_alpha.txt exists and is non-empty. Run head data/words_alpha.txt to verify it contains one word per line.
If the binary load crashes with a segfault, check that serializeNode and deserializeNode use the same field order. The read sequence must exactly mirror the write sequence.
Help me debug my dictionary loading or serialization issue.
✔️ Awesome, I've got everything!
Great. Double check you have saved src/radix_tree.cpp and that data/dictionary.bin now exists in your project.
ⓧ I'd like to double check the full code
Here is the complete src/radix_tree.cpp as it should look at this point:
#include "radix_tree.h"
#include <algorithm>
#include <queue>
RadixTree::RadixTree() : root(std::make_unique<TrieNode>()) {}
void RadixTree::insert(const std::string& word, int frequency) {
TrieNode* current = root.get();
std::string remaining = word;
while (!remaining.empty()) {
bool found = false;
for (auto& [key, child] : current->children) {
const std::string& label = child->edgeLabel;
size_t commonLen = 0;
while (commonLen < label.size() && commonLen < remaining.size()
&& label[commonLen] == remaining[commonLen]) {
commonLen++;
}
if (commonLen == 0) continue;
found = true;
if (commonLen == label.size() && commonLen == remaining.size()) {
child->isEndOfWord = true;
child->frequency = frequency;
return;
}
if (commonLen == label.size()) {
remaining = remaining.substr(commonLen);
current = child.get();
break;
}
auto newChild = std::make_unique<TrieNode>(label.substr(commonLen));
newChild->isEndOfWord = child->isEndOfWord;
newChild->frequency = child->frequency;
newChild->children = std::move(child->children);
child->edgeLabel = label.substr(0, commonLen);
child->isEndOfWord = false;
child->frequency = 0;
child->children.clear();
child->children[label[commonLen]] = std::move(newChild);
if (commonLen == remaining.size()) {
child->isEndOfWord = true;
child->frequency = frequency;
return;
}
remaining = remaining.substr(commonLen);
current = child.get();
break;
}
if (!found) {
auto newNode = std::make_unique<TrieNode>(remaining);
newNode->isEndOfWord = true;
newNode->frequency = frequency;
current->children[remaining[0]] = std::move(newNode);
wordCount++;
return;
}
}
wordCount++;
}
bool RadixTree::search(const std::string& word) const {
const TrieNode* current = root.get();
std::string remaining = word;
while (!remaining.empty()) {
bool found = false;
for (const auto& [key, child] : current->children) {
const std::string& label = child->edgeLabel;
if (remaining.size() >= label.size() &&
remaining.substr(0, label.size()) == label) {
remaining = remaining.substr(label.size());
current = child.get();
found = true;
break;
}
}
if (!found) return false;
}
return current->isEndOfWord;
}
bool RadixTree::startsWith(const std::string& prefix) const {
const TrieNode* current = root.get();
std::string remaining = prefix;
while (!remaining.empty()) {
bool found = false;
for (const auto& [key, child] : current->children) {
const std::string& label = child->edgeLabel;
size_t commonLen = 0;
while (commonLen < label.size() && commonLen < remaining.size()
&& label[commonLen] == remaining[commonLen]) {
commonLen++;
}
if (commonLen == 0) continue;
if (commonLen == remaining.size()) return true;
if (commonLen == label.size()) {
remaining = remaining.substr(commonLen);
current = child.get();
found = true;
break;
}
return false;
}
if (!found) return false;
}
return true;
}
void RadixTree::remove(const std::string& word) {
TrieNode* current = root.get();
std::string remaining = word;
while (!remaining.empty()) {
bool found = false;
for (auto& [key, child] : current->children) {
const std::string& label = child->edgeLabel;
if (remaining.size() >= label.size() &&
remaining.substr(0, label.size()) == label) {
remaining = remaining.substr(label.size());
current = child.get();
found = true;
break;
}
}
if (!found) return;
}
if (current->isEndOfWord) {
current->isEndOfWord = false;
wordCount--;
}
}
std::vector<std::pair<std::string, int>> RadixTree::autocomplete(
const std::string& prefix, int maxResults) const {
const TrieNode* current = root.get();
std::string remaining = prefix;
std::string builtPrefix;
while (!remaining.empty()) {
bool found = false;
for (const auto& [key, child] : current->children) {
const std::string& label = child->edgeLabel;
size_t commonLen = 0;
while (commonLen < label.size() && commonLen < remaining.size()
&& label[commonLen] == remaining[commonLen]) {
commonLen++;
}
if (commonLen == 0) continue;
found = true;
if (commonLen == remaining.size()) {
builtPrefix = prefix + label.substr(commonLen);
current = child.get();
remaining = "";
break;
}
if (commonLen == label.size()) {
builtPrefix += label;
remaining = remaining.substr(commonLen);
current = child.get();
break;
}
return {};
}
if (!found) return {};
}
std::vector<std::pair<std::string, int>> results;
if (builtPrefix.empty()) builtPrefix = prefix;
collectWords(current, builtPrefix, results, maxResults);
std::sort(results.begin(), results.end(),
[](const auto& a, const auto& b) { return a.second > b.second; });
if (static_cast<int>(results.size()) > maxResults) {
results.resize(maxResults);
}
return results;
}
void RadixTree::collectWords(const TrieNode* node, const std::string& currentWord,
std::vector<std::pair<std::string, int>>& results, int maxResults) const {
if (node->isEndOfWord) {
results.emplace_back(currentWord, node->frequency);
}
for (const auto& [key, child] : node->children) {
if (static_cast<int>(results.size()) >= maxResults * 2) return;
collectWords(child.get(), currentWord + child->edgeLabel, results, maxResults);
}
}
void RadixTree::serialize(const std::string& filename) const {
std::ofstream out(filename, std::ios::binary);
serializeNode(root.get(), out);
}
void RadixTree::serializeNode(const TrieNode* node, std::ofstream& out) const {
uint8_t flags = (node->isEndOfWord ? 1 : 0);
out.write(reinterpret_cast<const char*>(&flags), 1);
int32_t freq = node->frequency;
out.write(reinterpret_cast<const char*>(&freq), sizeof(freq));
uint16_t labelLen = static_cast<uint16_t>(node->edgeLabel.size());
out.write(reinterpret_cast<const char*>(&labelLen), sizeof(labelLen));
out.write(node->edgeLabel.data(), labelLen);
uint16_t childCount = static_cast<uint16_t>(node->children.size());
out.write(reinterpret_cast<const char*>(&childCount), sizeof(childCount));
for (const auto& [key, child] : node->children) {
out.write(&key, 1);
serializeNode(child.get(), out);
}
}
void RadixTree::deserialize(const std::string& filename) {
std::ifstream in(filename, std::ios::binary);
root = deserializeNode(in);
wordCount = getWordCount();
}
std::unique_ptr<TrieNode> RadixTree::deserializeNode(std::ifstream& in) {
auto node = std::make_unique<TrieNode>();
uint8_t flags;
in.read(reinterpret_cast<char*>(&flags), 1);
node->isEndOfWord = (flags & 1);
int32_t freq;
in.read(reinterpret_cast<char*>(&freq), sizeof(freq));
node->frequency = freq;
uint16_t labelLen;
in.read(reinterpret_cast<char*>(&labelLen), sizeof(labelLen));
node->edgeLabel.resize(labelLen);
in.read(node->edgeLabel.data(), labelLen);
uint16_t childCount;
in.read(reinterpret_cast<char*>(&childCount), sizeof(childCount));
for (uint16_t i = 0; i < childCount; i++) {
char key;
in.read(&key, 1);
node->children[key] = deserializeNode(in);
}
return node;
}
size_t RadixTree::getNodeCount() const {
return countNodes(root.get());
}
size_t RadixTree::countNodes(const TrieNode* node) const {
size_t count = 1;
for (const auto& [key, child] : node->children) {
count += countNodes(child.get());
}
return count;
}
size_t RadixTree::getWordCount() const {
return wordCount;
}Why binary serialization matters in interviews
Binary serialization is a common systems programming topic. It shows you understand how data is laid out in memory, how to design self-describing formats, and how to trade startup computation for disk space.
The speedup you measured (typically 3-5x) comes from skipping all string parsing, allocation of temporary buffers, and line-splitting logic. The binary reader just copies bytes directly into the tree structure.
Your spell checker now has real data and a fast binary cache. Next, you will build the interactive CLI that ties everything together into a usable tool.
Build the Interactive CLI and Benchmarking Module
You have a fully functional spell checker engine under the hood. The Radix Tree stores 466,000+ words, the Damerau-Levenshtein algorithm finds corrections, and binary serialization speeds up loading.
Now you need a way to actually use it. In this step, you will build an interactive command-line interface that lets you type sentences and see misspellings highlighted in real time. You will also add a benchmarking module that measures exactly how fast your engine performs.
In this step, get ready to:
- Create a benchmarking module that measures dictionary load time, lookup speed, and suggestion latency.
- Build an interactive REPL with spell-check, autocomplete, and benchmark commands.
- Compile and run the complete spell checker with ANSI-colored output.
Create the benchmarking module
Before building the CLI, you need a way to measure how well your engine performs. The benchmarking module wraps std::chrono timing around each operation so you can see concrete millisecond values for dictionary loading, word lookups, and suggestion generation.
- Create a new file include/benchmark.h and add the following header:
#pragma once
#include <string>
#include <chrono>
#include <functional>
#include <iostream>
#include <iomanip>
class Benchmark {
public:
static double measureMs(const std::function<void()>& func);
static void runAll(const std::string& dictionaryPath);
};What does this header declare?
The Benchmark class exposes two static methods. measureMs takes any callable (wrapped in std::function<void()>) and returns how many milliseconds it took to execute. runAll orchestrates a full benchmark suite given a dictionary file path.
- Save include/benchmark.h.
- Create src/benchmark.cpp and add the implementation:
#include "benchmark.h"
#include "spell_checker.h"
#include <vector>
double Benchmark::measureMs(const std::function<void()>& func) {
auto start = std::chrono::high_resolution_clock::now();
func();
auto end = std::chrono::high_resolution_clock::now();
return std::chrono::duration<double, std::milli>(end - start).count();
}
void Benchmark::runAll(const std::string& dictionaryPath) {
std::cout << "\n===== PERFORMANCE BENCHMARK =====\n\n";
SpellChecker checker;
// Measure how long it takes to parse the text dictionary
double loadTime = measureMs([&]() {
checker.loadDictionary(dictionaryPath);
});
std::cout << std::fixed << std::setprecision(2);
std::cout << "Dictionary load time: " << loadTime << " ms\n";
std::cout << "Dictionary size: " << checker.getDictionarySize() << " words\n\n";
// Save binary and measure reload speed
checker.saveBinaryDictionary("data/dictionary.bin");
SpellChecker checker2;
double binLoadTime = measureMs([&]() {
checker2.loadBinaryDictionary("data/dictionary.bin");
});
std::cout << "Binary load time: " << binLoadTime << " ms\n";
std::cout << "Speedup: " << std::setprecision(1) << (loadTime / binLoadTime) << "x\n\n";
// Benchmark individual word lookups
std::vector<std::string> testWords = {"hello", "world", "algorithm", "computer", "science",
"programming", "dictionary", "spell", "check", "fuzzy"};
double totalLookup = 0;
for (const auto& word : testWords) {
totalLookup += measureMs([&]() { checker.isCorrect(word); });
}
std::cout << "Avg lookup time: " << (totalLookup / testWords.size()) << " ms\n";
// Benchmark suggestion generation for misspelled words
std::vector<std::string> misspelled = {"helo", "wrld", "algoritm", "compter", "scince"};
double totalSuggest = 0;
for (const auto& word : misspelled) {
totalSuggest += measureMs([&]() { checker.suggest(word, 2, 5); });
}
std::cout << "Avg suggestion time: " << (totalSuggest / misspelled.size()) << " ms\n";
std::cout << "\n=================================\n";
}What does this code do?
The measureMs function captures a high-resolution clock timestamp before and after executing the callable, then converts the elapsed time to milliseconds.
The runAll function runs four benchmarks in sequence: text dictionary load time, binary load time (with speedup ratio), average lookup time across 10 correctly-spelled words, and average suggestion time across 5 intentionally misspelled words.
- Save src/benchmark.cpp.
Seeing include errors?
Make sure include/benchmark.h exists and is saved before compiling. The #include "benchmark.h" in the source file relies on the -Iinclude flag in your Makefile.
help me debug a missing header include error in my benchmark module
Build the interactive CLI
The CLI is the user-facing layer of your spell checker. It reads commands from stdin in a loop, dispatching to the appropriate handler. Correct words display in green, misspelled words in red, and suggestions in yellow using ANSI escape codes.
- Create src/main.cpp and add the includes and usage display function:
#include "spell_checker.h"
#include "benchmark.h"
#include <iostream>
#include <sstream>
#include <string>
void printUsage() {
std::cout << "\n\033[1;36m===== SPELL CHECKER ENGINE =====\033[0m\n\n";
std::cout << "Commands:\n";
std::cout << " \033[1;33mcheck\033[0m <sentence> - Check spelling of a sentence\n";
std::cout << " \033[1;33mcomplete\033[0m <prefix> - Autocomplete a prefix\n";
std::cout << " \033[1;33mbenchmark\033[0m - Run performance benchmarks\n";
std::cout << " \033[1;33mquit\033[0m - Exit\n\n";
}What are those escape codes?
The \033[1;36m sequences are ANSI escape codes that change terminal text color. 1;36m is bold cyan, 1;33m is bold yellow, and \033[0m resets the color back to default. These work in most modern terminal emulators.
- Below printUsage(), add the spell-check function that tokenizes a sentence and highlights each word:
void checkSpelling(const SpellChecker& checker, const std::string& sentence) {
std::istringstream iss(sentence);
std::string word;
std::cout << "\n";
while (iss >> word) {
// Strip punctuation, keep only alphabetic characters
std::string cleanWord;
for (char c : word) {
if (std::isalpha(c)) cleanWord += c;
}
if (cleanWord.empty()) continue;
if (checker.isCorrect(cleanWord)) {
// Correct words display in green
std::cout << "\033[1;32m" << word << "\033[0m ";
} else {
// Misspelled words display in red with suggestions in yellow
std::cout << "\033[1;31m" << word << "\033[0m ";
auto suggestions = checker.suggest(cleanWord, 2, 3);
if (!suggestions.empty()) {
std::cout << "\033[0;33m[";
for (size_t i = 0; i < suggestions.size(); i++) {
std::cout << suggestions[i].word;
if (i < suggestions.size() - 1) std::cout << ", ";
}
std::cout << "]\033[0m ";
}
}
}
std::cout << "\n\n";
}What does checkSpelling do?
For each word in the sentence, it strips non-alphabetic characters, checks if the cleaned word exists in the dictionary, and prints it colored accordingly. Misspelled words also trigger the fuzzy search engine, which returns up to 3 ranked suggestions displayed in yellow brackets.
- Below checkSpelling, add the autocomplete display function:
void showCompletions(const SpellChecker& checker, const std::string& prefix) {
auto results = checker.autocomplete(prefix, 10);
std::cout << "\nCompletions for '" << prefix << "':\n";
for (const auto& [word, freq] : results) {
std::cout << " " << word << " (freq: " << freq << ")\n";
}
std::cout << "\n";
}- Finally, add the main function with the interactive REPL loop:
int main(int argc, char* argv[]) {
std::string dictPath = "data/words_alpha.txt";
if (argc > 1) dictPath = argv[1];
std::cout << "Loading dictionary from: " << dictPath << "\n";
SpellChecker checker;
checker.loadDictionary(dictPath);
std::cout << "Loaded " << checker.getDictionarySize() << " words.\n";
printUsage();
std::string line;
while (true) {
std::cout << "\033[1;36m>\033[0m ";
if (!std::getline(std::cin, line)) break;
if (line.empty()) continue;
std::istringstream cmdStream(line);
std::string command;
cmdStream >> command;
if (command == "quit" || command == "exit") break;
if (command == "check") {
std::string rest;
std::getline(cmdStream, rest);
if (!rest.empty()) checkSpelling(checker, rest);
else std::cout << "Usage: check <sentence>\n";
} else if (command == "complete") {
std::string prefix;
cmdStream >> prefix;
if (!prefix.empty()) showCompletions(checker, prefix);
else std::cout << "Usage: complete <prefix>\n";
} else if (command == "benchmark") {
Benchmark::runAll(dictPath);
} else {
// Default: treat as spell check
checkSpelling(checker, line);
}
}
return 0;
}How does the REPL work?
- The main function loads the dictionary from a command-line argument (or defaults to data/words_alpha.txt).
- It enters an infinite loop reading lines from stdin until the user types quit or exit.
- The first token of each line determines which command to dispatch: check, complete, or benchmark.
- Any unrecognized command is treated as a sentence to spell-check, so you can just type words directly.
- Save src/main.cpp.
Seeing linker errors about multiple main functions?
Make sure you only have one main() function across all files in src/. If you created a test file with its own main in the src/ folder, move it to tests/ so the Makefile wildcard does not pick it up.
help me fix a linker error about duplicate main symbols
Compile and run the interactive spell checker
Your Makefile already uses a wildcard to compile all .cpp files in src/. The new files are automatically included in the build.
- Clean any previous build artifacts and recompile by running:
make clean && make- Run the spell checker with the dictionary file:
./spellcheck data/words_alpha.txtYou should see output showing how many words were loaded, followed by the colored command menu and a > prompt waiting for input.
- Try spell-checking a sentence by typing:
check ths is a tset sentanceCorrectly spelled words appear in green. Misspelled words appear in red with yellow suggestion brackets next to them.
- Try autocomplete by typing:
complete algoYou should see a list of words starting with "algo" along with their frequency scores.
- Run the benchmark suite by typing:
benchmarkThe benchmark report shows dictionary load time, binary load time with a speedup multiplier, average lookup time per word, and average suggestion generation time.
- Type quit to exit the REPL when you are done exploring.
Not seeing any colored output?
ANSI escape codes require a terminal that supports them. The built-in macOS Terminal app supports them by default. If you are running from an IDE's integrated terminal, make sure it has ANSI color support enabled.
If you see raw characters like \033[1;32m printed as text, your terminal does not interpret escape codes. Switch to the system Terminal app.
help me debug ANSI color codes not rendering in my terminal
✔️ Awesome, I've got everything!
Great. Double check you have saved all three new files: include/benchmark.h, src/benchmark.cpp, and src/main.cpp.
ⓧ I'd like to double check the full code
Here is the complete code for each new file.
#pragma once
#include <string>
#include <chrono>
#include <functional>
#include <iostream>
#include <iomanip>
class Benchmark {
public:
static double measureMs(const std::function<void()>& func);
static void runAll(const std::string& dictionaryPath);
};#include "benchmark.h"
#include "spell_checker.h"
#include <vector>
double Benchmark::measureMs(const std::function<void()>& func) {
auto start = std::chrono::high_resolution_clock::now();
func();
auto end = std::chrono::high_resolution_clock::now();
return std::chrono::duration<double, std::milli>(end - start).count();
}
void Benchmark::runAll(const std::string& dictionaryPath) {
std::cout << "\n===== PERFORMANCE BENCHMARK =====\n\n";
SpellChecker checker;
double loadTime = measureMs([&]() {
checker.loadDictionary(dictionaryPath);
});
std::cout << std::fixed << std::setprecision(2);
std::cout << "Dictionary load time: " << loadTime << " ms\n";
std::cout << "Dictionary size: " << checker.getDictionarySize() << " words\n\n";
checker.saveBinaryDictionary("data/dictionary.bin");
SpellChecker checker2;
double binLoadTime = measureMs([&]() {
checker2.loadBinaryDictionary("data/dictionary.bin");
});
std::cout << "Binary load time: " << binLoadTime << " ms\n";
std::cout << "Speedup: " << std::setprecision(1) << (loadTime / binLoadTime) << "x\n\n";
std::vector<std::string> testWords = {"hello", "world", "algorithm", "computer", "science",
"programming", "dictionary", "spell", "check", "fuzzy"};
double totalLookup = 0;
for (const auto& word : testWords) {
totalLookup += measureMs([&]() { checker.isCorrect(word); });
}
std::cout << "Avg lookup time: " << (totalLookup / testWords.size()) << " ms\n";
std::vector<std::string> misspelled = {"helo", "wrld", "algoritm", "compter", "scince"};
double totalSuggest = 0;
for (const auto& word : misspelled) {
totalSuggest += measureMs([&]() { checker.suggest(word, 2, 5); });
}
std::cout << "Avg suggestion time: " << (totalSuggest / misspelled.size()) << " ms\n";
std::cout << "\n=================================\n";
}#include "spell_checker.h"
#include "benchmark.h"
#include <iostream>
#include <sstream>
#include <string>
void printUsage() {
std::cout << "\n\033[1;36m===== SPELL CHECKER ENGINE =====\033[0m\n\n";
std::cout << "Commands:\n";
std::cout << " \033[1;33mcheck\033[0m <sentence> - Check spelling of a sentence\n";
std::cout << " \033[1;33mcomplete\033[0m <prefix> - Autocomplete a prefix\n";
std::cout << " \033[1;33mbenchmark\033[0m - Run performance benchmarks\n";
std::cout << " \033[1;33mquit\033[0m - Exit\n\n";
}
void checkSpelling(const SpellChecker& checker, const std::string& sentence) {
std::istringstream iss(sentence);
std::string word;
std::cout << "\n";
while (iss >> word) {
std::string cleanWord;
for (char c : word) {
if (std::isalpha(c)) cleanWord += c;
}
if (cleanWord.empty()) continue;
if (checker.isCorrect(cleanWord)) {
std::cout << "\033[1;32m" << word << "\033[0m ";
} else {
std::cout << "\033[1;31m" << word << "\033[0m ";
auto suggestions = checker.suggest(cleanWord, 2, 3);
if (!suggestions.empty()) {
std::cout << "\033[0;33m[";
for (size_t i = 0; i < suggestions.size(); i++) {
std::cout << suggestions[i].word;
if (i < suggestions.size() - 1) std::cout << ", ";
}
std::cout << "]\033[0m ";
}
}
}
std::cout << "\n\n";
}
void showCompletions(const SpellChecker& checker, const std::string& prefix) {
auto results = checker.autocomplete(prefix, 10);
std::cout << "\nCompletions for '" << prefix << "':\n";
for (const auto& [word, freq] : results) {
std::cout << " " << word << " (freq: " << freq << ")\n";
}
std::cout << "\n";
}
int main(int argc, char* argv[]) {
std::string dictPath = "data/words_alpha.txt";
if (argc > 1) dictPath = argv[1];
std::cout << "Loading dictionary from: " << dictPath << "\n";
SpellChecker checker;
checker.loadDictionary(dictPath);
std::cout << "Loaded " << checker.getDictionarySize() << " words.\n";
printUsage();
std::string line;
while (true) {
std::cout << "\033[1;36m>\033[0m ";
if (!std::getline(std::cin, line)) break;
if (line.empty()) continue;
std::istringstream cmdStream(line);
std::string command;
cmdStream >> command;
if (command == "quit" || command == "exit") break;
if (command == "check") {
std::string rest;
std::getline(cmdStream, rest);
if (!rest.empty()) checkSpelling(checker, rest);
else std::cout << "Usage: check <sentence>\n";
} else if (command == "complete") {
std::string prefix;
cmdStream >> prefix;
if (!prefix.empty()) showCompletions(checker, prefix);
else std::cout << "Usage: complete <prefix>\n";
} else if (command == "benchmark") {
Benchmark::runAll(dictPath);
} else {
checkSpelling(checker, line);
}
}
return 0;
}Your spell checker is now a fully interactive tool. You can check entire sentences for errors, explore completions for any prefix, and quantify exactly how fast your engine runs. Next up, you will push performance further by comparing your Compressed Trie against the basic Trie and generating a full benchmark report.
Secret mission
Keyboard-Distance-Aware Scoring
Your spell checker treats all character substitutions as equal. But on a real keyboard, pressing 'r' when you meant 'e' is far more likely than pressing 'r' when you meant 'p'. Can you make the algorithm aware of physical key proximity so that typos caused by fat-fingering adjacent keys get better corrections?
Clean Up Your Resources
Clean Up Your Resources
This project runs entirely locally with no cloud resources or paid APIs. There are no ongoing costs. All data files used are open-source and free.
Decide whether to keep your project files for future experimentation or delete them to free up disk space.
Resources you used:
- Your spell checker project folder on the Desktop (containing src/, include/, data/, build/, Makefile, and the compiled spellcheck binary).
- data/words_alpha.txt (downloaded dictionary from the dwyl/english-words repository).
- data/dictionary.bin (serialized Radix Tree binary for fast loading).
- Xcode Command Line Tools (provides the clang++ compiler, installed system-wide at /Library/Developer/CommandLineTools).
Keep everything running
No action needed. Choose this if you plan to continue experimenting with the spell checker, adding new features, or using it as a reference for future C++ projects.
- Your compiled spellcheck binary is ready to use anytime. Run it from your project folder with ./spellcheck.
- The serialized data/dictionary.bin file loads faster than re-parsing the text dictionary each time.
- Xcode Command Line Tools remains installed on your system. Many other development tools (Homebrew, Git, Python packages with C extensions) depend on it, so keeping it is recommended.
- Cursor remains installed as your code editor.
Pause - I'll come back to this later
There are no running processes or background services to stop. Your project is already paused by default since everything runs on-demand.
- Your project folder, compiled binary, and dictionary files all sit on disk without consuming CPU or memory when idle.
- When you return, just open your project folder in Cursor and run make to rebuild if you have made changes.
Delete - I don't want to use this again
Remove all project files from your machine. This frees up the disk space used by the source code, dictionary data, and compiled binaries.
- Clean the build artifacts first by running this from inside your project folder:
- Then navigate to your Desktop and delete the entire project folder:
make cleanNow delete the project folder from your Desktop:
cd ~/Desktop
rm -rf [[PROJECT_FOLDER="your spell checker project folder name"]]- Confirm the folder is gone by running:
lsYour spell checker project folder should no longer appear in the output.
What about Xcode Command Line Tools?
Xcode Command Line Tools is a system-wide dependency that many other tools rely on (Homebrew, Git, Python, Ruby, and any C/C++ development). Removing it will break those workflows.
If you are certain you no longer need any command-line development tools, Apple documents the removal process at their official Xcode documentation page. The commands are:
sudo rm -rf /Library/Developer/CommandLineTools
sudo pkgutil --forget com.apple.dt.commandlinetoolsMost learners should skip this step and keep Xcode Command Line Tools installed.
Nice Work!
Nice Work!
You just built a production-quality spell checker engine from scratch in C++. This is the kind of project that makes interviewers lean forward.
You've learned how to:
- Implement a Compressed Trie (Radix Tree) with memory-efficient string-edge storage, binary serialization for instant loading, and Damerau-Levenshtein fuzzy search with trie traversal pruning.
- Load and index 466,000+ English words with frequency-based ranking, then build an interactive CLI with spell-check and autocomplete modes using ANSI colored output.
- Benchmark your system with measurable metrics comparing text-loading vs binary-loading performance, average lookup times, and suggestion latency.
- Secret Mission: Added keyboard-distance-aware scoring using QWERTY key proximity so that typos caused by adjacent keys produce smarter suggestions.
Ready to quiz yourself?