[Namazu-users-ja 139] Namazu 2.0.13 のパターンマッチングの問題修正

Tadamasa Teranishi yw3t-trns @ asahi-net.or.jp
2004年 11月 26日 (金) 21:05:17 JST


寺西です。

Namazu 2.0.13 で発生した時間のかかるパターンマッチングを修正しました。
これは、Namazu-users-ja#67, #111 の対策です。
特に環境に依存せずに発生するようです。このため、環境依存と思われる
Namazu-devel-ja #138, #51 とはまた別ということのようです。

症状が発生するサンプルデータを提供していただきましたので、これを
基に解析したところ、やはり html.pl 内で非常に時間のかかるパターン
マッチングがあることがわかりました。
# で、その改悪をしたのは私なんだが...。

今回、Excel ファイルで問題が表面化したのは、xlhtml で変換した HTML 
ファイルは巨大なファイルになりやすいためでした。($TEXT_SIZE_MAX を
超えることが多々あります。)
このため、Excel ファイルを処理するために、$TEXT_SIZE_MAX をより大きな
値に変更している方が多いのだろうと思われます。

他の HTML ファイルでも同じ症状が発生するわけですが、Excel 以外の 
HTML ファイルは、Excel の HTML に比べてファイルサイズが小さく、
あまり表面化しなかったということのようです。

これは、問題のパターンマッチングの処理は、O(n) ではないので、
ファイルサイズが大きくなればなるほど、時間が爆発的にかかるためです。
(O(n) ならサイズに比例だが、O(n^2) なら致命的)

# diff -u html.pl.old html.pl
--- html.pl.old 2004-11-26 21:01:02.000000000 +0900
+++ html.pl     2004-11-26 21:01:15.000000000 +0900
@@ -148,7 +148,7 @@

     if ($$contref =~ m!<LINK\s[^>]*?HREF=([\"\'])mailto:(.*?)\1\s*>!i)
{ #"
            $fields->{'author'} = $2;
-    } elsif ($$contref =~ m!.*<ADDRESS[^>]*>(.*?)</ADDRESS>!is) {
+    } elsif ($$contref =~ m!<ADDRESS[^>]*>(.*?)</ADDRESS>!is) {
        my $tmp = $1;
 #      $tmp =~ s/\s//g;
        if ($tmp =~ /\b([\w\.\-]+\@[\w\.\-]+(?:\.[\w\.\-]+)+)\b/) {

ところで、別の問題も見つけてしまいました。その話はまた別でします。
-- 
=====================================================================
寺西 忠勝(TADAMASA TERANISHI)  yw3t-trns @ asahi-net.or.jp
http://www.asahi-net.or.jp/~yw3t-trns/index.htm
Key fingerprint =  474E 4D93 8E97 11F6 662D  8A42 17F5 52F4 10E7 D14E




Namazu-users-ja メーリングリストの案内