11
$\begingroup$

I am working on string searching algorithms that support multiple pattern search. I found two algorithms that seem like the strongest candidates in terms of running time, namely Aho-Corasick and Rabin-Karp. However, I could not find any comprehensive comparison between the two algorithms. Which algorithm is more efficient? Also, which one is more suitable for parallel computing and multiple patterns search? Finally, which one requires less hardware resources?

For AC algorithm, the searching phase takes $O(n+m)$ time, while it is $O(nm)$ for RK. However, the running time for RK is $O(n+m)$ which makes it similar to AC. My tentative conclusion is that RK seems practically better as it does not need as much memory as AC. Is that correct?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Are all your patterns of the same length? $\endgroup$ – Hendrik Jan Sep 15 '13 at 0:16
  • $\begingroup$ @HendrikJan No, different length patterns $\endgroup$ – Hawk Sep 15 '13 at 5:01
  • $\begingroup$ If the patterns are of different length it seems hard to process them in parallel using RK? The wikipedia page seems to suggest these patterns are of equal length, although updating the hashes can be done for different lengths. $\endgroup$ – Hendrik Jan Sep 15 '13 at 12:49
  • $\begingroup$ Are you interested in some kind of theoretical study or practical experience? $\endgroup$ – Raphael♦ Sep 16 '13 at 7:48
  • $\begingroup$ @Raphael Academically, we used to apply theoretical study first before we prove that empirically. I posted the question here because I do not expect programming answers. I need a logical algorithmic answer $\endgroup$ – Hawk Sep 18 '13 at 8:22
4
$\begingroup$

Asymptotic running time analysis is not likely to be the best tool to pick between these two algorithms: asymptotic analysis ignores constant factors, and the constant factors will be critical here. The two algorithms have basically the same asymptotic running time, so asymptotic analysis probably isn't very helpful to choose between them.

Instead, the right way pick between the two algorithms is through experimental analysis. Identify a representative workload, and then benchmark the performance of both algorithms on your workload, on the kinds of machines you intend to use in practice.

Incidentally, it sounds like you might have a slight confusion about the asymptotic running time of Rabin-Karp. On the one hand you say that Rabin-Karp has $O(nm)$ running time, but then in the next sentence you say Rabin-Karp has $O(n+m)$ running time. Perhaps you are confused by the difference between expected (average-case) vs worst-case running time.

Since Rabin-Karp is randomized, expected (average-case) running time is the appropriate metric to use to predict real-world performance in practice. In particular, here the average is taken over the random choice of hash function. It's specifically not an average taken over the choice of strings. Even for the worst possible string and pattern, the average running time will still be $O(n+m)$. With a suitable hash function, the probability that the running time is longer than $c\cdot(n+m)$ is exponentially small in $c$. To put it another way (and being slightly informal), there's only an exponentially small chance that Rabin-Karp takes longer than $O(n+m)$ time. We already have to accept exponentially small chances of bad things happen -- for instance, there's a tiny but non-zero chance of a cosmic ray causing a bit-flip in your memory that causes the program to loop forever. So, worrying about this exponentially small chance makes no sense.

From an engineering point of view, Rabin-Karp's running time is $O(n+m)$ [or it might as well be]. Ignore the $O(nm)$ stuff; that's not really relevant to practice.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

However, I could not find any comprehensive comparison between the two algorithms.

a question like this on relative performance of two algorithms generally depends on average case versus worst case which is dependent on actual data. the theoretical answer is that the $O(n + m)$ Aho-Corasick algorithm will outperform $O(n m)$ Rabin-Karp in the large data limit case/ asymptotically, but where that limit is reached is implementation and data dependent & the tradeoff between searching/ running times.

but wrt your implicit query for "comprehensive comparison", some papers have been written experimentally/ empirically comparing these two and other algorithms on real data and include analysis/ comparison of the pros/ cons/ tradeoffs of the different algorithms eg:

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.