Project: a spell checker, three ways

Way 2: a hash set

A set is a hash table, the structure you built in the data structures lesson: the word's hash picks a bucket, and only that bucket is searched. A lookup takes about the same time whether the set holds 60 words or 60 million, and adding a word is cheap too. The price is memory: a hash table keeps spare empty slots so collisions stay rare. And it has no order, so it can't answer "which words come after fen?" without looking at all of them.

Way 3: a trie

A trie (said "tree", from re*trie*val) stores words letter by letter in a tree of nested dictionaries. Words that share a beginning share a path: ridge, ridges and ridgeline all walk through r, i, d, g, e. A marker at the end of a path, here the key "$", says "a word ends here".

END = "$"

def trie_add(trie, word):
    node = trie
    for ch in word:
        node = node.setdefault(ch, {})    # walk down, creating the path as needed
    node[END] = True

def trie_has(trie, word):
    node = trie
    for ch in word:
        if ch not in node:
            return False
        node = node[ch]
    return END in node

trie = {}
for w in ["ridge", "ridges", "ridgeline", "rim"]:
    trie_add(trie, w)
print(trie_has(trie, "ridge"), trie_has(trie, "ridg"), trie_has(trie, "rims"))
print(list(trie["r"]["i"].keys()))       # after "ri": d or m

A lookup takes one step per letter, whatever the dictionary's size. "ridg" walks the whole path but finds no end marker, so it's a prefix, not a word. That's the trie's real strength: every word starting with a prefix sits below one node.

END = "$"


def trie_add(trie, word):
    node = trie
    for ch in word:
        node = node.setdefault(ch, {})
    node[END] = True


def with_prefix(trie, prefix):
    return [prefix]


trie = {}
for w in ["ridge", "ridges", "ridgeline", "rim", "pine"]:
    trie_add(trie, w)
print(with_prefix(trie, "rid"))

Measure, don't guess

Now the comparison. time.perf_counter times the build and 20,000 lookups (half real words, half not), and tracemalloc measures how much memory each structure allocates while it's built. Run it and compare the columns.

import bisect
import random
import time
import tracemalloc

def make_words(n, seed=0):
    rng = random.Random(seed)
    parts = ["al", "der", "fen", "hol", "low", "mes", "ra", "ridge", "pine", "gap", "tor", "ka", "lin", "mo", "ves", "tra"]
    words = set()
    while len(words) < n:
        words.add("".join(rng.choice(parts) for _ in range(rng.randint(2, 4))))
    return sorted(words)

END = "$"
def build_trie(words):
    trie = {}
    for w in words:
        node = trie
        for ch in w:
            node = node.setdefault(ch, {})
        node[END] = True
    return trie
def trie_has(trie, w):
    node = trie
    for ch in w:
        if ch not in node:
            return False
        node = node[ch]
    return END in node
def in_sorted(words, w):
    i = bisect.bisect_left(words, w)
    return i < len(words) and words[i] == w

WORDS = make_words(60_000)
rng = random.Random(1)
queries = rng.sample(WORDS, 10_000) + [w + "x" for w in rng.sample(WORDS, 10_000)]

ways = {
    "sorted list": (lambda ws: sorted(ws), in_sorted),
    "set": (lambda ws: set(ws), lambda s, w: w in s),
    "trie": (build_trie, trie_has),
}
for name, (build, has) in ways.items():
    tracemalloc.start()
    t0 = time.perf_counter()
    store = build(WORDS)
    built = time.perf_counter() - t0
    memory = tracemalloc.get_traced_memory()[0]
    tracemalloc.stop()
    t0 = time.perf_counter()
    hits = sum(has(store, q) for q in queries)
    looked = time.perf_counter() - t0
    print(f"{name:>11}: build {built * 1000:6.0f} ms   20,000 lookups {looked * 1000:5.0f} ms   memory {memory / 1e6:5.1f} MB   hits {hits}")

Every way finds the same 10,000 hits, so all three are correct. The numbers vary from run to run, but the pattern holds. The set is fastest to look up, and costs more memory than the sorted list's compact array. (The memory count leaves out the word strings themselves, which all three share.) The sorted list is smallest, with lookups several times slower than the set's. The trie, built from thousands of small dictionaries, is the slowest to build and to search (each letter is a separate dictionary step in Python), and by far the biggest. Real tries are written in compact arrays, not dictionaries, which is why phone keyboards can afford them.

Numbers like these are a starting point for a choice, not the whole of it. Ask what else the feature needs:

Measure on data shaped like yours, too: real dictionaries share far more prefixes than random syllables, which makes tries smaller, and lookups of real typos fail at different depths than invented ones.

Suggesting the right word

When a word isn't found, a checker suggests close words. The edit distance from the algorithms lesson measures closeness, but comparing a typo with all 60,000 words is slow. A neat trick turns it around: generate every string one edit away from the typo (each letter deleted, each neighboring pair swapped, each letter replaced and each letter inserted), then keep the ones that are real words. Here a swap means trading two neighboring letters, so tnet to tent is one edit; the algorithms lesson's edit distance has no such step and counts it as two replacements. That's a few hundred set lookups, and the set makes each one nearly free.

import string

def one_edit_away(word):
    letters = string.ascii_lowercase
    splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
    deletes = [a + b[1:] for a, b in splits if b]
    swaps = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b) > 1]
    replaces = [a + c + b[1:] for a, b in splits if b for c in letters]
    inserts = [a + c + b for a, b in splits for c in letters]
    return set(deletes + swaps + replaces + inserts)

dictionary = {"tent", "tents", "trail", "trial", "stove", "store", "lantern", "rope"}
for typo in ["tnet", "trial", "stve", "lnatren", "xyz"]:
    print(typo, sorted(one_edit_away(typo) & dictionary))

tnet finds tent by one swap, and stve finds stove by one insert. Notice that trial is spelled correctly but is also one swap from trail: a checker only suggests for words that aren't in the dictionary. lnatren is two swaps from lantern, so one edit finds nothing; applying one_edit_away to every result gives the words two edits away, a much bigger set, usually tried only when one edit finds nothing.