CS50-MCZ

Uma introdução aos empreendimentos intelectuais da Ciência da Computação e da arte da programação.


Speller

Para este problema, você irá implementar um programa que verifica a ortografia de um arquivo, semelhante ao abaixo, usando uma tabela hash.

$ ./speller texts/lalaland.txt
MISSPELLED WORDS

[...]
AHHHHHHHHHHHHHHHHHHHHHHHHHHHT
[...]
Shangri
[...]
fianc
[...]
Sebastian's
[...]

WORDS MISSPELLED:
WORDS IN DICTIONARY:
WORDS IN TEXT:
TIME IN load:
TIME IN check:
TIME IN size:
TIME IN unload:
TIME IN TOTAL:

Começando

Acesse o code.cs50.io, clique na sua janela do terminal e execute cd sozinho. Você deve encontrar que o prompt da sua janela do terminal se assemelha ao abaixo:

$

Em seguida, execute

wget https://cdn.cs50.net/2022/fall/psets/5/speller.zip

Para baixar um arquivo ZIP chamado speller.zip em seu codespace.

Em seguida, execute

unzip speller.zip

para criar uma pasta chamada speller. Você não precisa mais do arquivo ZIP, então pode executar

rm speller.zip

e responda com "y" seguido de Enter no prompt para remover o arquivo ZIP que você baixou.

Agora digite

cd speller

seguido de Enter para mover-se para (ou seja, abrir) esse diretório. Seu prompt agora deve se parecer com o abaixo.

speller/ $

Se tudo ocorreu com sucesso, você deve executar ls e deverá ver alguns arquivos e pastas:

dictionaries/  dictionary.c  dictionary.h  keys/  Makefile  speller.c  speller50  texts/

Se você encontrar algum problema, siga novamente essas mesmas etapas e veja se pode determinar onde errou!


Distribuição

Entendendo

Teoricamente, com entrada de tamanho n, um algoritmo com tempo de execução de n é "asintoticamente equivalente", em termos de O, a um algoritmo com tempo de execução de 2n. De fato, ao descrever o tempo de execução de um algoritmo, geralmente nos concentramos no termo dominante (ou seja, mais impactante) (ou seja, n neste caso, já que n pode ser muito maior que 2). No mundo real, porém, o fato é que 2n parece duas vezes mais lento que n.

O desafio que está à sua frente é implementar o verificador ortográfico mais rápido que puder! Mas, quando falamos de "mais rápido", estamos falando do tempo real de "relógio de parede", não do tempo assintótico.

No arquivo speller.c, criamos um programa que é projetado para verificar a ortografia de um arquivo depois de carregar um dicionário de palavras do disco na memória. Esse dicionário, enquanto isso, é implementado em um arquivo chamado dictionary.c. (Poderia ser implementado em speller.c, mas à medida que os programas ficam mais complexos, muitas vezes é conveniente dividi-los em vários arquivos.) Os protótipos das funções nele, enquanto isso, não são definidos em dictionary.c em si, mas em dictionary.h. Dessa forma, tanto speller.c quanto dictionary.c podem #include o arquivo. Infelizmente, não conseguimos implementar a parte de carregamento. Ou a parte de verificação. Ambos (e um pouco mais) deixamos para você! Mas primeiro, uma visita guiada.

dictionary.h

Abra o arquivo dictionary.h e você verá algumas novas sintaxes, incluindo algumas linhas que mencionam DICTIONARY_H. Não se preocupe com elas, mas, se tiver curiosidade, essas linhas garantem que, mesmo que dictionary.c e speller.c (que você verá em breve) incluam este arquivo, o clang o compilará apenas uma vez.

Em seguida, observe como nós #include um arquivo chamado stdbool.h. Esse é o arquivo em que bool em si é definido. Você não precisou dele antes, porque a biblioteca CS50 o #include para você.

Observe também o uso de #define, uma "diretiva do pré-processador" que define uma "constante" chamada LENGTH que tem um valor de 45. É uma constante no sentido de que você não pode (acidentalmente) mudá-la em seu próprio código. Na verdade, o clang substituirá todas as referências a LENGTH em seu próprio código por, literalmente, 45. Em outras palavras, não é uma variável, apenas um truque de localizar e substituir.

Por fim, observe os protótipos de cinco funções: check, hash, load, size e unload. Observe como três deles recebem um ponteiro como argumento, conforme o *:

bool check(const char *word);
unsigned int hash(const char *word);
bool load(const char *dictionary);

Lembre-se que char * é o que costumávamos chamar de string. Portanto, esses três protótipos são essencialmente apenas:

bool check(const string word);
unsigned int hash(const string word);
bool load(const string dictionary);

E const, por enquanto, apenas indica que essas strings, quando passadas como argumentos, devem permanecer constantes; você não será capaz de alterá-las, acidentalmente ou não!

dictionary.c

Agora abra o arquivo dictionary.c. Observe como, no topo do arquivo, definimos uma struct chamada node que representa um nó em uma tabela hash. E declaramos um array global de ponteiros, table, que representará (em breve) a tabela hash que você usará para controlar as palavras no dicionário. O array contém ponteiros de nó N, e definimos N igual a 26 por agora, para corresponder à função de hash padrão descrita abaixo. Provavelmente, você desejará aumentar isso dependendo da sua própria implementação de hash.

Em seguida, observe que implementamos load, check, size e unload, mas apenas o suficiente para que o código compile. Observe também que implementamos hash com um algoritmo de exemplo com base na primeira letra da palavra. Seu trabalho, em última análise, é reimplementar essas funções da maneira mais inteligente possível para que este corretor ortográfico funcione como anunciado. E rápido!

speller.c

Okay, em seguida, abra o arquivo speller.c e dedique algum tempo olhando o código e os comentários nele contidos. Você não precisará mudar nada neste arquivo e não precisa entender sua totalidade, mas tente ter uma noção de sua funcionalidade mesmo assim. Note como, por meio de uma função chamada getrusage, estaremos "fazendo benchmark" (ou seja, cronometrando a execução) de suas implementações de check, load, size e unload. Observe também como passamos, palavra por palavra, o conteúdo de algum arquivo para ser corrigido ortograficamente para a função check. Por fim, relatamos cada erro de grafia encontrado nesse arquivo, juntamente com várias estatísticas.

Observe, incidentalmente, que definimos o uso de speller como sendo:

Usage: speller [dictionary] text

Onde dictionary é assumido como um arquivo contendo uma lista de palavras em minúsculas, uma por linha, e text é um arquivo a ser verificado a ortografia. Como os colchetes sugerem, o fornecimento de dictionary é opcional; se esse argumento for omitido, speller usará o arquivo dictionaries/large por padrão. Em outras palavras, executando:

./speller text

será equivalente a executar

./speller dictionaries/large text

onde text é o arquivo que você deseja verificar a ortografia. Dito isso, o primeiro é mais fácil de digitar! (Claro, speller não será capaz de carregar nenhum dicionário até que você implemente load em dictionary.c! Até lá, você verá Could not load.)

Dentro do dicionário padrão, há 143.091 palavras, todas as quais devem ser carregadas na memória! Na verdade, dê uma olhada nesse arquivo para ter uma ideia de sua estrutura e tamanho. Observe que cada palavra nesse arquivo aparece em minúsculas (mesmo os nomes próprios e siglas para simplificar). De cima para baixo, o arquivo é ordenado lexicograficamente, com apenas uma palavra por linha (cada uma delas termina com \n). Nenhuma palavra tem mais de 45 caracteres e nenhuma palavra aparece mais de uma vez. Durante o desenvolvimento, você pode achar útil fornecer ao speller um dicionário próprio que contenha muito menos palavras, para não ter dificuldades em depurar uma estrutura enorme na memória. Em dictionaries/small há um dicionário desses. Para usá-lo, execute:

./speller dictionaries/small text

onde text é o arquivo que você deseja verificar a ortografia. Não avance até ter certeza de que entende como o próprio speller funciona!

Provavelmente, você não dedicou tempo suficiente para revisar o arquivo speller.c. Volte um passo e percorra-o novamente!

texts/

Para que você possa testar sua implementação do speller, também fornecemos uma grande quantidade de textos, incluindo o roteiro de La La Land, o texto da Affordable Care Act, três milhões de bytes de Tolstoy, alguns trechos de The Federalist Papers e Shakespeare, e muito mais. Para que você saiba o que esperar, abra e examine cada um desses arquivos, todos os quais estão em um diretório chamado texts dentro do seu diretório pset5.

Agora, como você deve saber após ter lido cuidadosamente o arquivo speller.c, a saída do speller, se executado com, por exemplo,

./speller texts/lalaland.txt

eventualmente se parecerá com o abaixo.

Abaixo está uma parte da saída que você verá. Por questão de informação, nós extraímos alguns exemplos de "erros de ortografia". E para não estragar a diversão, omitimos nossas próprias estatísticas por enquanto.

MISSPELLED WORDS

[...]
AHHHHHHHHHHHHHHHHHHHHHHHHHHHT
[...]
Shangri
[...]
fianc
[...]
Sebastian's
[...]

WORDS MISSPELLED:
WORDS IN DICTIONARY:
WORDS IN TEXT:
TIME IN load:
TIME IN check:
TIME IN size:
TIME IN unload:
TIME IN TOTAL:

TIME IN load representa o número de segundos que o speller gasta executando sua implementação de load. TIME IN check representa o número de segundos que o speller gasta, no total, executando sua implementação de check. TIME IN size representa o número de segundos que o speller gasta executando sua implementação de size. TIME IN unload representa o número de segundos que o speller gasta executando sua implementação de unload. TIME IN TOTAL é a soma dessas quatro medidas.

Observe que esses tempos podem variar um pouco entre as execuções do speller, dependendo do que mais sua área de códigos estiver fazendo, mesmo que você não altere seu código.

Aliás, para deixar claro, por "com erro de ortografia" nós simplesmente queremos dizer que alguma palavra não está no dicionário fornecido.

Makefile

E, por último, lembre-se de que o make automatiza a compilação do seu código para que você não precise executar o clang manualmente junto com um monte de opções. No entanto, à medida que seus programas crescem em tamanho, o make não será capaz de inferir do contexto como compilar o seu código; você precisará começar a dizer ao make como compilar o seu programa, particularmente quando eles envolvem múltiplos arquivos de origem (ou seja, arquivos .c), como no caso deste problema. E assim, vamos utilizar um Makefile, um arquivo de configuração que diz ao make exatamente o que fazer. Abra o Makefile, e você deverá ver quatro linhas:

  1. A primeira linha diz ao make para executar as linhas subsequentes sempre que você mesmo executar make speller (ou apenas make).
  2. A segunda linha diz ao make como compilar o speller.c em código de máquina (ou seja, speller.o).
  3. A terceira linha diz ao make como compilar o dictionary.c em código de máquina (ou seja, dictionary.o).
  4. A quarta linha diz ao make para vincular o speller.o e o dictionary.o em um arquivo chamado speller.

Certifique-se de compilar o speller executando make speller (ou apenas make). Executar make dictionary não funcionará!

Especificação

Certo, o desafio que está diante de você agora é implementar, em ordem, load, hash, size, check e unload de forma eficiente usando uma tabela hash, de tal forma que TIME IN load, TIME IN check, TIME IN size e TIME IN unload sejam todos minimizados. Para ter certeza, não é óbvio o que significa ser minimizado, na medida em que essas referências certamente variarão conforme você alimenta o speller com valores diferentes para dictionary e text. Mas aí reside o desafio, se não a diversão, deste problema. Este problema é a sua chance de projetar. Embora convidemos você a minimizar o espaço, seu inimigo final é o tempo. Mas antes de mergulhar, algumas especificações de nossa parte.

Ok, pronto para começar?

Dicas

Para comparar duas strings sem distinguir maiúsculas e minúsculas, você pode achar útil a função strcasecmp (declarada em strings.h)! Você provavelmente também vai querer garantir que sua função hash não diferencie maiúsculas de minúsculas, de modo que foo e FOO tenham o mesmo valor de hash.

Por fim, certifique-se de liberar a memória alocada em load no momento em que você chama a função unload! Lembre-se de que o valgrind é seu melhor amigo. Saiba que o valgrind procura vazamentos enquanto o seu programa está em execução, portanto, certifique-se de fornecer argumentos de linha de comando se você quiser que o valgrind analise o speller enquanto você usa um dicionário e/ou texto específico, como abaixo. É melhor usar um texto pequeno, no entanto, caso contrário, o valgrind pode demorar bastante para rodar.

valgrind ./speller texts/cat.txt

Se você executar o valgrind sem especificar um texto para o speller, suas implementações de load e unload não serão realmente chamadas (e, portanto, analisadas).

Se você não tem certeza de como interpretar a saída do valgrind, basta pedir ajuda ao help50:

help50 valgrind ./speller texts/cat.txt

Testando

Como verificar se o seu programa está exibindo as palavras com erro ortográfico corretas? Bem, você pode consultar as "chaves de resposta" que estão dentro do diretório keys que está dentro do seu diretório speller. Por exemplo, dentro de keys/lalaland.txt, estão todas as palavras que o seu programa deve considerar como tendo erro ortográfico.

Portanto, você pode executar o seu programa em algum texto em uma janela, como abaixo.

./speller texts/lalaland.txt

E você poderia executar a solução da equipe no mesmo texto em outra janela, como no exemplo abaixo.

./speller50 texts/lalaland.txt

E então você poderia comparar visualmente as janelas lado a lado. Isso poderia se tornar tedioso rapidamente, no entanto. Então, você pode querer "redirecionar" a saída do programa para um arquivo, como mostrado abaixo.

./speller texts/lalaland.txt > student.txt
./speller50 texts/lalaland.txt > staff.txt

Você pode então comparar ambos os arquivos lado a lado na mesma janela com um programa como diff, como no exemplo abaixo.

diff -y student.txt staff.txt

Alternativamente, para economizar tempo, você poderia simplesmente comparar a saída do seu programa (supondo que você a redirecionou para, por exemplo, student.txt) com uma das chaves de resposta sem executar a solução da equipe, como no exemplo abaixo.

diff -y student.txt keys/lalaland.txt

Se a saída do seu programa corresponder à da equipe, o comando diff irá produzir duas colunas que devem ser idênticas, exceto talvez pelos tempos de execução na parte inferior. No entanto, se as colunas diferirem, você verá um > ou | onde elas diferem. Por exemplo, se você vir

MISSPELLED WORDS                                                MISSPELLED WORDS

TECHNO                                                          TECHNO
L                                                               L
                                                              > Thelonious
Prius                                                           Prius
                                                              > MIA
L                                                               L

Isso significa que seu programa (cuja saída está à esquerda) não considera que Thelonious ou MIA estejam com erro de ortografia, mesmo que a saída da equipe (à direita) o faça, como é sugerido pela ausência, por exemplo, de Thelonious na coluna da esquerda e a presença de Thelonious na coluna da direita.

check50

Para testar seu código de forma menos manual (embora ainda não exaustiva), você também pode executar o seguinte.

check50 cs50/problems/2023/x/speller

Observe que o check50 também verificará vazamentos de memória, então certifique-se de ter executado o valgrind também.

style50

Execute o abaixo para avaliar o estilo do seu código usando style50.

style50 dictionary.c

Solução da equipe

Como avaliar quão rápido (e correto) é o seu código? Bem, como sempre, sinta-se à vontade para brincar com a solução da equipe, assim como com a abaixo, e comparar seus números com os seus.

./speller50 texts/lalaland.txt

Como Enviar

No seu terminal, execute o comando abaixo para enviar o seu trabalho.

submit50 cs50/problems/2023/x/speller