symspell_rs v7 introduces both significant implementation changes to SymSpell as well as algorithmic changes to the Damerau-Levenshtein calculation between v6.8.4 vs. v7.0.1.
The resulting performance improvements are measured with the new benchmark suite and discussed below.

Changes

Improved Damerau-Levenshtein calculation, optimal string alignment (OSA) variant

• Optimized SymSpell v7 damerau_levenshtein_osa by using bit-parallel OSA (Hyyrö 2003), making it 11x faster than SymSpell v6.8.4 damerau_levenshtein_osa.
• Optimized SymSpell v7 damerau_levenshtein_osa_fallback by using the multi-word block version of the bit-parallel OSA (Hyyrö 2003), to cover any length., making it 7x faster than than SymSpell v6.8.4 damerau_levenshtein_osa for terms > 64 chars.
• Exposed damerau_levenshtein_osa as a public method for standalone use.

Improved SymSpell implementation: internal storage, allocation free, shared term table, lightweight hasher

• Internal storage: words now maps terms to ids, and counts live in a new term table. Serialized dictionaries from previous versions (serde feature) are not compatible.
• The derived PartialEq on SymSpell compares term ids, so dictionaries with the same content but a different insertion order compare unequal.
• ASCII input now takes an allocation-free fast path: stack-based candidates, borrowed hits, and Suggestion strings created only for the returned results (after sort and max_results). Non-ASCII input uses a char-based path that shares the same verification code.
• Delete buckets store compact 8-byte entries (term id, length, ASCII flag) that refer to a shared term table, instead of a heap copy of the term per delete. This lowers memory use and removes pointer chasing.
• The deletes map uses a lightweight hasher, since its keys are already 32-bit hashes.

Verbose Benchmark setup

• Benchmark harness: divan with a tracking global allocator. Results below are the figures printed to stderr by the benchmark.
• 81 lookup experiments per version: English frequency dictionaries with 30k, 82k and 500k entries × prefix_length 5, 6, 7 × maximum edit distance 1, 2, 3 × Verbosity Top, Closest, All. The dictionary is rebuilt for each maximum edit distance (maximum dictionary edit distance = maximum edit distance), which gives 27 dictionary builds per version.
• Average latency = average time per lookup() call. Speedup = latency of v6.8.4 ÷ latency of current (higher is better).
• Build time = time to build the dictionary. Resident memory = resident memory after the build. Peak memory = maximum memory consumption during the build.
• Charts use a logarithmic y-axis where values span orders of magnitude (latency, build memory across dictionary sizes).
• Verbose benchmark based on divan: cargo bench --bench verbose --features gxhash

Basic benchmark setup

• Lookup latency experiments (162 in total): the 30k, 82k and 500k English frequency dictionaries × prefix_length 5, 6, 7 × maximum edit distance 1, 2, 3 × Verbosity Top, Closest, All × {this version, symspell_rs 6.8.4}.
• Load dictionary time experiments (27 in total): the 30k, 82k and 500k English frequency dictionaries × prefix_length 5, 6, 7 × maximum edit distance 1, 2, 3
• Damerau-Levenshtein OSA latency experiments (6 in total): maximum edit distance 1, 2, 3 x bit-parallel OSA, multi-word block bit-parallel OSA
• Basic benchmark: cargo bench --bench basic --features gxhash

Test data

noisy_query_en_1000.txt

For the query we use the first 1000 unique words from Norvig’s text corpus big.txt.

For each word a random number of edits in the range 0..Min(word.length/2 , 4) is chosen. For each edit a random type of edit (delete, insert random char, replace with random char, switch adjacent chars) is applied at a random position within the word. After the edits no duplicates and words with length<2 are allowed.

frequency_dictionary_en_30_000.txt

These are the 29,159 unique words from Norvig’s text corpus big.txt, together with their frequency in that corpus.

frequency_dictionary_en_82_765.txt

The frequency_dictionary_en_82_765.txt was created by intersecting the two lists mentioned below. By reciprocally filtering only those words which appear in both lists are used. Additional filters were applied and the resulting list truncated to ≈ 80,000 most frequent words.

• Google Books Ngram data (License) : Provides representative word frequencies
• SCOWL - Spell Checker Oriented Word Lists (License) : Ensures genuine English vocabulary

frequency_dictionary_en_500_000.txt

These are the most frequent 500,000 words from the English One Million list from Google Books Ngram data, together with their frequency.

All three test data files are released on GitHub.

Summary: what improved in the new version

• Faster Damerau-Levenshtein calculation, (optimal string alignment (OSA) variant). All 3 Damerau-Levenshtein experiments are faster, by a geometric mean of 10.9× (range 10.0× to 12.2×).
  • damerau_levenshtein_osa using bit-parallel OSA (Hyyrö 2003) (length <= 64 chars): 10.9x on average (10.0× to 12.2×)
  • damerau_levenshtein_osa_fallback using the multi-word block version of the bit-parallel algorithm (Hyyrö 2003) (any length): 6.9x faster on average (6.7x to 8.0x)
  • max edit distance 1: 12.2× (OSA), 8.0 (OSA fallback)
  • max edit distance 2: 10.6× (OSA), 6.2 (OSA fallback)
  • max edit distance 3: 10.0× (OSA), 6.7 (OSA fallback)
• Faster lookups in every experiment. All 81 lookup experiments are faster, by a geometric mean of 2.8× (range 1.5× to 5.9×).
  • Verbosity::Top: 3.0× on average (1.8× to 5.9×)
  • Verbosity::Closest: 2.9× on average (1.5× to 4.2×)
  • Verbosity::All: 2.7× on average (1.6× to 4.8×)
  • max edit distance 1: 2.4× on average (1.5× to 3.7×)
  • max edit distance 2: 2.8× on average (2.1× to 5.2×)
  • max edit distance 3: 3.4× on average (1.8× to 5.9×)
  • 30,000-word dictionary: 2.9× on average (1.5× to 4.8×)
  • 82,765-word dictionary: 3.0× on average (1.8× to 5.9×)
  • 500,000-word dictionary: 2.6× on average (1.6× to 3.5×)
• Much lower memory use during lookups. Peak heap allocation per lookup is on average only 31% of v6.8.4 (best case 17%, worst case 77%).
  • Verbosity::Top: 18% of v6.8.4 on average (17% to 18%)
  • Verbosity::Closest: 32% of v6.8.4 on average (18% to 73%)
  • Verbosity::All: 52% of v6.8.4 on average (33% to 77%)
• Roughly 40% less memory for the dictionary. Resident memory after the build is on average 62% of v6.8.4 (best case 48%, worst case 83%). Peak memory during the build is on average 64% of v6.8.4 (48% to 88%).
  • Largest example, 500k dictionary, prefix 7, edit distance 3: resident memory 874 MiB → 436 MiB, peak 874 MiB → 436 MiB, build time 14.20 s → 12.60 s.
• Build time is on par or slightly better. On average the build is 1.09× as fast as v6.8.4 (range 0.86× to 1.58×). 6 of 27 builds are marginally slower (at most 17%), so the memory savings come at no real build-time cost.

💡 The interesting part:

In the first step, we improved the Damerau-Levenshtein calculation only, while letting the SymSpell implementation unchanged. An 11x faster edit distance gave only a 20% speedup for SymSpell. That told us two things: 1️⃣ SymSpell’s makes spelling correction latency largely independent of raw edit distance performance. The symmetric delete algorithm already avoids most of that work. 2️⃣ Further performance gains had to come from SeekStorm implementation improvements rather than edit distance calculation optimization. We did, and achieved 300% speedup for SymSpell.

Damerau-Levenshtein (OSA) latency

• strsim v0.11.1 osa_distance uses a vanilla implementation of the Damerau-Levenshtein algorithm.
• SymSpell v6.8.4 damerau_levenshtein_osa uses a vanilla implementation of the Damerau-Levenshtein algorithm.
• SymSpell v7.0.1 damerau_levenshtein_osa uses bit-parallel OSA (Hyyrö 2003) (length <= 64 chars)
• SymSpell v7.0.1 damerau_levenshtein_osa_fallback uses multi-word block version of the bit-parallel OSA (Hyyrö 2003) (any length)

Using noisy_query_en_1000.txt, calculation the edit distance between misspelled_string and corrected_string, for the given maximum edit distance.

Lookup latency

30,000-word dictionary

30,000 words, Verbosity::Top

30,000 words, Verbosity::Closest

30,000 words, Verbosity::All

82,765-word dictionary

82,765 words, Verbosity::Top

82,765 words, Verbosity::Closest

82,765 words, Verbosity::All

500,000-word dictionary

500,000 words, Verbosity::Top

500,000 words, Verbosity::Closest

500,000 words, Verbosity::All

Dictionary build

Build time

Resident memory

Peak memory during build

Peak heap allocation during lookups

Peak heap allocation of a single lookup (tracking global allocator); lower is better. Ratio = current ÷ v6.8.4.

30,000-word dictionary

82,765-word dictionary

500,000-word dictionary

Notes

• Each lookup experiment is a short run, so single cells can be noisy; the trend is consistent across all 81 experiments.

Related Blog Posts: Algorithm, Benchmarks, Applications

1000x Faster Spelling Correction algorithm
Fast approximate string matching with large edit distances in Big Data
Very fast Data cleaning of product names, company names & street names
Sub-millisecond compound aware automatic spelling correction
SymSpell vs. BK-tree: 100x faster fuzzy string search & spell checking
Fast Word Segmentation for noisy text
The Pruning Radix Trie — a Radix trie on steroids

Application

Possible application fields of the SymSpell algorithm are those of fast approximate dictionary string matching: spell checkers for word processors and search engines, correction systems for optical character recognition, natural language translation based on translation memory, record linkage, de-duplication, matching DNA sequences, fuzzy string searching and fraud detection.

For a single user or for small edit distances other algorithms might just be fine. But for search engines and search-as-a-service search API where you have to serve thousands of concurrent users, while still maintaining a latency of a few milliseconds, and where spelling correction is not even the main procession task, but only one of many components in query preprocessing, you need the fastest spelling correction you can get.

Source code

The Rust implementation of the Symmetric Delete Spelling Correction algorithm is released on GitHub as Open Source under the MIT license.

The C# implementation of the Symmetric Delete Spelling Correction algorithm is released on GitHub as Open Source under the MIT license.

Ports

There are ports in C, C++, Crystal, Go, Haskell, Java, Javascript, Julia, Kotlin, Objective-C, PHP, Python, Ruby, Rust, Scala, Swift and Zig available.