[Python] 決定性有限オートマトンを使った文字列検索

以下の続きです。

下の動画を参考にしています。

⨘ } Algorithms } 38 } String Matching } Finite Automata }

決定性有限オートマトンを使うと、文字列検索アルゴリズムは以下の流れで表現できます。

オートマトンを作る

あるパターン$ P[0, 1, … , m-1] $が与えられたとして、そのパターンに基づきオートマトンを作ります。

$$ \begin{align} & Q = \{ 0, 1, 2, …, m \} \\ & Σ = \{x | x はパターンPに含まれる文字\} \\ & q_0 = 0 \\ & F = \{m\}\\ & δ : 状態遷移表の作り方は以下に述べる。 \\ \end{align} $$

⊏ と ⊐ の意味

⊐ という記号が、このアルゴリズムについての疑似コードを検索すると良く出てきます。文脈で何となくは意味は分かりますが、ちゃんと説明しているところがなかなか見つからず苦労しました。こちらのサイトに説明がありました。

Prefix 接頭辞

文字列 w が文字列 x の接頭辞である時、 w ⊏ x と書く。例えば、 ab ⊏abcca である。

Suffix 接尾辞

文字列 w が文字列 x の接尾辞である時、 w ⊐ x と書く。例えば、 cca ⊐ abcca である。

また、空文字列 ε は、全ての文字列の接頭辞でもあり、接尾辞でもある。

状態遷移表の作り方

状態遷移表は、入力文字列から新しい文字を持ってくる時、「文字列の接尾辞はパターンの接頭辞と一致する必要がある」ということから考えることができます。一致すると考えられる最長の文字列から比較を開始し、全く一致しない場合は初期状態に戻ります。一致する場合は、その一致する長さにより次の状態へと遷移します。

文字列の検索

オートマトンが出来れば、あとはただ文字列をスキャンして、受理状態になればマッチングしたと考えることができます。

import random
import string

def match_pattern_finite_automaton(text, transition_table, pattern):
	m = len(pattern)
	s = 0
	for i, c in enumerate(text):
		s = transition_table[s][c]
		if s == m:
			return i - m + 1
    
	return -1

def delta(pattern, text):
	prospected_letters = set(text)
	m = len(pattern)
	
	transition_table = [{c:0 for c in prospected_letters} for i in range(m)]

	for s in range(m):
		for c in prospected_letters:
			k = min(m, s+1)
			while (pattern[:s]+c)[-k:] != pattern[:k]:
				k-=1
				
			transition_table[s][c] = k
			
	return transition_table


def print_match_pattern_result(text, pattern):
	transition_table = delta(pattern, text)
	index =  match_pattern_finite_automaton(text, transition_table, pattern)
	if index>=0:
		print(f'"{pattern}"は {index}番目に見つかりました。')
	else:
		print(f'"{pattern}"は見つかりません。')


random.seed(1)
target_str = ''.join(random.choices(string.ascii_letters + string.digits, k=20))
# i0VpEBOWfbZAVaBSo63b
print(target_str)
# "BSo63"は 14番目に見つかりました。
print_match_pattern_result(target_str, "BSo63")
# "BSo6E"は見つかりません。
print_match_pattern_result(target_str, "BSo6E")

想定通りの結果を得ることができました。