わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

プログラミング科目の最終回~トライグラムか,連想配列か,自己参照か

f:id:takehikom:20210131075855j:plain

 前の前の木曜日の授業最終回,表紙の直後のスライドです.
 これを題材にしたきっかけは,1年ほど前の,教員間のメールです.プログラミング言語を決めていなかったけれど,1つにするよう要請があって協議していたときの話で,さる先生のメールに書かれていたのは「連想配列」です.
 とはいえ文脈としては,連想配列をサポートしていないC言語は学習に適していないという話ではなく,配列や繰り返しなど,プログラミングの基本を学んだ後の発展的なトピックとして,連想配列(辞書型データ構造)を紹介し実際にプログラムを動かしてもらうのが,いいのではないかといった内容でした.
 結局今年度は「Cコース」と「Pythonコース」に分かれました.Cコースの授業の最終回,授業計画では「プログラミング活用3」と書いていたこの回に,何を写経してもらうか検討したときに,連想配列を思い出したのでした.
 画像上部の「(1/3)」は,「トライグラム」というトピックで3枚,スライドを用意したうちの1枚目という意味です.2枚目以降は,スライドではなく地の文で説明します.「どのような3文字の並びが何回出現するか」を,プログラムで表すなら,次のような代入ができればよい,と考えます.

count["the"] = 40; 

 添字(a[b]のbの部分)に数値以外の値も使用できる配列を,「連想配列」といいます.「ハッシュ」「辞書」などと呼ばれることもあります.
 なのですがC言語の配列では,添字は整数でないといけません.JavaScriptで「count["the"] = 40;」という文を書いて差し支えなく,Pythonなら辞書,JavaならHashMapで,連想配列が実現できることは,最終回の授業日に受講者向けに公開した文章で言及しています.
 ではC言語でどうするかというと,3文字だから(そしてcharは整数型だから),3次元配列で表現するのが一つの方法です.代入は例えばcount['t']['h']['e'] = 40;になります.
 なのですが,この方法は採用しませんでした.3次元配列のトータルの要素数は,今どきのプログラムでは問題になりません.そこではなく,入力をもとに出現頻度を3次元配列に格納したあと,「どのような3文字の並びが何回出現するか」の出力処理に3重ループが必要となり,オンラインプログラミング環境ではここで,処理の停止が発生し得ると考えたからでした.
 かわりに(そして文字列から数値へのマッピングC言語で実現する方法として),要素数の同じ2つの配列を使用しました.コードは次のようになります.

char list[500][4];
int count[500];
strcpy(list[48], "the");
count[48] = 40;

 list[数値]が保持する文字列の出現回数をcount[数値]として,2つの配列listとcountを対応付けるわけです.
 「500」という,宣言時の要素数により,プログラムでは500種類の「3文字の並び」しか格納できないことになります.そのかわり前述の,オンラインプログラミング環境での停止の可能性を減らせます.ちなみに,授業の推奨環境paiza.IOで,サイズnの順列(ABC…の並び)を出力させたところ,数千行の出力で打ち切られました.
 トライグラムの紹介と,連想配列,それをC言語でどう実現するとよいかを,3枚のスライドにしても,まだソースコードとはいきません.というのも,「A new study.」が入力のときに,「A n」「ew 」「stu」「dy.」が「3文字の並び」なのだと誤解されるとまずいからです.
 プログラムの準備として,「1文字目から3文字目まで」「2文字目から4文字目まで」…の順に3文字ずつ取得すること,制御文字・非ASCII文字・空白文字は対象外とすること,ピリオドをはじめ記号はそのまま文字とすること,大文字は小文字に変換することを,箇条書きにしました.このように取り決めておくと,「A new study.」に対する3文字の並びは「ane」「new」「ews」「est」「stu」「tud」「udy」「dy.」になります.手作業で書き出しましたが,長さMの系列に対するn-gramの延べ語数はM-n+1で,10-3+1=8ですので合っています.
 C言語でプログラムを書くにあたり,3文字の並びは500語までを配列に格納し,それ以降に新たに出現する3文字の並びは無視すること,そして入力は,これまでのscanfではなく,getcharを使用して1文字ずつ読み出すこと,という情報も加えると,「プログラムの準備」は2枚のスライドに分かれました.
 ソースコードとその解説については省略します.ただし1点だけ記しておきます.最初に「ane」の3文字の並びを作り(上記と別のcharの配列に格納しておき),入力として「w」を受け取ったときに「new」に変更するための処理については,第3クォーターの授業の,配列の箱モデルをもとに図示しました.
【以下,事情により非表示とします.】