edit-distance

Levenshtein and restricted Damerau-Levenshtein edit distances

http://github.com/batterseapower/edit-distance

Version on this page:0.2.1.3
LTS Haskell 22.14:0.2.2.1@rev:1
Stackage Nightly 2024-03-29:0.2.2.1@rev:1
Latest on Hackage:0.2.2.1@rev:1

See all snapshots edit-distance appears in

BSD-3-Clause licensed by Max Bolingbroke
Maintained by [email protected]
This version can be pinned in stack with:edit-distance-0.2.1.3@sha256:fb4f17b4592f14b4bd8ff43916d8e1dccc5e8c2fe2f72673735a20c41bfc7c89,2799

Module documentation for 0.2.1.3

h1. Edit Distance Algorithms

You can help improve this README with extra snippets and advice by using the "GitHub wiki":http://github.com/batterseapower/edit-distance/wikis/readme.


h2. Installing

To just install the library:

<pre>
<code>runghc Setup.lhs configure
runghc Setup.lhs build
sudo runghc Setup.lhs install
</pre>
</code>

If you want to build the tests, to check it's all working:

<pre>
<code>runghc Setup.lhs configure -ftests
runghc Setup.lhs build
dist/build/edit-distance-tests/edit-distance-tests
</pre>
</code>


h2. Description

Edit distances algorithms for fuzzy matching. Specifically, this library provides:

* "Levenshtein distance":http://en.wikipedia.org/wiki/Levenshtein_distance
* "Restricted Damerau-Levenshtein distance":http://en.wikipedia.org/wiki/Damerau-Levenshtein_distance

They have been fairly heavily optimized. Indeed, for situations where one of the strings is under 64 characters long I use a rather neat "bit vector" algorithm: see "the authors paper":http://www.cs.uta.fi/~helmu/pubs/psc02.pdf and "the associated errata":[http://www.cs.uta.fi/~helmu/pubs/PSCerr.html for more information. The algorithms __could__ be faster, but they aren't yet slow enough to force me into improving the situation.


h2. Example

<pre>
<code>Text.EditDistance> levenshteinDistance defaultEditCosts "witch" "kitsch"
2</code>
</pre>


h2. Linkage

* "Hackage":http://hackage.haskell.org/cgi-bin/hackage-scripts/package/edit-distance
* "Bug Tracker":http://bsp.lighthouseapp.com/projects/14822-hs-edit-distance
* "GitHub":http://github.com/batterseapower/edit-distance