LoginSignup
4

More than 1 year has passed since last update.

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

Last updated at Posted at 2020-12-13

この記事は データ構造とアルゴリズム 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\}$が応答になります.
スクリーンショット 2020-12-13 19.43.38.png

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

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

計算機において文字は整数値として扱われますので,一般的な整数演算が適応できます.
それでは,「文字$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. 

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
4