Categoria Ferramentas

How to Write a Spelling Corrector


Peter Norvig, Google’s Director of Research, wrote an article explaining how to write a spelling corrector. He wrote using python in 21 lines. After this, many people implemented in other languages, I wrote in C to compare the amount of lines and speed.

I quote some of Norvig’s paragraphs below:

“In the past week, two friends (Dean and Bill) independently told me they were amazed at how Google does spelling correction so well and quickly. Type in a search like [speling] and Google comes back in 0.1 seconds or so with Did you mean: spelling. (Yahoo and Microsoft are similar.) What surprised me is that I thought Dean and Bill, being highly accomplished engineers and mathematicians, would have good intuitions about statistical language processing problems such as spelling correction. But they didn’t, and come to think of it, there’s no reason they should: it was my expectations that were faulty, not their knowledge.

I figured they and many others could benefit from an explanation. The full details of an industrial-strength spell corrector like Google’s would be more confusing than enlightening, but I figured that on the plane flight home, in less than a page of code, I could write a toy spelling corrector that achieves 80 or 90% accuracy at a processing speed of at least 10 words per second.

So here, in 21 lines of Python 2.5 code, is the complete spelling corrector:”

$file = file("http://marcelotoledo.com/stuff/spell/spell.py");
foreach ($file as $line) {
    echo $line;
}

And here is my version in C:

$file = file("http://marcelotoledo.com/stuff/spell/spell.c");
foreach ($file as $line) {
    echo $line;
}

The code was pasted, but you can download it here. You might be asking, where is the 184 lines of code? I used the same metric as Norvig, no blank lines, no main function and reduced as much as possible the extras, but keeping the readability and keeping the same code, see the result here.

“The code defines the function correct, which takes a word as input and returns a likely correction of that word. For example:”

In python:

>>> correct('speling')
'spelling'
>>> correct('korrecter')
'corrector'

In C:

$ ./spell boxng
Did you mean "boxing"?

$ ./spell speling
Did you mean "spelling"?

I knew how fast was Norvig’s code, when I first finished mine, I was very impressed with Python simplicity in 21 lines of code and it’s speed, very similar to C, in the beginning. I used the same 6.3MB dictionary for the initial tests:

$ du -sh big.txt
6,3M    big.txt

Python:

$ time python spell.py
spelling

real    0m1.911s
user    0m1.340s
sys     0m0.048s

C:

$ time ./spell speling
Did you mean "spelling"?

real    0m0.892s
user    0m0.812s
sys     0m0.076s

Result:

C was 1.01 seconds or 114.2% faster.

I really wanted to see how bad it was going to get if I grew up the dictionary. So I did tests with 50MB, 100MB, 168MB and 149MB.

The results using 50MB dictionary:

$ du -sh big.txt
50M     big.txt

Python:

$ time python spell.py
spelling

real    0m17.892s
user    0m11.353s
sys     0m0.684s

C:

$ time ./spell speling
Did you mean "spelling"?

real    0m6.896s
user    0m6.636s
sys     0m0.244s

Result:

C was 10.99 seconds or 159.4% faster.

The results using 100MB dictionary:

$ du -sh big.txt
100M    big.txt

Python:

$ time python spell.py
spelling

real    1m25.579s
user    0m24.262s
sys     0m1.704s

C:

$ time ./spell speling
Did you mean "spelling"?

real    0m14.474s
user    0m13.425s
sys     0m0.496s

Result:

C was 1 minute and 11.10 seconds or 491.2% faster.

The results using 168MB dictionary:

$ du -sh huge.txt
168M    huge.txt

Python:

$ time python spell.py

Killed

C:

$ time ./spell speling
Did you mean "speling"?

real    0m44.627s
user    0m21.689s
sys     0m1.324s

Result:

Couldn't compare, Python process took to much time and was killed by kernel.

Seeing this I tried with a smaller dictionary 149MB:

$ du -sh big.txt
149M    big.txt

Python:

$ time python spell.py
Killed

C:

$ time ./spell speling
Did you mean "spelling"?

real    0m24.974s
user    0m19.149s
sys     0m0.852s

Result:

Couldn't compare, Python process took to much time and was killed by kernel.

“Other computer languages:

After I posted this article, various people wrote versions in different programming languages. While the purpose of this article was to show the algorithms, not to highlight Python, the other examples may be interesting for those who like comparing languages:”

Language Lines of Code Author (and link to implementation)
Python 21 Peter Norvig
Haskell 24 Grzegorz
F# 34 Sebastian G
Ruby 38 Brian Adkins
Scheme 45 Shiro
Perl 63 riffraff
Erlang 87 Federico Feroldi
Scheme 89 Jens Axel
Rebol 133 Cyphre
C 184 Marcelo Toledo
Java 372 Dominik Schulz

 

Categoria Ferramentas
Organização pessoal: Como se tornar extremamente eficiente
Categoria Ferramentas
Como ser mais produtivo: remova aquilo que te atrapalha
Categoria Ferramentas
Golpe no MercadoLivre? Tentaram me aplicar um…
  • Martin

    Good job, but… what's the format of the dictionary?
    If it's just a list of files, such as:
    lemon
    moon
    new
    noon

    etc… it doesn't work — always returns (whatever) is correct, for example:

    “sperrin” is correct!

    any idea why?

    • Martin,

      The dictionary format is english text. I am using a free ebook.

      If it's always returning correct, it's because it's not loading the dictionary correctly.

  • satyam

    I think timing results are amazing.

    which dictionaries did u use. Can u please provide a link .

    Also, I do not see the body for the struct ENTRY. How does it work ?

  • Well , the view of the passage is totally correct ,your details is really reasonable and you guy give us valuable informative post, I totally agree the standpoint of upstairs. I often surfing on this forum when I m free and I find there are so much good information we can learn in this forum! http://www.in-donesia.net/

  • Span

  • Carolrx

    Não funciona apra português? Alguém conhece algum?

  • Funciona em qualquer idioma, basta utilizar um dicionário que tenha palavras no idioma que você quer corrigir.