An efficient implementation of static string pattern matching machines

Author

Aoe, Jun-Ichi

Author_Institution

Dept. of Inf. Sci. & Syst. Eng., Tokushima Univ., Japan

Volume

15

Issue

8

fYear

1989

fDate

8/1/1989 12:00:00 AM

Firstpage

1010

Lastpage

1016

Abstract

A technique for implementing a static transition table of a string pattern matching machine which locates all occurrences of a finite number of keywords in a string is described. The approach is based on S.C. Johnson´s (1975) storage and retrieval method of the transition table of a finite-state machine. By restricting the transition table of the finite-state machine to that of the string pattern-matching machine, triple arrays of Johnsons´s data structure can be reduced to two arrays. The retrieval program of the reduced data structure can be speeded up by a finite straight program without loops

Keywords

data structures; information retrieval; subroutines; Johnsons´s data structure; finite straight program; finite-state machine; implementation technique; keyword location; reduced data structure; retrieval program; static string pattern matching machines; transition table; triple arrays; Automata; Data structures; Filtering; Frequency; Information analysis; Information retrieval; Libraries; Pattern analysis; Pattern matching; Scanning probe microscopy;

fLanguage

English

Journal_Title

Software Engineering, IEEE Transactions on

Publisher

ieee

ISSN

0098-5589

Type

jour

DOI

10.1109/32.31357

Filename

31357