{'fraction_non_alphanumeric': 0.015217391304347827, 'fraction_numerical': 0.0, 'mean_word_length': 5.181208053691275, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Improving a hierarchical pattern matching algorithm using cache-aware Aho-Corasick automata

Enhanced Hierarchical Multipattern Matching Algorithm (EHMA) is an efficient pattern matching algorithm that divides the matching process into two phases so that it may reduce the number of the external memory accesses. But when the number of the patterns increases, the algorithm may not work well. In this paper we propose a method to solve this problem by combining EHMA algorithm with the Aho-Corasick algorithm. We also take into consideration the effect of cache memory in the network equipment by implementing a cache-aware algorithm that exploits the frequency of the characters in the network payload and the transition probability of links in the Aho-Corasick automata. The experiments show that our improvement can help to significantly reduce the number of the external memory access, compared to the original EHMA.