Hits:

Date of Publication:2022-10-09

Journal:计算机研究与发展

Issue:12

Page Number:2699-2706

ISSN No.:1000-1239

Abstract:Advanced AC (AAC) is the most widely used multi-patterns string matching algorithm. The building cost of AAC automaton is high for large-scale matching. In this article, the automaton building method of DFA (a basic single pattern string matching algorithm) is improved and it is expanded into multi-patterns matching field. Thus, an automaton for multi-pattern string matching called Set DFA is proposed and it is proved to be same as AAC automaton. The building method of Set DFA can be described in two steps: 1) Building trie and setting all undefined trans of the initial state point to the initial state. 2) Accessing all states of the trie in level-order, and setting all undefined trans. Let the string along the path from the initial state to the accessed state be u1u2uk, and let the trans character of the undefined trans be c, this undefined trans should be set to point to the result state after the string of u2ukc being inputted from the initial state on existing automaton. This building method can be also improved to liner time building. The experimental results indicate that building Set DFA is about two times faster than building AAC automaton, because AC failure function is not used in buliding Set DFA and each state in Set DFA just is accessed once after being generated.

Note:新增回溯数据