String matching based on finite automaton: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
Line 23: Line 23:


==Induction basis==
==Induction basis==
'''Abstract view:'''
# <math>R</math> is empty.
# The initial value of <math>q</math> is zero.
# The look-up table <math>\Delta</math> must be built.
'''Implementation:'''
# Set <math>R:=\emptyset</math>.
# Set <math>q:=0</math>.
# For <math>c\in \Sigma</math>: If <math>T[1]=c</math>, set <math>\Delta [0,c]:=1</math>; otherwise, set <math>\Delta[0,c]:=0</math>.
# For <math>j\in \{ 1,...,m\}</math> and <math>c \in \Sigma</math>:
## Set <math>k:=\min \{ m,j+1 \}</math>.
## While <math>k>0</math> and <math>(T[1],...,T[k]) \neq (T[j-k+2],...,T[j],c)</math>, decrease <math>k</math> by <math>1</math>.
## Set <math>\Delta[j,c]:=k</math>.
'''Proof:''' Nothing is to show for <math>R</math> and <math>q</math>, so consider <math>\Delta</math>. We have to show that the above-described intended semantics of <math>\Delta</math> is indeed fulfilled, because these intended semantics of <math>\Delta</math> will be the basis for the correctness proof of the induction step.
Correctness of Step 3 is also easy to see, so consider Step 4.
According to its intended semantics, <math>\Delta [j,c]</math> can neither be larger than <math>m</math> nor larger than <math>j+1</math>; in fact, any string longer than <math>m</math> is not a prefix of <math>T</math>, and any string longer than <math>j+1</math> is not a suffix of <math>(T[1],...,T[j],c)</math>. This observation justifies the initialization of <math>k</math> in Step 4.1.
Now, the countdown of <math>k</math> in Step 4.2 will terminate at the moment when, for the first time, <math>k</math> fulfills <math>(T[1],...,T[k])=(T[j-k+2],...,T[j],c)</math>. Note that this equality is tantamount to the statement that the prefix <math>(T[1],...,T[k])</math> of <math>T</math> is a suffix of <math>(T[j-k+2],...,T[j],c)</math>. Due to the countdown, <math>k</math> is largest, so <math>\Delta [j,c]</math> conforms to its intended semantics. On the other hand, if the countdown terminates with <math>k=0</math>, there was no such non-empty substring, so it is <math>\Delta [j,c]=0</math>, which conforms to the intended semantics in this case as well.


==Induction step==
==Induction step==

Revision as of 13:51, 1 October 2014

Algorithmic problem: One-dimensional string matching

Prerequisites:

Type of algorithm: loop

Auxiliary data:

  1. A current maximum prefix length [math]\displaystyle{ q\in \{ 0,...,m\} }[/math].
  2. A look-up table [math]\displaystyle{ \Delta }[/math] with rows [math]\displaystyle{ \{ 0,...,m\} }[/math] and one column for each character in the alphabet [math]\displaystyle{ \Sigma }[/math]. Intended semantics: The value [math]\displaystyle{ \Delta [j,c] }[/math] is the length of the longest prefix of [math]\displaystyle{ T }[/math] that is also a suffix of [math]\displaystyle{ (T[1],...,T[j],c) }[/math].

Abstract view

Invariant: After [math]\displaystyle{ i \ge 0 }[/math]:

  1. In ascending order, [math]\displaystyle{ R }[/math] contains the start indexes of all occurrences of [math]\displaystyle{ T }[/math] in [math]\displaystyle{ S }[/math] that lie completely in [math]\displaystyle{ (S[1],...,S[i]) }[/math]; in other words, the start indexes in the range [math]\displaystyle{ (1,...,i-m+1]) }[/math].
  2. The value of [math]\displaystyle{ q }[/math] is the largest value [math]\displaystyle{ k }[/math] such that [math]\displaystyle{ (S[i-k+1],...,S[i])=(T[1],...,T[k]) }[/math].

To understand the rationale of the second invariant, note that [math]\displaystyle{ (S[i-k+1],...,S[i])=(T[1],...,T[k]) }[/math] is equivalent to the informal statement that [math]\displaystyle{ (S[i-k+1],...,S[i]) }[/math] is a candidate for an occurrence of [math]\displaystyle{ T }[/math]. In particular, [math]\displaystyle{ i-q+1 }[/math] is always the "most advanced" candidate (and [math]\displaystyle{ q=0 }[/math] means that, at the moment, there is no candidate at all).

Variant: [math]\displaystyle{ i }[/math] increases by [math]\displaystyle{ 1 }[/math].

Break condition: [math]\displaystyle{ i=n }[/math].

Induction basis

Abstract view:

  1. [math]\displaystyle{ R }[/math] is empty.
  2. The initial value of [math]\displaystyle{ q }[/math] is zero.
  3. The look-up table [math]\displaystyle{ \Delta }[/math] must be built.

Implementation:

  1. Set [math]\displaystyle{ R:=\emptyset }[/math].
  2. Set [math]\displaystyle{ q:=0 }[/math].
  3. For [math]\displaystyle{ c\in \Sigma }[/math]: If [math]\displaystyle{ T[1]=c }[/math], set [math]\displaystyle{ \Delta [0,c]:=1 }[/math]; otherwise, set [math]\displaystyle{ \Delta[0,c]:=0 }[/math].
  4. For [math]\displaystyle{ j\in \{ 1,...,m\} }[/math] and [math]\displaystyle{ c \in \Sigma }[/math]:
    1. Set [math]\displaystyle{ k:=\min \{ m,j+1 \} }[/math].
    2. While [math]\displaystyle{ k\gt 0 }[/math] and [math]\displaystyle{ (T[1],...,T[k]) \neq (T[j-k+2],...,T[j],c) }[/math], decrease [math]\displaystyle{ k }[/math] by [math]\displaystyle{ 1 }[/math].
    3. Set [math]\displaystyle{ \Delta[j,c]:=k }[/math].

Proof: Nothing is to show for [math]\displaystyle{ R }[/math] and [math]\displaystyle{ q }[/math], so consider [math]\displaystyle{ \Delta }[/math]. We have to show that the above-described intended semantics of [math]\displaystyle{ \Delta }[/math] is indeed fulfilled, because these intended semantics of [math]\displaystyle{ \Delta }[/math] will be the basis for the correctness proof of the induction step.

Correctness of Step 3 is also easy to see, so consider Step 4.

According to its intended semantics, [math]\displaystyle{ \Delta [j,c] }[/math] can neither be larger than [math]\displaystyle{ m }[/math] nor larger than [math]\displaystyle{ j+1 }[/math]; in fact, any string longer than [math]\displaystyle{ m }[/math] is not a prefix of [math]\displaystyle{ T }[/math], and any string longer than [math]\displaystyle{ j+1 }[/math] is not a suffix of [math]\displaystyle{ (T[1],...,T[j],c) }[/math]. This observation justifies the initialization of [math]\displaystyle{ k }[/math] in Step 4.1.

Now, the countdown of [math]\displaystyle{ k }[/math] in Step 4.2 will terminate at the moment when, for the first time, [math]\displaystyle{ k }[/math] fulfills [math]\displaystyle{ (T[1],...,T[k])=(T[j-k+2],...,T[j],c) }[/math]. Note that this equality is tantamount to the statement that the prefix [math]\displaystyle{ (T[1],...,T[k]) }[/math] of [math]\displaystyle{ T }[/math] is a suffix of [math]\displaystyle{ (T[j-k+2],...,T[j],c) }[/math]. Due to the countdown, [math]\displaystyle{ k }[/math] is largest, so [math]\displaystyle{ \Delta [j,c] }[/math] conforms to its intended semantics. On the other hand, if the countdown terminates with [math]\displaystyle{ k=0 }[/math], there was no such non-empty substring, so it is [math]\displaystyle{ \Delta [j,c]=0 }[/math], which conforms to the intended semantics in this case as well.

Induction step

Complexity

Further information