KO | EN

GitLite

Minimalist Open Source Repository Search Engine

gitlite — search

#codex #developer-tools #typescript #ai-agents #claude-code #python #mcp #react #cli #macos #ai-agent #deepseek-harness

symspell-c99

★ 30 Open GitHub ↗

Fast spell-checking library - Pure C99 implementation of SymSpell algorithm

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# SymSpell C99

**A blazingly fast spell-checking library** - Pure C99 implementation of Wolf Garbe's SymSpell algorithm.

[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)
[![Language](https://img.shields.io/badge/language-C99-blue.svg)](https://en.wikipedia.org/wiki/C99)
[![POSIX](https://img.shields.io/badge/POSIX-compliant-green.svg)](https://en.wikipedia.org/wiki/POSIX)

**By Suman Pokhrel**

---

## Why SymSpell?

SymSpell is **1 million times faster** than traditional spell-checkers. Instead of generating all possible corrections for a misspelling, it pre-computes deletions of dictionary words, enabling lightning-fast lookups.

Original algorithm by [Wolf Garbe](https://github.com/wolfgarbe/SymSpell)

---

## Features

- ⚡ **Fast**: Average lookup time ~3µs (benchmarked, ~10x faster than the reference C# implementation)
- 🎯 **Accurate**: 82-84% correction rate on standard test sets
- 🧹 **Clean**: Zero compiler warnings, ~700 lines of well-structured code
- 🌐 **Portable**: POSIX-compliant, works on any Unix system
- ✅ **Complete**: Includes tests, benchmarks, and dictionary tools
- 📦 **Self-contained**: No external dependencies

---

## Quick Start
```bash
make
./test_symspell dictionaries/dictionary.txt
```

Interactive mode:
```
Enter words to correct (or 'quit' to exit):
recieve
  Suggestions:
    receive (distance=1, iwf=7.234567, prob=0.001234, freq=234567)
```

---

## Usage
```c
#include "symspell.h"

// Create dictionary with max edit distance=2, prefix length=7
symspell_dict_t* dict = symspell_create(2, 7);

// Load dictionary (86k words optimized for spell-checking)
symspell_load_dictionary(dict, "dictionaries/dictionary.txt", 0, 1);

// Lookup suggestions
symspell_suggestion_t suggestions[5];
int count = symspell_lookup(dict, "speling", 2, suggestions, 5);

// Print results
for (int i = 0; i < count; i++) {
    printf("%s (distance=%d)\n", 
           suggestions[i].term, 
           suggestions[i].distance);
}

// Cleanup
symspell_destroy(dict);
```

---

## Performance
```
Dictionary load time:    ~500ms (86,060 words, 688,710 deletes)
Average lookup time:     ~3.2µs (4,304-word Wikipedia misspelling benchmark)
Correction accuracy:     84.0%
Dictionary size:         86,060 words
Memory usage:            ~45MB (with deletes index)
```

Benchmarked head-to-head against the reference C# SymSpell implementation on the same dataset (.NET 10, Release build, JIT warmed to steady-state): this C99 port now loads the dictionary ~40% faster (~500ms vs. ~820ms) and edges out the reference implementation on lookup speed as well (~3.2µs vs. ~3.5µs average).

Tested on Apple Silicon (M-series), comparable results on x86.

---

## Building

**Requirements:**
- C99 compiler (GCC, Clang)
- Make
- POSIX-compliant system (Linux, macOS, BSD)

**Compile:**
```bash
make              # Build test and benchmark programs
make test         # Build and run tests
make benchmark    # Build and run benchmark
make clean        # Remove built programs
```

**Manual compilation:**
```bash
gcc -std=c99 -O2 -Iinclude test/test_symspell.c src/symspell.c -o test_symspell
```

---

## Understanding Results

### Edit Distance Matters

SymSpell returns suggestions based on **edit distance** (number of character changes needed):
```bash
# "helo" with max_distance=1
$ ./test_symspell dictionaries/dictionary.txt
> helo
  held (distance=1)    # One substitution: o→d

# "helo" with max_distance=2
$ ./test_symspell dictionaries/dictionary.txt --max-distance 2
> helo
  hello (distance=2)   # Two insertions: +l, +o
  held (distance=1)    # Still shown as closer match
```

**The algorithm prefers closer matches.** If you want "hello" as a suggestion, increase `max_edit_distance` when calling `symspell_lookup()`.

### Why Not 100% Accuracy?

Real-world typos are ambiguous:
- "helo" → "held" or "hello"?
- "teh" → "the" or "tea"?
- "there" → correct word or "their"?

Even commercial spell-checkers (Microsoft Word, Google Docs) achieve 80-85% accuracy on standardized test sets because:
1. Language is inherently ambiguous
2. Context is needed for many corrections
3. Trade-offs exist between precision and recall

Our 82-84% matches the original SymSpell paper and is competitive with commercial solutions.

### Performance Context

"~3µs average" means:
- ✅ 300x faster than Python implementations (~1000µs)
- ✅ 3000x faster than traditional approaches (~10000µs)
- ✅ Can check 1000 words in ~3ms (imperceptible to users)
- ✅ Real-time spell-checking with zero UI lag

For most applications, this is more than fast enough.

---

## Dictionaries

**Main dictionary** (`dictionaries/dictionary.txt`): 86,060 words
- Optimized for spell-checking accuracy (82-84%)
- Balanced across multiple test sets
- Recommended for general use

**Extras dictionary** (`dictionaries/dictionary-extras.txt`): 25,327 words
- Technical terms and acronyms
- For keyword extraction and IWF scoring
- DO NOT use for spell-checking (reduces accuracy)

**Building custom dictionaries:**
See `dictionaries/reference/` for source materials and tools.
Full documentation in `docs/DICTIONARY.md`.

---

## Project Structure
```
symspell-c99/
├── src/
│   └── symspell.c          # Implementation (~700 lines)
├── include/
│   ├── symspell.h          # Public API
│   ├── hash.h              # Hash table implementation
│   ├── xxh3.h              # xxHash for fast hashing
│   └── posix.h             # POSIX compatibility layer
├── test/
│   ├── test_symspell.c     # Interactive test program
│   ├── benchmark_symspell.c # Performance benchmarks
│   └── data/               # Test datasets
├── dictionaries/
│   ├── dictionary.txt      # Main 86k word dictionary
│   └── reference/          # Dictionary building tools
└── docs/
    ├── SYMSPELL.md         # Algorithm details
    └── DICTIONARY.md       # Dictionary customization
```

---

## Documentation

- **[SYMSPELL.md](docs/SYMSPELL.md)** - Algorithm explanation and implementation details
- **[DICTIONARY.md](docs/DICTIONARY.md)** - Dictionary building and customization guide
- **[dictionaries/README.md](dictionaries/README.md)** - Dictionary overview

---

## Algorithm

SymSpell uses **Symmetric Delete** spelling correction:

1. **Pre-computation**: Generate all deletions up to edit distance N for each dictionary word
2. **Lookup**: Generate deletions of the input word
3. **Match**: Find dictionary words that share these deletions
4. **Rank**: Sort by edit distance and word frequency

This trades memory for speed - pre-computing deletions makes lookups extremely fast.

---

## Testing

Run the test program:
```bash
./test_symspell dictionaries/dictionary.txt
```

Run benchmarks:
```bash
./benchmark_symspell dictionaries/dictionary.txt test/data/symspell/misspellings/misspell-codespell.txt
```

### Benchmark Test Datasets

The project includes standardized test datasets for accuracy and performance benchmarks. All test sets are located in `test/data/symspell/misspellings/`:

**Test Files and Sources:**

- **`misspell-codespell.txt`** - From [Codespell Project](https://github.com/codespell-project/codespell/blob/main/codespell_lib/data/dictionary.txt)  
  Common misspellings found in source code and documentation (63,704 entries)

- **`misspell-wikipedia.txt`** - From [Wikipedia: Lists of Common Misspellings/For Machines](https://en.wikipedia.org/wiki/Wikipedia:Lists_of_common_misspellings/For_machines)  
  Community-sourced misspellings from Wikipedia editors (4,305 entries)

- **`misspell-words.go.txt`** - From [client9/misspell words.go](https://raw.githubusercontent.com/client9/misspell/master/words.go)  
  Go-based spelling corrector dataset, derived from Wikipedia + additional curated errors (31,139 entries)

- **`misspell-microsoft.txt`** - From [Microsoft Research Spelling-Correction Data](http://www.microsoft.com/downloads/details.aspx?displaylang=en&FamilyID=f14a3359-b62d-4b96-9858-71c378f07806)  
  Real human typing errors captured from keystroke logs via Amazon Mechanical Turk (23,031 entries)

These test sets provide comprehensive coverage across different domains:
- **Technical/code** (Codespell)
- **General language** (Wikipedia) 
- **Programming context** (client9/misspell)
- **Real typing errors** (Microsoft Research)

**Accuracy Results:** 82-84% correction rate across all test sets, matching the original SymSpell paper.

---

## FAQ

**Q: Why does "helo" suggest "held" instead of "hello"?**

A: "held" has edit distance 1 (one character change), while "hello" has edit distance 2 (two insertions). SymSpell prefers closer matches. Increase `max_edit_distance` to get more suggestions.

**Q: Why only 82-84% accuracy?**

A: This is competitive with commercial spell-checkers and matches the original SymSpell paper. Perfect accuracy is impossible due to language ambiguity.

**Q: Compilation fails with undefined reference to `log`**

A: Add `-lm` flag to link the math library:
```bash
gcc -std=c99 -O2 -Iinclude test/test_symspell.c src/symspell.c -lm -o test_symspell
```

---

## License

MIT License - See [LICENSE](LICENSE) file for details.

This implementation is independent but follows the algorithm described in:
- [SymSpell](https://github.com/wolfgarbe/SymSpell) by Wolf Garbe (MIT License)

---

## Credits

- **Algorithm**: [Wolf Garbe](https://github.com/wolfgarbe) - Creator of SymSpell
- **Implementation**: Suman Pokhrel - Pure C99 port

Special thanks to [Dr. James Freeman](https://github.com/tachyon-ii) for his mentorship and guidance on this project.

---

## Author

**Suman Pokhrel**

- GitHub: [@sumanpokhrel-11](https://github.com/sumanpokhrel-11)
- Email: 11pksuman@gmail.com

---

## Contributing

This is the **first pure C99 implementation** of SymSpell. Contributions welcome:

- Bug reports and fixes
- Performance improvements
- Dictionary enhancements
- Documentation improvements
- Platform-specific optimizations

Please open an issue or pull request on GitHub!

---

## See Also

- [Original SymSpell (C#)](https://github.com/wolfgarbe/SymSpell) - Wolf Garbe's original implementation
- [SymSpell Ports](https://github.com/wolfgarbe/SymSpell#ports) - Implementations in other languages

---

*This is the first and only pure C99 implementation of SymSpell, designed for performance, portability, and clean code.*

symspell-c99

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README