Simple string matching algorithm - Revision history

Weihe: /* Abstract view */

2015-09-21T10:13:10Z

Abstract view

← Older revision		Revision as of 10:13, 21 September 2015
Line 8:		Line 8:
	'''Type of algorithm:''' loop		'''Type of algorithm:''' loop

	'''Auxiliary data''' A [[~~Sets and sequences#Stacks and queues\|FIFO queue~~]] <math>I</math> of natural numbers.		'''Auxiliary data''' An [[ordered sequence]] <math>I</math> of natural numbers.

	'''Invariant:''' After <math>i\ge 0</math> iterations:		'''Invariant:''' After <math>i\ge 0</math> iterations:

Luedecke at 22:49, 19 June 2015

2015-06-19T22:49:55Z

← Older revision		Revision as of 22:49, 19 June 2015
Line 1:		Line 1:
	[[Category:~~Checkup~~]]		[[Category:Videos]]
	[[Category:Algorithm]]		[[Category:Algorithm]]
	[[Category:Main Algorithm]]		[[Category:Main Algorithm]]

Luedecke at 17:32, 17 June 2015

2015-06-17T17:32:17Z

← Older revision		Revision as of 17:32, 17 June 2015
Line 1:		Line 1:
	~~__NOTOC__~~
	[[Category:Checkup]]		[[Category:Checkup]]
	[[Category:Algorithm]]		[[Category:Algorithm]]
	[[Category:Main Algorithm]]		[[Category:Main Algorithm]]
			{{#ev:youtube\|https://www.youtube.com/watch?v=5p4fZGRaYuo\|500\|right\|Simple string matching\|frame}}
	'''Algorithmic problem:''' [[One-dimensional string matching]]		'''Algorithmic problem:''' [[One-dimensional string matching]]

Weihe: /* Abstract view */

2015-05-16T13:31:03Z

Abstract view

← Older revision		Revision as of 13:31, 16 May 2015
Line 16:		Line 16:
	'''Variant:''' <math>i</math> increases by <math>1</math>.		'''Variant:''' <math>i</math> increases by <math>1</math>.

	'''Break condition:''' <math>i=n</math>.		'''Break condition:''' <math>n</math> iterations completed.

	==Induction basis==		==Induction basis==

Weihe: /* Induction step */

2015-04-29T13:27:06Z

Induction step

← Older revision		Revision as of 13:27, 29 April 2015
Line 30:		Line 30:
	# Afterwards:		# Afterwards:
	## If <math>S[i]=T[1]</math>, <math>i</math> is a new candidate and is thus appended at the tail of <math>I</math>.		## If <math>S[i]=T[1]</math>, <math>i</math> is a new candidate and is thus appended at the tail of <math>I</math>.
	## If <math>I\neq\emptyset</math> and ~~start index~~ <math>i-m+1</math> is the head element of <math>I</math>, this start index is removed from <math>I</math> and appended at the tail of <math>R</math>.		## If <math>I\neq\emptyset</math> and <math>i-m+1</math> is the head element of <math>I</math>, this start index is removed from <math>I</math> and appended at the tail of <math>R</math>.

	'''Implementation:''' Obvious.		'''Implementation:''' Obvious.

Weihe at 09:56, 29 April 2015

2015-04-29T09:56:47Z

← Older revision		Revision as of 09:56, 29 April 2015
Line 8:		Line 8:
	'''Type of algorithm:''' loop		'''Type of algorithm:''' loop

	'''Auxiliary data''' A [[Sets and sequences#Stacks and queues\|FIFO queue]] <math>I</math> of natural numbers~~, which always contains the start indexes of all occurrences of <math>T</math> in <math>S</math> that have been seen only partially thus far~~.		'''Auxiliary data''' A [[Sets and sequences#Stacks and queues\|FIFO queue]] <math>I</math> of natural numbers.

	'''Invariant:''' After <math>i\ge 0</math> iterations:		'''Invariant:''' After <math>i\ge 0</math> iterations:
	# In ascending order, <math>R</math> contains exactly the start indexes of all occurrences of <math>T</math> in <math>S</math> that lie completely in the substring <math>(S[1],...,S[i])</math> of <math>S</math>. In other words, <math>R</math> contains the start indexes in the range <math>S[1],...,S[i-m+1]~~</math>, where <math>m</math> is the length of <math>T~~</math>.		# In ascending order, <math>R</math> contains exactly the start indexes of all occurrences of <math>T</math> in <math>S</math> that lie completely in the substring <math>(S[1],...,S[i])</math> of <math>S</math>. In other words, <math>R</math> contains the start indexes in the range <math>S[1],...,S[i-m+1]</math>.
	# In ascending order, <math>I</math> contains exactly the start indexes of all occurrences of <math>T</math> in <math>S</math> that lie partially in the substring <math>(S[1],...,S[i])</math> of <math>S</math>. In other words, <math>I</math> contains the start indexes in the range <math>S[i-m+2],...,S[i]</math>.		# In ascending order, <math>I</math> contains exactly the start indexes of all "candidates," that is, all occurrences of <math>T</math> in <math>S</math> that lie partially in the substring <math>(S[1],...,S[i])</math> of <math>S</math>. In other words, <math>I</math> contains the start indexes in the range <math>S[i-m+2],...,S[i]</math>.

	'''Variant:''' <math>i</math> increases by <math>1</math>.		'''Variant:''' <math>i</math> increases by <math>1</math>.
Line 21:		Line 21:
	'''Abstract view:''' <math>R</math> and <math>I</math> have to be empty.		'''Abstract view:''' <math>R</math> and <math>I</math> have to be empty.

	'''Implementation:'''		'''Implementation:''' obvious.
	~~# <math>R:=\emptyset</math>~~
	~~# <math>I:=\emptyset</math>~~

	'''Proof:''' Nothing to show.		'''Proof:''' Nothing to show.
Line 29:		Line 27:
	==Induction step==		==Induction step==
	'''Abstract view:'''		'''Abstract view:'''
	# For each start index in <math>I</math>, we decide whether this is still a candidate ~~after we have seen~~ <math>S[i]</math>. If not, we remove this start index from <math>I</math>.		# For each start index <math>j</math> in <math>I</math>, we decide whether this is still a candidate, that is, whether <math>S[i]=T[i-j+1]</math>. If not, we remove this start index from <math>I</math>.
	# Afterwards:		# Afterwards:
	## If <math>S[i]=T[1]</math>, <math>i</math> is a new candidate and is thus appended at the tail of <math>I</math>.		## If <math>S[i]=T[1]</math>, <math>i</math> is a new candidate and is thus appended at the tail of <math>I</math>.
	## If start index <math>i-m+1</math> is at the head of <math>I</math>, this start index is removed from <math>I</math> and appended at the tail of <math>R</math>.		## If <math>I\neq\emptyset</math> and start index <math>i-m+1</math> is the head element of <math>I</math>, this start index is removed from <math>I</math> and appended at the tail of <math>R</math>.

	'''Implementation:''' Obvious.		'''Implementation:''' Obvious.
Line 40:		Line 38:
	# A start index <math>j</math> in <math>I</math> is to be dropped if, and only if, it turns out not to be a promising candidate anymore. As the induction hypothesis implies <math>(S[j],...,S[i-1])=(T[1],...,T[i-j])</math>, this is the case if, and only if, <math>S[i]\neq T[i-j+1]</math>.		# A start index <math>j</math> in <math>I</math> is to be dropped if, and only if, it turns out not to be a promising candidate anymore. As the induction hypothesis implies <math>(S[j],...,S[i-1])=(T[1],...,T[i-j])</math>, this is the case if, and only if, <math>S[i]\neq T[i-j+1]</math>.
	# Clearly, it would be incorrect to transfer any element of <math>I</math> except <math>i-m+1</math> to <math>R</math>. Thus, we are right to focus on <math>i-m+1</math> in Step 2.2. Now, <math>i-m+1</math> is in <math>I</math> if, and only if, (1) it was present immediately before the <math>i</math>-th iteration and (2) it has survived the first step of the <math>i</math>-th iteration. The induction hypothesis implies <math>(S[i-m+1],...,S[i-1])=(T[1],...,T[m-1])</math>, so it is correct to transfer <math>i-m+1</math> to <math>R</math> if, and only if, it is <math>S[i]=T[m]</math> as well.		# Clearly, it would be incorrect to transfer any element of <math>I</math> except <math>i-m+1</math> to <math>R</math>. Thus, we are right to focus on <math>i-m+1</math> in Step 2.2. Now, <math>i-m+1</math> is in <math>I</math> if, and only if, (1) it was present immediately before the <math>i</math>-th iteration and (2) it has survived the first step of the <math>i</math>-th iteration. The induction hypothesis implies <math>(S[i-m+1],...,S[i-1])=(T[1],...,T[m-1])</math>, so it is correct to transfer <math>i-m+1</math> to <math>R</math> if, and only if, it is <math>S[i]=T[m]</math> as well.
	# Clearly, it would also be incorrect to add any element to <math>I</math> except <math>i</math>. So we are right to focus on <math>i</math> in Step 2.1. ~~Obviously~~, all elements of <math>I</math> are less than <math>i</math>, so we are also right to append <math>i</math> at the tail of <math>I</math> in case <math>S[i]=T[1]</math>.		# Clearly, it would also be incorrect to add any element to <math>I</math> except <math>i</math>. So we are right to focus on <math>i</math> in Step 2.1.By induction hypothesis, all elements of <math>I</math> are less than <math>i</math>, so we are also right to append <math>i</math> at the tail of <math>I</math> in case <math>S[i]=T[1]</math>.

	==Complexity==		==Complexity==
	'''Statement:''' Let <math>r\in \mathbb{N}</math> denote the maximal number of candidates to be considered simultaneously. Then the worst-case run time is in <math>\mathcal{O}(n*r)</math>.		'''Statement:''' Let <math>r\in \mathbb{N}</math> denote the maximal number of candidates to be considered simultaneously. Then the worst-case run time is in <math>\mathcal{O}(n\cdot r)\subseteq\mathcal{O}(n\cdot m)</math>.

	'''Proof:''' Obviously, the first step of an iteration takes <math>\mathcal{O}(r)</math> time, and the other steps take constant time. The loop has <math>n</math> iterations.		'''Proof:''' Obviously, the first step of an iteration takes <math>\mathcal{O}(r)</math> time, and the other steps take constant time. The loop has <math>n</math> iterations. Of course, it is <math>r\leq m</math>.

	~~==Further information==~~

Weihe at 13:01, 10 November 2014

2014-11-10T13:01:35Z

← Older revision		Revision as of 13:01, 10 November 2014
Line 5:		Line 5:
	'''Algorithmic problem:''' [[One-dimensional string matching]]		'''Algorithmic problem:''' [[One-dimensional string matching]]

	~~'''Prerequisites:'''~~		==Abstract view==

	'''Type of algorithm:''' loop		'''Type of algorithm:''' loop

	'''Auxiliary data''' A [[FIFO queue]] <math>I</math> of natural numbers, which always contains the start indexes of all occurrences of <math>T</math> in <math>S</math> that have been seen only partially thus far.		'''Auxiliary data''' A [[Sets and sequences#Stacks and queues\|FIFO queue]] <math>I</math> of natural numbers, which always contains the start indexes of all occurrences of <math>T</math> in <math>S</math> that have been seen only partially thus far.

	~~==Abstract view==~~
	'''Invariant:''' After <math>i\ge 0</math> iterations:		'''Invariant:''' After <math>i\ge 0</math> iterations:
	# In ascending order, <math>R</math> contains exactly the start indexes of all occurrences of <math>T</math> in <math>S</math> that lie completely in the substring <math>(S[1],...,S[i])</math> of <math>S</math>. In other words, <math>R</math> contains the start indexes in the range <math>S[1],...,S[i-m+1]</math>, where <math>m</math> is the length of <math>T</math>.		# In ascending order, <math>R</math> contains exactly the start indexes of all occurrences of <math>T</math> in <math>S</math> that lie completely in the substring <math>(S[1],...,S[i])</math> of <math>S</math>. In other words, <math>R</math> contains the start indexes in the range <math>S[1],...,S[i-m+1]</math>, where <math>m</math> is the length of <math>T</math>.

Cuozzo at 10:31, 1 October 2014

2014-10-01T10:31:03Z

← Older revision		Revision as of 10:31, 1 October 2014
Line 1:		Line 1:
	__NOTOC__		__NOTOC__
			[[Category:Checkup]]
	[[Category:Algorithm]]		[[Category:Algorithm]]
	[[Category:Main Algorithm]]		[[Category:Main Algorithm]]

Cuozzo: /* Complexity */

2014-10-01T10:29:30Z

Complexity

← Older revision		Revision as of 10:29, 1 October 2014
Line 44:		Line 44:

	==Complexity==		==Complexity==
			'''Statement:''' Let <math>r\in \mathbb{N}</math> denote the maximal number of candidates to be considered simultaneously. Then the worst-case run time is in <math>\mathcal{O}(n*r)</math>.

			'''Proof:''' Obviously, the first step of an iteration takes <math>\mathcal{O}(r)</math> time, and the other steps take constant time. The loop has <math>n</math> iterations.

	==Further information==		==Further information==

Cuozzo: /* Induction step */

2014-10-01T10:24:36Z

Induction step

← Older revision		Revision as of 10:24, 1 October 2014
Line 29:		Line 29:

	==Induction step==		==Induction step==
			'''Abstract view:'''
			# For each start index in <math>I</math>, we decide whether this is still a candidate after we have seen <math>S[i]</math>. If not, we remove this start index from <math>I</math>.
			# Afterwards:
			## If <math>S[i]=T[1]</math>, <math>i</math> is a new candidate and is thus appended at the tail of <math>I</math>.
			## If start index <math>i-m+1</math> is at the head of <math>I</math>, this start index is removed from <math>I</math> and appended at the tail of <math>R</math>.

			'''Implementation:''' Obvious.

			'''Correctness:'''
			# Due to the second invariant, the induction hypothesis implies that all elements of <math>I</math> immediately before the <math>i</math>-th iteration must be from the set <math>\{i-m+1,...,i-1\}</math>. Therefore, if <math>i-m+1</math> is in <math>I</math>, it is the smallest element. Since the elements of <math>I</math> are in ascending order, <math>i-m+1</math> is then at the head of <math>I</math>.
			# A start index <math>j</math> in <math>I</math> is to be dropped if, and only if, it turns out not to be a promising candidate anymore. As the induction hypothesis implies <math>(S[j],...,S[i-1])=(T[1],...,T[i-j])</math>, this is the case if, and only if, <math>S[i]\neq T[i-j+1]</math>.
			# Clearly, it would be incorrect to transfer any element of <math>I</math> except <math>i-m+1</math> to <math>R</math>. Thus, we are right to focus on <math>i-m+1</math> in Step 2.2. Now, <math>i-m+1</math> is in <math>I</math> if, and only if, (1) it was present immediately before the <math>i</math>-th iteration and (2) it has survived the first step of the <math>i</math>-th iteration. The induction hypothesis implies <math>(S[i-m+1],...,S[i-1])=(T[1],...,T[m-1])</math>, so it is correct to transfer <math>i-m+1</math> to <math>R</math> if, and only if, it is <math>S[i]=T[m]</math> as well.
			# Clearly, it would also be incorrect to add any element to <math>I</math> except <math>i</math>. So we are right to focus on <math>i</math> in Step 2.1. Obviously, all elements of <math>I</math> are less than <math>i</math>, so we are also right to append <math>i</math> at the tail of <math>I</math> in case <math>S[i]=T[1]</math>.

	==Complexity==		==Complexity==

	==Further information==		==Further information==