New string search algorithm
volnitsky.com
New string search algorithm
1–10 of 63 posts
Re: New string search algorithm
#2This seems like a very practical website about the algorithm but where is the theory and proofs of the time complexity of the algorithm??
Re: New string search algorithm
#3No 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.
Re: New string search algorithm
#4From 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-averag...
Re: New string search algorithm
#5From 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.
Re: New string search algorithm
#6Skeptical 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.
Re: New string search algorithm
#7The 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).
Re: New string search algorithm
#8From 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
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.
Re: New string search algorithm
#9it 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.
Re: New string search algorithm
#10Pattern 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...