If i am gonna need a string search algorithm for something serious, i would definitely use KMP (knuth morris pratt). Linear in worst case complexity (wouldn't risk)
New string search algorithm
31–40 of 63 posts
Re: New string search algorithm
#32No DBLP profile for the author, no proofs on site, fastest algorithm known "to me " qualifier, no results for "suffix tree" on page, not a good sign. EDIT: Am I missing something??? Complexity analysis according to the author: m = search term, n = text O(m) preprocessing -- that's right, O(search term). And O(n times m) worst-case query string search, so the worst case traverses the whole text. Now compare that to su…
He's a Russian hacker. That's where awesome new algorithms come from these days, including things like Dual-Pivot Quicksort. (And QuickLZ may have been invented by some Scandinavian guy, but I'm pretty sure it was announced on encode.ru.) He's not an academic, but that doesn't mean he can't do competent algorithmic analysis.
I concur with the other commenters that it's silly for you to complain about his not comparing his online string-search algorithm against offline string-search algorithms that search an index of the text, such as suffix-tree algorithms.
Re: New string search algorithm
#33Interesting. 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…
For sequence alignment, the state of the art is BWA, which first compresses the "haystack", then builds a trie. See http://en.wikipedia.org/wiki/Burrows–Wheeler_transform or http://bioinformatics.oxfordjournals.org/content/early/2009/...
Thanks. That's interesting. I'm pretty confident that you don't really need to compress the reference that way. It doesn't make a lot of intuitive sense that you would, in a way: streaming over the reference can be very fast and the question is how many reads you can align per pass, how flexibly, and with how low a pre-processing cost. I think my stuff (which doesn't count since we didn't get to publication stage for other reasons, etc.) was probably faster and more flexible.
Re: New string search algorithm
#34Earlier quoted context omitted.
For sequence alignment, the state of the art is BWA, which first compresses the "haystack", then builds a trie. See http://en.wikipedia.org/wiki/Burrows–Wheeler_transform or http://bioinformatics.oxfordjournals.org/content/early/2009/...
Thanks. That's interesting. I'm pretty confident that you don't really need to compress the reference that way. It doesn't make a lot of intuitive sense that you would, in a way: streaming over the reference can be very fast and the question is how many reads you can align per pass, how flexibly, and with how low a pre-processing cost. I think my stuff (which doesn't count since we didn't get to publication stage for…
You'd be prerty confident in the other direction once you understand the problem better. The BWT is not compression as much as an extremely clever way of rearranging the haystack. There are many many different string alignment (not string search) algorithms that are useful with DNA, and where the BWT is used your algorithm is not going to be in the realm of useful. BWT based aligners run in time completely independent of the haystack length. When you have 2 billion needles of size 50-200, and the haystack is 3 billion long, it makes a ton of sense to pay the preprocessing cost of O(n lg n), since it only has to be done on the order of once a year.
Re: New string search algorithm
#35Interesting. 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…
For "DNA research" (or rather, searching for peptide sequence matches), there's HMMER at http://hmmer.janelia.org/ , which uses hidden markov models. Claims to be great at detecting distant homologs. And after an enormous engineering effort, it's as fast as BLAST (in practical use it's faster, because its servers are currently not known as widely).
Re: New string search algorithm
#36No DBLP profile for the author, no proofs on site, fastest algorithm known "to me " qualifier, no results for "suffix tree" on page, not a good sign. EDIT: Am I missing something??? Complexity analysis according to the author: m = search term, n = text O(m) preprocessing -- that's right, O(search term). And O(n times m) worst-case query string search, so the worst case traverses the whole text. Now compare that to su…
He's a Russian hacker. That's where awesome new algorithms come from these days, including things like Dual-Pivot Quicksort. (And QuickLZ may have been invented by some Scandinavian guy, but I'm pretty sure it was announced on encode.ru.) He's not an academic, but that doesn't mean he can't do competent algorithmic analysis. I concur with the other commenters that it's silly for you to complain about his not comparin…
His being Russian has no bearing on the issue. nginx and the pivot improvement to quicksort don't imply that Russian mathematicians no longer need to prove their claims. Not being an academic doesn't exempt you from having to do rigorous analysis either.
As for the online algorithm issue, see my reply below.
Re: New string search algorithm
#37No DBLP profile for the author, no proofs on site, fastest algorithm known "to me " qualifier, no results for "suffix tree" on page, not a good sign. EDIT: Am I missing something??? Complexity analysis according to the author: m = search term, n = text O(m) preprocessing -- that's right, O(search term). And O(n times m) worst-case query string search, so the worst case traverses the whole text. Now compare that to su…
He's a Russian hacker. That's where awesome new algorithms come from these days, including things like Dual-Pivot Quicksort. (And QuickLZ may have been invented by some Scandinavian guy, but I'm pretty sure it was announced on encode.ru.) He's not an academic, but that doesn't mean he can't do competent algorithmic analysis. I concur with the other commenters that it's silly for you to complain about his not comparin…
Dual-Pivot Quicksort is an "awesome new algorithm"? Hardly. It's very small step in the direction of Samplesort -- which is asymptotically optimal and has been around for four decades.
Dual-Pivot Quicksort is a demonstration that someone didn't read the existing literature; nothing more.
Re: New string search algorithm
#38Earlier 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.
how is m^2 not exponential growth
m^2 is exponential -- in the value 2. But the value 2 doesn't change very rapidly, so we tend to focus on the m component of the expression. :-)
Re: New string search algorithm
#39Earlier quoted context omitted.
He's a Russian hacker. That's where awesome new algorithms come from these days, including things like Dual-Pivot Quicksort. (And QuickLZ may have been invented by some Scandinavian guy, but I'm pretty sure it was announced on encode.ru.) He's not an academic, but that doesn't mean he can't do competent algorithmic analysis. I concur with the other commenters that it's silly for you to complain about his not comparin…
Dual-Pivot Quicksort is an "awesome new algorithm"? Hardly. It's very small step in the direction of Samplesort -- which is asymptotically optimal and has been around for four decades. Dual-Pivot Quicksort is a demonstration that someone didn't read the existing literature; nothing more.
Unfortunately I don't have access to the Samplesort paper, so I don't know which sense of "asymptotically optimal" you're using here. Quicksort is already asymptotically optimal in the sense that its asymptotic average performance is Θ(N log N), which is the best a sorting algorithm can do.
It's true that dual-pivot quicksort is a step in the direction of Samplesort. (I do understand Samplesort well enough to say that.) That doesn't mean it's not a worthwhile contribution in its own right. Jon Bentley (advisor of Brian Reid, Ousterhout, Josh Bloch, and Gosling while at CMU; later at Bell Labs in its glory days) was quoted as having a substantially different opinion from yours:
http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs...
> I think that Vladimir's contributions to Quicksort go way beyond
> anything that I've ever done, and rank up there with Hoare's original
> design and Sedgewick's analysis. I feel so privileged to play a very,
> very minor role in helping Vladimir with the most excellent work!
I am not sure Bentley will be persuaded by your claim that he didn't read the existing literature.
Re: New string search algorithm
#40Earlier quoted context omitted.
Dual-Pivot Quicksort is an "awesome new algorithm"? Hardly. It's very small step in the direction of Samplesort -- which is asymptotically optimal and has been around for four decades. Dual-Pivot Quicksort is a demonstration that someone didn't read the existing literature; nothing more.
Unfortunately I don't have access to the Samplesort paper, so I don't know which sense of "asymptotically optimal" you're using here. Quicksort is already asymptotically optimal in the sense that its asymptotic average performance is Θ(N log N), which is the best a sorting algorithm can do. It's true that dual-pivot quicksort is a step in the direction of Samplesort. (I do understand Samplesort well enough to say tha…
The asymptotic optimality of samplesort is in the sense that it takes (1 + o(1)) N log N / log 2 comparisons, i.e., you can't beat it by any constant factor.
Bentley's comments from that email don't make any sense to me. I can't understand what he was thinking, unless he's just unusually prone to flattering other people's work (I don't know Bentley personally, but I've met other people who do this, much to my irritation).