シンプルかつ高速な文字列照合アルゴリズムを紹介します

こんにちは！エンジニアリンググループマルチデバイスチーム新卒1年目の小林です。

エムスリーでは、2週間に1度、Tech Talkという社内LT会（現在はリモートで）が開催されています。これは、とある回の発表テーマリストです。

f:id:kobasato34:20200923184759p:plain — Tech Talkのとある回の発表テーマリスト

このように、最近エムスリーでは文字列が流行っている（？）ようなので、その勢いに乗って私も文字列照合アルゴリズムについて書きたいと思います！（業務とは全然関係ない話です）

Knuth-Morris-PrattやBoyer-Mooreアルゴリズムは解説記事がたくさん出ていると思うので、この記事ではシンプルかつ高速なQuick-SearchとQuite-Naiveアルゴリズムについて説明し、速度比較を行った結果についてご紹介します。

文字列照合アルゴリズムとは

テキストとパターンという文字列が与えられたときに、中に出現するの位置を全て出力するアルゴリズムです。例を見てみましょう。

t : abaababbbaaab
p : baa

このとき、出力は1と9です（0オリジン）。以後、の長さを、の長さをとします。

素朴なアルゴリズム

単純に、テキストの各位置においてパターンが出現しているかどうかをチェックする方法です。テキストのある位置にパターンをあてがって、テキストとパターンの対応する文字を左から右に1つずつ比較していきます。パターンの最後の文字まで一致していれば、パターンがそこに出現しているということです。途中で文字の不一致が起きたら、パターンを1文字分右にシフトした後に比較を再開します。

f:id:kobasato34:20200924194628p:plain — 素朴なアルゴリズムの例

C++で書くとこんな感じです。

void naive(std::string const& p, std::string const& t) {
    const int n = t.size();
    const int m = p.size();

    if (n == 0 || m == 0) {
        return;
    }

    int i = 0;
    while (i <= n - m) {
        int j = 0;
        while (j < m && p[j] == t[i + j]) ++j;
        if (j == m) {
            std::cout << i << std::endl;
        }
        ++i;
    }
}

テキストの各位置で最大回の文字の比較を行うため、最悪計算量は O(nm) です。

Quick-Searchアルゴリズム*1

素朴なアルゴリズムと同様に、左からテキストとパターンの文字を1文字ずつ比較していきます。不一致が起きたときのパターンのシフト量が素朴なアルゴリズムと異なります。

f:id:kobasato34:20200924170209p:plain — Quick-Searchアルゴリズムの例

この例だと、2文字目で不一致が起きていますね。素朴な手法だと、パターンを1文字分右にシフトしてから一番左から比較を再開します。しかし、シフト後のパターンの最後の文字 t[6 ]と p[5 ]に注目してみると、不一致が起きることが分かります。つまり、それよりも手前の文字が全部一致していたとしても、この位置で必ず不一致が発生してしまいます。これは無駄なので、少なくともこの位置の文字が一致するようにパターンをシフトすることができそうです。

f:id:kobasato34:20200924170325p:plain — Quick-Searchアルゴリズムの例

今、パターンを1文字シフトした後のパターンの最後の文字に対応するテキストの文字 t[6 ]は $\tt{b}$ です。パターンをシフトした後にこの位置の文字が一致して欲しいわけですから、パターン中に含まれる最右に出現する $\tt{b}$ がこの位置にくるようにパターンをシフトします。

f:id:kobasato34:20200924170349p:plain — Quick-Searchアルゴリズムの例

この例だと一気に4文字パターンをシフトできます。一度にたくさんシフトできて速そうですね！シフト後は最初の動作に戻ります。

次に、パターンを1文字シフトした後のパターンの最後の文字に対応するテキストの文字が $\tt{d}$ だったときの場合について考えてみましょう。

f:id:kobasato34:20200924170413p:plain — Quick-Searchアルゴリズムの例2

この例だと、パターン中に $\tt{d}$ は存在しません。つまり、この $\tt{d}$ とパターンのどこかが重なっているときは必ず不一致が発生するので、この場合はパターンを m+1 文字一気にシフトすることが可能です。

パターンのシフト量は、パターン中に含まれる各文字の最右の出現位置を事前に計算し、配列に保存しておきます。式で書くと、

$shift[c]=m + 1 - \max(\{i \mid p[i] = c, 0 \leq i \leq m-1 \} \cup \{0\})$

: 文字（ここでは文字をasciiコードとして扱います）

となります。 $p = \tt{aabaca}$ であれば、

	$\tt{a}$	$\tt{b}$	$\tt{c}$	その他
	1	4	2	7

となります。C++で実装するとこんな感じです。めちゃくちゃシンプル！

const int sigma = 256;

void quickSearch(std::string const& p, std::string const& t) {
    const int n = t.size();
    const int m = p.size();

    if (n == 0 || m == 0) {
        return;
    }

    int i;

    // Preprocessing phase
    int shift[SIGMA];
    for (i = 0; i < SIGMA; ++i) shift[i] = m + 1;
    for (i = 0; i < m; ++i) shift[p[i]] = m - i;

    // Searching phase
    i = 0;
    while (i <= n - m) {
        int j = 0;
        while (j < m && p[j] == t[i + j]) ++j;
        if (j == m) {
            std::cout << i << std::endl;
        }
        i += shift[t[i + m]];
    }
}

最悪計算量は、

前処理フェーズ： $O(m + \sigma)$
検索フェーズ：

です。 $\sigma$ は、アルファベットサイズ（文字集合のサイズ）です。

検索フェーズにおいて無駄な文字の比較をスキップできますが、計算量は素朴なアルゴリズムと同じです。しかし、最悪ケースは

$t=\tt{aaaaaa\cdots a}$

$p=\tt{aaaab}$

のようなときであり、実際にはこんなケースは少ないので実用上高速に動作します。速度比較は最後に行います。

Quite-Naiveアルゴリズム*2

パターンから $\delta$ 、 $\gamma$ という値を事前に計算します。定義はこちらです。

$\delta = \min(\{i \mid p[m - i - 1] = p[m-1], 1 \leq i \leq m - 1\} \cup \{m\})$ $\gamma = \min(\{i \mid p[m - i - 1] \neq p[m-1], 1 \leq i \leq m - 1\} \cup \{m\})$

$\delta$ は、パターンの最後の文字と同じ文字がそれよりも左において何文字前に出現しているかを表しています。 $\gamma$ は、パターンの最後の文字と異なる文字がそれよりも左において何文字前に出現しているかを表しています。該当する文字が存在しない場合は、値はになります。例を見てみましょう。

f:id:kobasato34:20200924175547p:plain — Quite-Naiveアルゴリズムの $\delta$ と $\gamma$ の例

このように、 $\delta$ と $\gamma$ の値のどちらかは必ず1となります。

この2つの値をうまく使って、効率よくパターンを検索します。では検索のフェーズを見ていきましょう。

このアルゴリズムでは、パターンの文字を右から左にチェックしていきます。文字の不一致が起きたとき、 $\delta$ または $\gamma$ 文字パターンを右にシフトします。どちらの値を使うかは、パターンの一番右の文字が対応するテキストの文字と一致しているかどうかで決めます。

パターンの一番右の文字が不一致： $\gamma$ 文字シフト
それ以外の場所で不一致： $\delta$ 文字シフト

というように行います。

まずは、パターンの一番右で不一致が起きた場合について考えてみます。

f:id:kobasato34:20200924175659p:plain — パターンの一番右で不一致が起きた場合

テキストの文字 t[5 ]が $\tt{a}$ 、パターンの文字 p[5 ]が $\tt{b}$ で不一致が起きています。 $\gamma$ の値から、パターンの右から3文字は $\tt{b}$ が連続していることが分かっているため、3文字未満のパターンのシフトを行っても、シフト後に必ず t[5 ]の位置で不一致が起きてしまいます。このことから、パターンの一番右で不一致が起きたときはパターンを一気に $\gamma$ 文字シフトすることが可能です。

f:id:kobasato34:20200924175725p:plain — パターンの一番右で不一致が起きた場合

パターンの一番右以外の位置で不一致が起きた場合はどうでしょうか。

f:id:kobasato34:20200924175747p:plain — パターンの一番右以外の場所で不一致が起きた場合

一番右の文字は $\tt{a}$ で一致しているので、パターンのシフト後にもこの t[5 ]の位置に $\tt{a}$ が来ていてほしいです。 $\delta$ の値から、最も近い $\tt{a}$ はパターンの最後から $\delta$ 文字前に存在していることが分かります。よって $\delta$ 文字未満のシフトを行っても必ず不一致が起きてしまうため、パターンの一番右以外の位置で不一致が起きた場合はパターンを一気に $\delta$ 文字シフトすることが可能です。

f:id:kobasato34:20200924175815p:plain — パターンの一番右以外の場所で不一致が起きた場合

実装例はこちらです。

void quiteNaive(std::string const& p, std::string const& t) {
    const int n = t.size();
    const int m = p.size();

    if (n == 0 || m == 0) {
        return;
    }

    // Preprocessing phase
    int gamma = 1, delta = 1;
    while (delta < m && p[m - delta - 1] != p[m - 1]) delta++;
    while (gamma < m && p[m - gamma - 1] == p[m - 1]) gamma++;

    // Searching phase
    int i = 0;
    while (i <= n - m) {
        if (p[m - 1] != t[i + m - 1]) {
            i += gamma;
        } else {
            int j = m - 2;
            while (j >= 0 && p[j] == t[i + j]) --j;
            if (j == -1) {
                std::cout << i << std::endl;
            }
            i += delta;
        }
    }
}

最悪計算量は、

前処理：
検索：

です。パターンのシフト量が増えて効率的に検索を行えますが、計算量の改善までには至っていません。

速度比較

素朴なアルゴリズム
Knuth-Morris-Pratt (KMP) アルゴリズム
Quick-Searchアルゴリズム
Quite-Naiveアルゴリズム

をC++で実装*3し、実行速度を比較します。テキストには、大腸菌の塩基配列*4と英語の文章（欽定訳聖書）*5を用います。パターンはテキストからランダムに抽出し、100回検索を行ったときのトータル時間を比較します。

f:id:kobasato34:20200924184431p:plain — 英語の文章における速度比較

f:id:kobasato34:20200924184452p:plain — 塩基配列における速度比較

まず、素朴な手法が意外と速いというところが興味深いですね。これは、英語のテキストや塩基配列のような実データにおいてはパターンの先頭の方で文字の不一致が起きることが多く、素朴な手法が実質線形時間で動いているためです。

Quick-SearchやQuite-Naiveアルゴリズムはパターンが長くなるにつれて速くなっています。これは、パターンが長いほうが１回あたりのパターンシフト量が大きくなることが期待できるためです。また、英語のテキストのようにアルファベットサイズが大きいデータの方がパターンシフト量が大きくなりやすいです。この2つのアルゴリズムの速度の差は僅かですが、Quick-Searchアルゴリズムは前処理で shift を準備するため $O(m+\sigma)$ の領域が必要なのに対して、Quite-Naiveアルゴリズムは O(1) の領域で済むという利点もあります（テキストとパターンの領域は除く）。

まとめ

シンプルかつ実用上高速なQuick-SearchとQuite-Naiveアルゴリズムを紹介しました。ちょっとした工夫でこんなに速度の差が生まれるのは面白いですね！

We are hiring!

エムスリーでは、アルゴリズムが好きなエンジニアを募集しています！ぜひご応募ください！

jobs.m3.com

*1:D. M. Sunday. A very fast substring search algorithm. Communications of the ACM, 33(8):132-142, 1990.

*2:Domenico Cantone and Simone Faro. Searching for a substring with constant extra-space complexity. InProceedings of Third International Conference on Fun with algorithms, pp. 118-131, 2004.

*3:gcc version 10.2.0を使用、-O3オプションを付けてコンパイルしました

*4:https://corpus.canterbury.ac.nz/descriptions/large/E.coli.html

*5:https://corpus.canterbury.ac.nz/descriptions/large/bible.html