IUP Publications Online
Home About IUP Magazines Journals Books Archives
     
Recommend    |    Subscriber Services    |    Feedback    |     Subscribe Online
 
The IUP Journal of Information Technology
A Comparative Analysis of Pattern Matching Algorithm Using Bit-Parallelism Technique
:
:
:
:
:
:
:
:
:
 
 
 
 
 
 
 

Pattern matching can be done with the help of bit-parallelism and character-based techniques. Bit-parallelism-based algorithms are currently the fastest and more efficient than other character-based for both exact and inexact pattern matching. This is due to the use of intrinsic parallelism of the bit operation inside a computer word which allows you to cut down the number of operations that algorithm performs by a factor up to w, where w is the number of bits in the computer word. The paper presents a comparative analysis of well-known bit-parallel matching algorithms such as Shift-Or, Shift-And, Backward Non-Deterministic Matching (BNDM) and two variants of BNDM algorithm. The resulting experimental shift mechanism of BNDM, SBNDM and FSBNDM using bit-parallelism technique is also discussed.

 
 

Pattern matching can be defined as finding the occurrences of a particular pattern of characters in a large text or sequence. Its application covers a wide range of digital libraries, web search engines, screen scrapers, word processors, natural language processing, computational molecular biology and so on (Raju and Somayajulu, 2011). Pattern matching can be classified into two categories: exact and inexact pattern matching algorithms (Nimisha and Deepak, 2012). Exact pattern matching means finding one or more exact occurrences of a string in a sequence, while inexact pattern matching algorithm is sometimes referred to as approximate pattern matching or matches with k mismatching/differences (Raju and Somayajulu, 2011). Examples of exact pattern matching algorithm are Boyer Moore, Horspool, Sunday Rita and Knuth-Morris-Pratt algorithms. Examples of inexact pattern matching algorithms are dynamic programming approach, automata approach, bit-parallelism approach, etc.

Pattern matching can be done through character-based and bit-parallelism techniques. Bit-parallelism is one of the most important techniques in the field of computer science (Faro and Lecroq, 2013). In the recent years, bit-parallelism plays an important role in pattern matching due to the length of pattern size that can be processed in parallel (Gulfishan and Nilay, 2014). Bit-parallelism is done by creating bit vectors of the pattern of characters, and then the matching is done with the help of bit operations in parallel. Experimental studies however, show that bit-parallelism performs better as compared to other character-based or non-bit parallel algorithms, but it imposes a limitation on the pattern size (Alina, 2006). Some of the well-known algorithms that use bit-parallelism technique to find the position of pattern in a large text/sequence are Shift-And, Shift-Or, Shift-Add and Backward Non-Deterministic Matching (BNDM) algorithms (Navarro and Raffinot, 2000).

 
 

Information Technology Journal, Bit-parallelism, Computer word, Exact, Shift-Or, Shift-And, Backward Non-Deterministic Matching (BNDM)