力まかせのアルゴリズム（Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

今回は、文字列の探索として力まかせのアルゴリズム（Brute Forcing Algorithm）について学んでいきます。

力まかせのアルゴリズムとは
Pythonで力まかせのアルゴリズムを実装してみる
動作確認
参考書籍

力まかせのアルゴリズムとは

力まかせのアルゴリズム（Brute Forcing Algorithm）とは、その名の通りパターンにマッチする文字列を順番に力まかせに探索を行うだけの単純なアルゴリズムになります。

例えば文字列として"strings"があった場合、"ring"というパターンと一致した部分を探索したい場合には、以下のように一文字ずつずらしながら探索をしていきます。

計算量としては、文字列の長さを $n$ 、一致させるパターンを $m$ とした場合、重ね合わせる部分を $n-m+1$ として、これを $m$ 回行うことになるので、合計で $m(n-m+1)$ となります。

この場合、 $m$ は $n$ に比べて小さいと考えると、計算量は $O(mn)$ となります。

しかし、自然言語においては通常最初の数文字を探索し、失敗した場合はその殆どを調べることはあまりないので、実質的には $O(n)$ であると言えます。

Pythonで力まかせのアルゴリズムを実装してみる

それでは、Pythonで力まかせのアルゴリズムを実装してみます。

# brute_forcing.py
import time

def brute_force_search(string, pattern):
    i = j = 0
    while i < len(string) and j < len(pattern):
        if string[i] == pattern[j]:
            i += 1
            j += 1
        else:
            i = i - j + 1
            j = 0

    if j == len(pattern):
        return i - j
    else:
        return None

with open("sample_string.txt", "r") as f:
    string = f.read()
pattern = "hoge"

start = time.time()
index = brute_force_search(string, pattern)

if index:
    print("The pattern starts with at index {}.".format(index))
else:
    print("No pattern matched.")
print("elapsed {} sec.".format(time.time() - start))

上記はPython組み込みのfind()のような関数です。

find()の場合、探索に失敗すると $-1$ を返しますが、ここではNoneを返します。