Scribd
Upload
17 views12 pages

Pattern Matching Algorithms Overview

The document discusses various pattern matching algorithms, including Brute Force, Boyer Moore, and Knuth-Morris-Pratt (KMP), detailing their methodologies and applications. It explains the Brute Force algorithm as a simple yet inefficient method, while the Boyer Moore algorithm is highlighted for its efficiency in searching patterns in text. Additionally, the KMP algorithm is noted for its linear time complexity and the use of a prefix table to optimize character comparisons during mismatches.

Uploaded by

vanithatellakula
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
17 views12 pages

Pattern Matching Algorithms Overview

The document discusses various pattern matching algorithms, including Brute Force, Boyer Moore, and Knuth-Morris-Pratt (KMP), detailing their methodologies and applications. It explains the Brute Force algorithm as a simple yet inefficient method, while the Boyer Moore algorithm is highlighted for its efficiency in searching patterns in text. Additionally, the KMP algorithm is noted for its linear time complexity and the use of a prefix table to optimize character comparisons during mismatches.

Uploaded by

vanithatellakula
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

SWARNA BHARATHI INSTITUTE OF TECHNOLOGY & SCIENCE Data Structures

UNIT-V

Pattern Matching Algorithms:

Pattern matching algorithms are sometimes also referred as string searching algorithms. These
algorithms are useful in the case of searching a sub string within the main string.

There are different types of pattern matching algorithms they are

1. Brute Force Algorithm


2. Boyer Moore Algorithm
3. Knuth Morris Partt Algorithm

Brute force Algorithm

 This is the most basic and simplest type of algorithm. A Brute Force Algorithm is the
straightforward approach to a problem i.e., the first approach that comes to our mind on seeing the
problem. More technically it is just like iterating every possibility available to solve that problem.

 Brute force approach is an algorithm that acts as a word processor which searches a word present in
a text document.

 This process of searching is done by comparing the letters of the word consecutively until the end
of the location in the text is reached.

 This is the basic algorithm starting from the first letter of text and first letter of the pattern and
checks whether these two letters are equal.

 If it is equal then check second letters of the text and pattern.

 If it is not equal then move the pattern to the second letter of the text then check.

 In this way the pattern is checked till we find the match or till end of the text.

 This Brute force algorithm is also called as Naïve algorithm.

Algorithm:

Bruteforce_Algrithm(s,p):return int
{
Ls=length(s)
Lp=length(p)
Max=Ls-Lp+1

1 Department of Computer Science & Engineering


SWARNA BHARATHI INSTITUTE OF TECHNOLOGY & SCIENCE Data Structures

for(i=1;i<=max;i++)
{
Falg=True
for(j=1; j<=Lp && Flag==True; j++)
{
ifp[j]!=s[j+i-1]
Flag=False

}
if(Flag==True)
return i;
}
return(0)
}
Example:

Pattern is matched at index 11 to 16.

In this above example underlined characters represents mismatch letters against letters of the text.

Advantages:

Very simple technique and also that does not require any preprocessing. Therefore total running time is
same as its matching time.

2 Department of Computer Science & Engineering


SWARNA BHARATHI INSTITUTE OF TECHNOLOGY & SCIENCE Data Structures

Disadvantage:

Very inefficient method, because this method takes only one position movement in each time.

------0------

Boyer Moore Algorithm:

 Boyer Moore algorithm is an efficient string search algorithm that is the standard benchmark for
practical string searching.
 The algorithm preprocesses the string being searched for pattern but not the sting being searched in
text.
 It is well suited for the applications in which the pattern is much shorter than text.
 The Boyer Moore algorithm uses information gathered during the preprocess step to skip section of
the text.
 In general the algorithm runs faster as the pattern length increases.
 In this algorithm match would be performed from right to left. i.e to match on the tail of the pattern
rather than the head and to skip along the text in jumps of multiple characters rather than searching
every single character in the text. and to skip along the text in jumps of multiple characters rather
than searching every single character in the text.
 Boyer Moore algorithm takes a back word approach.

Algorithm:

BoyerMoore_Algorithm(s,p)
{
m=length(p)
n=length(s)
i=m-1
j=m-1
do
{
ifp[j]==s[i]
{
if(j==0)
return i;
else
{
i=i-1

3 Department of Computer Science & Engineering


SWARNA BHARATHI INSTITUTE OF TECHNOLOGY & SCIENCE Data Structures

j=j-1
}
}
else
{
i=i+max(1,length(p),index(p)-1;
j=m-1
}
}
while(i<=n-1);
return -1
}
Example:
String: THIS IS MY TEST
Pattern: TEST
Bad Match Table or Last Match Table:

T=> Last occurrence of T is at index 3

Max(1,length(p)-index(p)-1)

Max(1,4-3-1)

Max(1,1)=1

E=> Last occurrence of E is at index 1

Max(1,4-1-1)=2

S=> Last occurrence of S is at index 2

Max(1,4-2-1)=1

Searching will be done from right to left of the pattern

4 Department of Computer Science & Engineering


SWARNA BHARATHI INSTITUTE OF TECHNOLOGY & SCIENCE Data Structures

Mismatch at S, value of S in bad match table is 1 so move pattern by 1 position

Mismatch at space since space is not in bad match table move pattern by 4 positions

Mismatch at M since M is not in bad match table move pattern by 4 positions

Mismatch at E, value of E in bad match table is 2 so move pattern by 2 position

Match is found at index position 11.


------0------
Knuth-Morris-Pratt Algorithm

KMP Algorithm is one of the most popular patterns matching algorithms. KMP stands for Knuth
Morris Pratt. KMP algorithm was invented by Donald Knuth and Vaughan Pratt together and
independently by James H Morris in the year 1970. In the year 1977, all the three jointly published KMP
Algorithm.

KMP algorithm was the first linear time complexity algorithm for string matching.

KMP algorithm is one of the string matching algorithms used to find a Pattern in a Text.

5 Department of Computer Science & Engineering


SWARNA BHARATHI INSTITUTE OF TECHNOLOGY & SCIENCE Data Structures

KMP algorithm is used to find a "Pattern" in a "Text". This algorithm campares character by character from
left to right. But whenever a mismatch occurs, it uses a preprocessed table called "Prefix Table" to skip
characters comparison while matching. Sometimes prefix table is also known as LPS Table. Here LPS
stands for "Longest proper Prefix which is also Suffix".

Steps for Creating LPS Table (Prefix Table)

Step 1 - Define a one dimensional array with the size equal to the length of the Pattern. (LPS[size])

Step 2 - Define variables i & j. Set i = 0, j = 1 and LPS[0] = 0.

Step 3 - Compare the characters at Pattern[i] and Pattern[j].

Step 4 - If both are matched then set LPS[j] = i+1 and increment both i & j values by one. Goto to Step 3.

Step 5 - If both are not matched then check the value of variable 'i'. If it is '0' then set LPS[j] = 0 and
increment 'j' value by one, if it is not '0' then set i = LPS[i-1]. Goto Step 3.

Step 6- Repeat above steps until all the values of LPS[] are filled.

Let us use above steps to create prefix table for a pattern...

6 Department of Computer Science & Engineering


SWARNA BHARATHI INSTITUTE OF TECHNOLOGY & SCIENCE Data Structures

7 Department of Computer Science & Engineering


SWARNA BHARATHI INSTITUTE OF TECHNOLOGY & SCIENCE Data Structures

How to use LPS Table

We use the LPS table to decide how many characters are to be skipped for comparison when a
mismatch has occurred.

When a mismatch occurs, check the LPS value of the previous character of the mismatched
character in the pattern. If it is '0' then start comparing the first character of the pattern with the next
character to the mismatched character in the text. If it is not '0' then start comparing the character which is
at an index value equal to the LPS value of the previous character to the mismatched character in pattern
with the mismatched character in the Text.

How the KMP Algorithm Works

Let us see a working example of KMP Algorithm to find a Pattern in a Text...

8 Department of Computer Science & Engineering


SWARNA BHARATHI INSTITUTE OF TECHNOLOGY & SCIENCE Data Structures

------0------

9 Department of Computer Science & Engineering


SWARNA BHARATHI INSTITUTE OF TECHNOLOGY & SCIENCE Data Structures

Tries:

1. In computer science, a tries is also called digital tree and sometimes radix tree or prefix tree.

2. Tries is a tree based data structure for storing strings in order to support fast pattern matching.

3. Tries are used for information retrieval.

4. Tries is used to store the character in each node not the key.

5. Path from root to node is associated with key.

6. Tries uses character of a key to guide the search process.

7. All the descendants of the node have a common prefix of the string associated with that node.

Types:

1. Standard Tries

2. Compressed Tries

3. Suffix Tries

1. Standard Tries:

 It is an ordered tree like data structure.


 Each node (except the root node) in a standard trie is labeled with a character.
 The children of a node are in alphabetical order.
 Each node or branch represents a possible character of keys or words.
 Each node or branch may have multiple branches.
 The last node of every key or word is used to mark the end of word or node.
 Example: Standard tries for the set of strings S ={ bear, bell, bid, bull, buy, sell, stock, stop}

10 Department of Computer Science & Engineering


SWARNA BHARATHI INSTITUTE OF TECHNOLOGY & SCIENCE Data Structures

2. Compressed Tries:

 A Compressed Trie is an advanced version of the standard trie.


 Each nodes(except the leaf nodes) have at least 2 children.
 It is used to achieve space optimization.
 To derive a Compressed Trie from a Standard Trie, compression of chains of redundant nodes is
performed.
 It consists of grouping, re-grouping and un-grouping of keys of characters.
 While performing the insertion operation, it may be required to un-group the already grouped
characters.
 While performing the deletion operation, it may be required to re-group the already grouped
characters.

3. Suffix Tries:

 A Suffix Trie is an advanced version of the compressed trie.


 The most common application of suffix trie is Pattern Matching.
 While performing the insertion operation, both the word and its suffixes are stored.
 A suffix trie is also used in word matching and prefix matching.
 To generate a suffix trie, all the suffixes of given string are considered as individual words.
 Using the suffixes, compressed trie is built.
Ex:

Suffixes of MINIMIZE are {E, ZE, IZE, MIZE, IMIZE, NIMIZE, INIMIZE, MINIMIZE}

Constructing Compressed trie using all suffixes

11 Department of Computer Science & Engineering


SWARNA BHARATHI INSTITUTE OF TECHNOLOGY & SCIENCE Data Structures

------0------

12 Department of Computer Science & Engineering

Common questions

Powered by AI

The Brute Force Algorithm is inefficient for large datasets due to its O(m*n) time complexity, as it repeatedly checks each position even after mismatches. In contrast, the KMP Algorithm has a linear O(n+m) time complexity, using the LPS table to skip unnecessary comparisons and avoid rechecking characters. Therefore, while Brute Force might be simpler to implement, KMP offers significant efficiency improvements in larger datasets where reduced repetition and rapid mismatch handling are crucial .

A Suffix Trie is more beneficial in scenarios involving extensive pattern matching or substring searches, as it allows for efficient searching of all suffixes of a string. It is constructed by treating each suffix of the string as an individual word and then building a Compressed Trie using these suffixes, which accelerates pattern and prefix matching .

The Brute Force Algorithm operates by sequentially comparing each character of the pattern with the characters in the text until a match is found or the text is fully traversed. This approach is simple and does not require preprocessing, which is its primary advantage. However, its major disadvantage is inefficiency, as it moves one position at a time, which can be time-consuming for large texts .

The Boyer Moore Algorithm preprocesses the pattern using a Bad Match Table to determine the optimal number of positions to skip when mismatches occur. This preprocessing allows for faster searching because the algorithm can take larger jumps in the text rather than checking each character sequentially. This is more efficient compared to the Brute Force Algorithm, which lacks such preprocessing and thus only advances one position at a time .

Compressed Tries improve space optimization by ensuring nodes (except leaves) have at least two children, compared to Standard Tries where nodes might have only one child. This is achieved by compressing chains of single-child nodes into single nodes, reducing redundancy and saving space .

The KMP Algorithm uses the LPS (Longest Prefix Suffix) table to skip unnecessary comparisons after a mismatch. The LPS table helps avoid re-checking characters of the pattern that match before the mismatch occurred by indicating the next position to resume matching based on the longest border at the mismatch, significantly reducing the number of comparisons compared to a straightforward approach like Brute Force .

The LPS table in the KMP Algorithm is significant because it keeps track of the longest prefix that is also a suffix, allowing the algorithm to avoid unnecessary comparisons by jumping directly to positions that have the potential to match when a mismatch occurs. This results in an overall linear time complexity, as opposed to a quadratic time complexity that might arise without such optimization .

The 'bad character rule' in the Boyer Moore Algorithm uses the last occurrence of a mismatched character within the pattern to decide how many positions the pattern can be safely shifted. By potentially skipping over sections of the text that can't match the pattern, this rule significantly increases the algorithm's efficiency compared to methods that don't preprocess mismatch information .

A Standard Trie is constructed as an ordered tree where each node (except the root) represents a character, and its children represent possible subsequent characters. Nodes are structured in alphabetical order. It is mainly used for efficient information retrieval by storing strings to support fast pattern matching, making searches for words or prefixes efficient .

Compressed tries can theoretically be transformed back into standard tries by decomposing newly grouped nodes into their individual component nodes. Such transformations would increase space usage but make operations like insertion more straightforward, as breaking down grouped nodes could lead to an increase in the number of nodes traversed, complicating deletion or re-grouping due to increased redundancy .

You might also like