An incremental algorithm for string pattern matching machines

Abstract

Aho and Corasick presented a string pattern matching machine (hereafter called machine AC) to locate multiple keywords. However, the machine AC must be reconstructed all over again when a keyword is appended. This paper proposes an efficient algorithm to append a keyword for the machine AC. This paper presents the time efficiency comparison with the original algorithm using the actual simulation results. The simulation results show the speed up factor, by the algorithm proposed, to be between 25 and 270 fold when compared with the original algorithm by Aho and Corasick which requires the reconstruction of the entire machine AC.

Keywords:

• String pattern matching
• Append a keyword
• Bibliographic search
• Text-editing
• Information retrieval

C.R.Categories:

• E.1
• H.3.3
• I.1.2