月別アーカイブ: 2010年4月

AhoCorasick法がわかってきた?

SkRegExp に AhoCorasick 法を実装しようとこのサイトで勉強させてもらっていました。

ただ、1週間読んでいたんですが、正直仕組みがよく理解できませんでした。

それでも、ハッシュリスト、THasedList見たいなモノがあったほうが良さそうだと思ったので、THasedStringList をハックして作りました。

でもそこから先が進みませんでした。

どこがわからなかったかと言うと failure 関数の仕組みです。ここがどうしても理解できなくて一行もコードが書けませんでした。

ところが今さっき、このサイトで配布しているパワーポイントを見ていたら突然理解できました。

ビル・ゲイツは成功する秘訣は成功するまで続けることと言いましたが、わからないことを理解する秘訣は理解するまで続けることですね。

急にPHPのことを書き始めた理由

実は昨年、私のサイトで使っているフォームメールスクリプト skformmail.php を公開しようとした。
 
HTML文書とアーカイブはサーバーアップロード済みだったが、直後に忙しくなったためそのまま忘れてしまっていた。
 
ところが昨日、skformmail の問い合わせを受けて思い出した次第。検索エンジンには載ってしまっているようだ。
 
しばらくPHPの環境を動かしていなかったため、慌てて環境を整えていたらはまってしまった。バージョンが古いのに気が付いてしまったばかりにこうなったのだ。古いまま動かして置けばよかったんだ。
 
ちなみに私は、xampp for windows と net beans で php の開発は行っている。xampp の 1.7.3 を導入してはまったのである。

xapmmで受信メールにDateフィールドが設定されない

ローカルで受信したメールにDateフィールドが設定されないのは、sendmail_pathを有効にしたため。
 

; For Unix only.  You may supply arguments as well (default: "sendmail -t -i").
; http://php.net/sendmail-path
;sendmail_path = ""C:xamppsendmailsendmail.exe" -t"

上のようにコメントアウトしたらDateフィールドが設定された。
 
では、なぜ、昨日は送信できなかったのか?
 
今のところ不明。気持ち悪い。

xamppでmb_send_mailがエラーになる件

 初めてPHPについて書くが自分のための覚書。
 
xamppでmb_send_mailがエラーになる件。1.7.2から1.7.3にバージョンアップしたらエラーになるようになった。
 
いろいろ試したが、php.ini の [mail function] セクションの3行目のコメントをはずすと動いた。 
 

; For Unix only.  You may supply arguments as well (default: "sendmail -t -i").
; http://php.net/sendmail-path
;sendmail_path = ""C:xamppsendmailsendmail.exe" -t"

 
これって、Unix専用じゃないの?
 

 

Aho Corasick法を実装中

TSkRegExp.Optimize の OptimaizeSelect について、Aho Corasick で実装した方が効率がいいとのアドバイスを頂きました。
 
早速 Aho Corasick について調べてみました。既に書かれているものがあるならそれを使ったほうが楽です。
 
最初に、Delphi のソースを探しましたがありませんでした。まあ、Delphi で書かれたものがあるとは期待していませんでしたが、CやC++でも適当なものが見つかりませんでした。あっても、どう考えても日本語ダメだろうと言うものばかり。
 
使えそうなのはスクリプト系の言語ですが、こっちは言語そのものがよくわかりません。
 
仕方ないのでアルゴリズムを解説した英語のサイトを何とか解読しながら作っています。ちゃんと理解できているかが不安です。

QuickSearch関数の使い方

SkRegExp には QuickSearch という関数があります。
 
この関数は、正規表現の先頭がリテラルのときに前処理で使っています。
 
たとえば、abc* と言う正規表現の場合、文字列が ab で始まらないとマッチしません。そこで、正規表現エンジンを起動する前に、QuickSearch で検索して、ab があるかどうかをチェックしています。
 
今のところ使っているのはこれだけなんですが、他にも、正規表現がリテラル文字だけの場合、正規表現エンジンを起動せずに、QuickSeach で検索すれば高速に処理することもできます。まあ、この辺りはおいおい対応します。
 
SkRegExp の QuickSearch は大文字小文字を区別しない、全角半角を区別しない、ひらがなカタカナを区別しないと言った SkRegExp のオプションが使えますので試しに使ってみてください。
 
構文

function QuickSearch(AText: PWideChar; ATextLen: Integer;
  APattern: PWideChar; APatternLen: Integer; AOptions: TRECompareOptions): PWideChar; overload;

 
パラメータ

AText: 検索対象の文字列へのポインタ
ATextLen: 検索対象の文字列の長さ
APattern: 検索文字列へのポインタ
APatternLen: 検索文字列の長さ
AOptions: 検索オプション

検索オプション
coIgnoreCase: 大文字小文字を区別しない
coIgnoreWidth: 全角半角を区別しない
coIgnoreKana: ひらがなカタカナを区別しない

返り値

検索文字列が見つかったときはその文字列へのポインタを、見つからなければ nil を返す。

 

 
P := QuickSearch('あいうえおかきくけこ', 'うえ', [coIgnoreKana, coIgnoreCase]);

異常に遅くなってあたふた

SkRegExp の性能を評価するため、いろいろ変更したらベンチマークを取るようにしています。

比較のターゲットにしているのは、ロジックが異なる何ちゃって正規表現 TSkRegExp0.9.4、公開停止になってしまったらしい(?)かつての定番 TRegExpr、そして今の定番らしい TPerlRegEx の3つ。同じ正規表現検索を5万回実行させて速度を比較しています。

そのベンチマークを昨日チェックしたら、何と最下位に落ち込んでしまいました。

かつて、47ミリ秒で終わった正規表現が、1047ミリ秒まで落ち込んでしまいました。

1.0.10 を公開したときは、ある種の繰り返しでは我がSkRegExpがダントツに速かったのですが、その他の正規表現でも軒並み速度が落ちていました。

最適化していたつもりが裏腹に遅くなったんですから慌てました。

取り敢えず、先頭文字一致のチェックが以前より後退していることに気づいて訂正したんですが、大して速度が上がりません。

悩んだ末、今日、過去のバージョンを引っ張り出して比較したらそれも同じように遅い。

ここでやっと気づきました。「コンパイルオプションだ!」。

設定マネージャでReleaseにしてコンパイルしたら元に戻りました。取り敢えず一安心。

無駄な時間をすごしました。

と言うわけで、version 1.0.11 公開しました。

http://skregexp.komish.com/download/

TSkRegExp.Optimizeメソッド実装中

SkRegExpの現在はTSkRegExp.Optimizeメソッドの実装中。

前にも書きましたが、this|that|theseと言った正規表現をth(?:is|at|ese)と最適化することと、ついでに、連続したリテラル(abcのような)の最適化もここで行うことにしました。

連続したリテラルはTREParseで処理してましたが、これだと上記の最適化が難しくなるため、TSkRegExp.Optimizeで行うことにしました。

正直、この最適化でどれだけ高速化ができるかは疑問ですが、DFAエンジンを搭載するときには、この仕組みの方がずっとやりやすいので。

それから、1.0.10の最適化で、ある種の正規表現が極端に遅くなってしまいました。近日中に修正します。

1.0.10以降

自分的には 1.0.10 で一段落です。

まだまだやりたいことはありますが、毎日バージョンアップするなんてことは、トラブルがない限り、しばらくはないと思います。

Delphi2007+DephiSpeedUpの組み合わせでIDEクラッシュすると言うトラブルがありますが、この問題、私のスキルでは太刀打ちできないかも知れません。

今は、もっと地味な最適化に着手しています。

もっとも今作業しているのは最適化するための下準備ですけどね。

NFAレベルで最適化するには、NFAのステートを削除したり、移動したりといった、意外に厄介な作業が必要で、実は3日ほど苦しんでいます。

方法は見えているのですが、コードにするのに苦労しています。

たとえば、次のような正規表現があったとします。

this|that|these

これ本当は次のように書いたほうがより効率的に正規表現が実行できます。

th(is|at|ses)

この手の適化をやろうとしているのです。そのためには、NFAステートを削除したり、移動したりは必須なのです。で、それが厄介なんですねえ。