Latest topics > 正規表現のパターンを得るためのアルゴリズム

正規表現のパターンを得るためのアルゴリズム - Dec 02, 2006

XUL/Migemoの動作の中で一番のネックになっているのは「辞書から正規表現のパターンを生成する」処理だそうで、そのために、本家XUL/Migemoでは200KB近いキャッシュファイルまで用意されていた。plus7さんの環境では一文字のパターンに対するキャッシュを生成するのに14秒もかかった（その間Mozillaはフリーズする）とまで書いてあって、他をどんなに改善してもここが足をひっぱってるんじゃあなあ、という感じだ。

んで、少しでもこれを高速化できないかな？と思って自分の分かる範囲で考えてみた。

以下は現在のコード。本家のものを多少書き換えてはいるけれども、アルゴリズムは変わってはいない。

// linesは、見つかった辞書内のエントリの配列。
for (var i = 0, maxi = lines.length; i < maxi; i++)
{
  searchterm += lines[i].replace(/\n/mg, '') + '\t'; // ごみの消去とタブで結合
}
searchterm = searchterm.substring(0, searchterm.length-1);
var arr = new Array();
arr[0] = XMigemoTextService.sanitize(aRomanTerm).toUpperCase(); // 元の入力
arr[1] = zen; // 全角文字に変換したもの
arr[2] = kana; // カタカナに変換したもの
arr[3] = hira; // ひらがなに変換したもの
searchterm = arr.concat(searchterm.split('\t')).sort(); // つなげてソート
var terms = searchterm[0];
var tmp_2 = '^'+terms;
var ichimoji = '';
var tmpregexp = new RegExp(tmp_2, 'i');
for (var i = 0, maxi = searchterm.length; i < maxi; i++)
{
  if (!searchterm[i].match(tmpregexp)) {
    if (searchterm[i].length == 1) {
      ichimoji += searchterm[i]; // 一文字なので文字クラスにまとめる
    }
    else{
      terms += '|' + searchterm[i]; // ふつー。
    }
    tmp_2 = '^' + searchterm[i];
    tmpregexp = new RegExp(tmp_2, 'i');
  }
}
pattern2 = '[' + ichimoji + ']|' + terms;

以下が、できるだけループを使わないようにして書き換えたもの。ループと正規表現による文字列処理とどっちが速いか確証は持てなかったけど、JavaScriptの世界でループ回すよりCとかC++とかの世界でループ回した方が速いかなー、と。

var arr = [];
arr.push(XMigemoTextService.sanitize(aRomanTerm).toUpperCase());
if (zen.charAt(0) != '[') arr.push(zen);
if (hira.charAt(0) != '[') {
  arr.push(kana);
  arr.push(hira);
}
searchterm = arr.concat(lines).join('\n').replace(/(\t|\n\n)+/g, '\n');

if (zen.charAt(0) == '[') pattern += (pattern ? '|' : '') + zen;
if (hira.charAt(0) == '[') pattern += (pattern ? '|' : '') + kana + '|' + hira;

// 一文字だけの項目だけは、抜き出して文字クラスにまとめる
var ichimoji = searchterm.replace(/^..+$\n?/mg, '').split('\n').sort().join('');
if (ichimoji) {
  pattern += (pattern ? '|' : '') + '[' + ichimoji + ']';
}

// foo, foobar, fooee... といった風に、同じ文字列で始まる複数の候補がある場合は、
// 最も短い候補（この例ならfoo）だけにする
var lastStr = '\t'; // dummy
searchterm = searchterm
  .split('\n')
  .sort()
  .join('\n')
  .replace(/^(.+)$\n?/mg, function(aString) {
    if (aString.indexOf(lastStr) == 0)
      return '';
    else {
      lastStr = RegExp.$1
      return XMigemoTextService.sanitize(aString);
    }
  })
  .replace(/^.$\n?/mg, '') // 一文字だけの項目は用済みなので削除
  .replace(/\n/g, '|');
pattern += (pattern ? '|' : '') + searchterm.substring(0, searchterm.length-1);

何回か試してベンチマークとってみたら、どうやら書き換えた後のものの方が若干高速ではあるようだ。でも驚くほどの差はなかったのが切ない。

文字列のreplaceメソッドに関数を渡すというテクニックは最近知ったので取り入れてみたんだけど、ここの関数呼び出しのオーバーヘッドが大きいのかなあ。配列のsortに比較関数を渡すとオーバーヘッドのせいで独自実装のクイックソートより遅くなるという話もあるし。

追記。

JSの正規表現はPerlを摸してると聞いたので、Perl正規表現雑技とか正規表現メモとか見てみたら、こういう用途だと後方参照を使えば関数渡さなくても正規表現だけでいけることが分かった。

（略）
// foo, foobar, fooee... といった風に、同じ文字列で始まる複数の候補がある場合は、
// 最も短い候補（この例ならfoo）だけにする
searchterm = searchterm
  .split('\n')
  .sort()
  .join('\n')
  .replace(/^(.+)$(\n\1.+$)+/mg, '$1')
  .replace(/^.$\n?/mg, ''); // 一文字だけの項目は用済みなので削除
searchterm = XMigemoTextService.sanitize(searchterm)
  .replace(/\n/g, '|');
pattern += (pattern ? '|' : '') + searchterm.substring(0, searchterm.length-1);

ベンチマークとってみたら、最初の奴の2～3倍は速くなった。正規表現おもしれー！　まあ、Cとかで書くのに比べたらやっぱりずっと遅いんだけどね……