An efficient implementation of static string pattern matching machines

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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>