SymSpell: A Spell Checker Made Of Deletes

SymSpell was the reason I needed most of the data structures from the previous articles. The algorithm itself is quite small.

Let's suppose we want to correct wrold. The direct approach is to compare it with every word in the dictionary, calculate edit distance for every pair, and keep the closest result. The usual dynamic-programming algorithm takes $O (nm)$ time for words of lengths $n$ and $m$ , and we have to repeat it for the whole dictionary. This becomes too slow when we want to correct every word in a text.

A trie avoids repeating work for dictionary words with the same prefix. We can traverse it while updating one row of the edit-distance matrix and stop exploring a branch once it can't produce a close enough word. This works very well for a single query, but correcting a text still requires a trie traversal for every word.

Another option is a character n-gram index. We split every dictionary word into overlapping fragments of a fixed length and map each fragment to the words that contain it. With bigrams, world becomes wo, or, rl and ld. For a query we generate the same fragments, collect the words that share enough of them, and calculate edit distance only for those candidates.

Choosing the fragment length and what counts as enough matches is a tradeoff. Small n-grams return long candidate lists, while large ones make a single typo change several fragments at once. The query also has to merge the lists for all of its fragments before it can check the candidates.

SymSpell builds an index over deletes instead of fixed-length fragments. During construction it generates every string obtained by deleting up to $d$ characters from each dictionary word. A query generates the same deletes and looks them up in the index. Only dictionary words found through a shared delete need an actual edit-distance calculation.

The original SymSpell design pays for fast queries with a large precomputed delete dictionary. In this article we'll build a memory-efficient version which doesn't keep the strings after construction. We'll use PTHash to map a delete to a slot, Elias-Fano to store the group offsets, and a bit array to store indexes.

Why Deletes Are Enough

Let's take hello and allow one edit.

Its deletion set, including the original word, is:

hello -> hello, ello, hllo, helo, hell

Now we do the same for the mistyped input heklo:

heklo -> heklo, eklo, hklo, helo, heko, hekl

Both sets share a member helo. That allows us to find hello without trying every possible character insertion or substitution of heklo.

An insertion or substitution can use any character, so generating them means trying the whole alphabet at every position. Deletes only remove characters that are already there. The candidate set for a query depends on its length alone, whether the alphabet is 26 letters or all of Unicode.

This works because an edit can be viewed from both sides. An insertion on one side is a deletion on the other. A substitution becomes one deletion from each string. For an adjacent swap, deleting the same one of the two swapped characters from both strings leaves the same subsequence. Every single edit costs at most one deletion on each side, so two strings within distance $d$ can each lose at most $d$ characters and meet at some common string.

The reverse isn't true. Two words can share a delete and still be farther than $d$ . At $d = 1$ , world and sword both produce word, but their Levenshtein distance is two.

After finding candidates, we still have to calculate the real Levenshtein or Damerau-Levenshtein distance before accepting one.

The Original Design

The reference implementation is a C# project with several verbosity modes, prefix truncation and word segmentation, but the structure underneath is a hash map from deletes to the words that produced them. A minimal version in Python would look like this:

def deletes(word, d):
    result = {word}
    layer = {word}

    for _ in range(d):
        layer = {w[:i] + w[i + 1:] for w in layer for i in range(len(w))}
        result |= layer

    return result


def distance(a, b):
    """
    Levenstein Distance. 
    A modified Wagner–Fischer algorithm with two rows
    https://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_with_two_matrix_rows
    """
    prev = list(range(len(b) + 1))

    for i, ca in enumerate(a, 1):
        row = [i]
        for j, cb in enumerate(b, 1):
            row.append(min(prev[j] + 1, row[j - 1] + 1, prev[j - 1] + (ca != cb)))
        prev = row

    return prev[-1]


class SymSpell:
    def __init__(self, words, d):
        self.words = words
        self.d = d
        self.index = {}

        for i, (word, _) in enumerate(words):
            for delete in deletes(word, d):
                self.index.setdefault(hash(delete), []).append(i)

    def search(self, query):
        best = None

        for delete in deletes(query, self.d):
            for i in self.index.get(hash(delete), ()):
                word, count = self.words[i]
                dist = distance(query, word)
                if dist > self.d:
                    continue
                if best is None or (dist, -count) < (best[1], -best[2]):
                    best = (word, dist, count)

        return best


words = [("hello", 120), ("help", 40), ("world", 90), ("sword", 30), ("word", 80)]
spell = SymSpell(words, 2)

for query in ["helo", "wrold", "word"]:
    print(query, "->", spell.search(query))

Construction and search use self.index from opposite directions. During construction, each delete is hashed and the dictionary word's id is appended to the group stored under that hash. During a search, the query produces its own deletes and reads the same groups.

Every word returned by the index is still only a candidate. In the final distance calculation we reject words outside $d$ , including false candidates introduced by hash collisions. Then among the remaining words we choose the one with the smallest distance and the highest frequency. This is why helo resolves to hello rather than help.

My implementation changes how the index is stored and deletes generation. I wanted to generate deletes from the complete words, so I made the index static and compressed it instead. I replace a hash map with PTHash, and I use Elias-Fano to store boundaries between groups, and a bit array stores the word ids. But with these optimizations adding a new word requires rebuilding the whole index, which is not important in my case.

Delete Generation

Construction and search steps both call the same deletes function. It produces every distinct string we can get from the word by deleting up to $d$ characters.

def deletes(word, d):
    return edits(word, d, {word})


def edits(word, d, seen):
    if d == 0:
        return seen

    for i in range(len(word)):
        delete = word[:i] + word[i + 1:]
        if delete not in seen:
            seen.add(delete)
            edits(delete, d - 1, seen)

    return seen


for delete in sorted(deletes("hello", 2), key=lambda s: (-len(s), s)):
    print(delete)

The first problem with this approach is that we need to keep already generated strings in memory and the second one is if the word has repeated characters we generate duplicates. For the word hello at distance $2$ this algorithm builds 21 strings and only keeps 11 of them. At edit distance 3 or 4 and with longer words and phrases this quickly become the bottleneck of the whole algorithm so we should try to improve it.

No duplicates

The version above chooses which character to delete and deletes one at a time, but what if we choose the characters we keep instead and build a slightly different algorithm around that?

Deleting $d$ characters from a word of length $n$ leaves $n - d$ of them in their original order, so every delete at distance $d$ is a subsequence of length $n - d$ . Let's build a recursion that chooses a single character to keep first and then passes the rest of the word to the next level. To prevent duplicates we check that we haven't already used the same character at an earlier position in this call.

def subsequences(word, k):
    if k == 0:
        return [""]

    result = []
    for i in range(len(word) - k + 1):
        if word[i] in word[:i]:
            continue
        for tail in subsequences(word[i + 1:], k - 1):
            result.append(word[i] + tail)

    return result


def deletes(word, d):
    result = []
    for distance in range(min(d, len(word)) + 1):
        result += subsequences(word, len(word) - distance)
    return result


for delete in deletes("hello", 2):
    print(delete)

Traced run of subsequences("hello", 3)

def subsequences_traced(word, k, depth=0):
    if k == 0:
        return [""]

    if depth == 0:
        print(f'"" + subsequences("{word}", {k})')

    pad = "│  " * (depth + 1)
    result = []
    for i in range(len(word) - k + 1):
        if word[i] in word[:i]:
            print(f'{pad}skip "{word[i]}"')
            continue

        if k > 1:
            print(f'{pad}"{word[i]}" + subsequences("{word[i + 1:]}", {k - 1})')

        tails = subsequences_traced(word[i + 1:], k - 1, depth + 1)
        branch = [word[i] + tail for tail in tails]
        print(f'{pad}<- ' + ", ".join(f'"{s}"' for s in branch))
        result += branch

    if depth == 0:
        print("<- " + ", ".join(f'"{s}"' for s in result))

    return result


subsequences_traced("hello", 3)

One delete at a time

Both versions return all the deletes at once, before we need them all. During construction we hash a delete, append the word id and forget the string, so we'd rather generate one delete at a time and never hold the whole list. To do that we need to rewrite the recursion as a loop.

When we recurse we leave the state on the stack, one frame per kept character, each holding the position that call stopped at. We can hold the same thing in one array. In positions[depth] we store the index of the character we keep at that depth, so for hello a positions[0] of 2 means we keep l first. We let yield remember where to resume:

def deletes(word, d):
    n = len(word)
    positions = [0] * n

    for distance in range(min(d, n) + 1):
        target_len = n - distance
        if target_len == 0:
            yield ""
            continue

        depth = 0
        position = 0
        while True:
            start = positions[depth - 1] + 1 if depth else 0
            last = n - (target_len - depth)
            while position <= last and word[position] in word[start:position]:
                position += 1

            if position > last:
                if depth == 0:
                    break
                depth -= 1
                position = positions[depth] + 1
                continue

            positions[depth] = position
            position += 1
            if depth + 1 == target_len:
                yield "".join(word[p] for p in positions[:target_len])
                continue

            depth += 1


for delete in deletes("hello", 2):
    print(delete)

With this one we solved both of the problems. We don't spend time hashing and checking if the newly generated string is in the set, and we have a stable memory profile regardless of word length (only linear) and delete distance.

Zig version

From this point on I'll use Zig in the examples since I want to show the full complexity of the algorithms without hiding memory allocations/copy etc. Here is the same iterative generator. We allocate positions and the output buffer once in init, and next fills the buffer with the characters we keep and returns a slice of it:

const std = @import("std");

const DeleteIterator = struct {
    word: []const u8,
    max_distance: usize,
    positions: []usize,
    buffer: []u8,

    distance: usize = 0,
    target_len: usize,
    depth: usize = 0,
    position: usize = 0,
    done: bool = false,

    
    pub fn init(
        allocator: std.mem.Allocator,
        word: []const u8,
        max_distance: usize,
    ) !DeleteIterator {
        return .{
            .word = word,
            .max_distance = @min(max_distance, word.len),
            .positions = try allocator.alloc(usize, word.len),
            .buffer = try allocator.alloc(u8, word.len),
            .target_len = word.len,
        };
    }


    
    pub fn deinit(self: *DeleteIterator, allocator: std.mem.Allocator) void {
        allocator.free(self.positions);
        allocator.free(self.buffer);
    }


    fn isFirstAtDepth(self: *const DeleteIterator, position: usize) bool {
        const start = if (self.depth == 0) 0 else self.positions[self.depth - 1] + 1;

        for (self.word[start..position]) |character| {
            if (character == self.word[position]) return false;
        }

        return true;
    }

    fn seek(self: *DeleteIterator) bool {
        while (true) {
            const last = self.word.len - (self.target_len - self.depth);
            while (self.position <= last and !self.isFirstAtDepth(self.position))
                self.position += 1;

            if (self.position > last) {
                if (self.depth == 0) return false;
                self.depth -= 1;
                self.position = self.positions[self.depth] + 1;
                continue;
            }

            self.positions[self.depth] = self.position;
            self.position += 1;
            if (self.depth + 1 == self.target_len) return true;

            self.depth += 1;
        }
    }

    pub fn next(self: *DeleteIterator) ?[]const u8 {
        while (!self.done) {
            if (self.target_len == 0) {
                self.done = true;
                return self.buffer[0..0];
            }

            if (self.seek()) {
                for (self.positions[0..self.target_len], 0..) |position, i| {
                    self.buffer[i] = self.word[position];
                }
                return self.buffer[0..self.target_len];
            }

            if (self.distance == self.max_distance) {
                self.done = true;
                break;
            }

            self.distance += 1;
            self.target_len = self.word.len - self.distance;
            self.depth = 0;
            self.position = 0;
        }

        return null;
    }
};


pub fn main() !void {
    var arena_state = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena_state.deinit();
    const allocator = arena_state.allocator();

    var iterator = try DeleteIterator.init(allocator, "hello", 2);
    defer iterator.deinit(allocator);

    while (iterator.next()) |delete| std.debug.print("{s}\n", .{delete});
}

We allocate only twice in init and then reuse the same buffer for every delete. The slice returned by next points into buffer, so it's valid only until we call next again, and the caller has to copy it to keep it.

This is an ASCII-only variant. In the repo I have an implementation that supports UTF-8.

The output is ordered by delete distance automatically. First comes the word, then all distance-one deletes, etc.

Building the Structure

In the original version of the algorithm we store delete hashes directly. For each dictionary word, we generate the deletes and append the word id to a hash-map entry:

index = defaultdict(list)
for word_id, word in enumerate(words):
    for delete in generate_deletes(word):
        key = hash(delete)
        index[key].append(word_id)

Even if we store only a hash of each delete, every distinct delete still needs:

At least 32 bits for the hash.
One hash-table entry pointing to its candidate list.
128 bits for that list: a 64-bit pointer, a 32-bit length, and one 32-bit word id.
Spare hash-table capacity, which can add another 30%-50% to the table itself.

Most deletes refer to only one word, so the references can occupy considerably more space than the word id we wanted to store.

Each delete hashes to a table entry whose pointer reaches a separately allocated candidate list

If we don't need live updates to the dictionary, we can concatenate the candidate lists into one large array and replace each pointer with an array offset. The offset and list length then fit together in a single u64, 32 bits for the offset and 32 for the length (40/24 could be more reasonable). We went from 96 bits per entry down to 64.

One concatenated array replaces the per-list allocations, and each entry packs its offset and length into a single u64

This is better, but even after that we still pay 32 bits for each key. To distinguish one delete from another, we have to store something per entry, but how can we store less data per item? The answer is a perfect hash function, and luckily we already built one in one of our previous articles. Using PHF we can reduce that to about 2-3 bits per key.

So now our PHF maps all our $N$ deletes to integers from $0$ to $N + c$ (we're not using MPHF but $c$ is tiny, $c \approx N*0.03$ ).

A perfect hash replaces the stored keys, so the table holds only the packed offset and length and has no spare capacity

Every slot still carries an offset and a length, we can get rid of the length if we sort the index. The groups are placed back to back in one array, so where one group ends the next one begins. If we keep only the offsets, for the group for slot $i$ const length = groups[i + 1] - groups[i], with one extra entry at the end so the last group has something to stop at.

So the index splits into two. values contains every word reference inlined, group after group. groups holds one offset per slot plus that final entry, and nothing else.

Surprisingly, now the groups array holds one interesting property that gives us yet another opportunity to further compress the data. It's a non-decreasing sequence after the sort, that means we can use Elias-Fano. Elias-Fano costs $2 + \log_2 (u/n)$ bits per value, and here the universe is the number of word ids while the count is the number of slots, so we have a good $u/n$ ratio, and pay around 3 bits per value instead of 32.

Elias-Fano holds the offsets, one per slot, and the group for a slot is the run of word ids between its offset and the next

The word ids are still a whole integer each. We can bit-pack them down to ceil(log2(dictionary.len)) bits and save more space, in exchange for a slower read.

Let's look at a general example next: both structures come from the earlier articles, so here they are only a build and a get. The whole construction is four stages:

const std = @import("std");
const pthash = @import("pthash.zig");
const ef = @import("ef.zig");

const PTHash = pthash.PTHash([]const u8, pthash.OptimalMapper(u64));
const EliasFano = ef.EliasFano;

const Self = @This();

pub const Token = struct { word: []const u8, count: u32 };

dict: []const Token,
pthash: PTHash.Type,
edits_index: EliasFano,
edits_values: []u32,

const WordEdit = struct { edit: []u8, i_word: u32, count: u32 };


const SortedEditsIterator = struct {
    array: []WordEdit,
    len: usize,
    i: usize = 0,

    pub inline fn size(self: *const @This()) usize {
        return self.len;
    }

    pub fn next(self: *@This()) ?[]const u8 {
        if (self.i >= self.array.len) return null;
        if (self.i == 0) {
            self.i += 1;
            return self.array[self.i - 1].edit;
        }
        while (std.mem.eql(u8, self.array[self.i - 1].edit, self.array[self.i].edit)) {
            self.i += 1;
        }
        self.i += 1;
        return self.array[self.i - 1].edit;
    }
};


pub fn init(allocator: std.mem.Allocator, seed: u64, dict: []const Token) !Self {
    var edits = std.ArrayListUnmanaged(WordEdit).empty;
    var generator = try EditsGenerator.init(allocator, longestWord(dict));

    for (dict, 0..) |token, i| {
        try generator.load(token.word, max_distance);
        while (generator.next()) try edits.append(allocator, .{
            .edit = try allocator.dupe(u8, generator.getValue()),
            .i_word = @intCast(i),
            .count = token.count,
        });
    }

    // Sorting by the edits so SortedEditsIterator can skip duplicates
    
    std.mem.sort(WordEdit, word_edits.items, {}, struct {
        fn func(_: void, a: WordEdit, b: WordEdit) bool {
            const order = std.mem.order(u8, a.edit, b.edit);
            if (order == .eq) return a.i_word < b.i_word;
            return order == .lt;
        }
    }.func);


    // SortedEditsIterator skips duplicates of an already sorted array
    var keys = SortedEditsIterator{ .array = edits.items, .len = countRuns(edits.items) };
    var ph = try PTHash.buildSeed(allocator, @TypeOf(&keys), &keys, PTHash.buildConfig(
        keys.size(),
        .{ .lambda = 6, .alpha = 0.97, .max_bucket_size = 512 },
    ), seed);

    const groups = try allocator.alloc([]WordEdit, ph.size());
    @memset(groups, &.{});

    var run: usize = 0;
    // Represent groups in sorted order
    for (1..edits.items.len + 1) |i| {
        const last = i == edits.items.len;
        if (!last and std.mem.eql(u8, edits.items[i].edit, edits.items[run].edit)) continue;
        groups[try ph.get(edits.items[run].edit)] = edits.items[run..i];
        run = i;
    }

    // Serializing values
    const offsets = try allocator.alloc(u32, ph.size() + 1);
    const values = try allocator.alloc(u32, countValues(groups));

    var j: u32 = 0;
    for (groups, 0..) |group, slot| {
        offsets[slot] = j;
        // If we sort values for a group based on count, we can early terminate at the search stage
        std.mem.sort(WordEdit, group, {}, struct {
            fn func(_: void, a: WordEdit, b: WordEdit) bool {
                return a.count > b.count;
            }
        }.func);

        for (group, 0..) |it, k| {
            if (k > 0 and it.i_word == group[k - 1].i_word) continue;
            values[j] = it.i_word;
            j += 1;
        }
    }
    offsets[ph.size()] = j;

    return .{
        .dict = dict,
        .pthash = ph,
        .edits_index = try EliasFano.init(allocator, j, offsets),
        .edits_values = values,
    };
}


pub fn deinit(self: *Self, allocator: std.mem.Allocator) void {
    self.pthash.deinit(allocator);
    self.edits_index.deinit(allocator);
    allocator.free(self.edits_values);
    self.* = undefined;
}


pub fn candidates(self: *const Self, delete: []const u8) ![]const u32 {
    const slot = try self.pthash.get(delete);
    const from = try self.edits_index.get(slot);
    const to = try self.edits_index.get(slot + 1);
    return self.edits_values[from..to];
}

Here we sort the records by delete and then by word id, and after that equal deletes sit next to each other, so SortedEditsIterator can skip duplicates without extra memory.

Then we build groups, a sorted array we get by placing every group directly at the index returned by the perfect hash function. groups contains a list of word ids for each delete.

Then we represent the groups array in a flat chunk of memory so we can keep the offsets in their own array, which lets us compress them using our EliasFano data structure.