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


この記事は データ構造とアルゴリズム Advent Calendar 2020 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法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)$時間で解くことができます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})$の範囲内に収まります.
したがって,

\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.