Linear-time minimization of Aho–Corasick automaton

Abstract Aho-Corasick automaton is widely used to find occurrences of words from a given set in a text. In our paper we introduce an equivalence relation <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mover> <m:mrow> <m:mo>∼</m:mo> </m:mrow> <m:mrow> <m:mi>R</m:mi> </m:mrow> </m:mover> </m:mrow> </m:math> $\stackrel{R}{\sim}$ on states of Aho–Corasick automaton and prove indistinguishability of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mover> <m:mrow> <m:mo>∼</m:mo> </m:mrow> <m:mrow> <m:mi>R</m:mi> </m:mrow> </m:mover> </m:mrow> </m:math> $\stackrel{R}{\sim}$ -equivalent states. We also propose an algorithm for construction of a <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mover> <m:mrow> <m:mo>∼</m:mo> </m:mrow> <m:mrow> <m:mi>R</m:mi> </m:mrow> </m:mover> </m:mrow> </m:math> $\stackrel{R}{\sim}$ -minimal automaton whose states are <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mover> <m:mrow> <m:mo>∼</m:mo> </m:mrow> <m:mrow> <m:mi>R</m:mi> </m:mrow> </m:mover> </m:mrow> </m:math> $\stackrel{R}{\sim}$ -equivalence classes. Time and space complexity of this algorithm are linear in the number of states of the original Aho–Corasick automaton. Finally we consider cases in which the relations of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mover> <m:mrow> <m:mo>∼</m:mo> </m:mrow> <m:mrow> <m:mi>R</m:mi> </m:mrow> </m:mover> </m:mrow> </m:math> $\stackrel{R}{\sim}$ -equivalence and indistinguishability are identical, and thus the proposed automaton is minimal.