「新・明解Pythonで学ぶアルゴリズムとデータ構造」で勉強日記#24

【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら

第7章 文字列探索

本章で学習するのは、文字列探索のアルゴリズムです。

7-1 力まかせ法

文字列の中に含まれる文字列を探索するアルゴリズムを学習します。

力任せ法のイメージとしては、
"STRING"
という文字列に
"IN"
が含まれているかを確認するとしたとき、それぞれの配列の添字どうしを見比べて一致するまで繰り返す。イメージです。

list7-1

#力任せ法による文字列探索

def bf_match(txt: str, pat: str) -> int:
    """力任せ法による文字列探索"""
    pt = 0 # txtをなぞるカーソル
    pp = 0 #patをなぞるカーソル
    
    while pt != len(txt) and pp != len(pat):
        if txt[pt] == pat[pp]:
            pt += 1
            pp += 1
        else:
            pt = pt - pp + 1
            pp = 0
            
    return pt - pp if pp == len(pat) else -1
    
if __name__ =='__main__':
    s1 = input('テキスト：') #テキスト用文字列
    s2 = input('パターン：') #パターン用文字列
    
    idx = bf_match(s1, s2) #文字列s1から文字列s2を力まかせ法で探索
    
    if idx == -1:
        print('テキスト中にはパターンは存在しません。')
    else:
        print(f'{(idx + 1)}文字目にマッチします。')

関数bf_matchは文字列txtから文字列patを探索し、照合に成功した位置のtxt側の添字を返します。
文字列txtから文字列patが複数含まれる場合に返すのは、最も先頭側の位置の添字です。なお、探索に失敗した場合は、-1を返します。

コラム7-1 文字コードを扱うord関数とchr関数

ord関数は単一のUnicode文字を表す文字列を受け取って、そのUnicodeコードポイントを表す整数を返却する組み込み関数です。例えばord('a')は整数97を返却します。
この関数と逆の変換を行う組み込み関数がchr関数です。(chr(97)は'a'を返す。)

コラム7-2 言語機能と標準ライブラリによる文字列探索

・言語レベルでの判定
帰属性判定演算子(in, not in 演算子)を使うとある文字列が、別の文字列に含まれているか否かを調べることができます。しかし、位置までは分かりません。

・find系メソッド/index系メソッドによる判定
ある文字列が別の文字列の中に含まれる位置を調べるために提供されるのが、strクラス型に所属するfind,rfind,index,rindexメソッドです。

str.find(sub[, start[, end]])
文字列strの[start:end]にsubが含まれれば、その最小のインデックスを返却し、そうでなければ-1を返却します。(省略可能な引数startとendはスライス表記と同様の指定です)
※引数を囲む[]は、その中の引数が省略可能であることを示す解説上の表記です。
本メソッドの場合、老けとる引数はsub,start,endの3個で、3番目のendのみの省略か、あるいは2番目にstartと3番目のendの両方の省略が可能(先頭のsubは省略不可)

str.rfind(sub[, start[, end]])
文字列strの[start:end]にsubが含まれれば、その最大のインデックスを返却し、そうでなければ-1を返却します。(省略可能な引数startとendはスライス表記と同様に解釈されます)

str.index(sub[, start[, end]])
find()と同様ですが、subが見つからない場合はValueError例外を送出します。

str.rfind(sub[, start[, end]])
rfind()と同様ですが、subが見つからない場合はValueError例外を送出します。

・with系メソッドによる判定
文字列が、他の文字列を先頭あるいは末尾に含むかどうかを判定するのがwith系メソッドです。

str.startswith(prefix[, start[, end]])
文字列の先頭がprefixで始まれば、Trueを、そうでなければFalseを返却します。prefixは見つけるべき複数の接頭語のタプルでも構いません。省略可能なstartが指定されていれば、その位置から判定を始めます。省略可能なendが指定されていれば、その位置で比較を止めます。

str.endswith(suffix[, start[, end]])
文字列の末尾が、suffixで終わればTrueを、そうでなければFalseを返却します。suffixは見つけるべき複数の接尾語のタプルでも構いません。省略可能なstartが指定されていれば、その位置から判定を始めます。省略可能なendが指定されていれば、その位置で比較を止めます。

7-2 KMP法

力まかせ法は、不一致文字に出会った段階で、それまでの照合結果を捨て去ってパターンの先頭文字からの照合を行い直すアルゴリズムでした。
照合結果を捨て去ることなく有効に活用するのが、KMP法(Knuth-Morris-Pratt法)です。
テキストとパターン中の重なっている部分をうまく見つけ出して照合を再開する位置を求め、パターンの移動をなるべく大きくしようというアルゴリズムです。何文字目から照合を再開するのかをパターン移動するたびに計算し直すのでは、高い効率は望めないため、その値を事前に表として作成しておきます。
表の作成にあたっては、パターン内の"重複した並び"を見つけます。その過程でもKMP法と同じ考え方を適用します。
パターンの1文字目が不一致の場合、パターンを1文字ずらして先頭文字から照合を行わなければならないことは分かり切っているので、2文字目以降を考えていきます。また、パターンとテキストを重ね合わせるのではなく、パターンどうしを重ね合わせて計算します。

ABCABDという文字列で考えると次のような表ができます。

文字列	A	B	C	A	B	D
再開値の添字	-	0	0	1	2	0

一文字ずらして照合を開始するため、再開値の添字は-です。

list7-2

#KMP法による文字列探索

def kmp_match(txt: str, pat: str) -> int:
    """KMP法による文字列探索"""
    pt = 1 #txtをなぞるカーソル
    pp = 0 #patをなぞるカーソル
    skip = [0] * (len(pat) + 1) #スキップテーブル
    
    #スキップテーブルの作成
    skip[pt] = 0
    while pt != len(pat):
        if pat[pt] == pat[pp]:
            pt += 1
            pp += 1
            skip[pt] = pp
        elif pp == 0:
            pt += 1
            skip[pt] = pp
        else:
            pp = skip[pp]
            
    #探索 
    pt = pp = 0
    while pt != len(txt) and pp != len(pat):
        if txt[pt] == pat[pp]:
            pt += 1
            pp += 1
        elif pp == 0:
            pt += 1
        else:
            pp = skip[pp]
    return pt - pp if pp == len(pat) else -1
    
if __name__ == '__main__':
    s1 = input('テキスト：') #テキスト用文字列
    s2 = input('パターン：') #パターン用文字列
    
    idx = kmp_match(s1, s2) #文字列s1から文字列s2をKMP法で探索
    
    if idx == -1:
        print('テキスト中にパターンは存在しません。')
    else:
        print(f'{(idx + 1)}文字目にマッチしました。')

KMP法のアルゴリズムは、複雑であるにも関わらず、次で学習するアルゴリズムと同等以下の性能しか発揮できないため、現実のプログラムではあまり、利用されません。

7-3 Boyer-Moore法

Boyer-Moore法(BM法)は、理論的にも実践的にもKMP法より優れたアルゴリズムです。
基本方針は、パターンの末尾文字から先頭側へと照合を行う過程で不一致文字を見つけた場合に事前に用意した表に基づいてパターンの移動量を決定します。

このアルゴリズムを利用するには、各文字に出会ったときの移動量(照合中の文字を何文字ずらせばよいのか)を格納した表を、事前に作っておく必要があります。パターン文字列の長さがnであるときの移動量は次のように決定します。

・パターンに含まれない文字
移動量はn。
・パターンに含まれる文字
最後に出現する位置の添字がkであれば移動量はn - k - 1。

例としてテキスト"ABCXDEZCABACABAC"、パターンを"ABAC"としたら次のようなスキップテーブルになります。

A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
1	2	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4

BM法のプログラムをlist7-3に示します。パターン中に存在し得るすべての文字の移動量を計算しなければならないため、スキップテーブルを格納する配列skipの要素数は256としています。

list7-3

#Boyer--Moore法による文字列探索(対象は0～255の文字)

def bm_match(txt: str, pat: str) -> int:
    """Boyer--Moore法による文字列探索"""
    skip = [None] * 256 #スキップテーブル
    
    #スキップテーブルの作成
    for pt in range(256):
        skip[pt] = len(pat)
    for pt in range(len(pat)):
        skip[old(pat[pt])] = len(pat) - pt - 1
        
    #探索
    while pt < len(txt):
        pp = len(pat) - 1
        while txt[pt] == pat[pp]:
            if pp == 0:
                return pt
            pt -= 1
            pp -= 1
        pt += skip[ord(txt[pt])] if skip[ord(txt[pt])] > len(pat) - pp else len(pat) - p
        
    return -1

コラム7-3 文字列探索アルゴリズムの計算量と実用度

テキストの文字数がnであり、パターンの文字列がmであるとして、本章で、学習した3つの文字列探索アルゴリズムについて考察します。

・力まかせ法
アルゴリズムの時間計算量はO(mn)ですが、作為的なわざとらしいパターンでない限り、実質的な時間計算量はO(n)となる事が知られています。単純なアルゴリズムですが、意外と高速に動作します。
・KMP法
アルゴリズムの時間計算量は、最悪でもO(n)と高速です。その一方で、処理が複雑であることや、パターン内に繰り返しがなければ効果が薄いといった欠点があります。ただし、探索の過程で、着目点を前方に戻す必要が一切ないため、順ファイルからの読み込みを行いながらの探索に適しています。
・BM法
アルゴリズムの計算量は最悪でもO(n)、平均的にはO(n/m)と高速です。なお、本来のアルゴリズムである、二つの配列を用いた方法は、KMP法と同様に、配列の作成に複雑な処理が必要なため、効果が相殺されてしまいます。したがって、簡略BM法でも十分に高速です。

プログラムでは、標準ライブラリを使うのが基本です。標準ライブラリ以外の手段を使うのであれば、簡略BM法(あるいはそれを改良したもの)、場合によっては、力まかせ法が利用されることが多いようです。

本日は以上です。
これで7章が終わりです。ありがとうございました。