HNHacker News
TopNewBestAskShowJobs

matt4711

215 karma · joined January 28, 2011

contact me at matthias@keenable.ai
submissionscomments
matt4711··on New string search algorithm
Sure, but they use a lot more space (even if you use suffix arrays instead of suffix trees) and are generally only worth if you search for more than one pattern on the same text.

In most academic papers I have read that deal with online pattern matching suffix arrays/trees are generally not compared.

matt4711··on New string search algorithm
I'm assuming he is only comparing online algorithms which process only the pattern not the text.
matt4711··on New string search algorithm
Pattern matching performance also depends on the alphabet size of the text. In his experiment he doesn't report the alphabet size of the text nor does he provide results for different text collections.

The algorithm itself looks very similar to the one used in agrep proposed by Wu and Manber [1].

I also found the book "Flexible Pattern Matching in Strings" to be a very good reference on all things related to pattern matching [2].

[1] S. Wu and U. Manber. A fast algorithm for multi-pattern searching. Report TR-94-17, Department of Computer Science, University of Arizona, 1994.

[2] http://www.amazon.com/Flexible-Pattern-Matching-Strings-Line...

← PreviousPage 4 of 4