ナンクロを解く(1) 辞書作り
前回はナンバープレイスを解いたので、今度はナンクロを解いてみます。ナンクロなんて知らない!という人は、wikipediaのナンクロのページを読んでください。
http://ja.wikipedia.org/wiki/ナンバークロスワード
ナンクロを解くには、カナをつなげた単語がちゃんと存在する名詞であることを確かめる必要があります。そこで、まずはナンクロ用の辞書を作りたいと思います。
クロスワード用の辞書としては、豚辞書というフリーの辞書が公開されていますので、今回はこの辞書を使います。下のページから『豚辞書』(第14版)がダウンロードできます。
http://www2u.biglobe.ne.jp/~butasan/download.htm
この辞書では以下のように1行1単語で構成されています。
あー
あーういんあれん
あーかいば
あーかいばー
あーかいぶ
あーかいぶす
あーかんさす
あーかんそー
あーがいる
あーがいるがら
このテキストファイルのまま使って問題を解いてもいいのですが、せっかくなのでもう少し効率的に辞書を引けるようにしたいと思います。
ナンクロでは同じ番号の箇所は同じカナが使われますので、それをヒントにして単語を推測します。例えば下の例では、単語は5文字で、2番目4番目のカナが同じで真ん中は1,2,4,5のどのカナとも違うということが分かります。このことから、おそらくこの単語は「しんぶんし」だろうということが分かります。
し 3 1 3 し →しんぶんし
このようにナンクロでは単語中のどの文字とどの文字が等しいか、というパターンの情報が重要になります。そこで、辞書の形式を以下のようにキーを単語のパターン、値をそのパターンにある文字列のリストとします。
12342123 あーるゆーあーる せんとびんせんと
1233145 いけだだいさく
12344356 あなたににたひと おらんだだんどく しようここうべん
121223 あいあいいど だいだいいろ
1223245 しののめのみち ずいいけいやく
12344156 かいせききかがく しやげききしよう しんけいいしよく つわもののつかさ
123131 うとそうそう
こうすることで、ナンクロの問題中の各数字列に対し、そのパターンに合う文字列の候補を取得できます。あとはその候補の中から、すでに数字<->カナの割り当てが分かっているものを当てはめて絞り込めばいいだけです。
では実際に辞書を作ってみます。今回はまたPerlで。
#!/usr/bin/perl # # ナンクロ用の辞書DBMを作成 # # Usage: # make_dicdb.pl dbpath < textfile # use strict; use warnings; use Encode qw(decode); use TokyoCabinet; sub make_pattern { my $word = shift; return if !$word; my $dec = decode 'utf-8', $word; my %map; my $cnt = 1; my $pattern; foreach my $ch (split //, $dec) { $map{$ch} = $cnt++ if !exists $map{$ch}; $pattern .= $map{$ch}; } return $pattern; } sub usage_exit { print "Usage: make_dicdbm.pl dbpath < textfile\n"; exit(1); } my $dbpath = shift @ARGV; usage_exit() if !$dbpath; my $dicdb = TokyoCabinet::HDB->new(); if (!$dicdb->open($dbpath, $dicdb->OWRITER | $dicdb->OCREAT | $dicdb->OTRUNC)) { die 'DBM error:' . $dicdb->errmsg($dicdb->ecode); } while (my $line = <STDIN>) { chomp $line; next if !$line; my $pattern = make_pattern($line); my $val = $dicdb->get($pattern); if ($val) { $val .= " $line"; } else { $val = $line; } $dicdb->put($pattern, $val); } if (!$dicdb->close()) { die 'DBM error: '.$dicdb->errmsg($dicdb->ecode); }
実行してみます。
% nkf --utf8 -d --overwrite buta014.dic % ./make_dicdb.pl dic.hdb < buta014.dic % tchmgr list -pv dicdb.hdb | head -10 11234562 いいんちようせん おおうたのしよう おおかみのえんか おおかみのばんか つついじゆんけい ななくさのせつく 123341 いおつつどい こせいいんこ しよううつし 121341 あくあとぴあ ありあかしあ いけいかせい いちいしめい いちいんせい うたうりゆう うほういどう うもうじよう うるうびよう くにくのさく しやしんぎし みなみのうみ ゆにゆうしゆ 12324125 しよちようしよく 112334 いいじままり おおはししぎ こころおおし ちちおややく ははおややく みみをすすぐ 12324524 あーさーくらーく おうふうりようり しよくようじよう たんげんしぶんし 12343545 えいこくこうくう 123424 えんこじんじ かいだんいん かきげんきん げーむるーる げつたーつー こせおんせん ずいしんいん そとぶうとう だいしんいん だいせんいん ばいしんいん ばとみんとん みさせいさい めんずのんの よこほうこう らなたーなー りしゆんしん 11211343 おおしおおんせん 11234556 おおそりはししぎ おおたきえいいち
ちなみに最長のパターンの1例はこんな感じ。思ったより短いかな?豚辞書だけだとちょっと単語量が少ないかもしれないですね。
12134536 かすからさぐらだ きんきようちよく しんしよくぎよう しんしよくさよう ほくほうりようど みなみじゆうじざ ゆにゆうぎようむ ゆにゆうちようか
今回の辞書の作成はここまでですが、更なる改良として単語の使用頻度の利用が考えられます。同じパターンの単語でも、やはりよく使われる単語の方が問題にも使用されやすいと思いますので、当てはめてみるときは使用頻度の多いものからの方が早く問題が解ける確率は高いでしょう。気が向いたらその辺も追加してみようと思います。
次はこの辞書を使って、実際にナンクロの問題を解いてみようと思います。
また、もっと効率のいい辞書形式が有るでしょ!などのご意見が有りましたら、ぜひ教えてくださいm(_ _)m