Research on an Single Pattern Matching Algorithm

Qiang Zheng

doi:10.4028/www.scientific.net/AMR.433-440.4468

Paper Titles

Parallel Algorithm for Transient Stability Online Simulation
p.4446

Development of Calculation Software of Steady State Parameters for HVDC Transmission
p.4452

An Efficient Frequent Patterns Mining Algorithm over Data Streams Based on FPD-Graph
p.4457

Design and Implementation of CRM Based on Data Mining
p.4463

Research on an Single Pattern Matching Algorithm
p.4468

A Fast Algorithm for Vector ARMA Parameter Estimation
p.4475

A Contrast Experiment Based on the Modification Theory of Toroidal Worm
p.4482

A Real-Time Experimental Method for Room Cooling Load Calculations
p.4490

Hybrid Behavior Ant Colony Algorithm
p.4496

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 433-440Research on an Single Pattern Matching Algorithm

Research on an Single Pattern Matching Algorithm

Abstract:

The design of exact single pattern string matching algorithm with high performance is the basis of all string matching problems. To overcome the defects of low efficiency of pattern matching, this paper improves one of the fastest exact single pattern matching algorithms known on English text, which is SBNDM2。The simplest form of the BNDM core loop is obtained, in which there are only 5 instructions per-character read by amending the relationship between position in the pattern and bit in the bit mask. And a cross-border protection method is added to the algorithm in order to reduce the cost of cross-border inspection. Two algorithms named S2BNDM and S2BNDM′ are presented. The experimental results indicate that both S2BNDM and S2BNDM′are faster than SBNDM2 in any case.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 433-440)

Pages:

4468-4474

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.433-440.4468

Citation:

Cite this paper

Online since:

January 2012

Authors:

Qiang Zheng

Keywords:

BNDM Algorithm, Single Pattern Exact Matching, String Matching

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] Hume A, Sunday D M. Fast string searching [J]. Software-Practice & Experience, 1991, 21(11) pp: 1721-1248.

DOI: 10.1002/spe.4380211105

Google Scholar

[2] Sheik S S, Aggarwal S K, Poddar A, et al. A fast pattern matching algorithm [J]. Journal Chemical Information and Computer Science, 2004, 44(4) pp: 1251-125.

DOI: 10.1021/ci030463z

Google Scholar

[3] Fredriksson K, Grabowski S. Practical and optimal string matching [G]/LNCS 3772: SPIRE 2005. Berlin, Springer, 2005 pp: 374-385.

Google Scholar

[4] Holub J, Durian B. Fast variants of bit parallel approach to suffix automata [OL]. [ 2008-10-02 ]. http: /www. cri. haifa. ac. il/events/2005/string/presentations/Holub. pdf.

Google Scholar

[5] Allauzen C, Crochemore M, Raffinot M. Factor oracle: A new structure for pattern matching [G]/LNCS 1725: Proc of SOFSEM 99. Berlin, Springer, 1999 pp: 291-306.

DOI: 10.1007/3-540-47849-3_18

Google Scholar

[6] Lecroq T. Fast exact string matching algorithm [J]. Information Processing Letters, 2007, 102(6) pp: 229-235.

DOI: 10.1016/j.ipl.2007.01.002

Google Scholar

[7] Navarro G, Raffinot M. Fast and flexible string matching by combining bit-parallelism and suffix automata [OL]. [2008-10-05]. http: /doi. acm. org/10. 1145/351827. 384246.

DOI: 10.1145/351827.384246

Google Scholar

[8] Peltola Hannu, Tarhio Jorma. Alternative algorithms for bit-parallel string matching [G]/LNCS 2857: Proc ofSPIRE 2003. Berlin: Springer, 2003 pp: 80-93.

DOI: 10.1007/978-3-540-39984-1_7

Google Scholar