技術的な解説

Wiktionary から単語の読みと説明を抽出して、それを元にちゃちゃっとクロスワードを生成してアプリに組み込んでいます。

まずデータ取得部について。

Wiktionary から全ページの最新版のダンプ(jawiktionary-YYYYMMDD-pages-meta-current.xml) を落としてきて、SAX で parse します。 これがまた XML になっているようでなっていない ので困ったものです。具体的には以下のような page 要素がだーっと並んで 250MB くらいのファイルになっています。

どういうことかと言うと...

text 要素がなかなかキてます。しかも単語ごとにいろんなバリエーションがあります。 なので、心折れそうになりながらも、ひたすら泥臭く解析します。

parser handler はこんな感じ(抜粋)。Ad hoc 楽しいめう!

こうしてなんとか (単語の読み, ヒント)[] が揃います。これを pickle にしておきます。今やるなら JSON にするところです。

そしたら今度はクロスワード生成部分です。

まず (単語の読み, ヒント)[] をシャッフルして、適当な大きさの白紙の問題ボードを作っておきます。

あとはひたすら、単語の置き方を全列挙してその中から 1 つランダムに選んで置いていきます。

単語の置き方とは、単語を置いた時ボードからはみ出なくて、置こうとしているところに既に違う文字や同じ方向に置かれた単語に含まれる同じ文字が置かれていなくて、これまで 1 個も置かれていない、または置こうとしているところに既に今回置く方向と直行する方向に置かれた単語の一部である同じ文字が置かれていてるようなものが 1 個以上あって、置こうとしている単語の周りのマスが既に置かれた同じ文字の所以外すべて空白であるような置き方 (x, y, direction) のことです。

意外とややこしいです...。

単語が 6 つ以上置けたらクロスワードが 1 問できたことになるので、実際に使われている大きさにボードをリサイズして記録します。で、ボードを空にして次の問題作成に移ります。

置き方がなくて詰んだ場合は使用単語を後ろにまわしてから再試行します。 未使用単語の残りが少なくなってくると何回やっても詰むことがあるのでそういう単語は捨てます。

よく覚えていないですが、695 問の生成に 30 秒くらいかかった気がします。この程度で終わるなら高速化は不要ですね。 問題セットが出来上がったら problems.js に出力します。

こんな感じ。

ということで、コンピュータっぽいことをして作ったなぁという実感が湧いてきます。

UI 部分については、ちとチープさが否めない感があります。これは今後の課題です。

以上、「クロスわ〜ず」の紹介でした。

2016/11/08
テーマ: リリース / 2016 / すべて