next up previous
Next: 7 課題5 Up: 2004年度情報処理II     第12回 まとめ Previous: 5 課題3

6 課題4

文中のアルファベットの出現頻度は `e' が一番高く、 その次は… などと言われ、 古典的な推理小説の暗号の話の種になったりしている。 Gutenberg Project の中のテキストで、 そのことを確かめて見よ。 手作業ではなく、なるべくコンピューターにやらせること。 テキストごとに大きな違いがあるか? 文字が別の記号に置き換えられた場合、 出現頻度情報から解読することの可能性について論ぜよ(要するに他の文字の出現頻度はどの程度まで一定しているのか調べる - 実際に 試してみると良いのだけど)。 なお、 文字の頻度を調べる hindo.c というプログラムを 用意した2。(このプログラムは文字の出現頻度順には表示しないが、 sort を使えば簡単に頻度順に並べられる。どうすればいいか?今回 説明した話の簡単な応用である。)
hindo.c のコンパイルと使用例
isc-xas06% gcc -o hindo hindo.c  
isc-xas06% cat hindo.c | ./hindo  

テキスト、 あるいは作家ごとに単語の使用頻度の癖のようなものがあると思われるが、 そのことを Gutenberg テキストで実際に調べてみよ。 ルイス・キャロルとマークトウェインの書いたものにどの程度の差があるか?

前半 (文字の出現頻度) については、 複数のテキストについて、 出現頻度の上位 5 つくらいまでを並べた表を作って、 それを参照しつつ論じるというのが一つの解答ルートでしょう。

80day10.txt etaon
aesop11.txt etaoh
alad10.txt etaio
alice29.txt etaoh
anne11.txt etaon
frank11a.txt etaon
hfinn10.txt etoan
moon10a.txt etoai
sawy210.txt etaon
sawy311.txt etaon
sawyr10.txt etoan
wizoz10.txt etoah

のような表を作れば (ちなみにこの表は半自動的に作りました)、 何か言えそうだと分かるでしょう。

filter ディレクトリィにある 12 個の小説のテキスト・ファイルでは、 いずれも e の出現頻度が 1 位, t の出現頻度は 2 位. 3 位は大抵 a であり、テキストによっては o であるが、 その場合も a は 4 位に入っている、くらいは言えそうです。

全部混ぜて測ってみるとどうだろう?と思ったら
oyabun% cat *.txt | ./hindo | sort -n -r +1 | head -5
e: 362970 (12.2%)
t: 268142 ( 9.0%)
a: 233099 ( 7.8%)
o: 225494 ( 7.6%)
n: 203841 ( 6.8%)

これを見ると、a と o はコンマ以下の争いで逆転が起こることもうなずけます。

出現頻度の平均や分散を調べるのも良いかもしれません。

単語についても同じような調子で調べてみるわけです (省略します)。

復号 (解読) するスクリプト decode.sh を置いておきます 3

ちなみに
isc-xas06% ./hindo angou.txt | sort -n +1 -r|head -5
u:  1789 (12.8%)
o:  1197 ( 8.6%)
g:  1150 ( 8.2%)
m:   990 ( 7.1%)
n:   939 ( 6.7%)

の結果から u, o, g, m が実は e, t, a, o ではとあたりをつけて

cat angou.txt | /usr/ucb/tr uogm etao
とかするわけです。 それからこれは ``the'' だろうと当りをつけて、n を h に置換して… という調子でやっていきます。 単語の頻度を見るのも良いかも
isc-xas06% cat angou.txt | /usr/ucb/tr uogmn etaoh | ./top20x 
 281 the
 132 awr
  88 he
  83 oy
  73 a
  71 to
  65 V
  58 dv
  55 dw
(略)
isc-xas06%

``awr'' は ``and'' かな? ``oi'' は ``on'' かな?だとすると w と n に… そろそろ色々な単語らしきものが見えてきます。それでまた当りをつけて… (以下略)


next up previous
Next: 7 課題5 Up: 2004年度情報処理II     第12回 まとめ Previous: 5 課題3
Masashi Katsurada
平成16年7月15日