A fast string search algorithm for computer networking

Author

Rafiq, A. N M Ehtesham ; El-Kharashi, M. Watheq ; Gebali, Fayez

Author_Institution

Dept. of Electr. & Comput. Eng., Victoria Univ., BC, Canada

Volume

2

fYear

2003

fDate

28-30 Aug. 2003

Firstpage

764

Abstract

Computer networking requires a fast string search algorithm for fast data manipulation. This algorithm must perform better in long text, long pattern, and large alphabet set. Boyer-Moore algorithm is one of the most suitable string search algorithms to meet these criteria. But, its implementation complexity is very high. We have simplified the Boyer-Moore algorithm, reduced memory requirement, and made it faster. Time complexity analysis was performed and then verified by numerical simulations. Simulation results also prove our algorithm´s superior performance in the networking environment.

Keywords

computational complexity; computer networks; string matching; Boyer-Moore algorithm; computer networking; data manipulation; memory requirement; numerical simulation; string search algorithm; time complexity analysis; Algorithm design and analysis; Analytical models; Application software; Application specific integrated circuits; Computational modeling; Computer networks; Computer security; Electronic mail; Performance analysis; Routing;

fLanguage

English

Publisher

ieee

Conference_Titel

Communications, Computers and signal Processing, 2003. PACRIM. 2003 IEEE Pacific Rim Conference on

Print_ISBN

0-7803-7978-0

Type

conf

DOI

10.1109/PACRIM.2003.1235893

Filename

1235893