Speller
Certifique-se de ler esta especificação na íntegra antes de começar para saber o que fazer e como fazê-lo!
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:
- A primeira linha diz ao
make
para executar as linhas subsequentes sempre que você mesmo executarmake speller
(ou apenasmake
). - A segunda linha diz ao
make
como compilar ospeller.c
em código de máquina (ou seja,speller.o
). - A terceira linha diz ao
make
como compilar odictionary.c
em código de máquina (ou seja,dictionary.o
). - A quarta linha diz ao
make
para vincular ospeller.o
e odictionary.o
em um arquivo chamadospeller
.
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.
- Você não pode alterar o
speller.c
ou oMakefile
. - Você pode alterar o
dictionary.c
(e, na verdade, deve fazê-lo para completar as implementações deload
,hash
,size
,check
eunload
), mas não pode alterar as declarações (ou seja, protótipos) deload
,hash
,size
,check
ouunload
. No entanto, você pode adicionar novas funções e variáveis (locais ou globais) aodictionary.c
. - Você pode alterar o valor de
N
emdictionary.c
, para que sua tabela de hash possa ter mais buckets. - Você pode alterar
dictionary.h
, mas não pode alterar as declarações deload
,hash
,size
,check
ouunload
. - Sua implementação de
check
deve ser insensível a maiúsculas e minúsculas. Em outras palavras, sefoo
estiver no dicionário, entãocheck
deve retornar verdadeiro para qualquer capitalização; nenhuma das palavrasfoo
,foO
,fOo
,fOO
,fOO
,Foo
,FoO
,FOo
eFOO
devem ser consideradas como palavras incorretas. - Em relação à capitalização, sua implementação do
check
deve retornar apenastrue
para palavras presentes nodicionário
. Tenha cuidado para não codificar palavras comuns (por exemplo,the
), para que não passemos sua implementação umdicionário
sem essas mesmas palavras. Além disso, apenas os possessivos permitidos são aqueles que estão realmente nodicionário
. Em outras palavras, mesmo quefoo
esteja nodicionário
,check
deve retornarfalse
parafoo's
sefoo's
não estiver nodicionário
também. - Você pode assumir que qualquer
dicionário
passado para o seu programa terá a mesma estrutura do nosso, ordenado alfabeticamente de cima para baixo com uma palavra por linha, cada uma delas terminando com\n
. Você também pode assumir que odicionário
contém pelo menos uma palavra, que nenhuma palavra terá mais deLENGTH
(uma constante definida emdictionary.h
) caracteres, que nenhuma palavra aparecerá mais de uma vez, que cada palavra conterá apenas caracteres alfabéticos minúsculos e possivelmente apóstrofos, e que nenhuma palavra começará com um apóstrofo. - Você pode assumir que o
check
só receberá palavras que contêm caracteres alfabéticos (maiúsculos ou minúsculos) e possivelmente apóstrofos. - Seu corretor ortográfico pode receber apenas
texto
e, opcionalmente,dicionário
como entrada. Embora você possa ser inclinado (particularmente se estiver entre aqueles mais confortáveis) a "pré-processar" nosso dicionário padrão para derivar uma "função hash ideal" para ele, você não pode salvar a saída de qualquer pré-processamento em disco para carregá-la de volta na memória em execuções subsequentes do seu corretor ortográfico para ganhar vantagem. - Seu corretor ortográfico não deve vazar qualquer memória. Certifique-se de verificar vazamentos com
valgrind
. - A função hash que você escrever deve ser sua própria, não uma que você procura on-line. Existem muitas maneiras de implementar uma função hash além de usar o primeiro caractere (ou caracteres) de uma palavra. Considere uma função hash que usa a soma dos valores ASCII ou o comprimento de uma palavra. Uma boa função hash tende a reduzir "colisões" e tem uma distribuição bastante uniforme nos "baldes" da tabela hash.
Ok, pronto para começar?
- Implementar
load
. - Implementar
hash
. - Implementar
size
. - Implementar
check
. - Implementar
unload
.
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