# Permuted Pattern Matching Algorithms on Multi-Track Strings
## 6 Experiments  
We performed some sets of experiments to evaluate the practical performance of the proposed algorithms. We measured the running time of our algorithms and the AC-automaton-based algorithm [7]. All experiments were performed on a computer with an Intel Xeon CPU E5-2609 8 core, 2.40 GHz, 256 GB memory, and a Debian Wheezy operating system. We set the parameter values as \(n=\) 100,000, \(m=10\), \(k=1000\), and \(\sigma=2\), and we changed one of the parameters in each experiment to see the relation between the parameters and the running time of the algorithms. We used randomly-generated texts and patterns. The source code of our algorithm is available at [[https://github.com/ushitora/permutedpatternmatching](https://github.com/ushitora/permutedpatternmatching)]([https://github.com/ushitora/permutedpatternmatching](https://github.com/ushitora/permutedpatternmatching)). The first set of experiments compared the running times of KMP-based algorithms, namely the multi-track KMP algorithm, the multi-track AC-automaton algorithm, and the multi-track permuted matching automaton algorithm. The purpose of this experiment was to see the changes in the running time of the multi-track KMP algorithm when extended to the multi-track AC-automaton algorithm and the multi-track permuted matching automaton algorithm. The results of the experiment are shown in Figure 4. From the results, we can see that the multi-track AC-automaton algorithm was slower than the multi-track KMP algorithm. The reason for this is that the multi-track AC-automaton algorithm uses state transitions instead of comparing multi-track symbols directly. This time difference is not significant considering that the multi-track AC-automaton algorithm focuses on dictionary matching instead of single pattern matching. Next, we can see that the multi-track permuted matching automaton algorithm is faster than the multi-track KMP algorithm. The multi-track permuted matching automaton algorithm can perform matching faster because the multi-track permuted matching automaton algorithm does not need to sort the text. The next experiment compared the running time of the multi-track Boyer-Moore algorithm and the multi-track Horspool algorithm. We also checked the effectiveness of track tries in reducing the matching times of both algorithms. Figure 5 shows the result of the experiment. While the multi-track Horspool was slightly faster than the multi-track Boyer-Moore algorithm, there was no significant difference between these algorithms. We can also see that track tries significantly reduced the matching times of both algorithms, since we do not need to sort the text when using track tries. Figure 4: Running time of the multi-track KMP (MTKMP), multi-track AC-automaton (MTACA), multi-track permuted matching automaton (MTPMA) algorithms on permuted pattern matching with respect to (**a**) the text length, (**b**) the track count, (**c**) the pattern length, and (**d**) the alphabet size. The third experiment set compared the running times of the filtering algorithms. We used three algorithms, the KMP algorithm, the Boyer-Moore algorithm, and the Horspool algorithm, as filtering algorithms. Figure 6 shows the running times of the filtering algorithms. There was no significant difference in running time between the filtering algorithms. We can see that the filtering algorithms were fast apart from when the pattern length was \(m=1\). The algorithms became very slow, because there were many occurrence position candidates when \(m=1\). The occurrence position candidates will be fewer if the pattern length is longer. Lastly, we compared the proposed algorithms with the AC-automaton-based algorithm [7]. Figure 7 shows the running time of the AC-automaton-based algorithm [7] and the proposed algorithms. We chose the fastest algorithms among the groups. We can see that the proposed algorithms were faster than the AC-automaton-based algorithm overall. The multi-track Boyer-Moore algorithm with track trie was the fastest among the algorithms.