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

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

はじめに

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

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

で、問題は何を発表するか。分散ネットワークのことなんて何一つできないしどうしよう
悩んだ挙句、テーマは「高校生が研究をするとどうなるか」という感じのテーマで発表をしよう、と。
題名は「ぼくとしりとりの約3.0*10^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<

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

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

現在文字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%くらいしかしりとりすることはできない。(これは既存の研究でもわかっている)

スクリプト言語の仕様を策定しつつ構文解析します

本題に入る前に。identの扱いですが、crc16でハッシュ値にしてもちまわることにしました。

ここまで考えた。

enum e_expression {
   EXPR_TYPE_NOT    , // 'not' <expr>
   EXPR_TYPE_LITERAL, // (<number>|<string>|<flag>)
   EXPR_TYPE_ARRAY  , // '[' [<expr> ',']* <expr> ']'
   EXPR_TYPE_VAR    , // <ident>
   EXPR_TYPE_LET    , // 'let' <ident> <expr>
   EXPR_TYPE_IF     , // 'if' <expr> 'then' <expr> ['else' <expr>]
   EXPR_TYPE_LOOP   , // 'loop' <expr> ';' <expr> ';' <expr> <expr>
   EXPR_TYPE_CALC   , // ('add'|'sub'|'mul'|'div'|'mod') <array>
   EXPR_TYPE_LOGIC  , // ('and'|'or') <array>
   EXPR_TYPE_GUARD  , // ('lt'|'gt'|'eq') <expr> <expr>
   EXPR_TYPE_MULTI  , // '{' [<expr> ',']* <expr> '}'
   EXPR_TYPE_CALL     // '#' <ident> <array>
};

enum e_literal {
   LIT_FLAG,
   LIT_INTEGER,
   LIT_STRING,
   LIT_ARRAY
};

まだexpressionだけだけど勘弁

んでもってこれをもとに構造体の定義(途中)をば

typedef struct _EXPR {
   enum e_expression type;
   union {
      int ident; /* EXPR_TYPE_VAR */
      struct { /* EXPR_TYPE_LITERAL */
         enum e_literal type; // ()
         int num;
         char *str;
      } lit;
      struct { /* EXPR_TYPE_ARRAY */
         int size;
         struct _EXPR **d;
      } ary;
      struct { /* EXPR_TYPE_GUARD */
         enum e_operand type;
         struct _EXPR *left;
         struct _EXPR *right;
      } guard; 
      .
      .
      .
   } d;
} EXPR;

うんうん。

いまイメージしてるインタプリタの流れとしては

1. tokenize関数でTOKEN*のストリーム(みたいなの)を生成
2. syntax_analysis関数で複数の関数定義FUN*(未定義)の構文木をつくる
3. 内部でexpression関数とかが呼ばれて、exprの式の構文解析をしてEXPR*の構文木をつくる
4. 意味解析して無効な参照を見つける(余裕があったらここで末尾再帰の検出)

中間表現（まだ考えてない）を吐く

あ、で構文解析ですが

   init_token_chain(chain);
   chain = tokenize();
   cur   = chain;

こんな感じでこの前の字句解析をさせてから始める
このcurをどんどん次に進めていきながら解析をするようにしようかなっておもう

void expression(EXPR *expr) {
   switch(cur->type) {
   case TOKEN_TYPE_SYMBOL :
   case TOKEN_TYPE_OPERAND:
   case TOKEN_TYPE_VARTYPE:
   case TOKEN_TYPE_RESVED :
   case TOKEN_TYPE_NUMBER :
   case TOKEN_TYPE_IDENT  :
   case TOKEN_TYPE_STRING :
   case TOKEN_TYPE_EOF    :
   default:
      fprintf(stderr, "SYNTAX ERROR: unknown syntax\n");
      exit(EXIT_FAILURE);
   }
}

このcase内でcur = cur->nextとかやっていろいろ動かす

スクリプト言語をつくります

テスト期間とかなにそれおいしいので赤点とらない程度の勉強で。
DxLib使ってCでRPGをみんなで作ろうってことになって、イベントデータを外部ファイルに置くことに。
ここでイベントに制御構造とかを持たせようとすると、イベントデータを読み込んでそれを解釈するインタプリタが必要になった。せっかくだし自分の腕試しがてらスクリプト言語をつくってみよっかなって思う。

とりあえず言語仕様とか
・構文解析に先読みとかいう高度なことをしないように、前置記法を全面に。
・ifとかは評価ができる（＝式。）だけどlambdaの概念いまいちわからんので関数は式じゃない。
・ゲームのための言語だし、bool型じゃなくてflag型ってかっこつけたい
・イベント(引数なし)と関数(引数あり)を用意する
・なんかこう、式たくさん！←

「こんなふうなのが実行できたらいいな」からBNFを書き起こせないかとたくらむ

var battle_f:flag true;
event battle_hoge
   if eq battle_f true then {
      var i:int,
      var num_win:int 0,
      #msg("えりっく", "チャンスは4回だ！2回勝てたらLv上げしてやろう"),
      loop let i 0; and lt i 10 lt num_win 2; inc i {
         #msg("えりっく", "#{i}回目！"),
         case #battle() of
            "win"  : {#msg("えりっく", "三<(^q^)>三"), inc num_win};
            "lose" :  #msg("えりっく", "m9(^q^)");
            "other":  #msg("えりっく", "＼(^q^)／")
      },
      if gt num_win 1 then {
         #msg("えりっく", "ﾔﾗﾚﾀｰ"),
         inc $level
      } else 
         #msg("えりっく", "まけてやんのー^q^"),
      let battle_f false
   } else 
      #msg("えりっく", "もうたたかえないよ^q^").

わぁきもちわるい

とりあえずトークンの定義。
SYMBOLが記号()<>,.;とか。
OPERANDがincとかandとかltとかifとか。
VARTYPEがintとかflagとか。
RESVEDがvarとかeventとかtrueとか。
IDENTがmsgとかbattle_fとか。
STRINGが"えりっく"とか。
うん、こんなもんだろ。
BNFとか言ったけど正規表現ぽいのまぜてえりっくだけわかる定義。
::= '(' | ')' | '{' | '}' | ',' | '.' | ':' | ';' | '#'
::='loop' |'lt' | 'gt' | 'eq' |'and' | 'or' | 'let' | 'if' | 'else' |
　　　　　　'add' | 'sub' | 'mul' | 'div' | 'mod' | 'inc' | 'dec'
::='int' | 'flag' | 'string'
::='event' | 'fun' | 'var' | 'true' | 'false'
::=[a-z][a-z0-9_]*
::='"'[^"]*'"'

コードにするとこんなかんじ

#define NUM_SYMBOL   9
#define NUM_OPERAND 16
#define NUM_VARTYPE  3
#define NUM_RESVED  21

enum e_token_type {
   TOKEN_TYPE_SYMBOL ,
   TOKEN_TYPE_OPERAND,
   TOKEN_TYPE_VARTYPE,
   TOKEN_TYPE_RESVED ,
   TOKEN_TYPE_NUMBER ,
   TOKEN_TYPE_IDENT  ,
   TOKEN_TYPE_STRING ,
   TOKEN_TYPE_EOF
};
enum e_operand {
   OP_LOOP,
   OP_LT, OP_GT, OP_EQ,
   OP_AND, OP_OR, OP_LET, OP_IF, OP_ELSE,
   OP_ADD, OP_SUB, OP_MUL, OP_DIV, OP_MOD, OP_INC, OP_DEC
};
enum e_resved {
   RSV_EVENT, RSV_FUN, RSV_VAR, RSV_TRUE, RSV_FALSE
};

typedef struct _TOKEN {
   int type;
   union {
      char ch;
      int  num;
      char *ptr;
   } d;
   struct _TOKEN *next, *prev;
} TOKEN;

とりあえずさくっと字句解析作ってみた。

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include "recrio.h"

static TOKEN *__chain;

const char symbol[NUM_SYMBOL] = {
   '(', ')', '{', '}', ',', '.', ':', ';', '#'
};
const char operand[NUM_OPERAND][16] = {
   "loop",
   "lt", "gt", "eq",
   "and", "or", "let", "if", "else",
   "add", "sub", "mul", "div", "mod", "inc", "dec"
};
const char vartype[NUM_VARTYPE][16] = {
   "int", "flag", "string"
};
const char resved[NUM_RESVED][16] = {
   "event", "fun", "var", "true", "false"
};

static TOKEN* new_token(void) {
   TOKEN *tok = (TOKEN*)malloc(sizeof(TOKEN));
   if(tok == NULL) {
      fprintf(stderr, "FATAL ERROR: Failed to allocate memory.\n");
      exit(EXIT_FAILURE);
   }
   tok->next = tok->prev = NULL;
   return tok;
}

void init_token_chain(TOKEN *chain) {
   chain = new_token();
   chain->prev = chain;
   __chain = chain;
}
void  end_token_chain(void) {
   while(__chain->prev != __chain) {
      TOKEN *temp;
      temp = __chain->prev;
      __chain->prev = __chain->prev->prev;
      if(temp->type == TOKEN_TYPE_STRING || temp->type == TOKEN_TYPE_IDENT) {
         free(temp->d.ptr);
      }
      free(temp);
   }
   free(__chain);
}

static void __add_token(TOKEN *tok) {
   __chain->prev->next = tok;
   tok->prev = __chain->prev;
   __chain->prev = tok;
   switch(tok->type) {
   case TOKEN_TYPE_SYMBOL : printf("[SYMBOL ]'%c'\n", tok->d.ch);break;
   case TOKEN_TYPE_OPERAND: printf("[OPERAND]%s\n", operand[tok->d.num]);break;
   case TOKEN_TYPE_VARTYPE: printf("[VARTYPE]%s\n", vartype[tok->d.num]);break;
   case TOKEN_TYPE_RESVED : printf("[RESVED ]%s\n", resved [tok->d.num]);break;
   case TOKEN_TYPE_NUMBER : printf("[NUMBER ]%d\n", tok->d.num);break;
   case TOKEN_TYPE_IDENT  : printf("[IDENT  ]%s\n", tok->d.ptr);break;
   case TOKEN_TYPE_STRING : printf("[STRING ]%s\n", tok->d.ptr);break;
   }
}

// TYPE = {symbol | operand | vartype | resved | number | ident | string}
#define add_token(TYPE, TOK) add_ ## TYPE ## _token(TOK)

static void add_symbol_token(char symbol) {
   TOKEN *tok = new_token();
   tok->type  = TOKEN_TYPE_SYMBOL;
   tok->d.ch  = symbol;
   __add_token(tok);
}
static void add_operand_token(int idx_operand) {
   TOKEN *tok = new_token();
   tok->type  = TOKEN_TYPE_OPERAND;
   tok->d.num = idx_operand;
   __add_token(tok);   
}
static void add_vartype_token(int idx_vartype) {
   TOKEN *tok  = new_token();
   tok->type   = TOKEN_TYPE_VARTYPE;
   tok->d.num  = idx_vartype;
   __add_token(tok);
}
static void add_resved_token(int idx_resved) {
   TOKEN *tok = new_token();
   tok->type  = TOKEN_TYPE_RESVED;
   tok->d.num = idx_resved;
   __add_token(tok);
}
static void add_number_token(int number) {
   TOKEN *tok = new_token();
   tok->type  = TOKEN_TYPE_NUMBER;
   tok->d.num = number;
   __add_token(tok);
}
static void add_ident_token(char *ident) {
   TOKEN *tok = new_token();
   tok->type  = TOKEN_TYPE_IDENT;
   tok->d.ptr = (char*)malloc(strlen(ident) + 1);
   strcpy(tok->d.ptr, ident);
   __add_token(tok);
}
static void add_string_token(char *string) {
   TOKEN *tok = new_token();
   tok->type  = TOKEN_TYPE_STRING;
   tok->d.ptr = (char*)malloc(strlen(string) + 1);
   strcpy(tok->d.ptr, string);
   __add_token(tok);
}


static int is_symbol(const int ch) {
   int i;
   for(i = 0; i < NUM_SYMBOL; ++i) if(symbol[i] == ch) return 1;
   return 0;
}
static int is_operand(const char *str) {
   int i;
   for(i = 0; i < NUM_OPERAND; ++i) if(!strcmp(str, operand[i])) return i;
   return -1;
}
static int is_vartype(const char *str) {
   int i;
   for(i = 0; i < NUM_VARTYPE; ++i) if(!strcmp(str, vartype[i])) return i;
   return -1;
}
static int is_resved(const char *str) {
   int i;
   for(i = 0; i < NUM_RESVED; ++i) if(!strcmp(str, resved[i])) return i;
   return -1;
}

TOKEN* tokenize(void) {
   int ch;
   while(1) {
      while(1) { // skip while space
         if((ch = getchar()) == EOF) goto TOKENIZE_END;
         if(!isspace(ch)) break;
      }
      // type:symbol
      if(is_symbol(ch)) {
         add_token(symbol, ch);
         continue;
      }
      // type:string
      if(ch == '"') {
         char str[1024];
         char *p;
         for(p = str; p != &str[1024-2]; ++p) {
            if((ch = getchar()) == EOF) goto TOKENIZE_END;
            if(ch == '"') break;
            *p = ch;
         }
         *p = '\0';
         add_token(string, str);
         continue;
      }
      // type:number
      if(isdigit(ch)) {
         char str[128];
         char *p;
         for(p = str, *(p++) = ch; p != &str[128-2]; ++p) {
            if((ch = getchar()) == EOF) goto TOKENIZE_END;
            if(!isdigit(ch)) break;
            *p = ch;
         }
         *p = '\0';
         add_token(number, atoi(str));
      }
      // type:(ident|operand|resved)
      if(isalpha(ch) || ch == '_') {
         int idx;
         char str[1024];
         char *p;
         for(p = str, *(p++) = ch; p != &str[1024-2]; ++p) {
            if((ch = getchar()) == EOF) goto TOKENIZE_END;
            if(!isalnum(ch) && ch != '_') break;
            *p = ch;
         }
         *p = '\0';
         if     ((idx = is_operand(str)) != -1) add_token(operand, idx);
         else if((idx = is_vartype(str)) != -1) add_token(vartype, idx);
         else if((idx = is_resved (str)) != -1) add_token(resved , idx);
         else   add_token(ident, str);
      }
   }
TOKENIZE_END:
   /* add end of file identifier */ {
      TOKEN *temp = new_token();
      temp->type = TOKEN_TYPE_EOF;
      __add_token(temp);
   }
   return __chain->next;
}

実は構文解析の途中までできてるのもあるんだけど、ちょっと不満な点があるからこれから書きなおす。