Paper Info
Title
A multipattern matching algorithm using sampling and bit index
Abstract
Pattern matching is one of the basic problems in computer science. In this paper we propose a new multiple pattern matching algorithm. Unlike the well known Knuth-Morris-Pratt, Boyer-Moore, Karp-Rabin and their variants, our algorithm is derived from the ideas of sampling and bit index, sampling for efficiency and bit index for flexibility, as a result providing the simplest way to search for multiple patterns. Theoretical analysis and experimental results show that our algorithm is average-optimal with average complexity of O(n/m) for the search of patterns of length m in a text of length n. It provides a proper solution to such needs as matching long dispersed patterns and especially bit pattern matching (newly introduced in this paper) in data analysis of some private protocols' communication.
Year
DOI
Venue
2008
10.1109/AICCSA.2008.4493509
AICCSA
Keywords
Field
DocType
knuth-morris-pratt,multiple pattern,length n,new multiple pattern,data analysis,theoretical analysis,pattern matching,length m,multipattern matching,average complexity,karp-rabin,multipattern matching algorithm,bit index,boyer-moore,bit pattern matching,boyer moore,indexation
String searching algorithm,Computer science,Algorithm,Theoretical computer science,Sampling (statistics),3-dimensional matching,Pattern matching,Boyer–Moore string search algorithm,Blossom algorithm
Conference
ISSN
ISBN
Citations 
2161-5322
978-1-4244-1968-5
0
PageRank 
References 
Authors
0.34
10
3
Name
Order
Citations
PageRank
J. Chen111223.18
Zhongfu Ye237949.33
Min Tang300.34