6 ms·

New string search algorithm

181 points by akaus 16y ago

zitterbewegung 16y ago
This seems like a very practical website about the algorithm but where is the theory and proofs of the time complexity of the algorithm??
- dasht 16y ago
  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(MN). 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(MN) example and then you can probably see from there why you can't do worse than that. Hint: if you can construct an example where you have to do the length M check for nearly every position in the length N haystack, aaaaaaaah... hmmmmm...., the rest should be clear.
  - deleted 16y ago
    [deleted]
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.
tansey 16y ago
From the site: >Preprocessing phase in O(M) space and time complexity. Searching phase average O(N) time complexity and O(N*M) worst case complexity. I don't trust the analysis of someone referring to "average O(N) time"; Big O notation refers to boundary times. Edit: Okay, based on arguments here and on [1], I'm going to accept that maybe he's just bastardizing the notation. [1] http://stackoverflow.com/questions/3905355/meaning-of-average-complexity-when-using-big-o-notation http://stackoverflow.com/questions/3905355/meaning-of-averag...
- mayank 16y ago
  > Big O notation refers to boundary times. No it doesn't. You can have an O(N) amortized time. Big-O is a bounding function up to a constant factor, not necessarily a boundary (as in worst-case) time. http://en.wikipedia.org/wiki/Amortized_analysis http://en.wikipedia.org/wiki/Amortized_analysis
  - pjscott 16y ago
    To say that something runs in amortized O(n) time guarantees an upper bound on the average time per operation in a worst-case sequence of operations. It does not deal with average-case time on random or typical data.
    - mayank 16y ago
      I didn't say it did. On the other hand, unless the author of the algorithm is really clueless (edit: or knowingly making a probabilistic statement), I'm sure he meant amortized time.
  - leif 16y ago
    This is not an amortized analysis, it is a probabilistic analysis.
- jemfinch 16y ago
  Big O notation is frequently used to refer to the average case bounds of an algorithm. Haven't you seen an analysis of quicksort?
aristus 16y ago
Skeptical but excited. Will definitely be studying this at the weekend. I had been working on a long writeup on string matching but stopped the project for lack of recent progress.
bnoordhuis 16y ago
The author states that preprocessing takes O(m) time but that is on average. A quick review of the code makes me think that its worst case is actually on the order of O((s * (s + 1)) / 2), where s = m / 2. The Achilles heel is the hash function. It's trivial to create collisions and have the insertion time for word w turn from O(1) to O(w).
- martincmartin 16y ago
  Um, O((s * (s + 1)) / 2) = O(m^2). Quadratic, not exponential.
  - bnoordhuis 16y ago
    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.
    - Locke1689 16y ago
      Exponential growth is O(2^m). This is not pedantic -- it's definition. O(m^k) is polynomial, O(k^m) is exponential.
    - bigiain 16y ago
      Because 2^m and m^2 are very different... Using terminology like "exponential" and "quadratic" correctly in a discussion of algorithms is not pedantic...
    - theoretical 16y ago
      x^2 is quadratic, 2^x (for example) is exponential. Have a look at http://en.wikipedia.org/wiki/Time_complexity http://en.wikipedia.org/wiki/Time_complexity , it's pretty comprehensive.
    - state_machine 16y ago
      Because 2, the exponent in that expression, is a constant. Exponential growth would be 2^m.
b0b0b0b 16y ago
it seems that his algorithm is faster because it exploits the model of computation (memory aligned accesses and multi-byte operations). He gets up to a constant factor more comparisons for free.
matt4711 16y ago
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/dp/0521039932 http://www.amazon.com/Flexible-Pattern-Matching-Strings-Line...
- dasht 16y ago
  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).
  - matt4711 16y ago
    An illustration from the book I cited above showing the importance of the alphabet size (y-axis) and the pattern length (x-axis): http://i.imgur.com/KGOZW.jpg http://i.imgur.com/KGOZW.jpg 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#SECTION0060 http://www-igm.univ-mlv.fr/~lecroq/string/node6.html#SECTION... BNDM: http://www-igm.univ-mlv.fr/~lecroq/string/bndm.html#SECTION00300 http://www-igm.univ-mlv.fr/~lecroq/string/bndm.html#SECTION0... BOM: http://www-igm.univ-mlv.fr/~lecroq/string/bom.html#SECTION00245 http://www-igm.univ-mlv.fr/~lecroq/string/bom.html#SECTION00...
dasht 16y ago
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 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.
- thisisnotmyname 16y ago
  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 http://en.wikipedia.org/wiki/Burrows–Wheeler_transform or http://bioinformatics.oxfordjournals.org/content/early/2009/05/18/bioinformatics.btp324.full.pdf http://bioinformatics.oxfordjournals.org/content/early/2009/...
  - dasht 16y ago
    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.
yhlasx 16y ago
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)

181 points by akaus 16y ago

This seems like a very practical website about the algorithm but where is the theory and proofs of the time complexity of the algorithm??

dasht 16y ago
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(MN). 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(MN) example and then you can probably see from there why you can't do worse than that. Hint: if you can construct an example where you have to do the length M check for nearly every position in the length N haystack, aaaaaaaah... hmmmmm...., the rest should be clear.
- deleted 16y ago
  [deleted]

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.

tansey 16y ago

From the site: >Preprocessing phase in O(M) space and time complexity. Searching phase average O(N) time complexity and O(N*M) worst case complexity. I don't trust the analysis of someone referring to "average O(N) time"; Big O notation refers to boundary times. Edit: Okay, based on arguments here and on [1], I'm going to accept that maybe he's just bastardizing the notation. [1] http://stackoverflow.com/questions/3905355/meaning-of-average-complexity-when-using-big-o-notation http://stackoverflow.com/questions/3905355/meaning-of-averag...

mayank 16y ago
> Big O notation refers to boundary times. No it doesn't. You can have an O(N) amortized time. Big-O is a bounding function up to a constant factor, not necessarily a boundary (as in worst-case) time. http://en.wikipedia.org/wiki/Amortized_analysis http://en.wikipedia.org/wiki/Amortized_analysis
- pjscott 16y ago
  To say that something runs in amortized O(n) time guarantees an upper bound on the average time per operation in a worst-case sequence of operations. It does not deal with average-case time on random or typical data.
  - mayank 16y ago
    I didn't say it did. On the other hand, unless the author of the algorithm is really clueless (edit: or knowingly making a probabilistic statement), I'm sure he meant amortized time.
- leif 16y ago
  This is not an amortized analysis, it is a probabilistic analysis.
jemfinch 16y ago
Big O notation is frequently used to refer to the average case bounds of an algorithm. Haven't you seen an analysis of quicksort?

aristus 16y ago

Skeptical but excited. Will definitely be studying this at the weekend. I had been working on a long writeup on string matching but stopped the project for lack of recent progress.

bnoordhuis 16y ago

The author states that preprocessing takes O(m) time but that is on average. A quick review of the code makes me think that its worst case is actually on the order of O((s * (s + 1)) / 2), where s = m / 2. The Achilles heel is the hash function. It's trivial to create collisions and have the insertion time for word w turn from O(1) to O(w).

martincmartin 16y ago
Um, O((s * (s + 1)) / 2) = O(m^2). Quadratic, not exponential.
- bnoordhuis 16y ago
  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.
  - Locke1689 16y ago
    Exponential growth is O(2^m). This is not pedantic -- it's definition. O(m^k) is polynomial, O(k^m) is exponential.
  - bigiain 16y ago
    Because 2^m and m^2 are very different... Using terminology like "exponential" and "quadratic" correctly in a discussion of algorithms is not pedantic...
  - theoretical 16y ago
    x^2 is quadratic, 2^x (for example) is exponential. Have a look at http://en.wikipedia.org/wiki/Time_complexity http://en.wikipedia.org/wiki/Time_complexity , it's pretty comprehensive.
  - state_machine 16y ago
    Because 2, the exponent in that expression, is a constant. Exponential growth would be 2^m.

b0b0b0b 16y ago

it seems that his algorithm is faster because it exploits the model of computation (memory aligned accesses and multi-byte operations). He gets up to a constant factor more comparisons for free.

matt4711 16y ago

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/dp/0521039932 http://www.amazon.com/Flexible-Pattern-Matching-Strings-Line...

dasht 16y ago
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).
- matt4711 16y ago
  An illustration from the book I cited above showing the importance of the alphabet size (y-axis) and the pattern length (x-axis): http://i.imgur.com/KGOZW.jpg http://i.imgur.com/KGOZW.jpg 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#SECTION0060 http://www-igm.univ-mlv.fr/~lecroq/string/node6.html#SECTION... BNDM: http://www-igm.univ-mlv.fr/~lecroq/string/bndm.html#SECTION00300 http://www-igm.univ-mlv.fr/~lecroq/string/bndm.html#SECTION0... BOM: http://www-igm.univ-mlv.fr/~lecroq/string/bom.html#SECTION00245 http://www-igm.univ-mlv.fr/~lecroq/string/bom.html#SECTION00...

dasht 16y ago

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 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.

thisisnotmyname 16y ago
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 http://en.wikipedia.org/wiki/Burrows–Wheeler_transform or http://bioinformatics.oxfordjournals.org/content/early/2009/05/18/bioinformatics.btp324.full.pdf http://bioinformatics.oxfordjournals.org/content/early/2009/...
- dasht 16y ago
  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.

yhlasx 16y ago

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)