フーリエ変換についてこれまでほぼ知らなかったのだが、大学の渋谷先生の講義で遂に出会ったので書いておく。講義資料はで、ここからの引用も多い。
個人的に気づきだったこと
-
ハミング重みは多項式の積の係数っぽくなる。
-
逆DFTは関数のN個の値から係数を導く操作だと思う。
問題設定
ハミング重みを求めたいとする。
ハミング重みとは、一致している文字の数を表す。
図は渋谷先生の講義資料から拝借
https://www.hgc.jp/~tshibuya/classes/seq2021_2fft.pdf
ハミング重みと多項式
文字の種類は結構少ないとし、今は「Cの一致数」についてだけ考えることにする。
一つ目の文字列（ここではAATGTCGCTACGTCGTCCAACGCATTAC->0000010100100100110010100001）と、二つ目の文字列（ここではCTACATG->1001000）を考える。
それぞれに対して、多項式を定義する。
一つ目: AATGTCGCTACGTCGTCCAACGCATTAC:
f(x) = 0 * x^n + 0 * x^{n-1} + ............ 0 * x^1 + 1 = An * x^n + An-1 * x^{n-1} + ......... A1 * x + A0
二つ目:CTACATG
g(x) = 1 * x^m + 0 * x^{m-1} + ............ 0 * x^1 + 0 = Bn * x^n + Bn-1 * x^{n-1} + ......... B1 * x + B0
こう思うと、f(x) * g(x)のx^mの係数についてかんがえると、Am * B0 + Am-1 * B1 ..... + A0 * Bm とかになっていて、なんかハミング重みっぽくなってくる。
ここで、Bを反転してみると、f(x) * g(x)がハミング重みを表しそう（はじっこの方はだめだけど）
ということで、多項式の積f(x) * g(x)が計算できればよい。この多項式の計算で出てくるのがFFT。
FFTについて
tatyamさんのを参考にした
一番書き残しておきたいこと：逆DFTは関数のN個の値から係数を導く操作だと思う
DFTと逆DFT
ぐぐると、周波数成分だとか、スペクトルだとか言う話もしばしばでてくるが、こういった三角関数の話は一旦ここでは忘れて多項式の世界を考える。
DFT
数列 A = (A0, A1, .... An) と、f(x) = An * x^{n} + ..... A1 * x^{1} + A0を考える。
今、単位円の根（e^{0*2*pi/N}など）にたいして、f(e^{0*2*pi/N})などを求める。
（お気持ち：これ単体で何か起きることはなさそう。代入して求めるだけなんよね）
逆DFT
ある多項式fをf(x) = CN * x^{N} + ..... C1 * x^{1} + C0として、以下のN+1個の入力-出力について値が分かっているとき（f(e^{0*2*pi/N}), f(e^{1*2*pi/N}), ... f(e^{(N-1)*2*pi/N})）CN,CN-1,.....C0が求まる。
（これは、e^{1*2*pi/N}....の性質がいいからか、楽に求まり、かつ必ず求まる？）
DFTと多項式
A = (A0, A1, .... An) と、B = (B0, B1, .... Bm)があって、f(x) = An * x^{n} + ..... A1 * x^{1} + A0, g(x) = Bn * x^{n} + ..... B1 * x^{1} + B0 とする。
f(x) * g(x) = h(x) とする。
この時、N = n*m -1 として、h(e^{0*2*pi/N}), h(e^{1*2*pi/N}), ... h(e^{(N-1)*2*pi/N})は、f(e^{0*2*pi/N})...,g(e^{0*2*pi/N})....などから簡単に求まる。
そうなると、hについて逆DFTをして、hの係数が求まってしまう。
FFT
