ワイルドカードを含むパターンマッチング

この記事は [データ構造とアルゴリズム Advent Calendar 2020](https://qiita.com/advent-calendar/2020/str) 14日目の記事です．

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

# 問題設定
パターンマッチングとは，
> テキスト文字列$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法](https://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%8C%E3%83%BC%E3%82%B9%E2%80%93%E3%83%A2%E3%83%AA%E3%82%B9%E2%80%93%E3%83%97%E3%83%A9%E3%83%83%E3%83%88%E6%B3%95)や[BM法](https://ja.wikipedia.org/wiki/%E3%83%9C%E3%82%A4%E3%83%A4%E3%83%BC-%E3%83%A0%E3%83%BC%E3%82%A2%E6%96%87%E5%AD%97%E5%88%97%E6%A4%9C%E7%B4%A2%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)があり，
これらのアルゴリズムは$\textrm{O}(n)$で実行できることが知られています．


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

では，文字列にシンボル'?'を含む場合のパターンマッチングがどうなるかというと，
例えば
$T="アブラカタブラ"$
から
$P="?ブラ"$
をマッチングした場合，
$k=\\{0,4\\}$が応答になります．
![スクリーンショット 2020-12-13 19.43.38.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/65731/968549f2-2105-8f79-8667-90d37c83992e.png)

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

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

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

```math
\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]$
を満たす場合，

```math
\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を割り当てます`．すると

```math
\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$について

```math
\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}$について

```math
\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$の計算を一般に[畳み込み](https://ja.wikipedia.org/wiki/%E7%95%B3%E3%81%BF%E8%BE%BC%E3%81%BF)と呼びます．
各$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（高速フーリエ変換）を完全に理解する話](https://qiita.com/ageprocpp/items/0d63d4ed80de4a35fe79)

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

```math
\mathcal{F}[x]_k = \sum_{i=0}^{n-1}x_i\zeta_n^{ki} \\
(0 \leq k < n)
```
を計算することを指します．
ここで，$\zeta_n$は1の原始$n$乗根で，以下の条件を満たします

```math
\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)を変形すると

```math
\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)の各項は同様に

```math
\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$)と解釈して下さい．

```math
=\sum_{i=0}^{l-1} p_{-i} t_{k-i}
```
$p_{-i}$を修正しましょう．
ここで，

```math
\bar{p}_i = p_{-i}
```
となる列$\bar{p}$を準備すると

```math
=\sum_{i=0}^{l-1} \bar{p}_{i} t_{k-i}
```
になり，畳み込みに帰着できました．

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

```math
\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)$時間で解くことができます[^1]．
問題設定から常に$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})$の範囲内に収まります．
したがって，

```math
\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))$です．

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

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