21–30 of 63 posts
Earlier quoted context omitted.
Um, O((s * (s + 1)) / 2) = O(m^2). Quadratic, not exponential.
Sorry, I updated my comment just as you posted yours. But - and I don't want to sound pedantic - how is m^2 not exponential growth? Edit: mea culpa guys, I carelessly translated from Dutch. You're all right: quadratic, not exponential growth.
Earlier quoted context omitted.
Um, O((s * (s + 1)) / 2) = O(m^2). Quadratic, not exponential.
Sorry, I updated my comment just as you posted yours. But - and I don't want to sound pedantic - how is m^2 not exponential growth? Edit: mea culpa guys, I carelessly translated from Dutch. You're all right: quadratic, not exponential growth.
Using terminology like "exponential" and "quadratic" correctly in a discussion of algorithms is not pedantic...
Earlier quoted context omitted.
Um, O((s * (s + 1)) / 2) = O(m^2). Quadratic, not exponential.
Sorry, I updated my comment just as you posted yours. But - and I don't want to sound pedantic - how is m^2 not exponential growth? Edit: mea culpa guys, I carelessly translated from Dutch. You're all right: quadratic, not exponential growth.
Have a look at http://en.wikipedia.org/wiki/Time_complexity , it's pretty comprehensive.
Earlier quoted context omitted.
Um, O((s * (s + 1)) / 2) = O(m^2). Quadratic, not exponential.
Sorry, I updated my comment just as you posted yours. But - and I don't want to sound pedantic - how is m^2 not exponential growth? Edit: mea culpa guys, I carelessly translated from Dutch. You're all right: quadratic, not exponential growth.
Exponential growth would be 2^m.
Note that the worst case of complexity for this algorithm is much, much worse than the worst case complexity for Boyer Moore. Do not use this algorithm carelessly. For example, if you use it in a thoughtless way in your web server, you may open yourself to a DoS attack.
Note that the author nicely characterizes it as of potential use for small alphabets and possibly multiple substrings (in a single search). That immediately made me think he might have devised it for genomics research. In most applications I would think you'd also want regexp features. Interestingly, DNA research and use in a regexp engine is something he goes on to suggest. (If you are searching for a very large number of regexps in a big genome database, I would not use this algorithm. I found that some simple variants on classic NFA techniques work very well for a wide class of typical regexps (e.g., regexps modeling SNPs, small read position errors, small numbers of read errors, etc. There probably isn't any one obviously right answer, though, and a lot depends on your particular hardware situation, data set sizes, etc.).
The HN headline is very bogus hype. "X2 times faster than Boyer-Moore" is far from true in the general case. "breakthrough" is a gross exaggeration: this is a technique that anyone with some good algorithms course or two under the belt should be able to think of an, for most applications, decide to not use because of the limitations of the thing. I can definitely see it being nice for some applications tolerant of its limitations but... breakthrough it ain't.
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…
This seems like a very practical website about the algorithm but where is the theory and proofs of the time complexity of the 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…
He talks a bit about how to pick the right number of successive letters to use as hash keys - which is where you can get a handle on alphabet sizes. I would guess (maybe it actually says) that he Wikipedia dump in the benchmark was UTF-8 or ASCII and, either way, treated as an alphabet of 8-bit characters. The DNA case is kind of interesting (2 bits min but more likely 3 or 4 in a typical genome record).
In the experiment he used patterns of different length on the same text collection. As you can see in the graph, different algorithms perform best for a certain alphabet size.
He describes the text collection as "text corpus taken from wikipedia text dump" so I'm guessing the alphabet size is around 90?
It's also probably not a good thing that all the strings he is searching for are prefixes of the same pattern.
References:
Shift-Or: http://www-igm.univ-mlv.fr/~lecroq/string/node6.html#SECTION...
BNDM: http://www-igm.univ-mlv.fr/~lecroq/string/bndm.html#SECTION0...
BOM: http://www-igm.univ-mlv.fr/~lecroq/string/bom.html#SECTION00...
Interesting. Note that the worst case of complexity for this algorithm is much, much worse than the worst case complexity for Boyer Moore. Do not use this algorithm carelessly. For example, if you use it in a thoughtless way in your web server, you may open yourself to a DoS attack. Note that the author nicely characterizes it as of potential use for small alphabets and possibly multiple substrings (in a single searc…
See http://en.wikipedia.org/wiki/Burrows–Wheeler_transform or http://bioinformatics.oxfordjournals.org/content/early/2009/...
This seems like a very practical website about the algorithm but where is the theory and proofs of the time complexity of the algorithm??
I don't mean to be a turd but the proofs are kind of obvious on the face on this one. He's claiming expected linear time in the string being searched for "natural" texts and worst case O(M N). Proof of the worst case is pretty trivial by construction (of examples of that complexity) and contradiction (reaching the non-existence of worse cases). One can't be casual about proofs of course but: try thinking of an O(M N)…
