先日もちょっと話した、ゲーセンのクイズゲームについて。あのゲームには「並べ替え」というクイズ形式がある。
例えば画面上部に「ＮＡＴＯを日本語でいうと？」という問題が出ていて、下部には「洋北約大構西条機」のような意味不明な文字列が並んでいる。これを「北大西洋条約機構」に並び替えれば正解。
一種のアナグラムみたいなものですね。
で、単純なアナグラムならコンピュータに解かせた方が楽だよなぁとふと思ってしまったので、解答を出すプログラムを作ってみる。
公開すると迷惑をかけそうな気がするので、ロジックだけ。
・Wikipediaの全記事タイトルを拾ってきて、アンスコ以降を削った上でDBに登録する
・拾ってきたタイトル文字列を、1文字ずつコード順でソートして並び替える（プレスリー→ スリレプーみたいに）
・ソートされた文字列を、SQLiteのFTS3なテーブルにbigramな感じで登録する（スリ リレ レプ プー みたいに）
・この時、「ヴァ」とか「ヴィ」とかはブレるので「バ」とか「ビ」に変換して登録しておく
・ついでに気休めとしてUnicode正規化をNFKCでかけておく
・問題が出題されたら、一生懸命画面下部の文字列を入力する
・打ち込まれた文字列をWikiのタイトルに対してしたのと同じようにソートとかをし、それを2文字ずつに分割して、分割した子たちを1個ずつbigramで登録したテーブルに対して検索していく
・検索にヒットした回数が多い上位20件くらいを取得
・上位たちのレーベンシュタイン距離を図って、スコアが良いものから順に5つほどを画面に表示する
という風にしてやってみたところ、9割以上の確率で正当を出してくれた。
この記事で使われていた手法の廉価版みたいな感じかも。
スペルミス修正プログラムを作ろう
http://d.hatena.ne.jp/naoya/20090323/1237775357
現状、いくつか問題もある。
1. 俳句の上の句が表示されて、下の句を答えなさいみたいな問題には対応出来ていない（辞書を充実させれば対応可能）
2. 実行時間が3秒ほどかかる（チューニングすればもう少し速くできるとは思う）
3.長い文字列を答えないといけない場合、入力＋解答という手順を踏むと制限時間に間に合わない（7文字くらいが限度かも）
というわけで、今のところこれを使えば最強みたいなレベルにはなっていない。
また、キューブ問題（正六面体などの多面体の各面に1文字ずつ文字が記載されていて、それを組み合わせて解答を作成する）もこのロジックで対応できると思っていたのだけど、全文字を拾って入力するのにかかる時間がけっこう長くて、制限時間に間に合わない率が並べ替え以上に高いので微妙。
一番のボトルネックは入力時間なので、写真撮影＋画像認識までやった上でさらに辞書を強化すれば、実用品になると思われる。
但し、実際にそういうレベルで出来るようになってそれを実戦でつかったりしたらドン引きになるので、予習の時以外は使ってはいけない。
並べ換えは簡単そうだったので取っかかりとしてやってみただけで、個人的なターゲットは○×問題。「長嶋茂雄は右打者である、○か×か」という問題に解答するのは、とても難しい。とても作れない。そこが楽しい。