O trabalho será baseado no código em Python para cálculo da distância de Levenshtein entre duas strings desenvolvido pelo Prof. Andrew McCallum. O trabalho deve ser desenvolvido totalmente em Python em grupos de no máximo 2 alunos. A data de entrega é 27/10/08 (até às 23:59h). O trabalho pode ser entregue por e-mail.

O primeiro passo é baixar e instalar o Python e baixar o módulo stredit.py desenvolvido pelo Prof. Andrew McCallum. Este módulo contém duas funções: stredit e stredit2. A primeira é mais curta e fácil de entender, mas calcula apenas a distância e não o alinhamento. A segunda calcula o alinhamento e a distância, colocando um * em cada posição da tabela que faz parte do alinhamento. Exemplo:

$ python
>>> import stredit
>>> stredit.stredit2('tom sawyer', 'thomas sawer')
          t   o   m       s   a   w   y   e   r
      0   1   2   3   4   5   6   7   8   9  10
  t   1 * 0   1   2   3   4   5   6   7   8   9
  h   2 * 1   1   2   3   4   5   6   7   8   9
  o   3   2 * 1   2   3   4   5   6   7   8   9
  m   4   3   2 * 1   2   3   4   5   6   7   8
  a   5   4   3 * 2   2   3   3   4   5   6   7
  s   6   5   4 * 3   3   2   3   4   5   6   7
      7   6   5   4 * 3   3   3   4   5   6   7
  s   8   7   6   5   4 * 3   4   4   5   6   7
  a   9   8   7   6   5   4 * 3   4   5   6   7
  w  10   9   8   7   6   5   4 * 3 * 4   5   6
  e  11  10   9   8   7   6   5   4   4 * 4   5
  r  12  11  10   9   8   7   6   5   5   5 * 4
  4

A função também pode ser usada para calcular a distância entre duas seqüências de palavras, representadas por listas. Por exemplo:

>>> stredit.stredit2(['He', 'quickly', 'ran', 'to', 'the', 'store'], ['He', 'walked', 'to', 'the', 'grocery', 'store'])

         He qui ran  to the sto
      0   1   2   3   4   5   6
 He   1 * 0 * 1   2   3   4   5
wal   2   1   1 * 2   3   4   5
 to   3   2   2   2 * 2   3   4
the   4   3   3   3   3 * 2   3
gro   5   4   4   4   4 * 3   3
sto   6   5   5   5   5   4 * 3
3

O trabalho tem duas partes:

Parte 1 - Modificar as funções stredit e stredit2 para calcular a distância de Needleman-Wunsch, ao invés da distância de Levenstein. Na distância de Needleman-Wunsch, o custo de uma substituição é variável e deve refletir o fato de que alguns caracteres tem maior chance de serem digitados acidentalmente no lugar de outro. Isso pode ser feito considerando o custo da substituição como sendo proporcional à distância entre os dois caracteres no teclado. Os valores exatos para os custos de substituição para cada par de caracteres devem ser escolhidos por cada grupo, de acordo com o que acharem razoável. Deve-se levar em conta que essas funções serão utilizadas em um corretor ortográfico para língua portuguesa (ver item abaixo). Logo, deve-se considerar caracteres acentuados. Nesse caso, deve se supôr que a distância entre um caracter e o mesmo caracter acentuado deva ser pequena, já que dessa forma o corretor seria capaz de sugerir a acentuação correta de uma palavra.

Parte 2 - Implementar um corretor ortográfico para língua portuguesa que use um dicionário de palavras da língua portuguesa e as funções definidas no passo anterior para sugerir correções. O corretor deve identificar as palavras que não estão no dicionário e para cada uma delas sugerir uma lista de palavras corretas que sejam próximas à palavra errada. O critério para decidir quantas palavras serão sugeridas deve ser definido pelo grupo. Um dicionário de português brasileiro desenvolvido pelo OpenOffice com mais de 300.000 palavras pode ser baixado aqui. Este é um .zip contendo dois arquivos: o arquivo pt_BR.dic que contém uma lista de lemas (formas canônicas da palavra) seguidos ou não por uma barra ("/") contendo códigos para os possíveis afixos que podem ser usados com este lema, e o arquivo pt_BR.aff que lista os afixos para cada código.

O que deve ser entregue

O módulo nwstredit.py contendo as funções nwstredit e nwstredit2 desenvolvidas na parte 1.
O módulo corretor.py que deve ter uma função que receba como entrada um arquivo texto e a cada palavra encontrada que não esteja no dicionário peça para o usuário escolher entre uma das opções de correção ou manter a palavra como está. O arquivo corrigido deve ser salvo.
Documentação explicando qual foi o critério usado para determinar a distância de substituição entre diferentes caracteres (parte 1) e como utilizar o módulo corretor.py (parte 2).