力まかせ法（単純な文字列検索方法）について解説（C言語サンプル付き）

このページでは、文字列検索における最も基本的なアルゴリズムである「力まかせ法」について解説します。

このサイトで文字列検索を扱うのが初めてなので、まずは文字列検索について解説し、その後、力まかせ法について解説していきます。

文字列検索の説明が不要という方は、力まかせ法とはまでスキップしていただければと思います。

文字列検索とは

文字列検索とは「”ある文字列” の中から “指定した文字列” が存在する位置を特定する」ことです。

文字列という言葉が２回出てきてちょっと分かりにくいので、以降では、”ある文字列” をテキスト、”指定した文字列” をパターンとそれぞれ呼びたいと思います。

つまり文字列検索とは「テキストの中からパターンが存在する位置を特定する」ことになります。

例えばテキストが "ABCDEFGH" でパターンが "EFG" の場合、"ABCDEFGH" の中から "EFG" が存在する位置を特定することになります。

では、"ABCDEFGH" の中のどの位置に "EFG" は存在するでしょうか？実際に、どの位置に存在するか特定してみてください！多分一瞬で特定できると思います。

先頭の文字を第 0 文字と考えると、"ABCDEFGH" の第 4 文字 〜 第 6 文字の位置に "EFG" が存在していますね！

01234567
ABCDEFGH

ただ、パターンが存在する位置の先頭の位置さえ分かってしまえば、テキストの “どの位置からどの位置” にパターンが存在するかはパターンの文字列長から特定可能です。

ですので、基本的に文字列検索の目的は、パターンが存在するテキストの位置の、特に先頭の位置を特定することであると考えて良いです。

なので、上記の例であれば、”第 4 文字” さえ特定すれば文字列検索は達成できたことになります。パターンの文字列長が 3 なので、先頭が第 4 文字であることが分かれば第 4 文字 〜 第 6 文字にパターンが存在することは明白です。

また、おそらくこれは直感的に理解されていると思いますが、”パターンが存在する” とは、テキストのある位置を先頭にして、そこからのテキストの文字がパターンの先頭の文字からパターンの末尾の文字まで全て一致することを言います。

さらに、そのテキストの先頭の位置が、パターンが存在する位置となります。

文字が一致するかどうかは “比較” によって確認することが出来ますので、要はテキストの文字とパターンの文字を比較していくことで、文字列を検索することになります。

先程の例だとテキストもパターンも短いため、すぐにパターンの存在する位置を特定することが出来たと思いますが、テキストやパターンの文字数が増えれば増えるほど、パターンの存在する位置を特定することが大変になります。

特にそのような場合に、効率的に文字列検索を行うためのアルゴリズムがたくさん考案されています。

で、ここで紹介するのが、このアルゴリズムの中で最も考え方が簡単な “力まかせ法” について解説します。

力まかせ法とは

力まかせ法は、文字列検索を行う際にまず最初に思い浮かぶ “単純な” 文字列検索アルゴリズムになります。

力まかせ法は「素朴なアルゴリズム」「ナイーブ法」「Brute Force 法」等とも呼ばれることがありますが、このサイトでは “力まかせ法” と読んで解説していきたいと思います。

では、この “力まかせ法” がどのようなものであるか解説していきます。

力まかせ法とは、パターンが存在する可能性のあるテキストの位置を “総当たり” で調べる文字列検索アルゴリズムです。

前述の通り、”パターンが存在する位置” とは下記のことを言います。

“パターンが存在する” とは、テキストのある位置を先頭にして、そこからのテキストの文字がパターンの先頭の文字からパターンの末尾の文字まで全て一致することを言います。

さらに、そのテキストの先頭の位置が、パターンが存在する位置となります。

なので、パターンが存在する可能性のあるテキストの “全文字の位置” を先頭の位置とし、各位置に対してパターンが存在するかどうかを調べることで、どの位置にパターンが存在するかどうかを “総当たり” で調べることができることになります。

そして、このような手法で文字列検索を行うのが力まかせ法になります。

上の図では後ろの２文字が “パターンが存在する可能性のある位置” になっていますが、この理由などは次の力まかせ法による文字列検索例や力まかせ法の実装の解説の中で説明していきます。

スポンサーリンク

力まかせ法による文字列検索例

例えばテキストが "ABAAABB" 、パターンが "AAB" の場合について考えてみましょう！

まずテキストの文字数は 7 文字です。したがって単純に考えれば、先頭の文字を第 0 文字とすると、テキストの第 0 文字 〜 第 6 文字の位置が “パターンが存在する位置” となり得ます。

ただし、最後の 2 つの位置（つまり第 5 文字と第 6 文字）の場合は、そこから続く文字がパターンの文字数 3 よりも短いので、その位置からパターンの先頭 〜 末尾の文字が全て一致する可能性はありません。

なので、第 5 文字 〜 第 6 文字はパターンの存在する可能性のない位置であり、パターンが存在する可能性のあるテキストの位置は第 0 文字 〜 第 4 文字に絞られます。

力まかせ法は前述の通りパターンが存在する可能性のあるテキストの位置を “総当たり” で調べるアルゴリズムです。したがって、テキストの第 0 文字 〜 第 4 文字の 5 つの位置全てに対してパターンが存在するかどうかを調べていきます。

つまり、第 0 文字 〜 第 4 文字をテキストの先頭の位置として、そこからのテキストの文字がパターンの先頭 〜 末尾の文字が全て一致するかどうかを調べます。

要は下記の５つを調べることになります。

• 第 0 文字の位置："ABA" と "AAB" が一致するか？
• 第 1 文字の位置："BAA" と "AAB" が一致するか？
• 第 2 文字の位置："AAA" と "AAB" が一致するか？
• 第 3 文字の位置："AAB" と "AAB" が一致するか？
• 第 4 文字の位置："ABB" と "AAB" が一致するか？

“パターンが存在する可能性のあるテキストの位置” 全てに対してパターンが存在するかを確認しているわけですから、テキストの中にパターンが存在する場合、必ずそのパターンの位置を特定することが出来ます。

上記の例だと、テキストの “第 3 文字の位置” からのテキストの３文字が、パターンの先頭の文字からパターンの末尾の文字まで全て一致しているので、第 3 文字の位置にパターンが存在すると結論づけることができますね。

このように、パターンが存在する可能性のあるテキストの全文字の位置を先頭の位置とし、各位置に対してパターンが存在するかどうかを “総当たり” で調べるのが「力まかせ法」です。

力まかせ法の実装

上記の例で、テキストが "ABAAABB" 、パターンが "AAB" の場合、下記を調べる必要があると説明しました。

• 第 0 文字の位置："ABA" と "AAB" が一致するか？
• 第 1 文字の位置："BAA" と "AAB" が一致するか？
• 第 2 文字の位置："AAA" と "AAB" が一致するか？
• 第 3 文字の位置："AAB" と "AAB" が一致するか？
• 第 4 文字の位置："ABB" と "AAB" が一致するか？

これらを調べる様子を図で表すと下の図のようになります（この図では比較が不一致した後も比較を継続していますが、後述するように不一致後の比較はスキップ可能です）。

この図からも分かるように、テキストの各文字の位置にパターンが存在するかどうかは、パターン自体をテキストに対して１文字ずつ後ろにずらしながら同じ位置にある文字を比較していくことで実現することが可能です。

さらに、パターン自体をずらした状態で、パターンの先頭の文字からパターンの末尾の文字までの文字全てが一致した場合、テキストの先頭から ”パターン自体をずらした文字数分” 後ろ側にパターンが存在すると考えることが出来ます。

つまり、テキストの先頭の文字を第 0 文字とすれば、パターン自体をずらした文字数そのものがパターンが存在する位置となります。

上記の考えを利用して力まかせ法により文字列検索を行なっていく様子について説明していきます（テキストやパターンの先頭の文字は第 0 文字として説明します）。

まずパターンの第 0 文字の位置をテキストの第 0 文字の位置に合わせた状態で、テキストの文字とパターンの文字が一致するかどうかをパターンの先頭から確認していきます。この状態では、パターン自体をずらした文字数は 0 です。

もしテキストの文字とパターンの文字が一致した場合、テキストとパターンの比較位置をそれぞれ１文字分後ろにずらし、再度文字が一致するかどうかを確認します。

これを繰り返し、もしパターンの先頭からパターンの最後まで全て比較が一致した場合、テキストの先頭からパターン自体をずらした文字数後ろ側に（この場合は 0）に、パターンが存在することになります（つまりパターンが存在する位置はテキストの第 0 文字の位置）。

もし途中で文字が不一致した場合、この位置にパターンは存在しないことになるので、それ以上比較しても無駄です。ですので、文字が一致しなかった際には即座に比較は中止し、次の位置にパターンが存在しないかどうかを調べるためにパターン自体を１文字分後ろ側に移動します。これによりパターン自体をずらした文字数は +1 されて 1 になります。

そして、パターン自体をずらした状態で、パターンの先頭から同じ位置にあるテキストの文字とパターンの文字を比較していきます。

あとはこの繰り返しです。

つまり、パターン自体をずらした状態で、パターンの第 0 文字から順に同じ位置にあるテキストの文字とパターンの文字の比較を行い、比較が一致している間はテキストとパターンの比較位置を１文字分後ろ側に移動させながら１文字ずつ文字の比較を行います。

比較を行なった文字が、パターンの先頭からパターンの末尾まで一致した場合、テキストの第 0 文字の位置から “パターン自体をずらした文字数” 先の位置にパターンが存在する位置になります。

例えばパターン自体をずらした文字数を shift とすれば、テキストの第 shift 文字目の位置がパターンが存在する位置になります。

比較が不一致した場合は、パターン自体を１文字分後ろ側に移動させて、再度パターンの第 0 文字から比較を再開します。パターン自体をずらした文字数を shift とすれば、パターン自体を１文字分後ろ側にずらした際に shift = shift + 1 されることになります。

これらの処理を、パターン自体をずらした文字数が “テキストの文字数 – パターンの文字数” になるまで繰り返し行うことで、パターンがテキスト内に存在する場合、そのパターンを漏れなく検索することが出来ます。

パターン自体をずらした文字数が “テキストの文字数 – パターンの文字数” を超えた場合、比較を行うテキストの文字が足りなくなるため、それ以降にパターンが存在する可能性はありません。

そのため、パターン自体をずらした文字数が “テキストの文字数 – パターンの文字数” になるまで繰り返せば、パターンが存在する可能性のある全てのテキストの文字の位置を調べたことになります。

力まかせ法による文字列検索プログラム

以上に基づいて作成した、力まかせ法による文字列検索プログラムのソースコード例は下記のようになります。

#include <stdio.h>
#include <string.h> /* strlen */

#define MAX_PATTERN 256
#define MAX_TEXT 1024

/*
 * 力まかせ法によりtextからpatternを見つけ出す
 * 
 * text：テキストの文字列
 * text_len：テキストの文字数
 * pattern：パターンの文字列
 * pattern_len：パターンの文字数
 * 戻り値：パターンが見つかった場合はその位置、パターンが見つからない場合は-1
 */
int forceSearch(char text[], int text_len, char pattern[], int pattern_len) {
    int shift; /* パターンをずらす文字数 */
    int pattern_pos; /* 比較位置 */

    /* パターンが存在しうるテキストの位置にパターンをずらすループ */
    for (shift = 0; shift <= text_len - pattern_len; shift++) {

        /* パターンの全文字と比較を行うループ */
        for (pattern_pos = 0; pattern_pos < pattern_len; pattern_pos++) {

            /* パターンをずらした時に同じ位置になる文字同士を比較 */
            if (text[shift + pattern_pos] == pattern[pattern_pos]) {

                /* 文字が一致した場合 */
                if (pattern_pos == pattern_len - 1) {
                    /* パターンの最後の文字と一致した場合 */

                    /* パターンが見つかったのでパターンが存在する位置を返却 */
                    return shift;
                }
            } else {
                /* 文字が不一致した場合 */

                /* パターンは絶対に存在しないので比較中止 */
                break;
            }
        }
    }

    /* パターンが見つからなかった場合は-1を返却 */
    return -1;
}

int main(void) {
    char text[MAX_TEXT] =  "baabaabaabaabaavaabaabaa";
    char pattern[MAX_PATTERN] = "aabaabaa";
    int find;

    find = forceSearch(text, strlen(text), pattern, strlen(pattern));
    if (find != -1) {
        printf("パターンはテキストの第%d文字に存在します\n", find);
    } else {
        printf("パターンはテキスト内に存在しません...\n");
    }

    return 0;
}

forceSearch 関数が力まかせ法で文字列検索を行う関数で、引数で与えられるテキスト text の中からパターン pattern を検索する関数になります。また、text_len はテキストの文字数、pattern_len はパターンの文字数です。 

テキストの中にパターンが存在した場合、最初に見つけたパターンが存在する テキストの位置 を整数として返却します。もしパターンが存在しなかった場合は -1 を返却します。

パターン自体をずらした文字数を shift としており、この shift を 0 〜 text_len - pattern_len まで下記の外側の for ループで変化させながら、パターンが存在するかどうかを調べていっています。

for (shift = 0; shift <= text_len - pattern_len; shift++) {
    /* 略 */
}

text_len - pattern_len までしかループしないのは、それよりも後ろの位置にパターンが存在する可能性がないためです。

パターンが存在するかどうかを調べている処理は下記の内側の for ループで行っています。

/* パターンの全文字と比較を行うループ */
for (pattern_pos = 0; pattern_pos < pattern_len; pattern_pos++) {

    /* パターンをずらした時に同じ位置になる文字同士を比較 */
    if (text[shift + pattern_pos] == pattern[pattern_pos]) {
        /* 略 */
    }
}

パターン自体を shift 文字ずらした際には、テキストの第 shift 文字の位置にパターンの第 0 文字目が移動してくることになりますので、これらの位置から１文字ずつ比較していっています。

パターンの最後の文字、つまり pattern_len - 1 の文字との比較が一致した場合は、テキストの第 shift 文字がパターンが存在する位置となります。この場合は、この位置 shift を return で関数呼び出し元に返却しています。

/* 文字が一致した場合 */
if (pattern_pos == pattern_len - 1) {
    /* パターンの最後の文字と一致した場合 */

    /* パターンが見つかったのでパターンが存在する位置を返却 */
    return shift;
}

その一方で、パターンの最後の文字が一致する前に比較が不一致した場合は、比較を中止するために break を実行して直ちに内側のfor ループを抜け出しています

内側の for ループを抜け出すと、前述の外側の for 文の shift++ の処理により shift が +1 され、これによりパターン自体が１文字分後ろに移動することになります。

pattern が存在することが分かった時点で return するようにしていますので、もし関数最後の return まで処理が進んだということは、text の中に pattern が存在しないことを意味します。

ですので、関数最後の return では、pattern が存在しなかったことを示すために -1 を返却するようにしています。 

スポンサーリンク

力まかせ法の別の実装

先ほどは、力まかせ法を “パターン自体をずらす文字数” に注目して実装しましたが、”テキストの比較位置” に注目して力まかせ法を実装することも可能です。

“テキストの比較位置” は、パターンの文字と比較を行うテキストの文字の位置のことを表しています。これに対して、比較を行うパターンの文字の位置を、ここからは “パターンの比較位置” と呼びたいと思います。

力まかせ法においては、文字の比較が一致している際には、テキストとパターンの比較位置をそれぞれ１文字分後ろにずらすと前述で解説しました。

つまり、文字の比較が一致した際には、”テキストの比較位置” と “パターンの比較位置” はそれぞれ下記のように変化することになります。

• テキストの比較位置：+1 される
• パターンの比較位置：+1 される

また、文字の比較が不一致した際には、”パターン自体を１文字分後ろにずらし、さらにパターンの先頭から比較を再開する” と前述で説明しました。

もしパターンの先頭の文字で不一致した場合、”テキストの比較位置” は１文字分後ろにずれることになります。

その一方で、パターンの先頭以外の文字で不一致した場合、”テキストの比較位置” は、その 不一致の直前の比較で一致した文字数 - 1 文字後ろにずれることになります。

つまり、文字の比較が不一致した際には、”テキストの比較位置” と “パターンの比較位置” はそれぞれ下記のように変化することになります。

• パターンの先頭の文字で不一致した場合
  • テキストの比較位置：+1 される
  • パターンの比較位置：0 に移動
• パターンの先頭の文字以外で不一致した場合
  • テキストの比較位置：- (直前の比較で一致した文字数 - 1) される
  • パターンの比較位置：0 に移動

まとめると、”テキストの比較位置” と “パターンの比較位置” が変化するタイミングと、それぞれのタイミングで変化する量は下記のようになります。

• 文字が一致した場合
  • テキストの比較位置：+1 される
  • パターンの比較位置：+1 される
• 文字が不一致した場合
  • パターンの先頭の文字で不一致した場合
    • テキストの比較位置：+1 される
    • パターンの比較位置：0 に移動
  • パターンの先頭の文字以外で不一致した場合
    • テキストの比較位置：- (直前の比較で一致した文字数 - 1) される
    • パターンの比較位置：0 に移動

要は、最初に “テキストの比較位置” と “パターンの比較位置” をそれぞれ 0 に設定し、あとは上記に基づいて “テキストの比較位置” と “パターンの比較位置” を移動させてやるだけで、力まかせ法を実現することが出来ます。

また、”パターンの比較位置” がパターンの末尾である時にテキストの文字と比較が一致すればパターンが見つかったことになります。この時、パターンが存在する位置は、 "テキストの比較位置" - (パターンの文字数 - 1) となります（”テキストの比較位置” は、パターンの末尾の文字と比較したテキストの文字の位置です）。

この考え方に基づいて作成した、力まかせ法による文字列検索プログラムのソースコード例は下記のようになります。

#include <stdio.h>
#include <string.h> /* strlen */

#define MAX_PATTERN 256
#define MAX_TEXT 1024

/*
 * 力まかせ法によりtextからpatternを見つけ出す
 * 
 * text：テキストの文字列
 * text_len：テキストの文字数
 * pattern：パターンの文字列
 * pattern_len：パターンの文字数
 * 戻り値：パターンが見つかった場合はその位置、パターンが見つからない場合は-1
 */
int forceSearch(char text[], int text_len, char pattern[], int pattern_len) {
    int text_pos; /* テキストの比較位置 */
    int pattern_pos; /* パターンの比較位置*/

    /* パターンの比較位置を先頭にセット */
    pattern_pos = 0;

    /* テキストの比較位置を先頭にセット */
    text_pos = 0;

    /* テキストの比較位置がテキストの最後を超えるまでループ */
    while (text_pos < text_len) {
        /* テキストの比較位置の文字とパターンの比較位置の文字が一致するかを判断 */
        if (text[text_pos] == pattern[pattern_pos]) {
            /* 一致した場合 */

            /* パターンの最後の文字までテキストの文字が一致したかどうかを判断 */
            if (pattern_pos == pattern_len - 1) {
                /* パターンが存在するテキストの位置を返却 */
                return text_pos - pattern_pos;
            }

            /* テキストとパターンの比較位置を１文字分後ろ側に移動する */
            text_pos++;
            pattern_pos++;

        } else {
            /* 不一致した場合 */

            /* 不一致した位置が先頭の位置であるかを判断 */
            if (pattern_pos == 0) {
                /* 先頭の位置で比較が不一致した場合 */

                /* テキストの比較位置を１文字分後ろ側に移動する */
                text_pos++;

                /* パターンの比較位置を先頭に移動する */
                pattern_pos = 0;
            } else {
                /* 先頭の位置以外で比較が不一致した場合 */

                /* テキストの比較位置を前側に移動する */
                text_pos -= (pattern_pos - 1);

                /* パターンの比較位置を先頭に移動する */
                pattern_pos = 0;
            }
        }
    }

    /* パターンが見つからなかった場合は-1を返却 */
    return -1;
}

int main(void) {
    char text[MAX_TEXT] =  "baabaabaabaabaavaabaabaa";
    char pattern[MAX_PATTERN] = "aabaabaa";
    int find;

    find = forceSearch(text, strlen(text), pattern, strlen(pattern));
    if (find != -1) {
        printf("パターンはテキストの第%d文字に存在します\n", find);
    } else {
        printf("パターンはテキスト内に存在しません...\n");
    }

    return 0;
}

力まかせ法による文字列検索プログラムで紹介したものと大きく異なっているように見えますが、この違いは注目するもの（”パターンをずらす文字数” or “テキストの比較位置”）の違いにより発生しているだけで、どちらも力まかせ法による文字列検索プログラムになります。

当然同じ検索結果が得られますし、比較を行う位置の順番も全く同じになるはずです。

直感的に分かりやすいのは力まかせ法による文字列検索プログラムの方に軍配は上がるかなぁと思います。

ただ、この “テキストの比較位置” に注目して実装することで、下記部分で “テキストの比較位置” が先頭以外の文字で不一致するたびに前側に移動してしまっていることが分かりやすくなります。

/* テキストの比較位置を前側に移動する */
text_pos -= (pattern_pos - 1);

つまり “テキストの比較位置” に対して手戻りが発生しています。この手戻りがあるせいで、力まかせ法の検索効率は低下してしまいます。

例えば文字列検索アルゴリズムの１つである KMP 法では、この “テキストの比較位置の前側への移動” をスキップすることで効率よく文字列検索を行います。そういったアルゴリズムと比較する際は、ここで紹介したソースコードの方が分かりやすいかなぁと思います！

KMP 法については下記ページで解説していますので、KMP 法について詳しく知りたい方は是非下記ページを読んでみてください！

KMP法についてわかりやすく解説（C言語サンプル付き）

力まかせ法の計算量

最後に力まかせ法の計算量について解説しておきます。

テキストの文字数を M、パターンの文字数を N とすると、力まかせ法の最悪計算量は、オーダー表記で O(MN) となります。これは力まかせ法による文字列検索プログラムを見ると分かりやすいと思います（約 M 回のループの中で最悪 N 回の比較を行なっている）。

ただし、最悪の計算量になるのは、毎回 N 回の比較が行われる時のみです。つまり毎回パターンの最後の文字の比較が不一致する場合です。

もちろんテキストやパターン内で使用される文字数が極端に少ない場合は上記のようなケースもあり得ますが、アルファベットや数字などが使用される一般的な文章の場合、使用される文字数は多く、パターンの最初の文字の比較で不一致するケースがほとんどです。

このあたりのことを考慮すると、実用上の性能は O(M) 程度であると考えることが出来ます。

まとめ

このページでは文字列検索アルゴリズムの１つである “力まかせ法” について解説しました！

単純に、パターンが存在する可能性のある “テキストの位置” 全ての位置を調べるのが “力まかせ法” になります。

単純なアルゴリズムですが、他の文字列検索アルゴリズムのベースとなっていることも多く、他の文字列検索アルゴリズムをスムーズに学ぶためにはこの “力まかせ法” の考え方はしっかり理解しておく方が良いと思います！

また、”値” を探索する時とは異なり、２次元的に比較を行なっていく必要があり、プログラミングするのは結構難しいと思います。ぜひご自身でも実際にプログラミングしてみて、この難しさを実感していただければと思います！

このページで紹介した力まかせ法を改良した文字列検索アルゴリズムに KMP 法があります。この KMP 法については下記ページで解説していますので、他の文字列検索アルゴリズムにも興味ある方は是非下記ページを読んでみてください！

KMP法についてわかりやすく解説（C言語サンプル付き）