Speller

何をすべきか、どのようにすべきかを知るために、課題を始める前に必ずこの仕様の全体を読んでください。

この問題では、以下のようなファイルのスペルチェックをハッシュテーブルを使って行うプログラムを実装します。

$ ./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:

始め方

VS Codeを開きます。

ターミナルウィンドウ内をクリックすることから始めて、それからcdを実行します。
その後プロンプトは次のようになっていることがわかります。

$

ターミナルウィンドウの内側をクリックし、次のように入力します。

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

その後にEnterを押すと、speller.zipというZIPがあなたのCodespaceにダウンロードされます。wgetと次のURLの間にあるスペースや、その他の文字を見落とさないように注意してください。

次に

unzip speller.zip

を実行して、spellerというフォルダを作成します。
ZIPファイルは不要になったため、

rm speller.zip

を実行し、プロンプトで “y “に続いてEnterで応答すると、ダウンロードしたZIPファイルが削除されます。

次に

cd speller

の後にEnterを押して、そのディレクトリに移動する（つまり、開く）。これでプロンプトは以下のようになります。

speller/ $

lsを実行すると、いくつかのファイルとフォルダーが表示されるはずです。

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

もし問題が発生した場合は、もう一度同じ手順を踏んで、どこが間違っていたかを確認してください

理解を深める

理論的には、サイズnの入力において、実行時間nのアルゴリズムは、実行時間2nのアルゴリズムに対して、Oに関して 「漸近的に等価」 です。実際、アルゴリズムの実行時間を記述する際には、通常、支配的な (最も影響力のある) 項 (すなわち、nは2よりもはるかに大きくなる可能性があるので、この場合はn) に注目します。しかし現実の世界では、2nはnに比べて2倍遅く思えます。

今回の課題は、最速のスペルチェッカーを実装することです。しかし、 「最速」 というのは、漸近的な時間ではなく、実際の 「壁時計」 でのことです。

speller.cには、ディスクからメモリに単語の辞書をロードした後、ファイルのスペルチェックを行うプログラムがあります。一方、この辞書はdictionary.cというファイルに実装されています (speller.cで実装することもできますが、プログラムが複雑になると、複数のファイルに分割すると便利な場合があります) 。一方、関数のプロトタイプはdictionary.c自体ではなく、dictionary.hに定義されています。このようにすると、speller.cとdictionary.cの両方に#ファイルを含めることができます。残念ながら、ロード部分やチェック部分を実装するのに十分な時間がありませんでした。どちらも (そして他にももう少し) あなたにお任せします。まずは各ファイルを概観しましょう。

dictionary.h

dictionary.hを開くと、DICTIONARY_Hを参照している数行を含む新しい構文がいくつか表示されます。これらを気にする必要はありませんが、興味深いことに、これらの行はdictionary.cとspeller.c (これについては後で説明します) がこのファイルを#includeしていても、clangは一度だけコンパイルします。

次に、stdbool.hというファイルを#includeする方法に注目してください。bool自体が定義されているファイルです。CS50ライブラリには#includeが含まれていたため、以前は必要ありませんでした。

また、#defineという 「プリプロセッサ指令」 を使用して、LENGTHという値45を持つ 「定数」 を定義していることにも注意してください。これは、コード内で (誤って) 変更できない定数です。実際、clangを使用すると、コード内でLENGTHが言及されるたびに、文字通り45に置き換えられます。つまり、これは変数ではなく、単なる検索置換のトリックです。

最後に、check、hash、load、size、unloadの5つの関数のプロトタイプに注目してください。これらのうちの3つが*のように引数としてポインタを取ることに注目してください。

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

char *をstringと呼んでいたことを思い出してください。これら3つのプロトタイプは基本的には以下と同じです。

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

一方constは、これらの文字列が引数として渡された場合、定数のままでなければならないと言っています。意図的にも誤って変更したとしても変更はできません。

dictionary.c

dictionary.cを開きます。このファイルの先頭で、ハッシュ・テーブルのノードを表すnodeという構造体を定義していることに注目してください。また、グローバルポインタ配列tableを宣言していますが、これは辞書内の単語を追跡するために使用するハッシュテーブルを（すぐに）表現するものです。この配列にはN個のノード・ポインタが含まれ、後述するデフォルトのhash関数と一致させるために、今のところNを26に設定しています。あなた自身のhashの実装によっては、この値を増やしたくなるかもしれません。

次に、load、hash、check、size、unloadを実装していることに注目してください。また、単語の最初の文字に基づいたサンプルアルゴリズムでハッシュを実装していることにも注目してください。あなたの仕事は、これらの関数をできるだけ巧妙に再実装して、このスペルチェッカーが仕様どおり動作するようにすることです。そして高速である必要があります！

speller.c

では、speller.cを開いて、コードとコメントを見てみましょう。このファイルの内容を変更する必要はなく、ファイル全体を理解する必要もありませんが、その機能について理解してください。getrusageという関数を使用して、check、load、size、unloadをベンチマーク (実行に要する時間を計測) していることに注目してください。また、スペルチェックの対象となるファイルの内容を単語単位でcheckを通していることにも注目してください。最終的には、ファイル内のスペルミスと多数の統計情報を報告します。

ちなみに、spellerの使い方は以下のとおりです。

Usage: speller [dictionary] text

ここで、dictionaryは小文字の単語を1行に1つずつ含むファイルで、textはスペルチェックを行うファイルです。括弧が示唆するように、dictionaryの引数は任意です。この引数を省略すると、spellerはデフォルトでdictionaries/largeを使用します。つまり、以下の実行は、

$ ./speller text

以下の実行と同じことです。

$ ./speller dictionaries/large text

ここで、textはスペルチェックを行うファイルです。前者の方がタイプしやすいと思っておけば十分でしょう (もちろん、dictionary.cにload を実装しない限り、speller は辞書をロードすることはできません。それまでは「Could not load」 と表示されます) 。

デフォルトの辞書には143,091語ありますが、そのすべてをメモリに読み込まなければなりません！実際にそのファイルを見て、その構造とサイズを把握してください。ファイル内のすべての単語は小文字で表示されます (簡略化のために固有名詞や略語も)。ファイルは、上から下に向かって辞書順にソートされ、1行に1つの単語だけが含まれます (各単語は\nで終わります) 。45文字を超える単語はなく、複数回出現する単語もありません。開発中には、メモリ内の巨大な構造をデバッグするのに苦労しないように、ずっと少ない単語数のdictionaryをspellerに用意しておくと便利です。dictionaries/smallはそのような辞書の1つです。これを使用するには、次のコマンドを実行します。

$ ./speller dictionaries/small text

ここで、text はスペルチェックを行うファイルです。speller 自体がどのように機能するかを理解するまで、先に進まないでください！

おそらくspeller.cを見るのに十分な時間をかけていなかったのではないでしょうか。少し戻って、もう一度復習してみてください。

texts/

あなたがspellerの実装をテストできるように、La La Landのスクリプト、Affordable Care Act (医療費負担適正化法) のテキスト、トルストイの300万バイトの文章、The Federalist PapersとShakespeareからの抜粋、King James V BibleとKoranの全文など、たくさんのテキストを提供しています。pset5ディレクトリ内のtextsと呼ばれるディレクトリにあるそれぞれのファイルをのぞいてみてください。

speller.cを注意深く読んだことでわかるように、spellerの出力はたとえば次のように実行されます。

$ ./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:

TIME IN loadは、spellerがloadの実行に費やす秒数を表します。TIME IN checkは、spellerがcheckを実行するのに要した合計秒数を表します。TIME IN sizeは、spellerがsizeの実行に費やす秒数を表します。TIME IN unloadは、spellerがunloadの実行に費やす秒数を表します。TIME IN TOTALは、これら4つの測定値の合計です。

これらの時間は、コードを変更しなくても、Codespacesが他に何をしているかによって、spellerの実行によって多少異なる場合があります。

なお、はっきりさせておくと、 「スペルミス」 とは単に、提供されているdictionaryに単語が含まれていないことを意味します。

Makefile

最後に、makeはコードのコンパイルを自動化するので、たくさんのスイッチを使って手動でclangを実行する必要がないことを思い出してください。しかし、プログラムのサイズが大きくなると、makeはコンテキストからコードのコンパイル方法を推測できなくなります。この問題の場合のように、特に複数のソースファイル (.cファイル) が関係する場合には、プログラムのコンパイル方法をmakeに指示する必要があります。そこで、makeに正確に何をすべきかを指示する構成ファイルであるMakefileを利用します。Makefileを開くと、次の4行が表示されるはずです。

  1. 最初の行は、make speller (あるいは単にmake) を実行するたびに次の行を実行するようmakeに指示します。
  2. 2行目は、speller.cをマシンコード (speller.o) にコンパイルする方法をmakeに指示します。
  3. 3行目は、dictionary.cをマシンコード (dictionary.o) にコンパイルする方法をmakeに指示します。
  4. 4行目は、speller.oとdictionary.oをspellerというファイルにリンクする方法をmakeに指示します。

必ずmake speller (あるいは単にmake) を実行してspellerをコンパイルしてください。make dictionaryを実行しても動作しません。

仕様

さて、load、hash、size、check、unloadを可能な限り効率的に実行するには、ハッシュテーブルを使用して、TIME IN load、TIME IN check、TIME IN size、TIME IN unloadをすべて最小化するように実装する必要があります。dictionaryとtextにspellerから異なる値を入力すると、これらのベンチマークは確かに異なるので、最小化することが何を意味するのかは明らかではありません。しかしそこにはこの問題の面白さではないにしても、挑戦のしがいがあります。この問題はそれをあなたが設計するチャンスです。使用するメモリは最小限にすることをお勧めしますが、あなたの究極の敵は時間です。課題に取り掛かる前に、いくつかの仕様があります。

  • speller.cまたはMakefileは変更できません。
  • dictionary.cは変更できます (実際、load、hash、size、check、unloadの順番に実装を完了する必要があります) が、load、hash、size、check、unloadの宣言 (プロトタイプ) は変更できません。ただし、dictionary.cに新しい関数や (ローカルまたはグローバルな) 変数は追加することもできます。
  • ハッシュテーブルがより多くのバケットを持つことができるように、dictionary.cのNの値を変更できます。
  • dictionary.hは変更してもよいが、load、hash、size、check、unloadの宣言は変更してはいけません。
  • check の実装では大文字と小文字を区別しないようにする必要があります。言い換えると、foo が辞書にある場合、checkは大文字小文字を問わずtrueを返します。foo、foO、fOo、fOO、Foo、FoO、FOo、FOOのいずれもスペルミスとは見なされません。
  • 大文字の使用はさておき、check の実装では、実際に辞書にある単語に対してのみtrue を返すようにしてください。ハードコーディングされた一般的な単語 (例えばthe) に注意してください。これらの単語を含まないdictionary は実装に渡すことがないようにします。しかも、所有格はdictionary に載っているものだけです。言い換えると、たとえfoo がdictionaryに存在していたとしても、foo'sがdictionaryに存在しない場合には、foo'sが指定されていればcheck はfalse を返します。
  • プログラムに渡されるdictionary は、私たちのdictionary と全く同じように構成され、アルファベット順に1行に1語ずつ、それぞれが\nで終わるように、上から下にソートされていると仮定します。また、dictionary には少なくとも1つの単語が含まれており、どの単語もLENGTH  (dictionary.hで定義されている定数) 文字より長くならず、どの単語も2回以上現れず、各単語は小文字のアルファベット文字と場合によってはアポストロフィを含み、どの単語もアポストロフィで始まらないと仮定することができます。
  • check では、アルファベット (大文字または小文字) と、場合によってはアポストロフィを含む単語が渡されると想定できます。
  • スペルチェッカーは、text とオプションでdictionary のみを入力として取ることができます。デフォルト辞書の 「理想的なハッシュ関数」 を導出するために、デフォルト辞書を 「前処理」 したくなるかもしれませんが (特にそれに慣れている場合) 、そのような前処理の出力をディスクに保存して、後でスペルチェッカーを実行するときにメモリにロードして利用することはできません。
  • スペルチェッカーはメモリリークしてはいけません。必ずvalgrindで漏れがないか確認してください。
  • hash関数は、ネットで検索したものではなく、最終的には自分で書いたものでなければなりません。

準備はできましたか？

  • loadを実装します。
  • hashを実装します。
  • sizeを実装します。
  • checkを実装します。
  • unloadを実装します。

ウォークスルー

このプレイリストには6つのビデオがあることに注意してください。

Spellerのチュートリアルでは、ネットで見つけたhash関数を使うのが妥当とされていますが、このビデオは古いバージョンの問題で、これを許可したものです。上記の仕様により、あなたが書いたハッシュ関数は最終的にあなた自身のものでなければならず、ネットで見つけたハッシュ関数を使うことはできません。ハッシュ関数を書く際に参照した外部ソースがあれば必ず引用してください。

ヒント

2つの文字列を大文字小文字を区別せずに比較するには、strcasecmp  (strings.hで宣言された) が便利です。また、fooとFOOのハッシュ値が同じになるように、ハッシュ関数で大文字と小文字を区別しないようにすることもできます。

最終的には、loadで割り当てたメモリをすべて解放 (free ) してください。valgrind が一番新しい親友だということを思い出しましょう。valgrind はプログラムが実際に実行されている間のリークを監視するので、以下に示すように、特定のdictionary やtextを使用している間にvalgrind にspellerを監視させたい場合は、必ずコマンドライン引数を指定してください。ただ、小さなテキストを使うのがベストです。そうでなければ、valgrindの実行にかなりの時間がかかります。

$ valgrind ./speller texts/cat.txt

spellerにtext を指定せずにvalgrind を実行した場合、load とunload の実装は実際には呼び出されません (そして解析されません) 。

valgrindの出力の解釈方法がわからない場合は、help50 にヘルプを求めてください。

$ help50 valgrind ./speller texts/cat.txt

テスト

​プログラムが正しくスペルミスの単語を出力しているかどうかをどのように確認しますか？​ speller ディレクトリ内のkeys ディレクトリ内にある 「answer keys」 を参照してください。​たとえば、keys/lalaland.txtには、プログラムがスペルミスと見なすべき単語がすべて含まれています。

したがって、次のように、1つのウィンドウ内で、テキストに対してプログラムを実行できます。

$ ./speller texts/lalaland.txt

そして、次のように別のウィンドウの同じテキストで、スタッフのソリューションをチェックできます。

$ ./speller50 texts/lalaland.txt

ウィンドウを並べて視覚的に比較できます。しかし、それはすぐに時間がかかりすぎると思うかもしれません。そのため、次のようにプログラムの出力をファイルに 「リダイレクト」 することもできます。

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

以下のように、diffのようなプログラムを使って、同じウィンドウ内で両方のファイルを並べて比較することができます。

$ diff -y student.txt staff.txt

あるいは、時間を節約するために、以下のようにスタッフのソリューションを実行せずに、プログラムの出力 (たとえば、student.txtにリダイレクトしたとします) をアンサーキーの1つと比較することもできます。

$ diff -y student.txt keys/lalaland.txt

プログラムの出力がスタッフの出力と一致する場合、diff は2つのカラムを出力します。これらのカラムは、おそらく一番下にある実行時間を除いて、同一でなければなりません。ただし、列が異なる場合は、その場所に>または|が表示されます。たとえば、次のように表示されます。

MISSPELLED WORDS                                                MISSPELLED WORDS

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

つまり、左の列にThelonious がなく、右の列にThelonious があることからわかるように、スタッフの出力 (右) がスペルミスであっても、プログラム (出力が左) はThelonious またはMIA がスペルミスであるとは考えていないということです。

check50

コードをあまり手動でテストしないようにするには (完全ではありませんが) 、以下を実行することもできます。

$ check50 cs50/problems/2022/x/speller

check50はメモリリークもチェックするので、必ずvalgrindも実行してください。

style50

以下を実行し、style50を使用してコードのスタイルを評価します。

style50 dictionary.c

スタッフの解法

どのようにしてコードの速さを評価する (そして修正する) のでしょうか？いつものように、以下のようにスタッフのソリューションを自由に試して、その数字をあなたのものと比較してください。

$ ./speller50 texts/lalaland.txt

提出方法

ターミナルで、以下を実行して提出してください。

submit50 cs50/problems/2022/x/speller