文字列検索アルゴリズム① ー Z algorithm

Last updated at 2024-04-02Posted at 2022-09-14

自分の勉強用備忘録を兼ねて自分なりの言葉で色々な文字列検索アルゴリズムについて紹介していこうと思います。
本記事では Z algorithm について紹介します。

Z algorithm は文字列 $S$ が与えられた時、 Z array（ $S$ と $S[i:]$ の最長共通接頭辞の長さを表す配列）を $O\left(\left|S\right|\right)$ で構築するアルゴリズムです。

他の文字列検索アルゴリズムについてもまとめているので、よければご覧ください。

1. Z arrayとは？

Z arrayとは $S$ と $S[i:]$ の最長共通接頭辞の長さを表す配列のことです。簡単にいうと「 $S$ の $i$ 番目から始めて $S$ の先頭から何文字目まで一致しているか」を表す配列です。例えば文字列 $S = \text{“}ababaababaabababc\text{”}$ に対して Z array $Z$ は以下の様になります。
$$Z = [17, 0, 3, 0, 1, 10, 0, 3, 0, 1, 5, 0, 4, 0, 2, 0, 0]$$

下記アニメーションを見ていただくと分かりやすいかと思います。

例えば下記画像の様に $S = \text{“}ababaa...\text{”}$ と $S[2:] = \text{“}abaaba...\text{”}$ は先頭から $3$ 文字目まで一致しているため $Z[2] = 3$ となっているのが確認できるかと思います。

Z array を用いると、文字列 $T$ が文字列 $S$ に含まれるかという文字列検索を $O(\left|S\right|+\left|T\right|)$ で行うことができます。
具体的には $S$ と $T$ に出現しない文字 $\$$ を使った文字列 $T\$S$ に対する Z array $Z$ について、 $Z[i] = \left|T\right|$ となるような $\left|T\right|+1$ 以上の $i$ が存在しているとき、かつそのときに限り、 $T$ は $S$ に含まれます。なので $\left|T\right|+1$ 以上の $i$ を順に見ていって $Z[i] = \left|T\right|$ となるかどうかを調べれば $O(\left|S\right|+\left|T\right|)$ で文字列検索が行えます。
例えば $S=\text{“}pineapple\text{”}$、 $T=\text{“}apple\text{”}$ に対して $T\$S$ の Z array $Z$ は
$$Z = [15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0]$$
となり、 $Z[10] = 5 = \left|T\right|$ より $T$ が $S$ に含まれていると分かります。

これに対して Z algorithm を用いると Z array を $O(\left|S\right|)$ で構築することができます。

2. Z algorithm の流れ

再度 $S = \text{“}ababaababaabababc\text{”}$ を例にとって考えます。求めた Z array $Z$ を眺めてみると、下図のように重複している部分があることが確認できます。

$Z[5]=10$ から $S[0:10] = S[5:15]$ が成り立つことが分かります。
ここで $Z[2] = 3$ に着目すると、これは $S[2:] = \text{“}abaaba...\text{”}$ と $S = \text{“}ababaa...\text{”}$ が先頭 $3$ 文字目まで一致しており、 $4$ 文字目は異なるということです。 $5$ 文字目以降は Z array の値に関係ないので $S[2:6] = \text{“}abaa\text{”}$ から始まる文字列については Z array の値は $3$ となるはずです。
$S[0:10] = S[5:15]$ より、 $S[2:6] = S[7:11]$ が導けるので $Z[7] = 3$ になると分かります。同様に考えると $Z[6], Z[8], Z[9]$ がそれぞれ $Z[1], Z[3], Z[4]$ と一致することが分かります。

下記アニメーションは $Z[5]=10$ を利用して、 $i = 6,7,8,9$ に対してそれぞれの $Z[i]$ を求める様子を図示したものです。

上述の通り $S[7:11] = S[2:6] = \text{“}abaa\text{”}$ より、 $Z[7] = Z[2] = 3$ となっていることが確認できます。

今度は $i=11,12,13,14$ に着目してみましょう。こちらは $Z[10]=5$ より、$S[10:]$ と $S$ が先頭から $5$ 文字まで一致しているにもかかわらず、 $Z[12] \neq Z[2]$ 、 $Z[14] \neq Z[4]$ となっています。

上述の通り $Z[2] = 3$ より、 $\text{“}abaa\text{”}$ で始まる文字列は Z array の値が $3$ となるはずでした。 $S[12:]$ をみてみると $\text{“}ababc\text{”}$ となっているので、 $\text{“}abaa\text{”}$ から始まる文字列ではないです。なので $Z[12] \neq Z[2]$ となることが分かります。 $Z[14] \neq Z[4]$ も同様に確認できます。

では $i=12,14$ に対しては $S$ と $S[i:]$ の先頭から比較する必要があるのかというと実はその必要はないです。

$S[12:] = \text{“}ababc\text{”}$ と $S[2:] = \text{“}abaaba...\text{”}$ を見比べてみると先頭 $3$ 文字の $\text{“}aba\text{”}$ は一致しています。これは $Z[10]=5$ から $S[10:15] = S[0:5]$ なので部分文字列について $S[12:15] = S[2:5]$ という様にして導けます。

また $Z[2]=3$ なので $S[12:15] = S[2:5] = S[0:3]$ が成り立つはずです。ということは $Z[12] \ge 3$ なので、 $4$ 文字目から比較を行えば良いです。
同様に $i=14$ についても $Z[10]=5$ と $Z[4]=1$ から $S[14:15] = S[4:5] = S[0:1]$ が成り立つので $Z[14] \ge 1$ より、 $2$ 文字目から比較を行えば良いです。

下記アニメーションは $Z[10]=5$ を利用して、 $i = 11,12,13,14$ に対してそれぞれの $Z[i]$ を求める様子を図示したものです。

上述の通り $S[12:15] = S[2:5] = \text{“}aba\text{”} (=S[0:3])$ より、 $Z[12] \ge 3$ となっていることが確認できます。

Z algorithm では、このようにすでに求めた Z array の値を利用することで全体の Z array を高速に求めることができます。

3. アルゴリズム

以下の様な手順で、すでに求めた Z array の値を利用しながら Z array $Z$ を求めることができます。

$l = r = 0, Z = \left[\left|S\right|,0,0,...,0\right]$ で初期化（$|Z| = |S|$）
$i = 1$ から始め、$i$ を $1$ ずつ増やし $i < |S|$ の範囲でステップ2a.2b.を繰り返す
2a. $Z[i-l] < r-i$ であれば、 $Z[i]=Z[i-l]$ を代入する
2b. $Z[i-l] \ge r-i$ であれば、 $r = max(r,i)$ を代入し、 $r < \left|S\right|$ かつ $S[r] = S[r-i]$ の間 $r$ を $1$ ずつ増やし、ループ後 $Z[i] = r-i, l = i$ を代入する

変数 $l,r,i$ はステップ2a.2b.の終了時、常に $l \le i \le r$ かつ $S[l:r] = S[0:r-l]$ という条件を満たしながら値を更新していきます。ただし、1つ前のステップで $i=r$ となっていたとき、 $i:=i+1$ の更新により、ステップの開始前には $i > r$ となっている可能性があります。このときステップ2a.2b.の条件式の右辺について $r-i < 0$ となり、また左辺については $Z[i-l] \ge 0$ であるため、このケースはステップ2b.において処理されます。

$S[l:r] = S[0:r-l]$ より、左辺右辺それぞれの部分文字列 $S[i:r]$ と $S[i-l:r-l]$ について $S[i:r] = S[i-l:r-l]$ も成り立ちます。
さらに $j:=i-l, z:=Z[i-l]$ とおき、これらに着目すると Z array の定義から、 $S[j:j+z] = S[0:z]$ かつ $S[j+z] \ne S[z]$ が成り立ちます。

これらのことから、$j+z < r-l$ すなわち $Z[i-l] < r-i$ が成り立てば、 $S[i:i+z] = S[i-l:i-l+z] = S[j:j+z] = S[0:z]$ かつ $S[i+z] = S[j+z] \ne S[z]$ が成り立ちます。以上より Z array の定義から、 $Z[i] = z = Z[i-l]$ と求めることができます。これはステップ2a.に対応しています。

前節の $S = \text{“}ababaababaabababc\text{”}$ の例を見るとステップ2a.は例えば下図で示した様な $S[7:11] = S[2:6] = \text{“}abaa\text{”}$ また $Z[2] = 3$ より、 $Z[7] = 3$ と求めるケースに対応しています。この時各変数の値は $l = 5, r = 15, i = 7$ となっています。

逆に $j+z \ge r-l$ すなわち $Z[i-l] \ge r-i$ のとき、
$i > r$ であれば、 $r=i$ と更新して、$S[i:r] = S[0:r-i]$ が成り立っている間 $r$ を $1$ ずつ増やします。
このループ後 $S[i:r] = S[0:r-i]$ かつ $S[r] \ne S[r-i]$ が成り立つため Z array の定義から、 $Z[i] = r-i$ と求められます。

$i \le r$ であれば、 $S[i:r] = S[j:r-l]$ かつ $S[j:j+z] = S[0:z]$ より、 $S[i:r] = S[j:r-l] = S[0:r-l-j] = S[0:r-i]$ が成り立ちます。よって $Z[i] \ge r-i$ は分かっているので、途中から比較を開始すればよいです。こちらも同様に $S[i:r] = S[0:r-i]$ が成り立っている間 $r$ を $1$ ずつ増やすことで、ループ後に $Z[i] = r-i$ と求めることができます。

これらをまとめると $Z[i-l] \ge r-i$ のときは、 $r=max(r,i)$ と更新して、 $S[r] = S[r-i]$ の間 $r$ を $1$ ずつ増やすことで $Z[i] = r-i$ と求めることができます。またこのループ後 $l=i$ を代入することで、 $l \le i \le r$ かつ $S[l:r] = S[0:r-l]$ の条件も満たされます。これらの操作はステップ2b.に対応しています。

このステップ2b.は前節の下図で示した様な $S[12:15] = S[2:5] = \text{“}aba\text{”} (=S[0:3])$ より、 $Z[12] \ge 3$ と求めて途中から比較を行うケースに対応しています。この時ステップ2b.開始前の各変数の値は $l = 10, r = 15, i = 12$ となっています。

4. コード

def z_algorithm(s):
    z = [0]*len(s)
    z[0] = len(s)
    l = r = 0
    for i in range(1,len(s)):
        if z[i-l] < r-i:
            z[i] = z[i-l]
        else:
            r = max(r,i)
            while r < len(s) and s[r] == s[r-i]:
                r += 1
            z[i] = r-i
            l = i
    return z

5. 計算量

6. 参考文献

https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05
https://snuke.hatenablog.com/entry/2014/12/03/214243

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up