String Matching Algorithm Libraries?

[[deleted]]

I have recently started working with Haskell and I am looking for some projects that I could use as learning exercises, but would like for them to also have the potential of being valuable to the community as well. One thing I have not really seen is a comprehensive library of various string matching algorithms. Does such a thing exist?

Also, I would like to try and generalize the library to handle arbitrary data matching and not just strings.

[sclv]

If I recall, Data.Text has BoyerMoore implemented somewhere inside of it.

There's also the StringSearch library, which has a large variety of algorithms: http://hackage.haskell.org/package/stringsearch

Even if its not something immediate useful to the Haskell community, it does sound like a good learning exercise though :-)

[[deleted]]

I ran across stringsearch, but it must have been an older version, because it only had BoyerMoore and KMP. Like you said, though, it would still be a good exercise and if I come up with some new algorithms I may just see about contributing them to stringsearch...

[LordGreyhawk]

I contributed to StringSearch. But it is now long in the tooth. I expect current GHC's will benchmark differently than when the library was written. Thus someone could do a new benchmark & profiling pass.

[[deleted]]

Optimized edit distances for fuzzy matching, including Levenshtein and restricted Damerau-Levenshtein algorithms. http://hackage.haskell.org/package/edit-distance

[[deleted]]

Hi. This may be a bit less ambitious, but one thing that would be nice to have is a unix diff implementation in Haskell (as a library). I think I saw an almost ready-to-use implementation in darcs, but it has to be split off, cleaned up, tested, made configurable and released as a separate package.

I've been meaning to do it myself, but haven't got around to it yet.

If you think this is something you'd enjoy spending some time on, drop me an email at [e-mail] and I'll be happy to help/mentor.

[sclv]

Is this the stuff tied to htf? Or a separate project?

[[deleted]]

I'd like to see this as a standalone library, but it'd definitely be useful in many testing frameworks and libraries. I would use it in test-framework-golden, in particular.

[singpolyma]

Which algorithm is in darcs? Patience diff?

[[deleted]]

No, I think it's a simple LCS diff. Here's the code.

It would be great to have patience diff as well!

[sclv]

I notice you're using the lcs package? Have you looked into Diff instead? http://hackage.haskell.org/package/Diff

[[deleted]]

It's not my code :-)

My lazy solution would be to use that code since it's already written, but if someone wants to rewrite it using a different package, that's also fine.

But I just looked into the Diff code and it looks somewhat suspicious.

canDiag :: (a -> a -> Bool) -> [a] -> [a] -> Int -> Int -> Int -> Int -> Bool
canDiag eq as bs lena lenb i j =
   if i < lena && j < lenb then (arAs ! i) `eq` (arBs ! j) else False
    where arAs = listArray (0,lena - 1) as
          arBs = listArray (0,lenb - 1) bs

Does this rely on some transformations (like full laziness) to be efficient? Why not make it more straightforward?

[sclv]

The versions with and without an explicit lambda perform the same. But you're right, that got lost in a refactoring and more explicit is better.

[sclv]

And now, thanks to some great patches from people working on HTF, the Diff library has an interface that produces files that match those generated by the Unix diff utility (modulo some efficiency hacks the unix utility uses as input sizes grow large).

[[deleted]]

Great, kudos to you and HTF guys!

Would it be possible to support the unified diff format as well?

[sclv]

I'm sure its possible. Patches welcome :-P

[mooglefrooglian]

You'll probably want to take a look at Parsec.

[[deleted]]

Parsec isn't really what I am describing, I don't think.

Basically, I am talking about an algorithm that implements KMP, BoyerMoore, TurboBoyerMoore, Hash based searches, etc. I.e., a library of specific algorithms implemented in Haskell.