Fast hybrid string matching algorithm using message passing programming model
Loading...
Date
2009-06
Authors
Abdul Rozaq, Atheer A.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
String matching is an operation that chec:ks the optimal alignment by comparisons
between the characters in pattern and text. It has become highly important in the last
two decades due to the advancement in technology. It has also become necessary to
solve string matching problem because of its application in many fields. The
consumed time, number of attempts and number of characters comparison are
considered as problems during matching process. It is advisable to use an efficient
and faster algorithm to complete the matching with higher speed and lowest cost.
The aim ofthis study is to take advantage of Two way, Karp-Rabin andQuick search
algorithms by formulating fast hybrid string matching algorithm that depends on the
good properties at each of the algorithm mentioned above and to evaluate the hybrid
algorithm in sequential and parallel phases. An experiment was conducted using C++
language and was applied on Aurora Cluster at the School of Computer Science in
USM. Also, the methodology included the use of different types of standard
databases with different pattern lengths and different number of processors during
parallelization. The performance of the sequential algorithm is improved compared
to the original algorithms. The hybrid algorithm showed less number of attempts,
less number of characters comparison and consumed less time than original
algorithms. The hybrid algorithm gives optimal results and performance during
parallelization. It produced higher speedup, efficiency and percentage of
performance gain when compared with the sequential. The performance in both
parallel and sequential hybrid algorithm was influenced by the type of data. The
Source code and English texts showed higher performance in sequential while DNA
sequence showed a higher performance in parallel.
Description
Keywords
String matching algorithm , Passing programming model