レアトークンの場合は飛ばさないほうがお得かもしれない

naoa commented 8 years ago

レアトークンがあると、chunkのデコードを大幅にスキップできるため、飛ばさないほうが得になることがあると思う

naoa commented 8 years ago

やはりお得な模様ただ、スマートにiiを選択できないどうしたもんか

本体フォークのngramで実装してみたやつ https://github.com/naoa/groonga/commit/5f88091c01f400f12bdc5154726c05772e7e03ae

naoa commented 8 years ago

良し悪しの判定がムズイ。悪くなるケースのが多いかもしれない。やはり基本的には飛ばした方がいいのかも。

naoa commented 8 years ago

はまるとはやくできるケースもある。レアトークンをいかし、その後のものを選択しても、結局トークン数が変わらないようなケース。の場合、ぐらいな気がする。

          {
            grn_obj tokens;
            GRN_RECORD_INIT(&tokens, GRN_OBJ_VECTOR, tokenizer->ii->header.domain);
            grn_table_tokenize(ctx, tokenizer->lexicon, (const char *)tokenizer->next, normalized_length_in_bytes, &tokens, GRN_TRUE);
            grn_p(ctx, &tokens);
            GRN_OBJ_FIN(ctx, &tokens);
          }

でinitの中でADD mode でトークナイズできる。この中からうまく選択できるだろうか。

naoa commented 8 years ago

まずトークナイズ結果を取得。それらを隙間があかないように結ぶグラフにする。最短経路の組み合わせを全部取得。最短経路の組み合わせのうち、レア度が高い組み合わせのものを１つ選ぶ。たぶん、トータルでレア度が高いというよりは、極端にレアなものを選んだほうが効果的かも？

naoa commented 8 years ago

このような処理は本体のtoken_info_buildでやりたいところ。まず実験してみて、いけそうならtoken_info_buildでの実装を検討する。

naoa commented 8 years ago

雑な実装だけど token_info_build に最短経路且つレア度が高い組み合わせ優先スキップを実装してみた。 https://github.com/naoa/groonga/commit/730211c6a1d5f48a4a66bfb46db22f4d310fd95e

こっちはトークナイザーで先頭から順に最短経路にスキップする実装。 https://github.com/naoa/groonga/commit/350230a942be04e105ae676b3a27c71c7d920b2f

最短経路 + レア度[0,1,3,5]: 0.09 sec / 0.11 sec(ii cursor min set なし) 最短経路 + 先頭順[0,2,4,5]: 0.26 sec / 0.26 sec(ii cursor min set なし) スキップなし[0,1,2,3,4,5]: 0.16 sec / 0.18 sec(ii cursor min set なし)

予想に反して先頭順で最短経路がスキップなしよりも遅くなるケースがある。レア度を考慮して最短経路を選ぶのは思ったより効果があり、頑張る価値がありそうだ。実装をもう少し頑張ってみよう。

[
  [
    0,
    1460778973.6488,
    0.000380277633666992
  ],
  [
    {
      "value": "情報",
      "position": 0,
      "force_prefix": false,
      "estimated_size": 1130550
    },
    {
      "value": "報処",
      "position": 1,
      "force_prefix": false,
      "estimated_size": 92306
    },
    {
      "value": "処理",
      "position": 2,
      "force_prefix": false,
      "estimated_size": 1475958
    },
    {
      "value": "理シ",
      "position": 3,
      "force_prefix": false,
      "estimated_size": 95071
    },
    {
      "value": "シス",
      "position": 4,
      "force_prefix": false,
      "estimated_size": 928786
    },
    {
      "value": "ステ",
      "position": 5,
      "force_prefix": false,
      "estimated_size": 1852329
    }
  ]
]

naoa commented 8 years ago

＋１トークンぐらいならたぶん、レア度を優先させたほうがいいケースもある。割り切れると最短経路が一意に決まってしまう。それをばらすために+1経路ぐらい許容したほうがよさそう。

naoa commented 8 years ago

token_info_buildでレア度を優先してオーバラップスキップできるとさらに利点があるかもしれない。token_cursorで単語とNgramトークン両方同じposで登録できるようにし、フレーズ検索の際、効率の良いものだけを選ぶ、なんてこともできるかも。

naoa commented 8 years ago

単純な幅優先探索なので、トークン数が増えると、キューのサイズが爆発的に増える。16トークン、2隣接で2582組み合わせ。最短までは382経路。探索にかかる時間も増えるだろう。

隣接リストのindex位置を32ビットで表現できる範囲にしてビット演算を使えば、省メモリにできるかな。スマートに実装できなそうだなぁ。

  uint32_t index = 1;
  int nth_bit = 0;
  index |= (0x01 << 31); /* n-1番目にビットをたてる */
  GRN_BIT_SCAN_REV(index, nth_bit); /* 先頭のビット位置を取得 */
  printf("index=%u nth_bit=%d\n", index, nth_bit);

naoa / groonga-tokenizer-yangram

レアトークンの場合は飛ばさないほうがお得かもしれない #4