この記事はデータ構造とアルゴリズム Advent Calendar 2020 14日目の記事です．

本記事では，ワイルドカード（任意の一文字）を含む文字列におけるパターンマッチングアルゴリズムの一つとして，
畳み込みを用いた$\textrm{O}(n\log m)$時間アルゴリズム¹を紹介します．

問題設定

パターンマッチングとは，

テキスト文字列$T=T[0] \dots T[n-1]$と
パターン文字列$P=P[0] \dots P[m-1]$が与えられたとき，
$T[k] \dots T[k+m-1] = P[0] \dots P[m-1]$
となる全ての$k$

を探す問題です．

よく知られているパターンマッチングアルゴリズムとしてKMP法やBM法があり，
これらのアルゴリズムは$\textrm{O}(n)$で実行できることが知られています．

ワイルドカードとは任意の一文字を指し示すシンボルのことで，
UNIXのshellでは '?' で表されます．
本記事でも，任意の一文字を指し示すシンボルを '?' と表記します．

では，文字列にシンボル'?'を含む場合のパターンマッチングがどうなるかというと，
例えば
$T="アブラカタブラ"$
から
$P="?ブラ"$
をマッチングした場合，
$k=\{0,4\}$が応答になります．

この問題を効率的に解くことを考えます．

式で見るパターンマッチング

計算機において文字は整数値として扱われますので，一般的な整数演算が適応できます．
それでは，「文字$s$と$t$が一致する ($s=t$)」という状況を値として捉えることを考えます．

まずはワイルドカードを含まない文字列について考えましょう．
ここで，
$$\texttt{cmp}(s, t) = (s-t)^2$$
という文字比較関数を置くと，

\left\{
\begin{array}{ll}
\texttt{cmp}(s, t) = 0 & (s = t) \\
\texttt{cmp}(s, t) > 0 & (s \neq t)
\end{array}
\right.

であることが明らかです．
したがって，$k$について
$T[k] \dots T[k+m-1] = P[0] \dots P[m-1]$
を満たす場合，

\begin{align}
\texttt{match}(T,P,k)=& \sum_{i=0}^{m-1} \texttt{cmp}(T[k+i], P[i]) \\\
=& \sum_{i=0}^{m-1} (T[k+1] - P[i])^2 & (1) \\\
=& 0
\end{align}

となります．

続いて，ワイルドカード'?'を含む場合にも対応できるように拡張した比較関数$\texttt{wcmp}(s,t)$を考えます.
$s$と$t$の比較で，どちらかが'?'である場合は常に両者は一致しているとみなされます．
ここで，ワイルドカード文字'?'に値として0を割り当てます．すると

\texttt{wcmp}(s, t) = st(s-t)^2 \\
\left\{ 
\begin{array}{ll}
\texttt{wcmp}(s, t) = 0 & (s = t\ \mathrm{or}\ s = \mathrm{`?`} \mathrm{or}\ t = \mathrm{`?`}) \\
\texttt{wcmp}(s, t) > 0 & \mathrm{otherwise}
\end{array}
\right.

という形で表現することができます．
したがって，位置$k$について

\begin{align}
\texttt{wmatch}(T,P,k)
=& \sum_{i=0}^{m-1} \texttt{wcmp}(T[k+i], P[i]) \\\
=& \sum_{i=0}^{m-1} T[k+1]P[i](T[k+i] - P[i])^2 & (2) \\\
=& 0
\end{align}

を計算し確認することでマッチを確認できます．

数値列の畳み込み

ここで先に畳み込みというテクニックの話をします．
数値列$a=a_0, a_1, \dots, a_{n-1}$と$b=b_0, b_1, \dots, b_{m-1}$について

\begin{align}
c_k =& \sum_{i=0}^{k} a_i b_{k-i} & (3) \\
& \left( \begin{array}{l}
0 \leq k < n+m-1, \\
a_u=0(u \geq n), \\
b_v=0(v \geq m)
\end{array} \right)
\end{align}

となる数値列$c$の計算を一般に畳み込みと呼びます．
各$k$について$c_k$を式(3)の通りに愚直に計算すると，全体の計算量は$\mathrm{O}((n+m)^2)$になりますが，
畳み込みはFFT(高速フーリエ変換)を用いることで$\textrm{O}((n+m) \log (n+m))$で計算できることが知られています．

FFTは数列$x=x_0, x_1, \dots, x_{n-1}$のDFT(離散フーリエ変換)を$\textrm{O}(n \log n)$で計算するアルゴリズムです．
FFTを用いる際は，あらかじめ$x$の長さを$l=2^t \geq n$に拡張し，拡張された位置には値0を割り当てます．
FFTそのものの解説は以下の記事を参考にしてください．
FFT（高速フーリエ変換）を完全に理解する話

DFTとは，数列$x$に対し

\mathcal{F}[x]_k = \sum_{i=0}^{n-1}x_i\zeta_n^{ki} \\
(0 \leq k < n)

を計算することを指します．
ここで，$\zeta_n$は1の原始$n$乗根で，以下の条件を満たします

\left\{
\begin{array}{l}
\zeta_n^n=1 \\
\zeta_n^i = \zeta_n^j\ \iff i \equiv j \mod n
\end{array}
\right.

$\zeta_n = \exp(\frac{2\pi i}{n})$がよく用いられます．

DFTを用いた畳み込みの計算方法ですが，
結論から言えば，
$$
c_k
= \sum_{i=0}^{n+m-2} a_i b_{k-i}
= \mathcal{F}^{-1}[\mathcal{F}[a] \cdot \mathcal{F}[b]]_k
$$
が成立します．(式変形で導出できます)
$(\mathcal{F}[a] \cdot \mathcal{F}[b])$は単に列$\mathcal{F}[a]$と$\mathcal{F}[b]$の内積を計算するだけなので$\mathrm{O}(n+m)$です．
$\mathcal{F}^{-1}$は離散フーリエ変換の逆関数で，FFTで同様に$\mathrm{O}((n+m) \log (n+m))$で計算できます．
よって，畳み込みそのものの計算量はFFTの計算量に依存し$\mathrm{O}((n+m) \log (n+m))$です．

畳み込みを用いた式の計算

式(2)を変形すると

\begin{align}
\texttt{wmatch}(T,P,k)
=& \sum_{i=0}^{m-1} T[k+i]P[i](T[k+1] - P[i])^2 \\\
=& \sum_{i=0}^{m-1} T[k+i]^3P[i] - 2\sum_{i=0}^{m-1} T[k+i]^2P[i]^2 + \sum_{i=0}^{m-1} T[k+i]P[i]^3 & (4)
\end{align}

となります．
$T[j]^p(0 \leq j < n, 1 \leq p \leq 3)$はそれぞれ$\textrm{O}(n)$で前計算（$P$も同様)しておきます．
すると式(4)の各項は同様に

\begin{align}
&\sum_{i=0}^{m-1} p_i t_{k+i} & (5)
\end{align}

という形で捉えることができます．
これは畳み込みに似た形(よく見ると少し違う)をしていますので，なんとか畳み込みに帰着して効率的に計算できないでしょうか．

まず，$T,P$の長さを$l = 2^t \geq n+m-1$に延長したとして，
$$=\sum_{i=0}^{l-1} p_i t_{k+i}$$
と扱いましょう．延長された箇所の値に0を割り当てれば，計算したい式(5)の値には影響を与えません．
とりあえず，$i$の符号を反転させてみます．
天下りな説明にはなりますが，ここでのインデックスの値は法$l$に従う($\textrm{mod}\ l$)と解釈して下さい．

=\sum_{i=0}^{l-1} p_{-i} t_{k-i}

$p_{-i}$を修正しましょう．
ここで，

\bar{p}_i = p_{-i}

となる列$\bar{p}$を準備すると

=\sum_{i=0}^{l-1} \bar{p}_{i} t_{k-i}

になり，畳み込みに帰着できました．

$\bar{p}$がどういう形をしているかというと，法$l$のもとでpのインデックスを反転させたものなので以下のようになります．

\mathrm{e.g.}\ m = 4, l = 8 \\
\bar{p} = p_0, 0, 0, 0, 0, p_3, p_2, p_1

以上で命題を$\mathrm{O}(n \log n)$で解くことができました．

計算量改善

実は，本記事の内容を少し応用すると，$\mathrm{O}(n \log m)$時間で解くことができます¹．
問題設定から常に$n \geq m$ですが，パターンマッチングの用途では$n \gg m$であることが多いため，この改善はかなり効果があります．
気が向けば加筆するかもしれませんが，興味のある方は考えてみて下さい．

回答 (2020/12/28 加筆)

テキスト$T$を$m$文字ずつのブロックに分割し，$i+1$番目のテキストブロックを$T_i$とします。
$T[k] \dots T[k+m-1]$は多くとも2つのブロック$(T_{\lfloor k/m \rfloor}T_{\lfloor k/m \rfloor + 1})$の範囲内に収まります．
したがって，

\mathtt{wmatch}(T, P, k) = \mathtt{wmatch}(T_{\lfloor k/m \rfloor}, P, k \mod m) + \mathtt{wmatch}(T_{\lfloor k/m \rfloor + 1}, P, -m+(k \mod m))

が成立します．
よって各$T_i$について$\mathtt{wmatch}(T_i, P, k')_{(-m+1 \leq k' \leq m-1)}$を畳み込みで計算すれば良いことになります．

計算量は，各ブロックの畳み込みが$\mathrm{O}(m \log m)$，ブロック数が$\lceil n/m \rceil$より，
全体で$(\lceil n/m \rceil \times \mathrm{O}(m \log m) = \mathrm{O}(n\log m))$です．

おわりに

以上，ワイルドカードを含むパターンマッチングについて解説しました．
畳み込みを用いたパターンマッチングの面白さは，文字列の比較を式で解析的に扱える点だと思います．
ここまで読んでくださり，ありがとうございました．

P. Clifford and R. Clifford, Simple deterministic wildcard matching. Inf. Process. Lett. 101(2): 53–54, 2007. ↩