Kernel/VM Advent Calendar 11日目(ということにして)　そろそろしりとりについて一言いっとくか

TST(Tsukuba Standard Time)ということで勘弁してもらえませんか・・・・！

はじめに

12月12日にSIProp勉強会というところで講演をしてきました。
え？おまえP2Pとかに明るいのかって？そんなわけないじゃないですか

SIProp勉強会とかに顔出していろいろ技術を勉強してみたいなとかぼんやり考えてそれをつぶやいたのが悪かったんですね
あっという間に発表する側に　　いいですかみなさん、SIPropに行くときはくれぐれも参加予告はしてはいけません(rakazawa)

で、問題は何を発表するか。分散ネットワークのことなんて何一つできないしどうしよう
悩んだ挙句、テーマは「高校生が研究をするとどうなるか」という感じのテーマで発表をしよう、と。
題名は「ぼくとしりとりの約3.0*10^3日間戦争〜今日、ぼくがしりとりのすべてを語り尽くす〜」
しりとりの研究をメインに３つの研究を紹介しました。

課題研究で作ったなんちゃってOS
一番いいしりとりの研究とつくばAC
ゲーム用自作インタプリタ

勉強会の雰囲気はid:rakazawaが書いてくれたのでじゃあぼくはぼくの発表のこととか書こうかなとか
発表したときの資料はこちら。ただし、odpな上に特殊フォント使ってたので崩れているというダメ仕様
http://dl.dropbox.com/u/8225108/siprop.odp

一番いいしりとりの研究とつくばAC

いろいろあるけど(とある理由で)時間がないのでしりとりのことだけ書かせてください

きっかけ

ユーザとしりとりをするwebサービス(ていうかbot)を公開
いろいろフィードバックがもらえたんだけど特に多かったのが「アルゴリズムどうにかしろ」
どうやったら長く続けさせる単語の選び方ができるか？

というわけで

仮説を立てた。
いま文字pから始まる単語を選ばなきゃいけないとき、あるアルゴリズムαによって次の文字nを決めることができるとき、これを繰り返すことでほぼ最長のしりとりを構成することができる(近傍探索法とかそれっぽい名前付いてるらしいですがぼくはしらない)
ここで暗黙の了解がひとつあるのですが、
ユーザが頭の中に保持している辞書≒こちらで用意した辞書
としています。いろいろツッコミ飛んでくるとおもうんですがちょっと待ってください。
ぼくらが「る」から始まる単語を連想しようとしたとき、「あ」で始まる単語よりは少ないでしょう。
また、広辞苑を引いても「る」より「あ」の方が多いでしょう。
つまり、単語の分布の割合はほぼ同じではないかという考え方です。
数学とかでも近似するときはA<

で、そのアルゴリズムαってなに

２つ思いつきました。
中学時代から「これならうまくいくべ」と思っていたやりかた
ぼくがいままでしりとりをしていたとき、「これなら長く続くんじゃないか」とぼんやり思っていた方法です。しかし、根拠無き方法だったのでプログラミングができるようになるまで検証のしようがありませんでした。さて内容はどういうのかというと

現在文字pから始まる単語を考えるとき、pから始まってその文字で終わる単語数が一番多い文字を次の文字とする

というもの。
いろいろ考えをひねり出して思いついたやりかた
そろそろ日本語で説明するのが難しくなってきます。パラメータxを取ります。(1〜使える文字数≒50)

現在文字pから始まる単語を考えるとき、文字pから始まることができる次の文字の候補のひとつひとつに対し、
その文字から始まる単語数が上位x位に入る文字の1〜x位まで単語数の総和を求め、候補の中で一番値が大きいものを
次の文字とする。

これで理解できたらあなた天才

***実験準備

形態素解析用の辞書を３つほど用意し、それぞれ測定しました。
IPA辞書が79610語、NAIST辞書が130503語、UniDic辞書が100588語ありました。
評価の基準として、(しりとりできた連鎖数)/(総単語数)を考えました。

***結果はどうでしたか

最初のアルゴリズムはこちら

辞書名	連鎖数	しりとり率
NAIST	8163連鎖	6.25%
IPA	6567連鎖	8.23%
UniDic	5963連鎖	5.93%

ひどい有様ですね
次のアルゴリズムはこちら

x	NAIST	IPA	UniDic
1	61640	35794	45868
10	65510	38533	50066
20	65602	38352	50244
30	65592	38241	50352
40	65651	38333	50434
50	65606	38357	50224
60	65601	38369	50222
70	65676	38418	50218

ほうほう

***結論

後者のアルゴリズムを使うといい感じにしりとりできるので幸せなしりとりライフが提唱できる
どんなに頑張っても自然界にある辞書を使うと50%くらいしかしりとりすることはできない。(これは既存の研究でもわかっている)