Verbindung zwischen KMP-Präfixfunktion und String-Matching-Automat

7

Sei der String-Matching-Automat für das Muster , das heißtAP=(Q,Σ,δ,0,{m})PΣm

  • Q={0,1,,m}
  • δ(q,a)=σP(P0,qa) für alle undqQaΣ

mit die Länge des längsten Präfixes von , das ein Suffix von , das heißtσP(w)Pw

σP(w)=max{kN0P0,kw} .

Nun lassen π die Präfix - Funktion aus dem Knuth-Morris-Pratt - Algorithmus , das heißt

πP(q)=max{kk<qP0,kP0,q} .

Wie sich herausstellt, kann man πP , um δ schnell zu berechnen . Die zentrale Beobachtung ist:

Nehmen Sie die obigen Begriffe und aΣ . Für q{0,,m} mit q=m oder Pq+1a gilt dies

δ(q,a)=δ(πP(q),a)

Aber wie kann ich das beweisen?


Als Referenz berechnen Sie auf folgende Weise πP :

m ← length[P ]
π[0] ← 0
k ← 0
for q ← 1 to m − 1 do
  while k > 0 and P [k + 1] =6 P [q] do
    k ← π[k]
    if P [k + 1] = P [q] then
       k ← k + 1
    end if
    π[q] ← k
 end while
end for

return π
Bob
quelle
3
Können Sie etwas mehr Details liefern? Was ist das Muster? Was genau ist die Präfixfunktion? Ich habe auf dem von Ihnen angegebenen Link keine Präfixfunktion gesehen. Ist der Automat deterministisch oder nicht deterministisch?
Dave Clarke
3
Ist das nicht die Definition der KMP-Übergangsfunktion? Diese Hinweise sind möglicherweise hilfreich (siehe jedoch Fußnote 1).
JeffE
Ich habe die Frage mit der Präfixfunktion von KMP
Bob
1
Ihre Frage ist also im Grunde, wie Sie beweisen können, dass der obige Code die Präfixfunktion von KMP berechnet.
Rgrig
2
@ Raphael: Ich finde die bearbeitete Frage viel weniger lesbar.
JeffE

Antworten:

3

Beachten Sie zunächst per Definition, dass per Definition

  • δ(q,a)=σP(P0,qa)=:s1 und
  • δ(πP(q),a)=σP(P0,πP(q)a)=:s2 .

Untersuchen wir und in einer Skizze:s1s2

skizzieren
[ Quelle ]

Nehmen wir nun an, ; dies widerspricht der maximalen Wahl von direkt. Wenn wir annehmen, widersprechen wir der Tatsache, dass sowohl als auch maximal gewählt werden, insbesondere weil . Da beide Fälle zu Widersprüchen führen, gilt , qeds2>s1s1s1>s2 s2πP(q)πP(q)s11s1=s2


Wie gewünscht, eine ausführlichere Version des Beweises:

Jetzt müssen wir ; Wir tun dies, indem wir zeigen, dass das Gegenteil zu Widersprüchen führt.s1=s2

  • Angenommen, . Beachten Sie, dass weil und per Definition von . Daher ist - ein Präfix von und ein Suffix von - länger als , was per Definition von das längste Präfix von das ist ein Suffix von . Dies ist ein Widerspruch.s2>s1P0,s2P0,qaP.0,s2P.0,πP.(q)einP.0,πP.(q)P.0,qs2P.0,s2P. P.0,qeinP.0,s1s1P.P.0,qein

Bevor wir mit dem anderen Fall fortfahren, lassen Sie uns sehen, dass . Beachten Sie, dass wir haben , weil . Angenommen, widerspricht sofort der maximalen Auswahl von ( befindet sich in der Menge, aus der ausgewählt wird).πP.(q)s1- -1P.0,s1P.0,qeinP.0,s- -1P.0,qπP.(q)<s1- -1πP.(q)s1- -1πP.(q)

  • Angenommen, . Wir haben gerade , und denken Sie daran, dass . Daher widerspricht der maximalen Auswahl von ( befindet sich in der Menge, aus der ausgewählt ist).s1>s2|P.0,πP.(q)ein|s1P.0,πP.(q)einP.0,qeins1>s2s2s1s2

Da weder noch können, haben wir bewiesen, dass , qeds1>s2s2>s1s1=s2

Raphael
quelle
Können Sie bitte Ihre Antwort für oder ? q=mP.q+1ein
@SCO: Was meinst du mit "rechtfertigen"? Dies ist nur eine Bedingung in der Anweisung, die sicherstellt, dass das "längste Präfix von P, das ein Suffix von w ist" verwendet wird.
Raphael