Home
Reading
Searching
Subscribe
Sponsors
Statistics
Posting
Contact
Spam
Lists
Links
About
Hosting
Filtering
Features Download
Marketing
Archives
FAQ
Blog
 
Gmane
From: ChrisK <haskell <at> list.mightyreason.com>
Subject: Announcing Very Fast Searching of ByteStrings
Newsgroups: gmane.comp.lang.haskell.libraries
Date: Friday 17th August 2007 13:49:28 UTC (over 10 years ago)
Attached is the Boyer-Moore algorithm implemented for strict and lazy
bytestrings (and combinations thereof).  It finds all the overlapping
instances
of the pattern inside the target.

I have performance tuned it.  But the performance for searching a strict
bytestring is better then for a lazy bytestring (even if they only had a
single
strict chunk), which almost certainly means I was not clever enough to get
GHC
to produce the optimal code.

There is much more description in the module's haddock header.

Hopefully Don or other ByteString experts/maintainers can tweak this even
further.

Also attaches is a Knuth-Morris-Pratt module which find non-overlapping
instances and is slightly slower on my benchmarks.

Happy Searching,
  Chris Kuklewicz
 
CD: 4ms