Multiple word spelling correction

Question

Correcting one word spelling mistakes (both non-word & real-word mistakes) is easy:

P(w|c) P(c)

Where w is the incorrectly spelled word and c is the candidate we're trying to match, such that the candidate is a one word token.

But in Google, when you enter something like spelligncheck, it corrects the word into two different words. Now, P(w|c) is easy here, if i use levenshtein distance. But that means i can't have one word (one token, rather) candidates anymore. So this will increase the size of my dictionary exponentially.

Moreover when I enter app le Google corrects it to apple...

So what is the best way of doing multiple word spelling correction, given a one-token dictionary?

Answer 1

I think you're looking for something like the pspell module.

I've prepared this demo to show you how almost achieve what you want - it clearly could be improved a lot more:

<?php

class SpellChecker
{
    public function __construct($lang)
    {
        $this->pspell = pspell_new($lang);
    }

    public function check($word)
    {
        return pspell_check($this->pspell, $word);
    }

    public function closest_suggestion($word)
    {
        $suggestions = pspell_suggest($this->pspell, $word);
        $similar_sounding_words = array_filter($suggestions,
            function ($current_word) use ($word) {
                return (metaphone($current_word) == metaphone($word));
            });

        // No similar sounding words, just return the first suggestion...
        if (count($similar_sounding_words) == 0) {
            return $suggestions[0];
        }

        // Return the closest match against similar sounding words...
        return array_reduce($similar_sounding_words,
            function ($prev, $next) use ($word) {
                return (is_array($prev))
                    ? $next
                    : ((levenshtein($prev, $word) < levenshtein($next, $word))
                          ? $prev
                          : $next);
            });
    }
}

$spellchecker = new SpellChecker('en');

foreach (array('spelligncheck', 'app le') as $word) {
    if (!$spellchecker->check($word)) {
        print "Closest match for \"$word\": {$spellchecker->closest_suggestion($word)}\n";
    }
}

I've tried here and got the following result:

Closest match for "spelligncheck": spellchecker
Closest match for "app le": apple

Good luck! :)