Efficient dictionary matching by Aho-Corasick automata of truncated patterns

摘要

We present a space-efficient data structure for dictionary matching. We truncate patterns to truncated patterns where symbols are ℓ-length substrings of the pattern. By employing the AC automaton of truncated patterns and that of ℓ-length substrings, we simulate the AC automaton of the original pattern set. The new structure is space economical as we apply the prefix merging to substrings of patterns. Using this structure, the dictionary matching runs in O(n log k + tocc log k + occ) time where n is the length of the text, k the number of patterns, occ the number of occurrences of patterns in the text, and tocc the number of occurrences of strings that are longest prefix of each pattern with length of a multiple of ℓ.