Math::Symbolic::Custom::Pattern - Pattern matching on Math::Symbolic trees

Location : Home > Languages > Perl > Package
Title : Math::Symbolic::Custom::Pattern

　Math::Symbolic::Custom::Pattern - Math::Symbolic ツリーのパターン適合

use Math::Symbolic qw/parse_from_string/;
use Math::Symbolic::Custom::Pattern;

my $patternstring = "VAR_foo + sin(CONST * VAR_foo)"
my $pattern = Math::Symbolic::Custom::Pattern( $patternstring );

my $formula = parse_from_string("a + sin(5 * a)");

if ($pattern->match($formula)) {
  print "The pattern matches the formula.\n";
}
else {
  print "The pattern does not match the formula.\n";
}

# "a" が "VAR_foo" で 5 が CONST にあたるので
# "The pattern matches the formula" を出力する。
# "a + sin(5 * b)" は、 "b" に出会ったときには
# VAR_foo は既に "a" と見なされるのでマッチしない。
# "VAR" はいかなる変数にもマッチする。
# "TREE" はいかなるツリーにもマッチする。
# "TREE_name" 及び "CONST_name" は期待通りに働く。

# または
my $pattern = $some_formula->to_pattern();

print "yes" if $formula->is_of_form($pattern); # やや速い
# これは人間にも可読にいてある構文（syntactic sugar）でもある。
print "yes" if $formula->is_of_form("VAR + TREE"); # 遅い！
print "yes" if $formula->is_of_form($another_formula); # ちょっと遅い...

説明

　本モジュールは Math::Symbolic モジュールの拡張である。基本的なモジュールの親和性が要求されている。
　Math::Symbolic::Custom::Pattern モジュールは Math::Symbolic ツリーにおけるパターン適合ルーチンを実装している。パターン自身は特別な意味を持ついくつかの変数からなる Math::Symbolic ツリーで構成されている。
　モジュールは２つのインタフェースを提供する。このクラスが提供する new() 及び match() メソッドを用いるか、 Math::Symbolic ツリーで to_pattern() 及び is_of_form() メソッドを用いるかである。（Math::Symbolic::Custom::Pattern::Export モジュールによりエクスポートされている。詳細は is_of_form() を参照のこと。）

　いかなる Math::Symbolic ツリーからもパターンを構築できる。単純のために文字列表現だけからなるツリー "a + (b * c)" について考えよう。ツリーは Math::Symbolic->sparse_from_string("a+(b*c)") で返されるものである。

　以下のように呼び出したとしよう。

my $pattern = Math::Symbolic::Custom::Pattern->new("a+(b*c)");

　まさにこのツリーにマッチするパターンを生成する。
　Math::Symbolic ツリー $tree で

my $boolean = $pattern->match($tree);

のように呼び出せば "a+(b*c)" である場合を除いて $boolean は false になる。

　これまでのところはいいだろう。これは印象的でもないし、 Math::Symbolic ツリーの is_identical() メソッドは同じ働きをする。（パターン適合が約２倍速いことを除けば）
　しかしながら、以下の文字列からパターンを生成すればことなる振る舞いをする： "VAR + (VAR*VAR)"｡さて、a, b, c で変数を入れ替えてみよう。（a + (x*x), b + (b*b), ...）
　以下のパターン文字列で名づけられた変数（ただしリテラルではない）にマッチできる："VAR_first + (VAR_first*VAR_second)" これは２つめのツリーの括弧の中の最初の変数が括弧の外側の変数と同じではないのでツリー "a + (a*b)" にマッチするが、 "a + (c*b)" にはマッチしない。 Note VAR_second はパターン内で１度しか現れていないので両方の例で変数 "b" はどんな変数にもなることに留意されたい。
　一般の VAR 及び名づけられた VAR_foo パターン要素と同様、いかなるサブツリーまたは名づけられたツリーへの TREE_foo とマッチするために TREE を使うことができる。たとえば、パターン "TREE_a + 5*TREE_a" はツリー "sin(b+c) + 5*sin(b+c)" にはマッチするが "sin(b+c) + 5*cos(b+c)" にはマッチしない。ツリー "sin(b+c)" 及び "sin(c+b)" は同じではないことに注意すること。数学的には等値であるが、同じ内部表現を持たない。内部表現の正規化はこの例では単純であるが一般の場合には不可能である。注意されたい。
　最後に、変数と一般のツリーと動作するものは定数とも動作する。パターン "CONST_foo * a + atan(CONST_foo)" を指定したとする。これは "0.5*a + atan(0.5)" とはマッチするが "2*a + atan(0.5)" とはマッチしない。名づけられた定数が異なるためである。一般形 CONST はいかなる定数に対するワイルドカードになる。

エクスポート

　本モジュールは何もエキスポートしない。

メソッド

　以下がパブリックメソッドである。

new

　new() は Math::Symbolic::Custom::Pattern オブジェクトのコンストラクタである。
　Math::Symbolic ツリーを第1引数としてとり、パターンに変換する。match() メソッドのドキュメントを参照のこと。

match

　本メソッドは Math::Symbolic ツリーを第1引数としてとる。そうでない場合は致命的なエラーを発する。
　パターンがツリーとマッチすれば true を返し、マッチしなければ false を返す。マッチする（matching） と言う言葉がこの文脈で何を意味するかにつついて説明で確認して欲しい。
　実際問題として、様々な VAR_foo, TREE_bar, CONST_baz 識別子によりマッチしたサブツリーがどのようなものか知りたければ、成功したマッチングの返り値を確認することになる。それはキーが trees, vars, constants であるキー／値の対からなるハッシュへの参照である。これらのそれぞれはハッシュを示している。これらのハッシュはマッチしたサブツリーの名前を格納している。たとえば、パターンが TREE_x + TREE_x であり、foo*bar + foo*bar にマッチしたなら返り値は以下のようになる。

{
  constants => {},
  trees     => {},
  vars      => {
    'x' => 'foo*bar',
  }s
}

実際に文字列ではなく Math::Symbolic ツリーに対応していることを除けば。サブツリーは実際にサブツリーであることに留意されたい。これらを修正することは元のツリーも変更することになる。
　もし終了すれば、１度だけ存在するあらゆる格納場所を削除し、さらなる一般的な適合に置き換える。
　しかし後にパターンを結合するためにここではスキップしている。

参考資料

　本モジュールの最新バージョンは http://steffen-mueller.net または CPAN で入手可能である。
　Math::Symbolic::Custom::Pattern::Export は is_of_form() 及び to_pattern() メソッドを実装している。
　Math::Symbolic
　 Math::Symbolic の拡張の詳細については Math::Symbolic::Custom 及び Math::Symbolic::Custom::Base を参照のこと。

著者

　Steffen Mueller, <symbolic-module at steffen-mueller dot net>

著作権とライセンス

　本ライブラリはフリーソフトウェアであり、Perl 本体と同等の条件で修正／再配布してもよい。Perl 5.8.4 またはユーザの選択で Perl5 のこれ以降のバージョンでもよい。

Updated : 2007/05/29