CS50 2020 week5 Data Structures Pset5 Speller スペルチェッカ ～ハッシュテーブルの実装～
CS50 2020 week5 Data Structures Pset5 Speller
スペルチェッカ ～ハッシュテーブルの実装～
なかなかの難しさだった…
一からコード書けって言われたら、まだ無理だけど、動いた時はむっちゃうれしかった。。
しかし「良いハッシュ関数はネットに溢れてる」みたいにダグ言ってたけど、イマイチ探し方がわからんかったので、頭文字アルファベット1文字だけのハッシュ関数にした。
↓内容
理論的には、サイズ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は一度だけコンパイルします。
C言語では、 #ifdef や #ifndef を使うことによって、条件付きのコンパイルが可能となる。 #ifdefは、次のようにして使う。 これは、「MACROが定義されて いる 場合は、#ifdef～#endifの中を有効にする」という意味である。 次に、#ifndefは、逆の意味で、以下のように使う。 これは、「MACROが定義されて いない 場合は、#ifndef～#endifの中を有効にする」という意味である。
次に、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というstruct構造体を定義したことに注目してください。また、グローバルポインタ配列tableを宣言しました。これは、辞書内の単語を追跡するために使用するハッシュテーブルを (すぐ後で) 表します。配列にはN個のノードポインタが含まれており、ここではNを1に設定しています。つまり、このハッシュテーブルには現在1つのバケットしかありません。Nを変更するなどして、バケットの数を増やしたい場合があるでしょう。
次に、load、hash、check、size、unloadが実装されていますが、コードのコンパイルをかろうじて通過しているだけです。最終的には、これらの関数を可能な限り賢く再実装して、このスペルチェッカーが宣伝どおりに機能するようにするのが仕事です。そして高速である必要があります！
speller.c
では、speller.cを開いて、コードとコメントを見てみましょう。このファイルの内容を変更する必要はなく、ファイル全体を理解する必要もありませんが、その機能について理解してください。getrusageという関数を使用して、check、load、size、unloadをベンチマーク (実行に要する時間を計測) していることに注目してください。また、スペルチェックの対象となるファイルの内容を単語単位でcheckを通していることにも注目してください。最終的には、ファイル内のスペルミスと多数の統計情報を報告します。
▼ルール
speller.c、dictionary.h、Makefileは変更できません。
dictionary.cは変更できます (実際、load、hash、size、check、unloadの順番に実装を完了する必要があります) が、load、hash、size、check、unloadの宣言 (プロトタイプ) は変更できません。ただし、dictionary.cに新しい関数や (ローカルまたはグローバルな) 変数は追加することもできます。
ハッシュテーブルがより多くのバケットを持つことができるように、dictionary.cのNの値を変更できます。
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で漏れがないか確認してください。
自分のコードに組み込んだハッシュ関数の出所を挙げる限り、 (良い) ハッシュ関数をオンラインで検索することができます。
ウォークスルー
▼load
辞書を取得してハッシュテーブルにロードする
引数として文字列＝辞書の名前を取得する
戻り値はbool。全てのデータをハッシュテーブルにロードできたらtrue、できなかったらfalse。
ハッシュテーブルは個々の連結リストの単なる配列であることを思い出してください。
単語を挿入する連結リストを決定する方法はハッシュ関数に基づいている
この場合は入力として文字列＝単語を受け取る関数
出力はその入力から生成できる数値。これはその特定の単語を配置する連結リストに対応する
ハッシュテーブルに保存したい5つの単語があるとする
apple
banana
bat
car
book
↑辞書からこれらの単語を取り出して1つの連結リストに入れる
しかし、特定の単語がデータ構造内にあるかどうかを調べたい場合は、5つの単語からなるかなり長い連結リストが必要になる
代わりに、いわばいくつかのバケットを作成して、それらをハッシュテーブルに入れることができる。文字Aで始まる全ての単語に対してAのバケットを作成し、文字Bで始まる全ての単語に対してBのバケットを作成し…それらをそれぞれの単語とリンクする
A→apple
B→bat→book→banana
C→car
ここで使用したのはハッシュ関数。この関数は入力として単語を受け取り、連結リスト(Aリスト、Bリスト、Cリスト…)を出力する関数
ハッシュ関数とは何か？
入力として単語を受け取り、この配列内のどのバケット、または要素に単語を格納したいかに対応する数値を出力する
その配列の最初の連結リストがインデックス0、次に1、次に2…というように配置されている配列
ハッシュ関数は単語を取得し、その特定の単語を配置するために使用する配列のインデックスを出力する
ハッシュテーブル内の各インデックスは連結リストになる
連結リストとは、nodeで構成されるデータを格納する方法で、全てのnodeには「値」と「次のnodeへのポインタ」がある
スペルチェッカでは連結リストの配列を持つハッシュテーブルを作成する
各nodeは単語を格納する場所を持つ
この場合、それは文字配列になり、任意の単語の最大長(LENGTH)まで単語を格納することができる
↓dictionary.cのコード
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
終端がNULLになる連結リストを作成する
const int N = 1;
node *table[N];
tableはハッシュテーブルを表す。それはnodeポインタの配列になる。その配列内の全ての要素がnodeへのポインタである配列
現在、このハッシュテーブルの配列には1つの要素しかない＝ハッシュテーブルにはバケットが1つしかない
↑定数Nを変更する必要がある
ハッシュテーブルがより多くのバケットを持つことができるようにNをより高い値に設定し直して、データをより均等に分散させる
ただし、最初はハッシュテーブルは空になる
ハッシュテーブルにデータを追加するにはどうすればいい？
そのためには、新しいnodeにメモリを割り当ててから、そのnodeにデータを入れる必要がある
node *n = malloc(sizeof(node));
↑こうして取得したnodeのメモリのアドレスをn内に保存する
そのnodeにデータを入れるには？
strcpy(n -> word,"Hello");
↑ソースから宛先に文字列をコピーする関数
nというnodeのwordフィールドに「Hello」という文字列を入れる
nextポインタを設定するには、次のnodeが何であるか知っていればすぐ設定できるが、わからない場合はNULLに設定する
n->next = NULL;
↑nは何も指していない＝終端であることを示す
もちろんこの連結リストではこれらのnodeのほとんどは連結リスト内の要素のシーケンスの次のnodeである他のnodeを持つことになる
では、このload()関数内では正確には何をすれば良いか？
・まず、辞書ファイルを開く
・開いた辞書ファイルから文字列を1つずつ読み込む(1度に1つの単語)
・これらの単語ごとに新しいnodeを作成する(値と次のnodeへのポインタを持つnode)
・そしてハッシュ関数を使用してその単語のハッシュ値を取得し、ハッシュテーブルにインデックスを付けて、このnodeを連結リストに挿入する時に使用する連結リストを決定する
・最後にこれらの各単語を取得し、ハッシュ関数によって指定された場所にあるハッシュテーブルにそのnodeを挿入する
↑これらのステップを1つずつ見ていこう
・まず、辞書ファイルを開く
load()関数は引数として辞書ファイルの名前を取得する
fopen()関数でそのファイルを開ける
fopen()の戻り値がNULLかどうかをチェックするのを忘れずに
(NULLだったらload()関数もfalseを返す)
・開いた辞書ファイルから文字列を1つずつ読み込む(1度に1つの単語)
fscanf(file, "%s",word)
最初の引数はスキャンするファイルのポインタ(先ほどfopenで開いたファイル)
2番目の引数は%sで、文字列を読み込むことを意味する
3番目の引数はwordで、文字配列＝単語を読み込もうとしている場所。つまり、単語を読み取った後、その単語のここの文字全てにアクセスできるメモリ内の文字配列
↑辞書内の単語ごとにこれを何度も繰り返し、fscanfがEOFを返すまで一度に1つの単語を取得しながら、ファイルに対して何度もfscanfを何度も呼び出す
fscanfがEOFを返した時には辞書内の全ての単語を読み終わっている
↑単語を一つずつ読み込み続ける何らかのループが必要になる
・これらの単語ごとに新しいnodeを作成する(値と次のnodeへのポインタを持つnode)
読み込んだ個々の単語をハッシュテーブル内に格納する新しいnodeを作成する
mallocを使う
strcpy関数で単語をnodeにコピーする
・そしてハッシュ関数を使用してその単語のハッシュ値を取得し、ハッシュテーブルにインデックスを付けて、このnodeを連結リストに挿入する時に使用する連結リストを決定する
作成したnodeをハッシュテーブルに挿入する方法を理解する
ハッシュテーブルは連結リストの単なる配列であることを思い出してほしい
作成したばかりのこの特定のnodeを配置する場所を決定する時にどの連結リストを使用するかを決める必要がある
そのために単語をハッシュする
辞書で定義されている(別途コードを書かなければならない)ハッシュ関数を使用する
これは文字列を受け取り、インデックスを返す関数で、連結リストにインデックスを付けるために使用できるいくつかの数値
現状では特定の入力ごとに0を返すだけのハッシュ関数を提供している
後半で、このハッシュ関数をより優れたものに置き換える
しかし、今のところload()内でハッシュ関数を呼び出すだけでこの新しいnodeを挿入するときに使用する必要があるハッシュテーブルのインデックスを決定できる
・最後にこれらの各単語を取得し、ハッシュ関数によって指定された場所にあるハッシュテーブルにそのnodeを挿入する
使用する連結リストを決定したら、次のステップは実際にその単語を連結リストに挿入する
繰り返しになるが、ハッシュテーブルは連結リストの配列である
この特定の単語を追加するために使用する連結リストを取得するために、ハッシュテーブルにインデックスを作成する必要がある
そのためには連結リストに新しいnodeを追加する必要がある
したがって、ポインタを正しい順序で設定していることを確認する必要がある
どういう意味か？
head → bat → book → banana
new_node → blue
↑の図でheadが連結リストの開始点を表す変数であると想像してほしい
bananaはNULLを指している
そして、新たにmallocで作成したばかりの新しいnode、blueがある
blueをこの連結リストの新しい先頭にしたい場合、blueにheadから矢印を引くことを想像するかもしれない
しかし、これをやってしまうとbat以降のnodeへの繋がりが失われてしまう
headとnew_nodeがblueを指しているだけで、blueは何も指していない
→正しい順序は、まず新しいnodeであるblueに連結リストのheadの次のnode＝batへのポインタを設定すること
次に、連結リストの最初の要素であるheadからblueへのポインタを設定する
↑辞書内の全ての単語に対してこの操作を実行する
fscanfで辞書ファイルから単語を読み込み、
その単語を格納するために必要なメモリを割り当て、
その単語をnodeにコピーし、
ハッシュ関数を呼び出した結果に基づいて、
ハッシュテーブル内の連結リストの1つにそのnodeを挿入する
辞書内の全ての単語にこの操作を実行すると、メモリのハッシュテーブルに正常に読み込まれ、スペルチェック・プロセスを開始できるようになる
▼hash
メモリ内に辞書の単語を読み込むとき、および単語のスペルチェックを行うときには、ハッシュ関数を呼び出す必要がある
これは単語を取得する関数で、その単語を見つけたり、データ構造に単語を挿入したりするために使用する必要があるハッシュテーブルのインデックスを返す
ハッシュ関数はハッシュする単語を表す入力として文字列を取得し、その特定の単語に対応するハッシュテーブルのどのインデックスを使用する必要があるかを表す(負にならない整数である)符号無し整数を返す
入力として単語を取得する
その単語にはアルファベット文字が含まれ、アポストロフィも含む場合がある
そして、ハッシュ関数の出力は0からN-1までの数値インデックスになる
↑Nはファイルの先頭で定義されていたことを思い出してほしい
Nはハッシュテーブル内のバケットの総数、つまり、連結リストの配列の長さ
デフォルトではNは1に設定されている
ただし、Nをより大きな値に設定して、ハッシュテーブルにより多くのバケットを作成し、データをもう少し分散させることができる
重要なことに、ハッシュ関数は決定論的でなければならない＝同じ入力を何度与えても同じ出力を返す
例えばappleのような単語をloadするときに、単語appleのハッシュ値を計算して、appleをハッシュテーブルのインデックスに挿入することができる
そして、appleという綴りが正しいかどうかを確認するときに、appleという単語のハッシュ関数を呼び出して、前と同じ値を取得し、その特定の連結リストのみを確認できるはず。ハッシュテーブルを使用して、appleという単語が存在するかどうかを確認するということ
したがって、Nの値、つまりハッシュテーブルが保持するバケットの数、つまり配列の長さ、およびハッシュ関数が返す可能性がある値を決定する必要がある
Nの値が大きいほど、バケットとハッシュテーブルの数が多いことを意味するため、データが分散され、検索時間が短縮される可能性がある
ただし、ハッシュ関数の出力が0からN-1までの値であることを確認する必要がある
これは、ハッシュテーブルへの唯一の有効なインデックスになるため
関数が最終的にNより大きい値になる場合は、その値をNで割った値またはNで割った余りを取ることができる
つまり、適切な範囲内の値を取得することができる
ハッシュ関数には種類がある
非常に単純なハッシュ関数は単語の最初の文字を取るだけかもしれない
単語の最初の文字がAだったらハッシュ値は0になり、Bだったら1になる…Zなら25になる
この場合、アルファベットの全ての文字に1つずつバケットがあるため、Nは26になる
辞書内の単語が14万3千以上であることを考えると、この26だけのバケットでは足りなさそう…
そこで、最初の2つ、または3つ以上の文字を調べたり、文字の個々の値をすべて使用して何らかの計算を行ったりするなど、他のハッシュ関数の使用を検討することもできる
ハッシュ関数が完成すると、単語を取得して、ハッシュテーブル内のどの連結リストに対応するかを調べることができる
※個人メモ
ハッシュテーブルは配列の各要素が各連結リストの先頭へのポインタになっている
根本的に配列なので、各連結リストにはインデックスを利用したランダムアクセスが可能
▼size
size関数では辞書内にある単語の数を返す必要がある
方法はいくつかある
ハッシュテーブル内の全ての連結リストを繰り返し処理し、各連結リスト内のnodeの数を数えることを想像するかもしれない
または、ハッシュテーブルを読み込んでいるときに、それまでに辞書に追加した単語の数を何らかの方法で追跡し、その値をsize関数で返すこともできる
▼check
check関数では単語を取得して、その単語が辞書に載っているかどうかを確認する
check関数は単語を表す文字列を入力として受け取り、bool変数、trueかfalseを返す
単語が辞書内にあればtrue、なければfalseを返すように実装する必要がある
また、check関数は大文字と小文字を区別しないように設計する必要がある
まずやるべきことは、ハッシュ値を得るために、前に実装したハッシュ関数を利用して単語を取得し、その単語をハッシュすること
次に、ハッシュテーブルの特定のインデックスにあるそのハッシュ値で連結リストにアクセスする
個々の連結リストにアクセスすると、その単語が辞書にある場合、そのリストにあることがわかる。その単語がその連結リストになければ、辞書内にその単語は含まれないということ
そのため、一度に1つのnodeにアクセスして問題の単語を探し、文字列を比較するstrcmpに似たstrcasecmp関数を使用して、連結リストをトラバース(端から端まで横切る)する。
strcasecmpは大文字と小文字を区別せずに2つの文字列を比較できる。
したがって、単語に対して大文字を小文字に直す…などの操作を行う必要がない。
単語を正常に見つけることができた場合、trueを返す
連結リストをどのようにトラバースすればいいか？
head → bat → book → banana
↑の場合、headが連結リストの最初の要素へのポインタだとする
bookを持つnodeに対するポインタを持つnodeにあるbat…
例えばcursor(カーソル)という名前の変数を設定できることは想像に難くないだろう
最初は、この要素は連結リストの最初の要素へのポインタだが、それが探している単語でなかった場合、カーソルを連結リストの次のnodeに移動する
次のnodeはどこに保存されている？
現在カーソルが指しているnodeのnextフィールドに格納されている
cursor = cursor->next;
↑カーソルを取得し、カーソルの次のポインタが現在指しているものと等しく設定するということを意味する
そのため、連結リストの次のnodeにカーソルが移動する
そして、次のnodeをチェックしてそれが探している単語かどうかを確認できる
もう一度strcasecmpを使用して2つの文字列を比較し、同じ文字が含まれているかどうかを大文字小文字区別せずに確認する
それも探している単語でなければ、またcursor = cursor->next;を実行し、カーソルを次のnodeに移動するプロセスを繰り返す
問題の単語が見つかったらtrueを返す
どこでやめればいい？ある種のループになっている
最終的に連結リストの終端に到達すると、cursor = cursor->next;はNULLになる
したがって、ここでカーソルを次に移動するとcursorはNULLになり、単語が連結リストの中に見つからなかったことを意味する
この時点で辞書にその単語は含まれないと判断できるので、check関数はfalseを返す
連結リストをトラバースする方法を簡単に要約すると…
・連結リストの最初のnodeに設定されたカーソルから始める
・node->wordが探している単語かどうかをstrcasecmpで確認する
・探している単語でなければ、カーソルを次のnodeに移動し続ける
・探している単語が見つかったらcheck関数にtrueを返させる
・カーソルがNULLになったらcheck関数にfalseを返させる
▼unload
スペルチェッカの実行プロセスで割り当てたメモリを解放する関数
mallocを使用して動的にメモリを割り当てるときはいつでもそのメモリに対してfreeを呼び出し、解放してコンピュータに戻すまでがプログラマの責任であることを思い出してほしい
unload関数はmallocを使用して割り当てた任意のメモリでfreeを呼び出し、正常に実行できた場合はbool値、trueを返す。
ハッシュテーブルは実際には個々の連結リストの単なる配列であることを思い出してほしい
これらの連結リストはmallocを用いてメモリを割り当てたnodeで構成されている
したがって、これらのnodeをそれぞれ解放する必要がある
ハッシュテーブルを反復処理し、それらの個々の連結リストを調べて、それらの連結リスト内の全てのnodeでfreeを呼び出すことを想像するかもしれない
しかし、連結リスト内の全てのnodeを解放するにはどうすればいいか？
例を見てみよう
head → bat → book → banana
ここでも連結リストの最初の要素へのポインタになるheadという変数がある連結リストがある
この場合、batという単語が含まれるnodeにbookを指す次のポインタがあり、その次にはbananaを指すポインタがある
ここでもこのnodeに等しく設定されたcursor(カーソル)という変数を使用できると想像できる
まずbatへのポインタ。mallocを使用して最初にメモリを割り当てたこのnodeを解放したい場合、次のような構文を考えられる
free(cursor);
つまり、カーソルが指しているnodeを取得し、先に進んでメモリを解放する
しかし、そうしてしまうと、batがなくなってしまい、次のbook以降への道筋が失われてしまう
使い終わる前にメモリを解放してしまうと、解放する必要がある連結リスト内の残りのnodeにアクセスできなくなってしまう
この連結リスト内のどこにいるかを把握し、次のnodeを見失わないようにするために新たな変数が必要だと思われる
cursorがbatを指している状態に戻ってみよう
ここで、更にcursorと等しくなるtmpという変数を用意する
↑どちらも同じnode＝batを指している
つまり、どちらも連結リスト内のこの最初の要素のアドレスを含んでいる
ここでやりたいことは、この最初のnodeを指しているこの一時ポインタを解放すること
しかし、同時に連結リストの残りを見失わないようにしたい
そのためにできることは、cursor = cursor->next;という構文を使って、
最初の要素を解放する前に連結リストの次のnodeにカーソルを移動しておく
現在、カーソルは連結リストの2番目のnode＝bookを指していて、tmpは依然として最初のnode＝batを指している状態。
したがって、ここでfree(tmp);を実行すると、連結リストの残りを見失うことなくbatを解放できる(cursorが次のnode＝bookに移動しているから)
ここからは同じプロセスを繰り返す
→tmpをcursorと同じものにする(次のnodeを指す)
→cursorを次のnodeに移動する
→tmpを解放する
最終的に連結リストの終端に到達し、cursorがNULLを指したら終了
この時点でその連結リストに割り当てた全てのメモリは解放された
ハッシュテーブル内の全ての連結リストにこれを繰り返せば、ハッシュテーブル全体のメモリを解放することができる
▼手こずったところ
・table[N]に触るとセグメンテーション・フォールトになっちゃう
debug50を駆使して色々試したところ、table[N]自体がNULLだった
↑バケット＝連結リストの先頭であるheadにもmallocでメモリを割り当てる必要があった
・check関数でtable[hashed]に触るとセグメンテーション・フォールトになっちゃう
hash関数を頭文字に設定していたので、aのASCII値97を毎回引いてた←textから読み込んだ頭文字が大文字だった時に、例えばAのASCII値65から97引いちゃってたので、table[-32]とかにアクセスしてしまっていた
↑とりあえずhashed(hash関数の結果)に+32することで回避
▼dictionary.c 実装
// Implements a dictionary's functionality
#include <stdbool.h>
#include <stdio.h>
#include <strings.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "dictionary.h"
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
// Number of buckets in hash table
// Nはハッシュテーブルのバケットの数。変更可。
const unsigned int N = 26;
// Hash table
// 辞書内の単語を追跡するために使用するハッシュテーブル
// 配列なので、この時点でメモリは割り当てられている(mallocでメモリを取得する必要はない)
node *table[N];
// Loads dictionary into memory, returning true if successful, else false
// メモリに辞書を読み込む。上手く読み込めたらtrue、読み込めなかったらfalseを返す
// 辞書内の全ての単語をハッシュテーブルなどのデータ構造に読み込む
bool load(const char *dictionary)
{
// TODO
for(int i =0;i < N;i++)
{
table[i] = malloc(sizeof(node));
if(table[i] == NULL)
{
return false;
}
table[i]->next = NULL;
}
//まず、辞書ファイルを開く
FILE *file = fopen(dictionary,"r");
if(file == NULL)
{
return false;
}
//開いた辞書ファイルから文字列を1つずつ読み込む(1度に1つの単語)
char dic_word[LENGTH + 1];
while(fscanf(file,"%s",dic_word)!=EOF)
{
//これらの単語ごとに新しいnodeを作成する(値と次のnodeへのポインタを持つnode)
node *n = malloc(sizeof(node));
if(n == NULL)
{
return false;
}
//strcpyで単語をnのwordフィールドにコピーする
//strcpyの第1引数にはコピー先のアドレス、第2引数にはコピー元のアドレスを記入
strcpy(n->word,dic_word);
//そしてハッシュ関数を使用してその単語のハッシュ値を取得し、ハッシュテーブルにインデックスを付けて、
//このnodeを連結リストに挿入する時に使用する連結リストを決定する
unsigned int hashed = hash(n->word);
//最後にこれらの各単語を取得し、ハッシュ関数によって指定された場所にあるハッシュテーブルにそのnodeを挿入する
//まず新しいnodeであるnに連結リストの先頭の次のnodeへのポインタnextを設定
//一番最初の要素なら、nextはNULLになる(終端になるため)
n->next = table[hashed]->next;
table[hashed]->next = n;
}
return true;}
// Hashes word to a number
// 単語を取得してハッシュ関数を実行し、その単語に対応する数値を返す
unsigned int hash(const char *word)
{
// TODO
// まずはa～zでやってみる(ASCIIでは97～122なので、97を引く)
unsigned int hashed = (word[0]-97);
return hashed;}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
// 辞書に含まれる単語数を返す関数
unsigned int size(void)
{
// TODO
// とりあえずハッシュテーブルのnodeの数をひたすら数える
int size = 0;
for(int i = 0;i < N;i++)
{
for(node *tmp = table[i]; tmp != NULL; tmp = tmp ->next)
{
size++;
}
}
//headがN個あるので、その分を差し引けば単語数になる
size = size - N;
return size;}
// Returns true if word is in dictionary, else false
// 辞書の中にその単語があればtrue、無ければfalseを返す
bool check(const char *word)
{
// TODO
// まずは別途作成したhash関数でwordをハッシュ→どのバケットにあるかを確認
int hashed = hash(word);
if(hashed < 0)
{
hashed = hashed + 32;
}
// バケットの最初のnodeにカーソルを合わせる
// strcasecmp関数を使って比較(大文字小文字の区別をせずに比較することができる)
// strcasecmp(文字列1,文字列2)←文字列が等しければ0を返す(等しくなければ0以外)
node *cursor = table[hashed]->next;
while(cursor != NULL)
{
if(strcasecmp(cursor->word,word) == 0)
{
return true;
}
cursor = cursor->next;
}
return false;}
// Unloads dictionary from memory, returning true if successful, else false
// 辞書をメモリから解放する
bool unload(void)
{
// TODO
// cursorとtmpという二つの変数が必要。cursorで次のnodeを指してから、tmpでそのnodeをfreeにする
node *cursor;
node *tmp;
for(int i =0;i < N;i++)
{
cursor = table[i]->next;
while(cursor != NULL)
{
tmp = cursor;
cursor = cursor->next;
free(tmp);
}
}
return true;}