Answers are grounded in this paper and cite their sources.
This research reports a new algorithm for minimizing Aho-Corasick automaton states, suggesting efficiency improvements.
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> R~ 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> R~ -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> R~ -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> R~ -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> R~ -equivalence and indistinguishability are identical, and thus the proposed automaton is minimal.
No takes yet. Share an insight, caveat, or question.
Evgeniya Igorevna Furletova (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: