Premium
The effect of multiple reference characters on detecting matches in string‐searching algorithms
Author(s) -
Mhashi Mahmoud Moh'd
Publication year - 2005
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.672
Subject(s) - algorithm , string (physics) , string searching algorithm , matching (statistics) , position (finance) , computer science , mathematics , pattern matching , artificial intelligence , statistics , finance , economics , mathematical physics
The effect of multiple reference characters and the condition types on the performance of exact string‐searching algorithms is tested. In order to perform such a test a new algorithm called the Multiple Reference Characters Algorithm (MRCA) is developed. An experiment is performed using English text; the results are compared with the known string‐matching algorithms called Boyer–Moore–Horspool (BMH) and Straight Forward (Naïve). With the MRCA algorithm, the shift distance is increased up to 3 m + 1 positions in comparison with exactly one position in the Naïve algorithm and up to m positions in BMH. Furthermore, by using the new algorithm MRCA, the results suggest that the evaluation criteria of the average number of comparisons, the average number of shifts, and the clock time required by BMH are improved up to 73.1%, 64.7%, and 49.6%, respectively. The same evaluation criteria required by Naïve are improved by MRCA up to 98.1%, 98%, and 94.7%, respectively. Copyright © 2005 John Wiley & Sons, Ltd.