文字列マッチングアルゴリズムの2:有限自動機を利用する
下一篇:string matchingアルゴリズムの一つ(Naive and Rabin_Karp)
有限自動機:
有限自動機Mは5要素群(Q,q 0,A)である.Σ, δ), 次のようになります.
・Qは状態の有限集合である
・q 0∈Q初期状態
・A⊆Qは受容状態の集合である
· Σ 制限された入力アルファベット
· δ Qから× Σ Qへの関数をMの遷移関数(transition function)と呼ぶ
有限自動機は、状態q 0から開始する、入力文字列の1文字を読み込むたびに、
状態qにおいて入力文字aが読み込まれると、状態qからδ(q, a).
その現在の状態qが(受入れ状態の集合)Aに属する場合、自動機Mは、これまで読込んだ文字列を受入れているという.
受信入力がないことを拒否された入力と呼ぶ.
有限自動機Mは1つの関数を導出することができるφ, 終態関数と呼ばれます.φ(w)は、スキャン文字列wの後にMが終了したときの状態である.
φ(ε)
=
q0,
φ(wa)
=
δ(φ(w), a) for w ∈ Σ*, a ∈ Σ.
したがって、Mは、文字列wがφ(w) ∈ A
文字列マッチングロボット
与えられたモードP[1̈m]は、補助関数を定義するσ対応するPの接尾辞関数を数える.
関数＃カンスウ＃σからΣ*{0,1,..,,m}へのマッピング:
σ(x)はxの接尾辞であり、pの最長接頭辞の長いである.
σ(x) is the length of the longest prefix of P that is a suffix of x:
σ(x) = max {k : Pk ⊐ x}.
例えばモードP=ab、σ(ccaca) = 1, and σ(ccab) = 2
長さmのモードPにとって、σ(x)=m当である、P⊐x(Pがxの接尾辞)のみである.
与えられたパターンP[1.m]は、対応する文字列が自動機の定義に一致する.
l状態セットQは{0,1,...,m},初期状態q 0,状態mは一意の受け入れ状態である.
l任意の状態qと文字aに対して、遷移関数δの定義は次のとおりです.δ(q, a) = σ(Pqa). (ここでPqはPのプレフィックスP[1.q])
すなわち、状態qを現在一致する長いとする.
例えばパターンP=ababaca.テキストT=abababacaba.
ありますδ(5,b)=4、状態q=5のときにオートマチックから1つのbを読み込むとPqb=abababとなり、abababの接尾辞がPに一致する最長接頭辞はP 4=abababとなる.
(The longest prefix of P that is also a suffix of ababab is P4 = abab)
付録:
使用するΣ* 表示用アルファベットΣのすべての制限された長さの文字列の集合
長さ0の空白文字列用εに表示されます.εに属するΣ*
文字列接頭辞
ある文字列y∈Σ*,x=wyとすると、wはxの接頭辞であり、wwがxの接尾辞であればw
《Introduction to Algorithms》- CLRS
有限自動機:
有限自動機Mは5要素群(Q,q 0,A)である.Σ, δ), 次のようになります.
・Qは状態の有限集合である
・q 0∈Q初期状態
・A⊆Qは受容状態の集合である
· Σ 制限された入力アルファベット
· δ Qから× Σ Qへの関数をMの遷移関数(transition function)と呼ぶ
有限自動機は、状態q 0から開始する、入力文字列の1文字を読み込むたびに、
状態qにおいて入力文字aが読み込まれると、状態qからδ(q, a).
その現在の状態qが(受入れ状態の集合)Aに属する場合、自動機Mは、これまで読込んだ文字列を受入れているという.
受信入力がないことを拒否された入力と呼ぶ.
有限自動機Mは1つの関数を導出することができるφ, 終態関数と呼ばれます.φ(w)は、スキャン文字列wの後にMが終了したときの状態である.
φ(ε)
=
q0,
φ(wa)
=
δ(φ(w), a) for w ∈ Σ*, a ∈ Σ.
したがって、Mは、文字列wがφ(w) ∈ A
文字列マッチングロボット
与えられたモードP[1̈m]は、補助関数を定義するσ対応するPの接尾辞関数を数える.
関数＃カンスウ＃σからΣ*{0,1,..,,m}へのマッピング:
σ(x)はxの接尾辞であり、pの最長接頭辞の長いである.
σ(x) is the length of the longest prefix of P that is a suffix of x:
σ(x) = max {k : Pk ⊐ x}.
例えばモードP=ab、σ(ccaca) = 1, and σ(ccab) = 2
長さmのモードPにとって、σ(x)=m当である、P⊐x(Pがxの接尾辞)のみである.
与えられたパターンP[1.m]は、対応する文字列が自動機の定義に一致する.
l状態セットQは{0,1,...,m},初期状態q 0,状態mは一意の受け入れ状態である.
l任意の状態qと文字aに対して、遷移関数δの定義は次のとおりです.δ(q, a) = σ(Pqa). (ここでPqはPのプレフィックスP[1.q])
すなわち、状態qを現在一致する長いとする.
例えばパターンP=ababaca.テキストT=abababacaba.
ありますδ(5,b)=4、状態q=5のときにオートマチックから1つのbを読み込むとPqb=abababとなり、abababの接尾辞がPに一致する最長接頭辞はP 4=abababとなる.
(The longest prefix of P that is also a suffix of ababab is P4 = abab)
// FINITE-AUTOMATON-MATCHER(T, δ, m)
1 n ← length[T]
2 q ← 0
3 for i ← 1 to n
4 do q ← δ(q, T[i]) //δ ， ，
5 if q = m
6 then print "Pattern occurs with shift" i – m Θ(n). // δ
COMPUTE-TRANSITION-FUNCTION(P, Σ)
1 m ← length[P]
2 for q ← 0 to m
3 do for each character a ∈ Σ
4 do k ← min(m + 1, q + 2)
5 repeat k ← k - 1
6 until Pk ⊐ Pqa
7 δ(q, a) ← k
8 return δ O(m3 |Σ|).. 。
付録:
使用するΣ* 表示用アルファベットΣのすべての制限された長さの文字列の集合
長さ0の空白文字列用εに表示されます.εに属するΣ*
文字列接頭辞
ある文字列y∈Σ*,x=wyとすると、wはxの接頭辞であり、wwがxの接尾辞であればw
《Introduction to Algorithms》- CLRS