Space-efficient multiple string matching automata

Aho–Corasick (AC) automaton is a data structure for multiple string matching. We <br />present two compressing methods that enable the AC automaton to work on systems with limited <br />resource such as mobile devices. By the first method, the AC automaton for a pattern set P over <br />an alphabet of size σ needs (σ + 1)I + (1 + log|P| + logM)M + o(M) bits where M and I are the <br />number of states and the number of non-leaf states of the AC automaton respectively, an