SymSpell: Searching and Word Segmentation

In the previous part we finished the index and went through every optimization I made to fit it into memory. That was the part where most of my work went and I actually changed something.

Here however we're going to discuss how to use our existing index and focus on original approaches. Search and word segmentation are the original SymSpell, I didn't touch the algorithms themselves, so if you've read Wolf Garbe's SymSpell and Word Segmentation articles you already know how both of them work.

We'll start with the search, how a query generates deletes, what happens when the perfect hash returns a slot for a delete that was never indexed, and where it can stop early. Then word segmentation and the benchmarks are at the end.

Searching

To do the search we use the deletes generator that we discussed in the previous article. We take the query word, generate its deletes and look up each one in the index.

In the original version the hash map stored a hash for every delete, so a delete that was never indexed came back with nothing. Our perfect hash function returns a slot for any string we pass, so instead of a miss we get the group of some other delete. But this is not a problem, every candidate goes through the edit distance check anyway.

Here is a minimal example of how this works in practice. We even have our own small and the world's most inefficient perfect hash function implementation:

from zlib import crc32



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


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]


def is_subsequence(needle, haystack):
    it = iter(haystack)
    return all(c in it for c in needle)



class BruteForcePHF:
    def __init__(self, keys, factor=3):
        self.size = int(len(keys) * factor)

        for seed in range(1, 100000):
            self.seed = seed
            if len({self.get(key) for key in keys}) == len(keys):
                return

        raise ValueError('Not Found')

    def get(self, key):
        return crc32(key.encode(), self.seed) % self.size


class SymSpell:
    
    def __init__(self, words, d):
        self.words = words
        self.d = d
        self.total = sum(count for _, count in words)
        self.max_len = max(len(word) for word, _ in words) + d

        groups = {}
        for i, (word, _) in enumerate(words):
            for delete in sorted(deletes(word, d)):
                groups.setdefault(delete, []).append(i)

        self.phf = BruteForcePHF(groups)

        by_slot = {self.phf.get(delete): ids for delete, ids in groups.items()}
        self.offsets = []
        self.values = []
        for slot in range(self.phf.size):
            self.offsets.append(len(self.values))
            self.values += sorted(set(by_slot.get(slot, ())), key=lambda i: -words[i][1])
        self.offsets.append(len(self.values))


    def candidates(self, delete):
        slot = self.phf.get(delete)
        return self.values[self.offsets[slot]:self.offsets[slot + 1]]

    def search(self, query):
        best = None
        seen = set()

        for delete in deletes(query, self.d):
            ids = self.candidates(delete)
            if not ids or not is_subsequence(delete, self.words[ids[0]][0]):
                continue

            for i in ids:
                if i in seen:
                    continue
                seen.add(i)

                word, count = self.words[i]
                if abs(len(word) - len(query)) > self.d:
                    continue

                dist = distance(query, word)
                if dist <= self.d and (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)]
sym_spell = SymSpell(words, 2)

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

for delete in ["ab", "zh"]:
    print(delete, "was never indexed, its slot holds",
          [words[i][0] for i in sym_spell.candidates(delete)])
Copy

is_subsequence here is what saves us some extra comparisons in case of hash collisions. The delete is a subsequence of every word in its group, so an indexed delete always passes and a foreign one usually doesn't, and we skip the whole group without calculating a single distance.

The last two lines of the output are that case, ab and zh were never indexed and both come back with a group. Both of them do not survive the is_subsequence check, and we never calculate a distance for any of those words.

So the whole search function is:

1. Generate the deletes of the query.
2. Get a slot for each one and read its group.
3. Drop the group if the delete isn't a subsequence of its first word.
4. Skip the words we already reached through another delete.
5. Measure what's left against the query and keep the closest/most frequent word.

Word segmentation

Word segmentation is the process of dividing written text into meaningful units, putting spaces back into a text that lost them, helloworld into hello world. This can be useful in a variety of cases - search queries preprocessing, OCR post processing, in a text editor.

We can also combine this process with spelling correction while cutting the text, so helwrold will come out as help world. That extra step would make it harder than segmentation alone.

Each gap between neighbouring characters is an independent yes-or-no, so $n$ characters give us $2^{n-1}$ possible cuts. Ten characters, 512 variants. A 35-character sentence, 17 billion. Enumerating them is not an option, so we'll need something smarter than trying every possible cut.

Scoring a cut

How do we define the best candidate? Every part we score first goes through the spelling correction step, which gives us an edit distance and a word frequency. We compare two cuts by the total edit distance first and by the total word probability second. If a part matches nothing in the dictionary we keep the text and count every character of that part as an edit, so "not found" is represented in the distance.

But even when nothing matches we still need a probability. We start from 1 / total (total is the sum of all dictionary counts) because a word we never saw can't be more common than a word we've seen once. Then we make it 10 times less likely for every character after the first, on the idea that a long sequence of letters is less and less likely to be a word at all. That's 10 / (total * 10 ** len), the 10 in the numerator is what puts a single character exactly at 1 / total.

Logarithms get added to avoid multiplying probabilities, a handful of word frequencies multiplied together already underflows a double.

def correct(part):
    hit = search(part)
    if hit:
        word, dist, count = hit
        return word, dist, log10(count / total)

    return part, len(part), log10(10 / (total * 10 ** len(part)))
Copy

Recursive version

The straightforward way is a recursion over the remainder of the string. We take a prefix of every allowed length, up to the longest dictionary word plus $d$ (max edit distance), that's max_len in the code. We correct the prefix, find the best segmentation of what's left and keep the best combination:

from math import log10

words = [("hello", 120), ("help", 40), ("world", 90), ("sword", 30), ("word", 80)]
d = 2
total = sum(count for _, count in words)
max_len = max(len(word) for word, _ in words) + d



def distance(a, b):
    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]



def search(query):
    best = None
    for word, count in words:
        if abs(len(word) - len(query)) > d:
            continue
        dist = distance(query, word)
        if dist <= d and (best is None or (dist, -count) < (best[1], -best[2])):
            best = (word, dist, count)

    return best


def correct(part):
    hit = search(part)
    if hit:
        word, dist, count = hit
        return word, dist, log10(count / total)

    return part, len(part), log10(10 / (total * 10 ** len(part)))


calls = 0


def segment(text):
    global calls
    calls += 1
    if not text:
        return 0, 0.0, []

    results = []
    for j in range(1, min(len(text), max_len) + 1):
        word, dist, probability = correct(text[:j])
        dist_sum, probability_sum, parts = segment(text[j:])
        results.append((dist + dist_sum, probability + probability_sum, [word] + parts))

    return min(results, key=lambda it: (it[0], -it[1]))


for text in ["helloworld", "helwrold", "swordword", "helphello"]:
    calls = 0
    dist, probability, parts = segment(text)
    print(f"{text} -> {' '.join(parts)}  distance={dist} log10(p)={probability:.1f} calls={calls}")
Copy

This works but take a look at the call counter. helloworld is only ten characters and we made 1012 calls, and every extra character doubles that. We're walking all $2^{n-1}$ segmentation variants, only with a stack instead of a loop, and we solve the same subproblem over and over.

But whether we cut helloworld as hel|lo|world or as hello|world, after the fifth character we're left with world both times, and its best cut doesn't depend on how we got there because we don't scan backwards. We can use that to cache the results.

Cache over the remainder

This is Garbe's dynamic programming variant, we cache the function response over the remaining text:

from math import log10

words = [("hello", 120), ("help", 40), ("world", 90), ("sword", 30), ("word", 80)]
d = 2
total = sum(count for _, count in words)
max_len = max(len(word) for word, _ in words) + d



def distance(a, b):
    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]


def search(query):
    best = None
    for word, count in words:
        if abs(len(word) - len(query)) > d:
            continue
        dist = distance(query, word)
        if dist <= d and (best is None or (dist, -count) < (best[1], -best[2])):
            best = (word, dist, count)

    return best


def correct(part):
    hit = search(part)
    if hit:
        word, dist, count = hit
        return word, dist, log10(count / total)

    return part, len(part), log10(10 / (total * 10 ** len(part)))



calls = 0


def segment(text):
    cache = {}

    def best(rest):
        global calls
        if not rest:
            return 0, 0.0, []
        if rest in cache:
            return cache[rest]

        results = []
        for j in range(1, min(len(rest), max_len) + 1):
            calls += 1
            word, dist, probability = correct(rest[:j])
            dist_sum, probability_sum, parts = best(rest[j:])
            results.append((dist + dist_sum, probability + probability_sum, [word] + parts))

        cache[rest] = min(results, key=lambda it: (it[0], -it[1]))
        return cache[rest]

    return best(text)


for text in ["helloworld", "helwrold", "swordword", "helphello"]:
    calls = 0
    dist, probability, parts = segment(text)
    print(f"{text} -> {' '.join(parts)}  distance={dist} log10(p)={probability:.1f} calls={calls}")
Copy

The text of size $n$ has $n$ distinct suffixes and for each we try at most max_len prefixes, let's call it $L = \text{max\_len}$, so correct only runs $n \cdot L$ times instead of $2^{n-1}$. Regarding memory, we end up with $n$ keys holding $n^2 / 2$ characters, it's not that bad but we can store way less if we change the cache key and find a smarter way to throw away entries we no longer need.

Optimal cache

Let's take a look at our cache key, it's a suffix of the original text without any modifications, we can replace that with just the start index of that suffix and that's an integer. If we key the cache by that integer, the whole cache becomes an array, and we can even fill that array without recursion.

Let's first replace the cache:

def segment(text):
    cache = [None] * (len(text) + 1)

    def best(i):
        if i == len(text):
            return 0, 0.0, []
        if cache[i] is not None:
            return cache[i]

        results = []
        for j in range(i + 1, min(len(text), i + max_len) + 1):
            word, dist, probability = correct(text[i:j])
            dist_sum, probability_sum, parts = best(j)
            results.append((dist + dist_sum, probability + probability_sum, [word] + parts))

        cache[i] = min(results, key=lambda it: (it[0], -it[1]))
        return cache[i]

    return best(0)
Copy

Now the recursion. best(i) calls best(j) with $j > i$, so if we process the string in reverse from the right end, every entry we need is already there in the cache:

def segment(text):
    best = [None] * (len(text) + 1)
    best[len(text)] = (0, 0.0, [])

    for i in reversed(range(len(text))):
        results = []
        for j in range(i + 1, min(len(text), i + max_len) + 1):
            word, dist, probability = correct(text[i:j])
            dist_sum, probability_sum, parts = best[j]
            results.append((dist + dist_sum, probability + probability_sum, [word] + parts))

        best[i] = min(results, key=lambda it: (it[0], -it[1]))

    return best[0]
Copy

Here we have the same amount of calls to correct: $n \cdot L$, but with way less additional data stored.

Now let's look at the inner loop, j never goes past i + max_len, so to compute best[i] we only read the max_len entries right after it. And since i only decreases, once we're done with i-th iteration we don't need best[i + max_len] again. At any point we only need the entry we are writing and the max_len entries after it, max_len + 1 in total.

So we can limit our cache size to max_len + 1 instead of len(text) + 1 and write to slot i % (max_len + 1) instead of just i:

from math import log10

words = [("hello", 120), ("help", 40), ("world", 90), ("sword", 30), ("word", 80)]
d = 2
total = sum(count for _, count in words)
max_len = max(len(word) for word, _ in words) + d



def distance(a, b):
    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]


def search(query):
    best = None
    for word, count in words:
        if abs(len(word) - len(query)) > d:
            continue
        dist = distance(query, word)
        if dist <= d and (best is None or (dist, -count) < (best[1], -best[2])):
            best = (word, dist, count)

    return best


def correct(part):
    hit = search(part)
    if hit:
        word, dist, count = hit
        return word, dist, log10(count / total)

    return part, len(part), log10(10 / (total * 10 ** len(part)))



def segment(text):
    size = max_len + 1
    best = [None] * size
    best[len(text) % size] = (0, 0.0, [])

    for i in reversed(range(len(text))):
        results = []
        for j in range(i + 1, min(len(text), i + max_len) + 1):
            word, dist, probability = correct(text[i:j])
            dist_sum, probability_sum, parts = best[j % size]
            results.append((dist + dist_sum, probability + probability_sum, [word] + parts))

        best[i % size] = min(results, key=lambda it: (it[0], -it[1]))

    return best[0]


for text in ["helloworld", "helwrold", "swordword", "helphello"]:
    dist, probability, parts = segment(text)
    print(f"{text} -> {' '.join(parts)}  distance={dist} log10(p)={probability:.1f}")
Copy

You may notice this version is different from the one Garbe shows in his article. That's because when writing the article I wanted the same recursive -> optimize computations -> optimize memory progression like with the delete generation algorithm, and during the optimization of DP approach I found we can process the suffixes backwards, which is natural when you follow the steps to unfold the recursion. That way we end up with a better version of the algorithm, without a special case for the first iteration or complex comparisons at the same complexity.

Benchmarks

Against the original: Wolf Garbe's SymSpell in C#, .NET 8, Release build. Same dictionary, same queries, same machine. frequency_dictionary_en_82_765.txt from the SymSpell repo, Damerau-Levenshtein, -O ReleaseFast, Zig 0.16.0, Apple M1 Max. Every number is an untimed warmup pass and then the fastest of seven timed ones, the whole suite run three times over and the minimum taken.

Query sets, 5000 words each: hit is dictionary words as they are, typo the same words with one or two random edits, miss 7 to 12 random letters. segment is 200 phrases, 3 to 5 frequent words glued together, every second one carrying a typo. text is a 1200-word document with 5% or 10% of its words misspelled, and fixed is the share of that document that came back right.

C# generates deletes only from the first 7 characters of a word by default, prefixLength = 7. miara has the same option, prefix_length, off by default. Both ran with and without it, 30 on the C# side means every delete is generated. Size is the serialized index for miara and the managed heap after LoadDictionary for C#, both 1024-based megabytes, both including the words and counts. Sources: gen_queries.py, bench.zig, bench.cs - the generator writes the query sets to a file both benchmarks read, so the two sides answer the same words rather than the same recipe.

The four query columns move by up to 2x between runs on a loaded machine, so read them as ratios between rows rather than as absolute times. fixed does not move at all, every configuration on both sides corrects the same 97.0% of the document.

Size is the point of the whole series and it's 28x: 9.38 MB against 260 MB for the same set of deletes at $d = 2$, 15x with the 7-character prefix on both sides. The prefix costs nothing in results, a word within $e$ edits of the query always shares a delete of at most $e$ deletions with it and that stays true when both are cut to the same window, so the same candidates are found and the distance is still computed on the whole words. On all 15,000 queries the prefix 7 index returns the same word at the same distance as the full one.

Build is 2x slower on our side. Sorting all deletes and building the perfect hash costs more than filling a hash map, and it's paid once per dictionary.

Hits are level, around 110 ns on both sides, but only because of a second index. Reaching a known word through the delete index takes three dependent loads - the perfect hash, the Elias-Fano offset pair, the bit-packed dictionary reference - where C# does one hash map probe, and that's the 314 ns on the no exact index row. exactIndex is a minimal perfect hash over the 82,834 words themselves: 194 KB, 3% on top of the index, and it buys 3x on hits and a third off the document workload, so it's on by default. A perfect hash answers for keys it doesn't hold, so the string compare is the check and anything failing it falls through to the normal search.

Typos are 10-45% faster. Deletes come out of the generator by distance and a layer can only hold words at that distance or worse, so once the layer passes the best distance found the search stops, while C# walks all of them. The distance function is bounded on top of that: it trims the common prefix and suffix, fills only the band of width max around the diagonal, and gives up the moment a whole row is past the limit.

Misses are 1.1-1.7x slower, and that one is structural: a perfect hash cannot say absent. A hash map answers a delete that was never indexed at the bucket and stops. PTHash returns a slot for any string we hand it, so every probe has to read the Elias-Fano offset pair, read the group's first dictionary reference and fetch that word before the subsequence check can conclude nothing is there. Three dependent loads against one, once per delete the query generates, and nothing stops early. At $d = 1$, where a query generates about eight deletes, that constant is the whole measurement: 1,333 ns against 771. At $d = 2$ there are hundreds of probes and both sides are bound by memory instead, so it narrows to 1.1x.

Segmentation is $n \cdot L$ searches per phrase and most of them are misses, so it tracks that column, near enough level prefix for prefix. Compare like with like or it will mislead: the $d = 1$ row without a prefix generates twice the deletes of the C# row above it and looks 2x slower for it. On accuracy we recover the original phrase 87.5% of the time against 74%, and the gap is one condition in Garbe's WordSegmentation. A candidate's distance is distanceSum + separatorLength + topEd, but the probability tie-break also fires on distanceSum + topEd, the same sum with the separator dropped, which lets a candidate one edit worse win on probability alone. Delete that disjunct and C# lands on 87.5% too.

Compression is close to free. Dropping Elias-Fano doubles the $d = 2$ index to 18.7 MB and dropping the bit packing as well takes it to 24.5 MB, and misses come out worse rather than better, 18,636 ns against 13,194. The decode is arithmetic on words we already loaded, the cache line it saves is a trip to memory.

Benchmarks New

In this sections we'll compare our zig implementation (miara) which also includes some optimizations that I didn't show in the article against original C# implementation (SymSpell) I'll use the dictionary from the SymSpell repo frequency_dictionary_en_82_765.txt , for both zig and C# i'll use same queries and same CPU, Apple M1 Max (aarch64). Each time measurment is the lowest of seven benchmark passes after a warmup.

Columns:

• hit - average query time for 5000 dictionary words
• typo - the same words with 1 or 2 random edits
• miss - 5000 random strings, 7 to 12 characters
• segment - 200 real sentences of 4 to 9 words from Alice in Wonderland, four variants: spaces removed, spaces removed plus a typo, random add/remove spaces, random add/remove spaces plus a typo
• exact - the percentage of those sentences that were succesfully restored to the original state
• text - 1200-word text where 10% of the words have random edits

Original C# version generates deletes only from the first 7 characters of a word by default - prefixLength = 7. We take a key function instead, for the bench I'll use Keys.ends(7, 0) - 7 prefix, 0 suffix characters and the whole word when not specified. 30 on the C# side means every delete is generated.

Size is the serialized index size for zig (in runtime most of the memory is concentrated in big arrays so there's almost no fragmentation). For C# it is heap bytes after LoadDictionary(...) and forcing the GC to collect all the free memory and compact, in real allplications it would be slightly higher.

Sources: gen_queries.py, bench.zig, bench.cs. The generator writes one query file both benchmarks read, so the two sides answer the same words, and takes the book as a --corpus argument, Project Gutenberg text 11.

Build time is a very unstable reading, so it's here just for the reference. Correctness is the same 97% on text runs for every algorithm and options so I decided not to include that column. On all 15k queries with the prefix 7 index returns the same word at the same distance as the full version.

Size wins is about 5-17x in different scenarios, 3MB vs 27MB, 10MB vs 170MB for the same deletes and distance. This win comes at cost of mutability

Build is ~2-3x slower, sorting the edits and building PHF costs way more than filling a hash map.

Hits are about the same in most cases at 100-150ns, if we go full memory savings mode (disable secondary word hashes) it's about 3x slower - 300ns. But I'm pretty the original algorithm design can be faster that 100ns per hit, we're on par here because of the language choice, C# version makes allocations on hit route but we do not. If we implement hash-map version in zig with no allocations in search route we probably can push that to 30ns territory on a standard english dictionary.

Typos are about 30-55% faster. But again original implementation would be faster if not for allocations.

Misses are level at $d = 1$ with the prefix and 1.4-1.7x faster everywhere else, and this one is only possible bacuse we have a secondary structure where we store 4 additional hash bits per delete to early terminate on unknown strings, because a perfect hash can't differentiate between known/unknown items. The smallest rows have this feature disabled and it's about 1.5-2x slower than with it. But it's only 5% of the index in this case so disabling it makes little sense.

Segmentation is basically $n \cdot L$ searches, but mostly misses. We recover the original phrase 61.5% of the time but C# only 27.0%. That's because zig version assigns different cost to each operation, inserting a space costs less than changing a word, default configuration is 2 per edit, 1 for insert space, 2 for remove space/punctuation.

Final Words Old

So what was this for? I've implemented SymSpell once before, in C++, back in 2019/2020. I had a dictionary of about 300k words and phrases for fixing the text after the OCR, it was composition for cosmetics and food and usually the photos was rough, even with good OCR the results were bad, so when i tried to find solutions that I can reasonably run i came across spellcheckers I've started with a simple trie based algorithm then found SymSpell and build my system on that, but I had to include longer phrases in the dictionary with bigger edit distances up to 4, and when our. That gave me something like 5-10 million distinct deletes at prefix size 9 or 10 and up to 1GB of memory consuption and about 500ms per text sample, i was able to cut this down to 100 mb and slightly faster text segmentation in 300-400ms territory, overall i was happy with the results but i used PHF as a black box and didn't actually learned any of the algorithms. I was just solving a task as quick as possible, but about a year ago I was interested in zig programming language and decided to implement SymSpell in zig with zero external libraries, it took me about 2 months back and after a while i started to write this posts here and this journey allowed me to push it even futher, i often stopped in the middle of article for each algorithm to fix it or improve and here we are and.

Also go check the library code if it was interesting, it contains more optimizations that i described in articles miara Also you may also find out why the library is called like that.

Thanks for reading all of this!

Final Words

So what was this for? I've implemented SymSpell once before, in C++, back in 2019/2020. I had a dictionary of about 300k words and phrases for fixing text after OCR: ingredient lists for cosmetics and food, usually photographed badly and even with a good OCR the results were quite bad. Looking for something I could reasonably use I ended up in spellcheckers (before that I actually tried with a simple trie based algorithm, but that didn't go well), then found SymSpell and built my system on that. But when tuning I had to include longer and longer phrases in the dictionary, with edit distances up to 4-5. That gave me something like 5-10 million distinct deletes at prefix size 9-10 and up to 1GB of memory, segmentation took about 500ms per task. After experimenting with the algorithm and applying different optimization techniques and discoveritng PHF I got it down to 100mb and slightly faster text segmentation. Overall I was happy with the results, but I used the perfect hash as a black box and didn't actually learn any of the algorithms. I was just solving a task as quickly as possible.

About a year ago I got interested in the zig programming language and decided to implement SymSpell and some perfect hash function (I choose PTHash) in zig with zero external libraries. It took me about two months, and after a while I started to write these posts here. That's what let me push it further, I often stopped in the middle of writing an article to go back and fix or improve something. And here we are.

You can always check the library code for more details, it contains some optimizations than I dont't touch in the articles: miara. You may also find out why the library is called like that.

Thanks for reading all of this!