Terminology
What is String Matching?
Exact String Matching Algorithms
Brute Force or Naive String Matching Algorithm
Knuth Morris Pratt String Matching Algorithm
Rabin- Karp String Matching Algorithm
What is approximate String Matching?
Hamming and Edit Distance
What are the applications of String Matching Algorithms?
Intrusion Detection
Spam Filters
Spell Checkers
Plagiarism Detection
Information Retrieval
Content Searching in large databases or search engines
Bioinformatics
String: A String is an ordered sequence of characters. The number of characters in a string is called its length and is denoted by |S|, where S is a string. If we want to refer a character of the string at position i, we use S[i] or Si.
Substring: It is a sequence of consecutive contiguous elements of the string, denoted by S [i….j], where i and j denote the starting and ending positions of the substring.
Prefix: It is a substring starting at position 1.
Suffix: It is a substring ending at position |S|.
For example, consider a string S= “aaabbcc”.
Then |S|= 7
S [2] =a
Substring sub [2, 5] =”aabbc”
Prefix sp [1, 2] =”aa”
Suffix ss [5, 7] =”bcc”
String Matching means finding the occurrences of a pattern (or a substring) in a given string. A string matching algorithm is an algorithm that performs string matching on a particular text (or string). An exact string matching algorithm finds the number of occurrences whenever there is an exact match of pattern P in text T. An approximate string matching algorithm finds the number of occurrences whenever P matches most of the text T.
Assumptions:
String T (called the Text) is an array T [1…n] of length n.
String P (called the Pattern) is an array p [1…m] of length m < = n.
We take the starting positions of P and T as 1.
The elements of P and T are drawn from a finite alphabet ∑. For example, ∑ = {0, 1}, ∑ = {a, b, c, d, …,z}.
P occurs with shift s in T i.e. P occurs at position s+1 in T if 0<= s < = n-m and T [s+1…s + m] = P [1…m].
s is a valid shift if P occurs with shift s in T, otherwise, we call s an invalid shift.
For Example, given a text and pattern as:
Text T: a a b b d c d e f b
Pattern P: b d c
We see that P occurs in T with shift s=3. Hence, s=3 is a valid shift.
This algorithm compares every character of pattern P with equal number of characters from text T, for all possible shifts. Consider a text T [1….n] and pattern P [1….m] over an alphabet ∑.
Initially P is aligned with T at first index position.
A match between the first characters of pattern and text is done.
If they match, we move to the next character of pattern and compare it with next character of the text.
If they do not match, we only move to the next character of text and compare it with the current character of pattern. If they do not match, we move forward until the text ends or we get a match.
Algorithm:
NaiveStringMatching(T,P)
n=|T|
m=|P|
//loop for each possible shift
for s=0 to n-m
//to check whether the current shift is valid or not
//it involves an explicit loop to check if every corresponding character of T and P matches
do if P[1…m]= T[s+1…..s+m]
Running time:
There can be (n-m+1) possible shifts. So the loop at step 3 executes for about (n+m-1) times. For each shift, we have to compare m characters. So the explicit loop at step executes m times. Hence, this algorithm takes time O((n-m+1)m), in the worst case.
Example: Consider the given text T: acaabc and pattern P: aab. A vertical line indicates that a match is found and a jagged line indicates a miss match. Here s = 2 is the only valid shift as the pattern exactly matches the part of the text in this shift.
Implementation in C++:
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
void NaiveStringMatching(char *P, char *T)
{
int M = strlen(P);
int N = strlen(T);
/* for every possible shift */
for (int s= 0; s <= N - M; s++)
{
int j;
/* For current shift s, check for pattern match */
for (j = 0; j < M; j++)
{
if (T[s + j] != P[j])
break;
}
if (j == M) // if P[0...M-1] = T[s, s+1, ...s+M-1]
cout<<"\nPattern occurs at shift : "<<s+1;
}
}
/* Driver program to test above function */
int main()
char *T = "AABAACAADAABCDDAAABAA";
char *P = "AABA";
cout<<"TEXT : "<<T;
cout<<"\nPATTERN : "<<P;
NaiveStringMatching(P, T);
return 0;
The output of the above program will be:
TEXT: AABAACAADAABCDDAAABAA
PATTERN: AABA
Pattern occurs at shift: 1
Pattern occurs at shift: 17
The Naive approach of string matching can be useful when the length of the text is small. But when the text is large enough and the pattern is very small as compared to the text, it becomes difficult to check every possible shift. Moreover, it will take much time to match every character of text with the pattern. The KMP string matching or Knuth-Morris-Pratt algorithm reduces this number of comparisons to be made between the text and the pattern by shifting the pattern more than one position each time.
Suppose we are given a text T and a pattern P. We check if P occurs at position ‘x’ in T. Say, P matches k characters with T [x…..], but a mismatch occurs at position k+1, i.e.
P [1….k] = T[x…..x+k] but P[k] ≠ T[x+k+1],
then we can say that, for any r such that, 0<r<k, if T [x+r…..x+k] is not a prefix of P, P cannot occur at position x+r. Hence, we can skip these positions in T and start matching P and T after skipping these positions. To find the next position of the match we define a prefix function (π). The prefix function creates a prefix table that contains the information about skipping a particular number of comparisons.
Algorithm for Prefix Function:
PrefixFunction(P)
m = |P|
π[1] = 0
for q = 2 to m
while k>0 and P[k+1] ≠ P[q]
k = π(k)
if P[k+1] = P[q]
k = k+1
Algorithm for KMP matcher function:
KMPStringMatching(T,P)
n =|T|
// q: number of characters matched
q=0
π=PrefixFunction(P)
for i = 1 to n
do while q>0 and P[q+1]≠ T[i]
// if next character does not match
do q=π(q)
if P[q+1]= T[i]
//if next character matches
then q= q+1
// if all of P is matched
if q=m
then print “Pattern found”
// look for next match of P in T
q=π(q)
Running Time:
The PrefixFunction() takes O(m) time since the loop from step 3 to step 8 runs up to the length of the pattern i.e. m. The KMPStringMtching() function takes O(n) time since the loop from step 5 to step 12 runs up to the length of the text i.e. n. Hence, the running time for the algorithm is O(n+m).
Example:
P= a b a b a c a
T= a b a b a b a b a c a b
|P|= 7 and |T|=12
Computing prefix table for P:
q=0, k = 0 so, π(2) = 0
P
a
b
c
Q
1
2
3
4
5
6
7
Π(q)
0
q = 3, k = 0 so, π(3) =1
A
q = 4, k = 1 so, π(4) = 2
q = 5, k = 2 so, π(5) = 3
q = 6, k = 3 so, π(6) =1
q = 7, k = 1 so, π(7) = 1
8
9
10
11
12
T
Step 1: i=1, q=0 Step 2: i=2, q=1
T[1]=P[1] so, q=1 T[2]=P[2] so, q=2
Step 3: i=3, q=2 Step 4: i=4, q=3
T[3]=P[3] so, q=3 T[4]=P[4] so, q=4
Step 5: i=5, q=4 Step 6: i=6, q=5
T[5]=P[5] so, q=5 T[6]≠P[6] so, q=3
Now, T[6]=P[3] so, q=4
Step 7: i=7, q=4 Step 8: i=8, q=5
T[7]=P[5] so, q=5 T[8]≠P[6] so, q=3
Now, T[8]=P[3] so, q=4
Step 9: i=9, q=4 Step 10: i=10, q=5
T[9]=P[5] so, q=5 T[10]=P[6] so, q=6
Step 11: i=11, q=6
T[11]=P[7] so, q=7
Now, q = m = 7 so, Pattern matched
Consider a text T [1….n] and pattern P [1….m] over an alphabet ∑. We assume that each character is a digit in radix-d notation, where d=|∑|.For example, if ∑={0,1,2,3,…,9} then each character is a decimal digit, radix 10 notation. Hence, a string can be represented in dual notation, i.e., string S= 2345 will be written as decimal S’=2345. Let p be the decimal value of P and ts be the decimal value of T[s+1, s+2,….,s+m] for s=0,1,2,3….,n-m. ts =p if and only if T[s+1, s+2,….,s+m]= P[1….m].
This algorithm involves two stages:
Preprocessing Stage: hash values of P and m character subsequence of text T is calculated in this stage.
Matching Stage: characters of pattern P and text T are compared in this stage.
First, we calculate a hash value for the pattern P and for each m-character sub sequence of the text T.
If the hash values are equal then we compare the pattern and the sub sequence of the text character by character.
If the hash values are unequal then we calculate a new hash value for next m-character sub sequence of text T.
Now a string S of length m can be represented as a number N, in a positional number system with base ‘d’ as:
N= S[0]*d(m-1) + S[1]*d(m-2)+….+ S[m-1]d0
So, p can be calculated in a same way as:
p = P[1]*d(m-1) + P[2]*d(m-2)+….+ P[m]d0
Also, t0 for s=0 can be calculated as:
t0 for T[1…m] = T[1]*d(m-1) + T[2]*d(m-2)+….+ T[m]d0
t1 for T[2…m+1]= T[1]*d(m-1) + T[2]*d(m-2)+….+ T[m+1]d0
Hence, ts+1 = (ts=T[s+1] d(m-1))d+T[s+m+1]
If m and d are big enough, it will result into large values of p and ts. Hence, we use a prime number q and divide p and ts by it. So,
ts+1 = (ts=T[s+1] h)d+T[s+m+1] mod q where h = d(m-1) mod q.
We now compare the values of p mod q and ts. If they are unequal, it clearly means that ts ≠ p (also called as unsuccessful hit). But if they are equal, it may lead to the conclusion that ts = p (spurious hit or a successful hit).
RabinKarpStringMatching(T,P,d,q)
n = |T|
h = d(m-1) mod q
p = 0
t0 = 0
// preprocessing
for i = 1 to m
do p = (dp+ P[i]) mod q
t0 = (dt0+T[i]) mod q
//matching all possible shifts with p
for s = 0 to n-m
do if p = ts
//an implicit loop is required to match every character of P and T
then if P[1…m]=T[s+1….s+m]
then print “pattern occurs at shift” s
if s< n-m
then ts+1 = (ts=T[s+1] h)d+T[s+m+1] mod q
The for loop at step 6 takes O(m) processing time. The for loop at step 9 takes O((n-m+1)m) processing time just like naïve string matching algorithm as it compares the text and pattern character by character. But here the valid shifts are assumed to be very few for a text as compared to (n+m-1) valid shifts. So the running time is expected to be O(n+m) plus the time taken to process spurious shifts. Now we expect that the number of spurious hits is O(n/q). The running time thus becomes O(n) + O(m(v+n/q)) where v is the number of valid shifts. If the number of valid shifts is very small and q is very large as compared to m then the running time becomes O(n+m).
For example: Consider the following text T of length 19. We need to find a pattern P= 31415 in the text. So, we will calculate P modulo 13 to get p and compare it with every 5 character sub sequence of text modulo 13. The cases where these values are equal are the possible cases where the pattern P can be found. So we will perform a character by character check for only those cases.
Approximate String Matching or fuzzy string searching is a variant of exact string matching algorithm. In this method, we find out the number of occurrences of patter P where it matches most of the text T. To make P match a sub sequence of T exactly, we need to do some changes in text T. These changes can be the following:
Substitution: We substitute character(s) in T to make it equal to P.
Insertion: We insert character(s) in T to make it equal to P.
Deletion: We delete character(s) in T to make it equal to P.
For example:
1. T: a a b b c c d d e f g h
P: a a c b c c
Substitute b by c in T to make it equal to P.
2. T: a a b b c c d d _ e d c
P: d a e d c
Insert a in T to make it equal to P.
3. T: a a a b b c f g s _
P: b f g s v
Delete c from T and insert v in T to make it equal to P.
Hamming Distance: is the maximum number of single-character substitutions required to make a sub sequence of T to match P. The hamming distance in above example for (i) will be 1.
Edit Distance: It is the maximum number of edits (insertions and deletions) required to make a sub sequence of T to match P. The edit distance in above example for (iii) will be 2.
String matching algorithms are used in the following areas:
Intrusion Detection is a technique used for computers and networks to identify possible security breaches and misuse. It uses string matching algorithms to recognize patterns of attacks. Malicious codes are stored in the database and all the incoming packets in a network are compared with them. If a match is found, it means that the packet is malicious. If no match is found, the packets are accepted.
Spam Filters are used to separate spam or unsolicited commercial emails or unsolicited bulk emails in our mailbox. These spam filters use string matching algorithms to identify signature patterns in the email content. As shown in the figure, suspected spam keywords are stored in the database. A test mail is sent to the spam detection module that uses string matching algorithms to match the content of the mail with the keywords. If a match occurs, the mail is suspected to be a spam.
A Spell Checker is used to find the words in a document that may not be spelled correctly. These spell checkers contain pre defined patterns or words. These words are matched with the words of the document to find a misspelled word. They use finite automata to match the predefined pattern set with the text. They are able to suggest the correct word due to this predefined pattern set.
Plagiarism Detectors are used to find plagiarism within a document. They use string matching algorithms to compare two or more documents and find similarities between them. As shown in the figure, if you need to compare two documents, each document is decomposed into string tokens. A string matching algorithm then matches those tokens and finds the similarities between those documents.
In data mining, large pieces of text are analyzed. This analysis is used to retrieve unknown information. String matching algorithms help in finding similar text, topics and information that will help in analyzing the text. As shown in the figure, in order to retrieve information from an information data base, a query is generated. The query is decomposed into tokens. These tokens are compared to the information in the database by a string matching module. The information is retrieved based on the result of the comparison.
We know that there is huge amount of data present over the internet. But this data is uncategorized. Hence, it becomes difficult to search a specific content from this data. So, the large databases and search engines use string matching algorithms to categorize the data. Some predefined keywords are used to categorize the data, as shown in the figure.
Bioinformatics is the study of large amounts of biological information like DNA molecules. Bioinformatics uses computer science to study the molecules. It uses string matching algorithms to find DNA patterns. As shown in the figure, the DNA analyzer and string matching modules work together to find the desired results over a DNA data.
Watch this Video for more reference
More Readings
Exact String Matching
Attach Files