Hatena::ブログ(Diary)

おもちうにょーんにっき

2010-12-17

***結論

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


はじめに

12月12日にSIProp勉強会というところで講演をしてきました。

え?おまえP2Pとかに明るいのかって?そんなわけないじゃないですか

SIProp勉強会とかに顔出していろいろ技術を勉強してみたいなとかぼんやり考えてそれをつぶやいたのが悪かったんですね

あっという間に発表する側に  いいですかみなさん、SIPropに行くときはくれぐれも参加予告はしてはいけません(rakazawa)

で、問題は何を発表するか。分散ネットワークのことなんて何一つできないしどうしよう

悩んだ挙句、テーマは「高校生が研究をするとどうなるか」という感じのテーマで発表をしよう、と。

題名は「ぼくとしりとりの約3.0*10^3日間戦争〜今日、ぼくがしりとりのすべてを語り尽くす〜

しりとりの研究をメインに3つの研究を紹介しました。

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

勉強会の雰囲気はid:rakazawaが書いてくれたのでじゃあぼくはぼくの発表のこととか書こうかなとか

発表したときの資料はこちら。ただし、odpな上に特殊フォント使ってたので崩れているというダメ仕様

http://dl.dropbox.com/u/8225108/siprop.odp

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

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

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

仮説を立てた。

いま文字pから始まる単語を選ばなきゃいけないとき、あるアルゴリズムαによって次の文字nを決めることができるとき、これを繰り返すことでほぼ最長のしりとりを構成することができる(近傍探索法とかそれっぽい名前付いてるらしいですがぼくはしらない)

ここで暗黙の了解がひとつあるのですが、

ユーザが頭の中に保持している辞書≒こちらで用意した辞書

としています。いろいろツッコミ飛んでくるとおもうんですがちょっと待ってください。

ぼくらが「る」から始まる単語を連想しようとしたとき、「あ」で始まる単語よりは少ないでしょう。

また、広辞苑を引いても「る」より「あ」の方が多いでしょう。

つまり、単語の分布の割合はほぼ同じではないかという考え方です。

数学とかでも近似するときはA<<Bのとき、A/B≒0とやるように、比で考えます(いまたぶん余計なこと言った)

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

2つ思いつきました。

中学時代から「これならうまくいくべ」と思っていたやりかた

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

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

というもの。

いろいろ考えをひねり出して思いついたやりかた

そろそろ日本語で説明するのが難しくなってきます。パラメータxを取ります。(1〜使える文字数≒50)

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

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

形態素解析用の辞書を3つほど用意し、それぞれ測定しました。

IPA辞書が79610語、NAIST辞書が130503語、UniDic辞書が100588語ありました。

評価の基準として、(しりとりできた連鎖数)/(総単語数)を考えました。

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

辞書名連鎖数しりとり率
NAIST8163連鎖6.25%
IPA6567連鎖8.23%
UniDic5963連鎖5.93%

ひどい有様ですね

次のアルゴリズムはこちら

xNAISTIPAUniDic
1 616403579445868
10655103853350066
20656023835250244
30655923824150352
40656513833350434
50656063835750224
60656013836950222
70656763841850218

ほうほう

後者のアルゴリズムを使うといい感じにしりとりできるので幸せなしりとりライフが提唱できる

どんなに頑張っても自然界にある辞書を使うと50%くらいしかしりとりすることはできない。(これは既存の研究でもわかっている)

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/siritoria/20101217/1292605214