Subscribed unsubscribe Subscribe Subscribe

枕を欹てて聴く

香炉峰の雪は簾を撥げて看る

Taberarelooのタグ補完について

Taberarelooは基本的にid:ConstellationによるTombloo experimental branch on Chromiumだと思ってもらって結構で, 面白いと思ったことを放り込みます. そのためbugがでて急遽修正というreleaseも多いのですが...
また一方で

tomblooと違うというところは大抵bugであるとみなしてもらって結構です.

Twitter / Constellation: @you999 何かbugありましたかー? 基本的に ...

と公言していたりするのですが(Chromeでは実現不可能とかいう部分以外に関して), Tomblooと意図的に差別化している部分があります. それがタグ補完部分です. 今回logicをもうちょっと変更しいろいろ面白くなったので記事にしました.

補完, 何やってるの?

Taberarelooの補完はAbbreviation Scorerです.

// scoreFor関数部分
function(toscore, abb){
  if(!abb) return 0.9;
  var td = toscore.toLowerCase(), tdLength = toscore.length, pivot = abb.length;
  if(tdLength < pivot) return 0.0;
  var ad = abb.toLowerCase(), ahead, atail, found, score, tail, tail_score, penalty, skipped;
  for(; 0 < pivot; --pivot){
    ahead = ad.substring(0, pivot);
    atail = ad.substring(pivot) || "";
    found = td.indexOf(ahead);
    if(~found){
      tail = toscore.substring(found+pivot) || "";
      tail_score = arguments.callee(tail, atail);
      if(0 < tail_score){
        if(found){
          skipped = toscore.substring(0, found);
          if(/\s$/.test(skipped)){
            var nws = skipped.replace(/\S/, "").length;
            penalty = nws + (skipped.length - nws)*0.15;
          } else if(/^[A-Z]/.test(toscore.substring(found))){
            var nuc = skipped.replace(/[^A-Z]/, "").length;
            penalty = nuc + (skipped.length - nuc)*0.15;
          } else {
            penalty = skipped.length;
          }
        } else {
          penalty = 0;
        }
        score = (found + pivot - penalty + tail_score*tail.length)/tdLength;
      }
    }
    if(score) return score;
  }
  return 0.0;
}

これに現在のwordと候補candidateを渡してscoreを計算, scoreが高い順に表示しています. また, 0のときはまったく一致せずなので消し飛ばしています.
ちなみに, Tombloo/Taberarelooは日本語のtagでも普通に表示します. これは, Yahoo形態素解析APIによって振り仮名を振り, そこからローマ字に変換. それを読み仮名として付加することでこの情報からscoreを計算し, 表示しています.

で, これの問題点が先ほど

tombloo/tabeの日本語タグ補完 ziだけでなくてjiも"じ"にマッチしてほしい というほど日本語のタグないんだけれど

Twitter / ku: tombloo/tabeの日本語タグ補完 ziだけで ...

という風に, ziと変換されるとjiにならないんです. 例えばsha / syaだと先頭文字が一致しているのである程度無視してscoreが評価してくれたりするのですが, 先頭が違うといかんせんばっさり切られる可能性が高いです.

改善

これをばーっと変更しました.

// getCandidates method部
function(hint){
  var cands = [];
  var scoreFor = this.scoreFor;
  var func = function(reading){
    return scoreFor(reading, hint);
  }
  this.candidates.forEach(function(cand){
    if(cand.reading){
      var score = scoreFor(cand.reading, hint);
    } else {
      var score = Math.max.apply(Math, cand.readings.map(func));
    }
    if(score > this.score)
      cands.push({
        score: score,
        cand : cand
      });
  }, this);
  var values = this.values();

  var index = values.indexOf(hint);
  if(~index) values.splice(index, 1);

  return cands.sort(function(a, b){
    return b.score - a.score;
  }).reduce(function(memo, pair){
    if(pair && !~values.indexOf(pair.cand.value)){
      memo.push(pair.cand);
    }
    return memo;
  }, []);
}

雰囲気がつかめるでしょうか. candidatesを取得する部分のメソッドです. 現在持っているcandidatesについて逐一scoreForを計算し, その値がthis.score以上なら候補に乗せて, それをscoreの高い順に並べ替えてその値を入れて返しています.
今回変更した部分の一部は,

  var func = function(reading){
    return scoreFor(reading, hint);
  }
// ...
    if(cand.reading){
      var score = scoreFor(cand.reading, hint);
    } else {
      var score = Math.max.apply(Math, cand.readings.map(func));
    }

ここです. readingだけでなくreadingsという値で配列を許容しています. これはいったい何をしているかというと, 例えば「事件」というcandが存在するときに, 今までは

console.log(cand.reading);
// => 'zikenn'

だったのを, readingsに配列として

console.log(cand.readings);
// => ['jikenn', 'zikenn']

という風に考えられるpatternを収めることを許しました. この結果ziでもjiでもhitすることができます.

しかしこれではもしも「ジジジジジジジジジジジジジジジジジジジジ」みたいなtagがきたときに, 2**20の要素の配列というとんでもない数の要素が出てきて, あっという間に破綻してしまいます.
これを防ぐ目的で, このpattern作成関数には, pattern数が20以下までしか許容しないという風に制限がかかっています.
それがここです.

//  duplicateRomaReadings: method
function(s){
  // 分岐件数依存で一定数(この場合20)以上になるようであれば打ち切る(Tombloo標準の優先文字を使う)
  // 分岐件数が「ジェジェジェジェジェジェジェジェジェジェジェ」などになると天文学的になるのに対する対応
  // abbreviation scorerが後になるほど評価対象として低いので, 結果に影響が出ない
  var stack = [];
  var count = 1;
  for(var i = 0, roma, kana, table = this.katakana ; i < s.length ; i += kana.length){
    kana = s.substring(i, i+2);
    roma = table[kana];

    if(!roma){
      kana = s.substring(i, i+1);
      roma = table[kana] || kana;
    }

    var len = this.lengthMap[kana];
    if(len){
      var r = count * len;
      if(r > 20){
        stack.push(roma[0]);
      } else {
        count=r;
        stack.push(roma);
      }
    } else {
      stack.push(roma);
    }
  }
  return this.stackWalker(stack).map(function(l){ return l.join('') });
}

前提としてkatakata tableが用意されていて, また高速化のためにlengthMapが用意されています.
* allow loose char code map · 30203d0 · Constellation/taberareloo · GitHub

カタカナtableには'ジャ'などの要素のときだけ['ja', 'zya']のように配列で入っています.
lengthMapには配列のときだけその配列の長さが入っているので, このようにlenがあれば配列であったとすることができます.
countで計算しているのは, もしこの分岐を許容すれば, pattern数はいくらになるのかというのを計算しています.
つまり,

[['ja', 'zya'], ['ja', 'zya']]

からは

['jaja', 'jazya', 'zyaja', 'zyazya'].length === ['ja', 'zya'].length * ['ja', 'zya'].length;

の4パターンが作られます. 累乗です.
r > 20でpatternが20以上なら分岐を停止しています. このとき, ['ja', 'zya']なら先頭の'ja'がとられます. このため配列の1番目には優先度の高い代替文字が入っています.
20という数はどうなのでしょうか?
2分岐なら4文字, 3分岐ばかりなら2文字まで分岐します. しかし3分岐は「ジェ」しかないので, 実質2分岐がほとんどです. 多くて4文字16patterns, 少なくて3文字12patternsがほとんどでしょう.

多すぎるのではという目線から見ると, これはそもそも日本語のtagでしか計算せず, しかも日本語で分岐を持つものしか計算しません. 日本語であればそれほど長いものにはならない + 日本語のtag自体が極端に多くはないことを鑑みれば十分計算しきれる値であると思われます.

では少なすぎるのではという目線から見るとどうでしょうか? Abbreviation Scorerは文字が後に出てくるようになればscore評価対象として低くなります. これはこのやり方と非常に相性がいいです. つまり先頭から曖昧分3文字 (しかし実際3文字連続で曖昧な文字がつながることはそんなにないので, 3文字分になるころにはかなり多くの文字が評価されている) 分以降分岐を省き, 優先文字をとったとしても, 後ろのほうの文字なので誤差範囲として勘定することができるというわけです.

実際やってみましたが, 特に問題になるほどの遅延は発生しませんでした. Taberareloo 1.1.10から有効になっていますが, 目だったbug報告も来ていません. 問題になるようであればissueのほうに報告いただければいろいろ考えます. 最悪の場合は, optionによる切り替え可能にすればまあ何とかなるという楽観視点でお送りしております.

処理

一部へんな処理をしているのは, 高速化のためだったりします.
例えば, Tomblooはカタカナに変換するときに一気に変換するほうが効率的にいいので全部つなげてからtoKatakana()及びtoRoma()します. このとき単語境界に\u0000を使用しています. \u0000という文字はタグとしてはまあ現れませんね. また, \u0001とからへんの文字, 例えば改行とかもタグとしてはまあ現れません.
何でこんな話をするかというと, 先ほどのパターン生成関数. それぞれの候補一つごとに適用しないといけないので, 配列で区切っておかないといけないのですが, これだと元のTomblooの\u0000で連結したものより格段に速度が落ちます. メソッド呼び出しがびっくりするほど増えるので.
そこでTaberarelooでは重複pattern考慮によるpattern再計算を限られた単語にのみ適応するようにしています.

//toSparseRomaReadings:
function(s){
  var res = [];
  for(var i = 0, roma, kana, table = this.katakana ; i < s.length ; i += kana.length){
    kana = s.substring(i, i+2);
    roma = table[kana];

    if(!roma){
      kana = s.substring(i, i+1);
      roma = table[kana] || kana;
    }

    if(kana in this.lengthMap){
      roma = '\u0001';// contains flag
    }

    res.push(roma);
  }
  return res.join('').replace(/ltu(.)/g, '$1$1').split('\u0000');
}

method名がなんだかわかんなくなっちゃってますが, lengthMapにあるつまり重複パターンが考えられる場合, roma = '\u0001'にしています. このsは\u0000で連結された文字列なのですが,

\u0000----何らかの文字----\u0000----何らかの文字----\u0000

という形にすることで, Tomblooは高速化をしています.
ここで, Taberarelooは重複文字を見つけたときに\u0001をもぐりこませます.

\u0000----何らかの文字----\u0000----何らかの文字-\u0001----\u0000

これは後でsplit('\u0000')されます. このとき, splitされた後のそれぞれのstringであるreadingに対し,

if(~reading.indexOf('\u0001')){
  // 重複文字が見つかった場合
  // 重複文字も考慮するpatternで再計算する
}

として, すべて上記の重複パターンの可能性も含めたやり方で計算することを防いでいます.

補足

以上のやり方で, ある程度migemoなしで日本語を含めたtagをうまいこと補完することができます.