Home > Latest topics

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

宣伝。日経LinuxにてLinuxの基礎?を紹介する漫画「シス管系女子」を連載させていただいています。 以下の特設サイトにて、単行本まんがでわかるLinux シス管系女子の試し読みが可能! シス管系女子って何!? - 「シス管系女子」特設サイト

正規表現のパターンを得るためのアルゴリズム - 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とかで書くのに比べたらやっぱりずっと遅いんだけどね……

分類:Mozilla > 拡張機能 > xulmigemo, , , , , , , 時刻:00:42 | Comments/Trackbacks (0) | Edit

Comments/Trackbacks

TrackBack ping me at


の末尾に2020年11月30日時点の日本の首相のファミリーネーム(ローマ字で回答)を繋げて下さい。例えば「noda」なら、「2006-12-02_algorithm.trackbacknoda」です。これは機械的なトラックバックスパムを防止するための措置です。

Post a comment

writeback message: Ready to post a comment.

2020年11月30日時点の日本の首相のファミリーネーム(ひらがなで回答)

Powered by blosxom 2.0 + starter kit
Home

カテゴリ一覧

過去の記事

1999.2~2005.8

最近のコメント

最近のつぶやき