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

51–60 of 63 posts

Re: New string search algorithm

#51

Post by lvvlvv »

dasht wrote: post #25

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…

> Note that the worst case of complexity for this algorithm is much, much worse than the worst case complexity for Boyer Moore.

Can you explain your thought process for why worst case complexity is worse than other? Did you do any measurements? I believe you are incorrect. I am author of this page. I've just did quick test for SS = "aaa ...aaaBaaa...aaa", with SS_size=240. My algorithm is faster than 3 BMs out of 4 tested.

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

Same can be said about all BM, naive and BSD's memmem/strstr. Possibility of DOS for substring search algorithm was known for a long time - but it never materialized. The cure is trivial - limit substring size.

> That immediately made me think he might have devised it for genomics research.

No, it wasn't. It was devised when I was preparing for Google interview (which I failed). And of cause algorithms which pre-index haystack will always be faster. I myself do not consider haystack pre-indexing algorithms a "text search" algorithms (maybe incorrectly).

> gross exaggeration

If you count pre-indexing algorithms and edge cases - then you are correct. For most common case - can you show me something faster (from a student or even yourself)?

Re: New string search algorithm

#52

Post by leif »

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

Universal hashing will prevent collision problems.

Re: New string search algorithm

#53

Post by leif »

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…

Asymptotic bounds can be given in the worst case, the best case, the average case ("in expectation"), or with high probability. All have rigorous definitions and you should go learn about them. There is nothing bastardized about this notation.

Re: New string search algorithm

#54

Post by leif »

mayank wrote: post #5
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 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

This is not an amortized analysis, it is a probabilistic analysis.

Re: New string search algorithm

#55

Post by leif »

pjscott wrote: post #13
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,…

I love how beautiful that median algorithm is. :-D

Re: New string search algorithm

#56

Post by lvvlvv »

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

I am the author. You are right. I've updated the page.

Re: New string search algorithm

#57

Post by cperciva »

anatoly wrote: post #48
kragen wrote: post #39

Earlier quoted context omitted.

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…

When that thread came up originally, I was intrigued by the idea of the dual-pivot quicksort, and went on to browse Robert Sedgewick's Ph.D. thesis, _Quicksort_, published in 1978. Sedgewick considers and analyzes several variants of quicksort in his thesis, and I've quickly discovered that he analyzes and dismisses the dual-pivot variant under a different name. I don't know whose analysis is better, but it does foll…

Times change. The relative cost of a compare is considerably higher now than it was in 1978, thanks to the cost of branch (mis)predictions.

It's entirely possible that a modification which was a significant loss in 1978 is a significant gain in 2008.

Re: New string search algorithm

#58

Post by epistasis »

dasht wrote: post #45
epistasis wrote: post #34

Earlier quoted context omitted.

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

Given a (not even very large) cluster, we (with the fairly brute force-ish but cleverly tuned NFA) can populate hash tables for the read-based NFA of your 2 billion needles just about as fast as you can transmit the data and give you optimal alignment (by flexible criteria) just about as fast as you can then stream through the 3 billion base pairs. We are down to, at most, single or double digit dollar differences ei…

You have just been shown an amazing invention: the BWT. Rather than dismiss it and the entire field of performance obsessed people that find it more useful than any hash based algorithm, perhaps you should study it. The speculation in your comment is laughable, from a cluster costing double digit dollar difference over a single machine, to sequence data being used in forensic DNA. Sure, you throw around some introductory jargon that may fool an outsider into thinking you know what you're talking about, and that's why I'm bothering to comment so that no one is deceived.

BWT =~ suffix tree with far far greater memory efficiency

Re: New string search algorithm

#59

Post by kragen »

cperciva wrote: post #57
anatoly wrote: post #48

Earlier quoted context omitted.

When that thread came up originally, I was intrigued by the idea of the dual-pivot quicksort, and went on to browse Robert Sedgewick's Ph.D. thesis, _Quicksort_, published in 1978. Sedgewick considers and analyzes several variants of quicksort in his thesis, and I've quickly discovered that he analyzes and dismisses the dual-pivot variant under a different name. I don't know whose analysis is better, but it does foll…

Times change. The relative cost of a compare is considerably higher now than it was in 1978, thanks to the cost of branch (mis)predictions. It's entirely possible that a modification which was a significant loss in 1978 is a significant gain in 2008.

Yes, but the number of comparisons and the number of swaps wouldn't change. Sedgewick and Yaroslavskiy can't both be right, unless anatoly misread something.

Re: New string search algorithm

#60

Post by cperciva »

kragen wrote: post #59
cperciva wrote: post #57

Earlier quoted context omitted.

Times change. The relative cost of a compare is considerably higher now than it was in 1978, thanks to the cost of branch (mis)predictions. It's entirely possible that a modification which was a significant loss in 1978 is a significant gain in 2008.

Yes, but the number of comparisons and the number of swaps wouldn't change. Sedgewick and Yaroslavskiy can't both be right, unless anatoly misread something.

Oops, I misread what he wrote.
Post reply on HN