Improved algorithms for multiple patterns matching

Li Hua Yin; Bin Xing Fang; Hong Li Zhang

Improved algorithms for multiple patterns matching

Li Hua Yin^*
, Bin Xing Fang
, Hong Li Zhang

^*Corresponding author for this work

Faculty of Computing

Harbin Institute of Technology

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

Combined with the advantages of the Tuned Boyer-Moore algorithm, an effective algorithm for performing multiple patterns matching in a string was put forward on the concept of deterministic finite state automata (DFSA), and achieved better performance by shifting unmatched characters consecutively. Experimental results indicate that, to search a string, the algorithm takes only 1/2-1/3 that of AC and 9/10 of AQR in case of short patterns while the ratio is 1/4-1/8 and 3/4 in case of long patterns.

Original language	English
Pages (from-to)	1925-1929
Number of pages	5
Journal	Harbin Gongye Daxue Xuebao/Journal of Harbin Institute of Technology
Volume	39
Issue number	12
State	Published - Dec 2007

Keywords

Computational complexity
Finite state automaton
Multiple patterns matching
String matching
Tuned BM algorithm

Cite this

@article{ca9a697b55f24ddcb458d46c2b8888eb,

title = "Improved algorithms for multiple patterns matching",

abstract = "Combined with the advantages of the Tuned Boyer-Moore algorithm, an effective algorithm for performing multiple patterns matching in a string was put forward on the concept of deterministic finite state automata (DFSA), and achieved better performance by shifting unmatched characters consecutively. Experimental results indicate that, to search a string, the algorithm takes only 1/2-1/3 that of AC and 9/10 of AQR in case of short patterns while the ratio is 1/4-1/8 and 3/4 in case of long patterns.",

keywords = "Computational complexity, Finite state automaton, Multiple patterns matching, String matching, Tuned BM algorithm",

author = "Yin, \{Li Hua\} and Fang, \{Bin Xing\} and Zhang, \{Hong Li\}",

year = "2007",

month = dec,

language = "英语",

volume = "39",

pages = "1925--1929",

journal = "Harbin Gongye Daxue Xuebao/Journal of Harbin Institute of Technology",

issn = "0367-6234",

publisher = "Harbin Institute of Technology",

number = "12",

}

TY - JOUR

T1 - Improved algorithms for multiple patterns matching

AU - Yin, Li Hua

AU - Fang, Bin Xing

AU - Zhang, Hong Li

PY - 2007/12

Y1 - 2007/12

N2 - Combined with the advantages of the Tuned Boyer-Moore algorithm, an effective algorithm for performing multiple patterns matching in a string was put forward on the concept of deterministic finite state automata (DFSA), and achieved better performance by shifting unmatched characters consecutively. Experimental results indicate that, to search a string, the algorithm takes only 1/2-1/3 that of AC and 9/10 of AQR in case of short patterns while the ratio is 1/4-1/8 and 3/4 in case of long patterns.

AB - Combined with the advantages of the Tuned Boyer-Moore algorithm, an effective algorithm for performing multiple patterns matching in a string was put forward on the concept of deterministic finite state automata (DFSA), and achieved better performance by shifting unmatched characters consecutively. Experimental results indicate that, to search a string, the algorithm takes only 1/2-1/3 that of AC and 9/10 of AQR in case of short patterns while the ratio is 1/4-1/8 and 3/4 in case of long patterns.

KW - Computational complexity

KW - Finite state automaton

KW - Multiple patterns matching

KW - String matching

KW - Tuned BM algorithm

UR - https://www.scopus.com/pages/publications/38549126149

M3 - 文章

AN - SCOPUS:38549126149

SN - 0367-6234

VL - 39

SP - 1925

EP - 1929

JO - Harbin Gongye Daxue Xuebao/Journal of Harbin Institute of Technology

JF - Harbin Gongye Daxue Xuebao/Journal of Harbin Institute of Technology

IS - 12

ER -

Improved algorithms for multiple patterns matching

Abstract

Keywords

Other files and links

Fingerprint

Cite this