4 ms·

No 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

by mayank 16y ago

No 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 suffix trees: O(n) preprocessing O(m) string search where worst case complexity is linear in search term.

Radim 16y ago
I guess it depends on what type of queries you expect; if you want to find the same (fixed) substring across a body of (dynamic) texts, the O(n) cost of preprocessing (suffix trees/arrays) is terrible. If, on the other hand, you have a fixed "corpus" and a dynamic query, O(n) search time (this algo, purportedly) is terrible.
- mayank 16y ago
  Hmm...there's no mention of it being suited for a dynamic or "online" setting as another commenter notes (not sure why my other comment was downvoted for that). I don't know what to make of this from the description: "This algorithm especially well suited for long S, multi-substrings, small alphabet, regex/parsing and search for common substrings." Long source text: the O(n times m) worst-case time per search kills it. Even for a single search, O(n times m) worst case here versus O(n + m) for suffix trees. multi-substrings: suffix trees do each substring of length m in O(m), but are not compared. search for common substrings: again, suffix trees would be more appropriate.
matt4711 16y ago
I'm assuming he is only comparing online algorithms which process only the pattern not the text.
- mayank 16y ago
  Nevertheless, it's inexcusable to be proposing a string matching algorithm without at least mentioning why suffix trees can't do the job. At the very least, showing that your algorithm beats suffix trees in any instantiation does wonders for credibility. For the record, suffix trees can be built online as well: http://www.springerlink.com/content/kq55005qu6479276/ http://www.springerlink.com/content/kq55005qu6479276/
  - matt4711 16y ago
    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.
kragen 16y ago
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.
- mayank 16y ago
  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.
- cperciva 16y ago
  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.
  - kragen 16y ago
    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.devel/2628 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.

by mayank 16y ago

Radim 16y ago

I guess it depends on what type of queries you expect; if you want to find the same (fixed) substring across a body of (dynamic) texts, the O(n) cost of preprocessing (suffix trees/arrays) is terrible. If, on the other hand, you have a fixed "corpus" and a dynamic query, O(n) search time (this algo, purportedly) is terrible.

mayank 16y ago
Hmm...there's no mention of it being suited for a dynamic or "online" setting as another commenter notes (not sure why my other comment was downvoted for that). I don't know what to make of this from the description: "This algorithm especially well suited for long S, multi-substrings, small alphabet, regex/parsing and search for common substrings." Long source text: the O(n times m) worst-case time per search kills it. Even for a single search, O(n times m) worst case here versus O(n + m) for suffix trees. multi-substrings: suffix trees do each substring of length m in O(m), but are not compared. search for common substrings: again, suffix trees would be more appropriate.

matt4711 16y ago

I'm assuming he is only comparing online algorithms which process only the pattern not the text.

mayank 16y ago
Nevertheless, it's inexcusable to be proposing a string matching algorithm without at least mentioning why suffix trees can't do the job. At the very least, showing that your algorithm beats suffix trees in any instantiation does wonders for credibility. For the record, suffix trees can be built online as well: http://www.springerlink.com/content/kq55005qu6479276/ http://www.springerlink.com/content/kq55005qu6479276/
- matt4711 16y ago
  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.

kragen 16y ago

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.

mayank 16y ago
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.
cperciva 16y ago
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.
- kragen 16y ago
  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.devel/2628 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.