Title : Math::WalshTransform
|
Location : Home > Languages > Perl > Package Title : Math::WalshTransform |
|
Math::WalshTransform - 高速アダマール変換及びウォルシュ変換
use Math::WalshTransform;
@f = (1.618, 2.718, 3.142, 4.669); # ２のべき乗個数でなければならない
@FH1 = &fht(@f); # アダマール変換
@fh1 = &fhtinv(@FH1);
# または
@FW2 = &fwt(@f); # ウォルシュ変換
@fw2 = &fwtinv(@FW2);
@FH2 = &walsh2hadamard(@FW2);
@PS = &power_spectrum(@f);
import Math::WalshTransform qw(:ALL);
@whats_going_on = &biggest(9,&fwt(&sublist(\@time_series,-16)));
@EVENT1 = &fwt(&sublist(\@time_series,478,16));
@EVENT2 = &fwt(&sublist(\@time_series,2316,16));
@EVENT3 = &fwt(&sublist(\@time_series,3261,16));
$EVENT1[$[]=0.0; $EVENT2[$[]=0.0; $EVENT3[$[]=0.0; # 定数を無視
@EVENT1 = &normalise(@EVENT1); # ignore scale
@EVENT2 = &normalise(@EVENT2);
@EVENT3 = &normalise(@EVENT3);
@TYPICAL_EVENT = &average(\@EVENT1, \@EVENT2, \@EVENT3);
...
@NOW = &fwt(&sublist(\@time_series,-16));
$NOW[$[] = 0.0;
@NOW = &normalise(@NOW);
if (&distance(\@NOW, \@TYPICAL_EVENT) < .28) { &get_worried(); }
これらのルーチンは高速アダマール変換（fast Hadamard Transform）及びウォルシュ変換（Walsh Transform）並びにそれらの逆変換を実装している。またアダマール変換とウォルシュ変換を互いに変換するルーチンも含まれている。２つのリストの論理畳み込み（Logical Convolution）またはリストの論理自己相関（Logical Autocorrelation）・ウォルシュパワースペクトルの計算−つまり、ウォルシュ変換で行いたいことのほとんどを行う。たとえば64サンプルのブロックを変換し、いくつかの最大変換要素を以外を除き、逆変換することで再構築する。すなわちこれらの変換は時系列からもっとも重要な要素を抽出する。例えば時系列データ such as システム・ネットワーク管理データ・株価・通貨・生態系・世論調査・プロセス管理データなどを監視するソフトウェアにおいては重要な事柄を指摘することは有用である。
Version 1.10 からは Math::WalshTransform は変換のために C ルーチンを使用している。これで過去のバージョンに比べて25から30倍速くなっている。
多次元のアダマール変換・ウォルシュ変換・論理及び数的自己相関関数間の変換・ウォルシュパワースペクトル及びフーリエパワースペクトル間の変換については未対応である。
ルーチンは引数として１配列をとり、配列は１以上の参照のリストからなる。
fht(@f)
引数 @f は変換されるべき値のリストである。
その数は２のべき乗個でなければならない。
fht は @f のアダマール変換のリストを返す。
fhtinv(@F)
引数 @F は逆変換されるべき値のリストである。
その数は２のべき乗個でなければならない。
fhtinv は @F の逆アダマール変換のリストを返す。
fwt(@f)
引数 @f は変換されるべき値のリストである。
その数は２のべき乗個でなければならない。
fwt は @f のウォルシュ変換のリストを返す。
fwtinv(@F)
引数 @F は逆変換されるべき値のリストである。
その数は２のべき乗個でなければならない。
fwtinv は @F のウォルシュ変換のリストを返す。
walsh2hadamard(@F)
引数 @f はウォルシュ変換である。
walsh2hadamard は対応するアダマール変換のリストを返す。
hadamard2walsh(@F);
引数 @F はアダマール変換である。
hadamard2walsh は対応するウォルシュ変換のリストを返す。
logical_convolution(\@x, \@y)
引数は値 x 及び y の、要素数が２のべき乗個である同じサイズの２つの配列への参照である。
logical_convolution は値の２つの集合の論理的（または２進）畳み込みを返す。数学的説明セクションを見よ。
logical_autocorrelation(@x)
引数は値 x のリストである。
その数は２のべき乗個でなければならない。
logical_autocorrelation は値の集合の論理的（または２値）自己相関のリストを返す。数学的説明セクションを見よ。
power_spectrum(@x)
引数は値 x のリストである。
その数は２のべき乗個でなければならない。
power_spectrum は値の集合のウォルシュパワースペクトルのリストを返す。数学的説明セクションを見よ。
以下のルーチンはデフォルトではエクスポートされない。しかし ALL タグのもとではエクスポートされる。その場合は以下のように書かねばならない。
import Math::WalshTransform qw(:ALL);
biggest($k,@x)
最初の引数 $k は確保されるべき配列 @x の要素の数である。
biggest は最大の $k 要素がそのままでかわりに他の要素が全てゼロに設定された配列を返す。
$k が 0 または負の値であれば biggest は平均値（の絶対値）よりも小さい要素が全てゼロに設定された配列を返す。
sublist(\@array, $offset, $length)
本ルーチンは splice が行うように元の配列を変更することなしに @array の部分を返す。
substr が文字列に適用する文法と同じ種類の配列に適用する。sublist は配列の前から $offset 要素から始まる部分から抽出される。$offset が負の値であれば sublist は配列の後ろから始まる。$length が省略されれば配列の最後までが返される。$length が負の値であれば length だけ配列の最後から残すべき要素を計算する。
distance(\@array1, \@array2)
本ルーチンは２つの配列のユークリッド計量における距離を返す。すなわち対応する要素間の差の自乗和の平方根である。
size(@array)
本ルーチンは配列とゼロ配列とのユークリッド計量における距離を返す。すなわち各要素の自乗和の平方根である。
normalise(@array)
本ルーチンはその size が 1.0 であるようにスケール化された配列を返す。
average(\@array1, \@array2, ... \@arrayN)
本ルーチンは各要素が全引数配列の対応する要素の平均であるような配列を返す。
product(\@array1, \@array2)
本ルーチンは各要素が引数配列の対応する要素の積であるような配列を返す。
アダマール行列（Hadamard matrix）は±１からなる正方行列で行と列は互いに直交している。このことから行列の積及び転置は行列の次数に等しい単位行列の定数 N 倍の行列となる。もし N が２のべき数ならば、アダマール行列は再帰的に以下のように定義できる。
| 1 1 |
Had = | |
2 | 1 -1 |
| Had Had |
| N N |
Had = | |
2N | Had -Had |
| N N |
アダマール行列の各行はアダマール関数 Had(j,k) （ただし j = 0...N-1）に対応している。
ウォルシュ行列（Walsh matrix）はアダマール行列から定義され、符号の変化の数が昇順となるよう行を並び替えたものである。ウォルシュ行列の各行はウォルシュ関数 Wal(j,k) （ただし j = 0...N-1）に対応している。
１次のアダマール変換対は以下のように定義される。
F(j) = (1/N) * Sigma f(k)*Had(j,k) f(j) = Sigma F(k)*Had(j,k)
１次のウォルシュ変換対は以下のように定義される。
F(j) = (1/N) * Sigma f(k)*Wal(j,k) f(j) = Sigma F(k)*Wal(j,k)
２つの変換及び両者間の変換は構成要素の順を除けば等価である。
ウォルシュ関数は符号変化の数の昇順に並べてあるため、ウォルシュ変換はフーリエ変換のようである。そのため、CPU時間を大量に使うがよく使われる。行列の全要素が 1 または -1 であるので、変換にはほとんど乗算がなく、計算は効率的である。２つの配列 x・y に対する論理（２値）畳み込みは以下の式で定義される。
z(k) = (1/N) * Sigma x(k^j)*y(j)
ただし ^ は Perl の意味で用いられ、ビットワイズ排他的論理和である。
２つの数列の論理畳み込みのウォルシュ変換はそれらのウォルシュ変換の積であり、２つの数列の積のウォルシュ変換はウォルシュ変換同士の論理畳み込みであるという論理畳み込み定理（Logical or Dyadic Convolution Theorem）がある。これと同様に、
Likewise there exists a Logical Wiener-Khintchine Theorem, stating that ウォルシュパワースペクトルは論理自己相関関数（ Logical Autocorrelation Function）のウォルシュ変換を意味するという論理ウィーナー＝キンチン定理（Logical Wiener-Khintchine Theorem）がある。また論理畳み込み（Logical Convolution）と正規数的畳み込み（the normal Arithmetic Convolution）、ウォルシュパワースペクトルと正規フーリエパワースペクトルとを変換する線形変換が存在する。
Peter J Billam, http://www.pjb.com.au/comp/contact.html
以下のものを参照のこと。
|
|
Updated : 2007/06/05 |