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

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.

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

(see 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.

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

(see 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.

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

(see 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).

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)

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).

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}