# How Hallelujah IM Uses Damerau-Levenshtein Distance for Fuzzy Spell Checking

> Discover how Hallelujah IM leverages Damerau-Levenshtein distance for fuzzy spell checking by ranking candidate words within an edit distance of three.

- Repository: [dongyuwei/hallelujahim](https://github.com/dongyuwei/hallelujahim)
- Tags: deep-dive
- Published: 2026-02-28

---

**The Hallelujah IM input method combines native macOS spell-checking with phonetic encoding and Damerau-Levenshtein distance calculations to rank candidate words, filtering phonetic matches to only those within an edit distance of three or less.**

The `hallelujahIM` repository implements an intelligent input method for macOS that leverages the **Damerau-Levenshtein distance** algorithm to provide fuzzy spell-checking capabilities. By integrating phonetic encoding with edit distance calculations, the engine can suggest words that account for typos, transpositions, and phonetic similarities.

## The Three-Stage Candidate Generation Pipeline

The spell-checking engine in `src/ConversionEngine.mm` aggregates suggestions from three distinct sources before applying the Damerau-Levenshtein filter.

### Native macOS Spell-Checker Integration

The engine first queries the system `NSSpellChecker` to obtain standard dictionary guesses for the typed buffer. This provides baseline corrections for common misspellings.

```objc
NSSpellChecker *checker = [NSSpellChecker sharedSpellChecker];
NSArray *result = [checker guessesForWordRange:NSMakeRange(0, buffer.length)
                                      inString:buffer
                                      language:@"en"
                      inSpellDocumentWithTag:0];

```

*(see [ConversionEngine.mm L58-L62](https://github.com/dongyuwei/hallelujahIM/blob/master/src/ConversionEngine.mm#L58-L62))*

### Phonex-Based Phonetic Dictionary Lookup

When the input buffer exceeds three characters, the engine performs a phonetic lookup using the **phonex** encoding algorithm. This retrieves words that sound similar to the input, regardless of spelling.

```objc
NSArray *words = (self.phonexEncoded)[[self phonexEncode:buffer]];

```

*(see [ConversionEngine.mm L64-L66](https://github.com/dongyuwei/hallelujahIM/blob/master/src/ConversionEngine.mm#L64-L66))*

### Damerau-Levenshtein Distance Filtering

The phonetic candidates are filtered using the **Damerau-Levenshtein edit distance**, which calculates the minimum number of single-character operations (insertions, deletions, substitutions, and transpositions) required to transform one string into another.

The implementation relies on the third-party **MDCDamerauLevenshtein** framework, which adds the `mdc_levenshteinDistanceTo:` category method to `NSString`.

```objc
NSUInteger distance = [text mdc_levenshteinDistanceTo:word];
if (distance <= 3) {
    [mutableArray addObject:@{@"w": word, @"d": @(distance)}];
}

```

*(see [ConversionEngine.mm L141-L148](https://github.com/dongyuwei/hallelujahIM/blob/master/src/ConversionEngine.mm#L141-L148))*

## Ranking and Merging Candidates

After filtering phonetic matches by edit distance, the engine sorts candidates by their Damerau-Levenshtein score in ascending order (closest matches first).

```objc
NSSortDescriptor *descriptor = [[NSSortDescriptor alloc] initWithKey:@"d" ascending:YES];
NSArray *sorted = [mutableArray sortedArrayUsingDescriptors:@[descriptor]];
// …
[finalResult addObjectsFromArray:[self subarrayWithRang:wordsWithSimilarPhone range:range]];

```

*(see [ConversionEngine.mm L149-L170](https://github.com/dongyuwei/hallelujahIM/blob/master/src/ConversionEngine.mm#L149-L170))*

The final list deduplicates entries, truncates to a maximum of 50 suggestions, and inserts the original user input at the first position. This hybrid approach ensures that phonetically similar words with minimal edit distance surface alongside native spell-checker recommendations.

## Summary

- The Hallelujah IM engine combines native macOS spell-checking, phonex phonetic encoding, and Damerau-Levenshtein distance calculations to generate fuzzy matches.
- Phonetic candidates are filtered using the `mdc_levenshteinDistanceTo:` method from the MDCDamerauLevenshtein framework, with a maximum threshold of 3 edits.
- Candidates are ranked by ascending edit distance and merged with native spell-checker suggestions in `src/ConversionEngine.mm`.
- The algorithm accounts for insertions, deletions, substitutions, and transpositions, making it robust against common typing errors.

## Frequently Asked Questions

### What is Damerau-Levenshtein distance?

**Damerau-Levenshtein distance** is a string metric that measures the minimum number of single-character operations required to transform one word into another. Unlike the standard Levenshtein distance, it includes **transpositions** (swapping adjacent characters) as a single operation, making it particularly effective for catching common typing errors such as "hte" instead of "the".

### How does Hallelujah IM calculate edit distance?

The project delegates distance calculations to the **MDCDamerauLevenshtein** CocoaPod, which implements the algorithm as a category on `NSString`. In `src/ConversionEngine.mm`, the engine calls `[text mdc_levenshteinDistanceTo:word]` to compute the distance between user input and phonetic candidates, then filters results to only those with a distance of three or less.

### Why combine phonex encoding with edit distance?

**Phonex encoding** reduces words to phonetic fingerprints, allowing the engine to retrieve candidates that sound like the input regardless of spelling. However, phonetic matches can include words that are phonetically similar but orthographically distant. By applying **Damerau-Levenshtein distance** as a secondary filter, the engine eliminates phonetic false positives and surfaces only those candidates that are both phonetically and orthographically close to the typed buffer.

### What is the maximum edit distance threshold used?

The implementation in `ConversionEngine.mm` uses a **hard threshold of 3** for the Damerau-Levenshtein distance. Candidates with a distance greater than 3 are discarded, while those with a distance of 0 (exact match), 1, 2, or 3 are retained, sorted by distance, and presented to the user. This threshold balances recall (catching reasonable typos) against precision (avoiding irrelevant suggestions).