What is the best algorithm available till date for pattern matching?
Answers
Answered by
1
Usually a general pattern matching program may not be the most efficient one in terms of time consumed. Also on the memory space used. With some assumptions on the type of patterns and specific to applications in a particular field, optimizations can be made. Then one can have best algorithms related to a specific application/subject. So there is no overall-best algorithm in all situations and in all subjects or applications.
The Boyer-Moore-Horspool algorithm for string pattern matching is supposed to be very efficient. That is for natural languages. There is a BMH-2 algorithm too.
There are hybrid pattern matching algorithms that combine the best features of two or more of the good algorithms available today. Like:
K-M-P (Knuth-Morris_Pratt) algorithm
B-M-H- (Boyer-Moore_Horspool) algorithm
B-M-S- Boyer-Moore-Sunday algorithm
R-C - Reverse-Colussi algorithm
Turbo-BM - Turbo-Boyer-Moore algorithm
KMP gives the time complexity = O(length of the string).
There is a hybrid algorithm taking K-M-P and B-M-P algorithm. It is called FJS algorithm by Franek and jennings. It is faster in many cases and competitive to the above.
There is a RS algorithm (2012) for biological pattern sequences by Senapati, Sandeep and Sahoo. This works good in biology field.
There is a MEPSM (Multiple Exact Packed String Matching algorithm) by Faro & Kulekci of Italy. This is fast for the biological data including DNA sequences (field of computational biology). This uses SSE technology of Intel ie., Streaming SIMD (Single Instruction Multiple Data) technology of Intel processors to make pattern searches faster.
There is Aho-Corasick algorithm which works very efficiently for repetitive searches of the same patterns in a database.
The Boyer-Moore-Horspool algorithm for string pattern matching is supposed to be very efficient. That is for natural languages. There is a BMH-2 algorithm too.
There are hybrid pattern matching algorithms that combine the best features of two or more of the good algorithms available today. Like:
K-M-P (Knuth-Morris_Pratt) algorithm
B-M-H- (Boyer-Moore_Horspool) algorithm
B-M-S- Boyer-Moore-Sunday algorithm
R-C - Reverse-Colussi algorithm
Turbo-BM - Turbo-Boyer-Moore algorithm
KMP gives the time complexity = O(length of the string).
There is a hybrid algorithm taking K-M-P and B-M-P algorithm. It is called FJS algorithm by Franek and jennings. It is faster in many cases and competitive to the above.
There is a RS algorithm (2012) for biological pattern sequences by Senapati, Sandeep and Sahoo. This works good in biology field.
There is a MEPSM (Multiple Exact Packed String Matching algorithm) by Faro & Kulekci of Italy. This is fast for the biological data including DNA sequences (field of computational biology). This uses SSE technology of Intel ie., Streaming SIMD (Single Instruction Multiple Data) technology of Intel processors to make pattern searches faster.
There is Aho-Corasick algorithm which works very efficiently for repetitive searches of the same patterns in a database.
Similar questions