のんびり読書日記

日々の記録をつらつらと

ナンクロを解く(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