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

Knuth–Morris–Pratt algorithm

en.wikipedia.org

Post reply on HN
Print view View original

11–20 of 50 posts

Re: Knuth–Morris–Pratt algorithm

#11

Post by IsTom »

yxhuvud wrote: post #10
mavam wrote: post #5

KMP starts with the first character of the pattern (or substring/needle) and then jumps forward by the length of the mismatch. A related algorithm is Boyer-Moore (BM)( http://en.wikipedia.org/wiki/Boyer–Moore_string_search_algor... ), which operates the other way round: it begins with the last character of the pattern and then compares backwards until the full pattern matches. The advantage of BM is that it allows fo…

One difference is that BM is O(m*n) while KMP is O(n + m). Depending on how the input string looks like, this can matter - especially in small alphabets where the likelihood of pattern repeating themselves are bigger.

BM is too provably O(n + m) (and without dependence on alphabet size unlike KMP) if you apply two heurestics that I don't really remember. For some reason it's not mentioned on wikipedia.

Re: Knuth–Morris–Pratt algorithm

#12

Post by noir_lord »

foobarian wrote: post #8
jiggy2011 wrote: post #3

Earlier quoted context omitted.

That's the risk with interview questions, that the candidate suggests a better solution that the interviewer anticipated. Leaving the interviewer with the task of ascertaining whether the solution is correct.

I love to be surprised like that in interviews, let me tell you. Makes my decision much easier.

> Makes my decision much easier.

You didn't say which way, I've worked with and for people who wouldn't hire someone smarter than them, the human psyche is a dark place.

Re: Knuth–Morris–Pratt algorithm

#15

Post by robert_tweed »

bitL wrote: post #9
ekr wrote: post #6

Earlier quoted context omitted.

The time complexity of KMP is O(n), while the complexity of your idea is O(n^2). Considering the fact that KMP is not even doing a lot of things in its inner loop, (few memory accesses), a rep cmpsb approach is really no match for it, even in the trivial cases. So no, it's much faster.

I know about the time complexity, but my argument points to the CPU architecture and cache/branch prediction efficiency. KMP has a lot of branching which is more expensive than a simple cache (line) hit, cache REP CMPSx doesn't have any branching, aborts immediately after a mismatch with only a single loop over the starting position, search is also pretty much linear. This is not a Turing machine where it is being ex…

As with most optimisations the only way to be sure is to try it. Big-O complexity says very little about actual runtime on real-world data.

Re: Knuth–Morris–Pratt algorithm

#16

Post by techdebt5112 »

bitL wrote: post #4

KMP is conceptually very cool, as well as other clever string searching algorithms (BM, RK, AC), though one of the questions for me always was if even its most efficient implementation wouldn't be always slower than executing a brute-force combination of REP CMPSL/CMPSB instructions (x86) for vast majority of searched strings?

If you don't have the entire string in memory then Boyer-Moore is usually fastest because you can avoid doing a lot of I/O (since you skip comparing many subsequences, you don't have to read those subsequences in the first place). This is why grep is very fast given a static string pattern to search for, even on huge files, but grepping for a regex is dog slow.

Re: Knuth–Morris–Pratt algorithm

#17

Post by taeric »

jiggy2011 wrote: post #3
kevingadd wrote: post #2

I've always liked the elegance of this algorithm, fun little example of how you can make things incredibly fast by thinking about your problem. And a related anecdote: I was interviewing at Apple for a systems development related role (graphics drivers, I think?) and one of the senior-level folks asked me to write strstr on the whiteboard. I started with a naive, working implementation, then he asked me how I'd optim…

That's the risk with interview questions, that the candidate suggests a better solution that the interviewer anticipated. Leaving the interviewer with the task of ascertaining whether the solution is correct.

This story is borderline baffling, though. If you flat out named the algorithm and it contains a famous name like Knuth, that should be good enough to go. That you may not have all of the points of it memorized is irrelevant.

Now, if you name a very obscurely named algorithm, that is one thing. But seriously, Knuth!? Is anyone involved with optimizations and serious algorithm design not aware of that name?

Re: Knuth–Morris–Pratt algorithm

#18

Post by dalke »

bitL wrote: post #9
ekr wrote: post #6

Earlier quoted context omitted.

The time complexity of KMP is O(n), while the complexity of your idea is O(n^2). Considering the fact that KMP is not even doing a lot of things in its inner loop, (few memory accesses), a rep cmpsb approach is really no match for it, even in the trivial cases. So no, it's much faster.

I know about the time complexity, but my argument points to the CPU architecture and cache/branch prediction efficiency. KMP has a lot of branching which is more expensive than a simple cache (line) hit, cache REP CMPSx doesn't have any branching, aborts immediately after a mismatch with only a single loop over the starting position, search is also pretty much linear. This is not a Turing machine where it is being ex…

This depends completely on your needle and your haystack. If it's the string "ABC" in "QABC" then certainly the naive algorithm will be the fastest.

"Mechanical sympathy" unfortunately is easily misinterpreted to mean to only listen to the machine. Remember though that Martin Thompson is alluding to Jackie Stewart and Formula One racing. All of the cars competed on the same track. But you wouldn't enter a Formula One car for the Baja 1000.

In fact, I don't think you should use term unless you have a specific goal in mind. KMP is only best for certain classes of searches. Boyer-Moore is used for others. And there are plenty of other algorithms with there own pros and cons. See http://www-igm.univ-mlv.fr/~lecroq/string/index.html for descriptions.

Python, for example, uses (or used?) the algorithm described at http://effbot.org/zone/stringlib.htm , for the reasons listed therein.

Re: Knuth–Morris–Pratt algorithm

#19

Post by jasode »

IsTom wrote: post #11
yxhuvud wrote: post #10

Earlier quoted context omitted.

One difference is that BM is O(m*n) while KMP is O(n + m). Depending on how the input string looks like, this can matter - especially in small alphabets where the likelihood of pattern repeating themselves are bigger.

BM is too provably O(n + m) (and without dependence on alphabet size unlike KMP) if you apply two heurestics that I don't really remember. For some reason it's not mentioned on wikipedia.

Turbo BM?

http://www-igm.univ-mlv.fr/~lecroq/string/node15.html

Re: Knuth–Morris–Pratt algorithm

#20

Post by rimantas »

alayne wrote: post #7
ekr wrote: post #6

Earlier quoted context omitted.

The time complexity of KMP is O(n), while the complexity of your idea is O(n^2). Considering the fact that KMP is not even doing a lot of things in its inner loop, (few memory accesses), a rep cmpsb approach is really no match for it, even in the trivial cases. So no, it's much faster.

O(m*n) is not the same as O(n^2).

It's the same when m=n.
Post reply on HN