Knuth–Morris–Pratt algorithm • Hacker News Board

Re: Knuth–Morris–Pratt algorithm

#41

Post by mightybyte » Sun, Jul 06, 2014, 12:07 AM UTC

pedrocr wrote: post #35

mightybyte wrote: post #25

Earlier quoted context omitted.

IMO the Boyer-Moore string searching algorithm is way more elegant. Average case performance of O(n/m)?!? That means that the longer the string you're searching for the faster you can find it! It obviously makes perfect logical sense once you think about it, but when I first heard about the algorithm it seemed magical.

Wikipedia says Boyer Moore is O(n+m) which is the same as this algorithm. https://en.wikipedia.org/wiki/Boyer-Moore_string_search_algo...

That's worst case complexity. It's the average case where Boyer Moore wins over KMP.

Re: Knuth–Morris–Pratt algorithm

#42

Post by alayne » Sun, Jul 06, 2014, 12:08 AM UTC

xyzzyz wrote: post #33

alayne wrote: post #7

Earlier quoted context omitted.

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

Yes, but if something is O(m*n) and m <= n (which is the case in string search), then it's also O(n^2). On the other hand, since m can be of the order of, say, n/2, it's not too confusing to say that naive string search is O(n^2), since it's actually Theta(n^2).

Yes, you are right of course.

I really just meant that "in practice" the growth of the string length (m) varies independently and common cases behave more like O(n) than O(n^2). Also that naive search is probably heavily optimized with SSE assembly instructions and cache tuned. I have implemented several of these algorithms in C and it is difficult to impossible to beat C's strstr consistently with a simple implementation, even on cases that start to make the naive algorithm really inefficient.

You'd most likely need a hybrid approach to make a good general purpose string search function that is effective across many domains.

Re: Knuth–Morris–Pratt algorithm

#43

Post by platz » Sun, Jul 06, 2014, 1:02 AM UTC

chaoxu wrote: post #39

I have implemented KMP in Haskell. This version doesn't use any index! It is built purely functionally by realizing KMP's failure table is just a finite state automaton(well, almost...) However it is much longer than the C++ version... Code: https://github.com/Mgccl/haskell-algorithm/blob/master/KMP.h... Description: http://www.chaoxuprime.com/posts/2014-04-11-the-kmp-algorith... Actually, KMP is a little harder to p…

Looks like there's also a KMP implementation here specialized to ByteStrings: http://hackage.haskell.org/package/stringsearch

Re: Knuth–Morris–Pratt algorithm

#44

Post by sitkack » Sun, Jul 06, 2014, 2:14 AM UTC

techdebt5112 wrote: post #16

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.

Until they implement a JIT and compile the regex.

Re: Knuth–Morris–Pratt algorithm

#45

Post by waps » Sun, Jul 06, 2014, 3:14 AM UTC

rimantas wrote: post #20

alayne wrote: post #7

Earlier quoted context omitted.

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

It's the same when m=n.

Of course in string search it never is. In m=n case KMP would simply compare the first character, and if it doesn't match declare nothing was found.

Yes there'd be much more different instructions involved but I think KMP would start beating naive pretty quickly in the m=n case.

Re: Knuth–Morris–Pratt algorithm

#46

Post by freditup » Sun, Jul 06, 2014, 4:05 AM UTC

volaski wrote: post #13

Why is KMP on the front page of HN? Not complaining, just confused. Is this related to some other news?

I personally like this kind of submission. If it's something I was familiar with, then it's a good review/reminder; if it's something I was unfamiliar with, it's a good lesson.

Re: Knuth–Morris–Pratt algorithm

#47

Post by vidarh » Sun, Jul 06, 2014, 7:13 AM UTC

volaski wrote: post #13

Why is KMP on the front page of HN? Not complaining, just confused. Is this related to some other news?

In addition to all the other possible reasons, Knuth-Morris-Pratt was brought up just a few days ago, in the discussion on another article about a letter Knuth wrote about software patents.

Re: Knuth–Morris–Pratt algorithm

#48

Post by Intermernet » Sun, Jul 06, 2014, 1:35 PM UTC

Cieplak wrote: post #27

Here is the boost implementation: http://www.boost.org/doc/libs/1_55_0/libs/algorithm/doc/html...

Here's one in Go :-)

http://play.golang.org/p/chYGT69vBc

Re: Knuth–Morris–Pratt algorithm

#49

Post by techdebt5112 » Sun, Jul 06, 2014, 9:01 PM UTC

sitkack wrote: post #44

techdebt5112 wrote: post #16

Earlier quoted context omitted.

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.

Until they implement a JIT and compile the regex.

No, you're missing the point -- using a regex does not allow you to read in less than all of the input (in the best case, even). If you grep a 1GB file with a regex you must read 1GB from disk, no exceptions, and that's many orders of magnitude slower than anything on the CPU (or in memory). With Boyer-Moore you can do less than 100% of the file size in I/O, especially if the given pattern is long relative to the full text.

Re: Knuth–Morris–Pratt algorithm

#50

Post by sitkack » Sun, Jul 06, 2014, 11:30 PM UTC

techdebt5112 wrote: post #49

sitkack wrote: post #44

Earlier quoted context omitted.

Until they implement a JIT and compile the regex.

No, you're missing the point -- using a regex does not allow you to read in less than all of the input (in the best case, even). If you grep a 1GB file with a regex you must read 1GB from disk, no exceptions, and that's many orders of magnitude slower than anything on the CPU (or in memory). With Boyer-Moore you can do less than 100% of the file size in I/O, especially if the given pattern is long relative to the ful…

We have no context to the environment that those regexs are running. For all we know they could have implicit limits and be getting compiled down to FPGAs. I can guarantee you that those regexs aren't running unbounded.

No point was missed.