Como escrever um corretor ortográfico
“O Diretor de Pesquisa do Google, Peter Norvig, publicou em seu website um artigo que explica como escrever um corretor ortográfico, similar ao que o próprio Google utiliza quando você escreve uma palavra incorreta, "Você quis dizer: foobar?", ele utilizou Python e precisou de somente 21 linhas. Implementações em outras linguagens foram feitas por outras pessoas, uma delas foi em C, por Marcelo Toledo, que publicou em seu Blog uma comparação de quantidade de linhas e desempenho.”
Enviado por dacker (danvackerΘgmail·com) - referência (blog.marcelotoledo.org).
(postado por Augusto Campos)
Comentários dos leitores
Comentário de silveira
11/08/07 12:44 - usuário registrado #14
Linguagem e linhas de código: Legal é essa tabel que ele colocou no final do artigo: O mesmo programa, escrito em várias linguagens:
Sem provocações...
--
Silveira Neto - Fortaleza-CE.
www.eupodiatamatando.com
- Python, 21 linhas
- Haskell, 24 linhas
- F#, 34 linhas
- Ruby, 38 linhas
- Scheme, 45 linhas
- Perl, 63 linhas
- Scheme, 89 linhas
- Rebol, 133 linhas
- Java, 372 linhas
Sem provocações...
--
Silveira Neto - Fortaleza-CE.
www.eupodiatamatando.com
Comentário de Clésio Luiz
11/08/07 17:58 - usuário registrado #13300
Python: Agora eu entendo porque tem tanta gente elogiando ele, 21 linhas. Coitado dos programadores Java, 372 linhas... E a produtividade ó...
--
"... e não sabendo que era impossível, ele foi lá e fez."
--
"... e não sabendo que era impossível, ele foi lá e fez."
Comentário de nemesis
11/08/07 18:35 - usuário registrado #1514
nem tudo são flores: LOC é uma medida interessante e concisão e expressividade algo desejável, mas de fato performance pode ser um problema.
Nos testes iniciais, o Toledo usou um pequeno dicionário de 6MB e a diferença não foi lá grandes coisas entre a verbosa implementação C e a concisão em Python. Mas conforme ele foi aumentando o dicionário, a performance de python foi ficando gradativamente mais sofrível, até que eventualmente, com um dict de 160MB, ele escreveu isso:
"Couldn't compare, Python process took too much time and was killed by kernel."
De maior interesse, em minha opinião, é o fato de que a versão em Haskell do algoritmo é apenas 24 linhas. Como se sabe, Haskell é uma das mais modernas e robustas linguagens de programação, uma linguagem funcional, estaticamente compilada e incrivelmente concisa. O algoritmo ficou no mesmo tamanho que o em Python, mas duvido que tenha os mesmos problemas, embora o autor não tenha feito a mesma análise minuciosa do Toledo. Ele também alerta que é uma tradução literal do algoritmo de Norvig e utilizou uma implementação lenta.
--
;; ((lambda (x) x) "Isto é um comentário e não será executado nunca")
Nos testes iniciais, o Toledo usou um pequeno dicionário de 6MB e a diferença não foi lá grandes coisas entre a verbosa implementação C e a concisão em Python. Mas conforme ele foi aumentando o dicionário, a performance de python foi ficando gradativamente mais sofrível, até que eventualmente, com um dict de 160MB, ele escreveu isso:
"Couldn't compare, Python process took too much time and was killed by kernel."
De maior interesse, em minha opinião, é o fato de que a versão em Haskell do algoritmo é apenas 24 linhas. Como se sabe, Haskell é uma das mais modernas e robustas linguagens de programação, uma linguagem funcional, estaticamente compilada e incrivelmente concisa. O algoritmo ficou no mesmo tamanho que o em Python, mas duvido que tenha os mesmos problemas, embora o autor não tenha feito a mesma análise minuciosa do Toledo. Ele também alerta que é uma tradução literal do algoritmo de Norvig e utilizou uma implementação lenta.
--
;; ((lambda (x) x) "Isto é um comentário e não será executado nunca")
Comentário de cesar
12/08/07 8:08 - usuário registrado #685
O velho programador: Acho que isso explica um pouco porque eu ao mesmo tempo gosto e detesto o Python... já ouve uma época em que eu ganhava por linha de codigo... to ficando velho.
--
Cesar Gimenes http://crg.eti.br
Linux user #76132
--
Cesar Gimenes http://crg.eti.br
Linux user #76132
Comentário de Felipe Raposo
12/08/07 10:48 - usuário registrado #226
Sem noção: Não tem sentido essa comparação. Um "hello world" em Java leva muitas linhas mesmo. Mas faça um sistema gigante, com EJB e tudo o mais em Java e depois tenta fazer o mesmo sistema em outras linguagens. Dai você faz as comparações decentemente. Aliás, faça outras comparações também, como portabilidade, ferramentas auxiliares (como IDEs), qualidade de software (para futuras manutenções), segurança (tratamento de memória automático por um garbage collector), etc.
Falar que o Java perde pontos porque um programa simples foi feito em 372, onde 320 foram geradas automaticamente por uma IDE, se uma boa foi utilizada, é no mínimo uma indicação de falta de conhecimento sua.
A produtividade Java, utilizando as ferramentas corretas, vai muito bem.
--
Felipe Raposo
Falar que o Java perde pontos porque um programa simples foi feito em 372, onde 320 foram geradas automaticamente por uma IDE, se uma boa foi utilizada, é no mínimo uma indicação de falta de conhecimento sua.
A produtividade Java, utilizando as ferramentas corretas, vai muito bem.
--
Felipe Raposo
Comentário de Peter Parker
13/08/07 17:33 - usuário registrado #642
Linhas de código: Sobre a implementação em Java:
Fiz uma com 87 linhas: http://raelcunha.com/spell-correct.php
Sim, óbvio, é mais verboso do que a belíssima implementação em Python (como era de se esperar), mas é menor que a de C, como deveria ser.
E agora, defendendo a implementação em python: óbvio que a implementação em C ficaria mais rápido... mas toda linguagem alto nível ficará mais lerda do que C, é inevitável. Mas qual seria realmente o gargalo para esta aplicação? Me parece que o que demora mais num sistema como o Google é a busca web em si do que o "check spelling".
Em relação ainda a performance: basta ver a elegência do código em Python: o que será que seria mais fácil de se manter? O que é mais fácil de ler? ... Sempre há um preço a se pagar, é a evolução da computação, é inevitável: maior legibilidade em troca de performance. Assim como C é mais legível porém mais lerdo do que Assembly.
--
Rael - http://www.raelcunha.com
Fiz uma com 87 linhas: http://raelcunha.com/spell-correct.php
Sim, óbvio, é mais verboso do que a belíssima implementação em Python (como era de se esperar), mas é menor que a de C, como deveria ser.
E agora, defendendo a implementação em python: óbvio que a implementação em C ficaria mais rápido... mas toda linguagem alto nível ficará mais lerda do que C, é inevitável. Mas qual seria realmente o gargalo para esta aplicação? Me parece que o que demora mais num sistema como o Google é a busca web em si do que o "check spelling".
Em relação ainda a performance: basta ver a elegência do código em Python: o que será que seria mais fácil de se manter? O que é mais fácil de ler? ... Sempre há um preço a se pagar, é a evolução da computação, é inevitável: maior legibilidade em troca de performance. Assim como C é mais legível porém mais lerdo do que Assembly.
--
Rael - http://www.raelcunha.com
Comentário de nemesis
12/08/07 17:55 - usuário registrado #1514
simplicidade: "320 foram geradas automaticamente por uma IDE"
Gerar é fácil. Ler é que é difícil. Pq se em um algoritmo simples vc tem que se embrenhar por 320 linhas de java para encontrar os cerca de 20 linhas código que efetivamente realizam algum processamento, imagine a merda que é perfazer seu caminho em sistemas maiores.
Com sorte, suas IDEs pesadas e seus frameworks kilométricos podem te ajudar nessa empreitada, hein? ;)
--
;; ((lambda (x) x) "Isto é um comentário e não será executado nunca")
Gerar é fácil. Ler é que é difícil. Pq se em um algoritmo simples vc tem que se embrenhar por 320 linhas de java para encontrar os cerca de 20 linhas código que efetivamente realizam algum processamento, imagine a merda que é perfazer seu caminho em sistemas maiores.
Com sorte, suas IDEs pesadas e seus frameworks kilométricos podem te ajudar nessa empreitada, hein? ;)
--
;; ((lambda (x) x) "Isto é um comentário e não será executado nunca")
Comentário de Felipe Raposo
12/08/07 18:03 - usuário registrado #226
Simplicidade inicial?: Ah, se aquelas linhas estão ali é porque tem o seu motivo. Os engenheiros nao as puseram ali de bobeira.
Java não foi desenvolvido pensado em programas de 20 linhas e sim para programas realmente grandes e importantes. Ai você vai ver a diferença que fazem essas linhas geradas automaticamentes pelas IDEs. Fora o javadoc.
Aliás, como eu vi que você está sendo irônico nos seus posts, acho que você não tem conhecimento nenhum sobre o assunto e está falando como se fosse um torcedor contra. Se você quiser mesmo saber as vantagens que o Java tem, procure ser um pouco mais sério no próximo post. Ou procura por você mesmo em java.sun.com. Agora se quiser só zuar mesmo, te entendo.
Abraço,
Felipe Raposo
Java não foi desenvolvido pensado em programas de 20 linhas e sim para programas realmente grandes e importantes. Ai você vai ver a diferença que fazem essas linhas geradas automaticamentes pelas IDEs. Fora o javadoc.
Aliás, como eu vi que você está sendo irônico nos seus posts, acho que você não tem conhecimento nenhum sobre o assunto e está falando como se fosse um torcedor contra. Se você quiser mesmo saber as vantagens que o Java tem, procure ser um pouco mais sério no próximo post. Ou procura por você mesmo em java.sun.com. Agora se quiser só zuar mesmo, te entendo.
Abraço,
Felipe Raposo
Comentário de nemesis
12/08/07 18:18 - usuário registrado #1514
é, não conheço nada. eu: é, não conheço nada. eu geralmente falo sem pensar e sem saber, só pra irritar...
--
;; ((lambda (x) x) "Isto é um comentário e não será executado nunca")
--
;; ((lambda (x) x) "Isto é um comentário e não será executado nunca")
Comentário de Psycho Mantys
14/08/07 9:17 - usuário registrado #14319
Tlv nao tao lerdo quanto asm: E dificil escrever um codigo em assembly mais rapido do que C. Acredite em mim. O compilador salva. E um compilador icpc faz milagres onde nao ah codigo rapido.
E praticamente impossivel vc conhecer tanto de assembly, e se conhecer, sera que e pra maquina que vc ta programando? E nao toh falando nem de usar instruções genericas, e sim de que codigo usar em cada situaçao, cache, pipeline diferente para cada maquina, pre execuçao de instruçoes.... E por ai vai. Ou seja, segura nao mao do compilador, e tenha fe!
(ps:. Mas fazer otimizaçoes em codigo jah passado pra assembly eu nao vejo nada de mais, ainda :P :)
--
L.U. 450347
E praticamente impossivel vc conhecer tanto de assembly, e se conhecer, sera que e pra maquina que vc ta programando? E nao toh falando nem de usar instruções genericas, e sim de que codigo usar em cada situaçao, cache, pipeline diferente para cada maquina, pre execuçao de instruçoes.... E por ai vai. Ou seja, segura nao mao do compilador, e tenha fe!
(ps:. Mas fazer otimizaçoes em codigo jah passado pra assembly eu nao vejo nada de mais, ainda :P :)
--
L.U. 450347
Comentário de Peter Parker
14/08/07 13:59 - usuário registrado #642
Eu não sabia: Legal este seu comentário. Como eu nunca fiz nada sério em Assembly, não sabia da dificuldade em escrever coisas com bom desempenho.
--
Rael - http://www.raelcunha.com
--
Rael - http://www.raelcunha.com
Com certeza eu vou usar esse código do Peter Norvig em algum projeto meu :)
--
Silveira Neto - Fortaleza-CE.
www.eupodiatamatando.com