Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

New string search algorithm

volnitsky.com

Post reply on HN
Print view View original

11–20 of 63 posts

Re: New string search algorithm

#11

Post by jemfinch »

tansey wrote: post #4

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/39…

Big O notation is frequently used to refer to the average case bounds of an algorithm. Haven't you seen an analysis of quicksort?

Re: New string search algorithm

#12

Post by mayank »

pjscott wrote: post #8
mayank wrote: post #5

Earlier quoted context omitted.

> 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

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.

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.

Re: New string search algorithm

#13

Post by pjscott »

tansey wrote: post #4

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/39…

It could be just an abuse of notation, in the same way that people say that Quicksort is O(n lg n) on average. Sure, on perverse data the best time bound you can prove is O(n^2), but on random data you get expected O(n lg n) time, and on typical data with good partition selection you can generally expect to not go quadratic.

(You could also use the O(n) time median algorithm to construct a truly O(n lg n) Quicksort, but that's just a fun theoretical side-note here.)

Re: New string search algorithm

#14

Post by Radim »

mayank wrote: post #3

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 su…

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.

Re: New string search algorithm

#15

Post by matt4711 »

mayank wrote: post #3

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 su…

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

Re: New string search algorithm

#16

Post by mayank »

matt4711 wrote: post #15
mayank wrote: post #3

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 su…

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

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/

Re: New string search algorithm

#17

Post by matt4711 »

mayank wrote: post #16
matt4711 wrote: post #15

Earlier quoted context omitted.

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

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/

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.

Re: New string search algorithm

#18

Post by martincmartin »

bnoordhuis wrote: post #7

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

Um, O((s * (s + 1)) / 2) = O(m^2). Quadratic, not exponential.

Re: New string search algorithm

#19

Post by mayank »

Radim wrote: post #14
mayank wrote: post #3

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 su…

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.

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.

Re: New string search algorithm

#20

Post by bnoordhuis »

martincmartin wrote: post #18
bnoordhuis wrote: post #7

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

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.

Post reply on HN