# edit-distance-linear

[![Build Status][travis-badge]][travis]
[![Hackage][hackage-badge]][hackage]

The pure Haskell implementation of the Levenshtein edit distance, with linear space complexity.

## Comparison

There are already several other existing implementations, but the goals and design decisions vary. In particular, this package is intended to be used to:
* compare long strings (think tens of thousands of characters), driving the implementation to live in the `ST` monad and aim at linear space complexity to lower GC pressure;
* not care about Unicode, thus accepting `ByteString`s and comparing them byte-by-byte rather than character-by-character (or glyph-by-glyph, or whatever is the right notion of an edit for Unicode).

Among the alternatives:
* [text-metrics](http://hackage.haskell.org/package/text-metrics) — uses a similar algorithm, but cares about Unicode, making it 4-5 times slower.
* [edit-distance](http://hackage.haskell.org/package/edit-distance) — uses a very different algorithm (which we might implement here one day with huge potential benefits), which tends to consume more memory (I'm not up for estimating its space asymptotics, though).

[travis]:        <https://travis-ci.org/0xd34df00d/edit-distance-linear>
[travis-badge]:  <https://travis-ci.org/0xd34df00d/edit-distance-linear.svg?branch=master>
[hackage]:       <https://hackage.haskell.org/package/edit-distance-linear>
[hackage-badge]: <https://img.shields.io/hackage/v/edit-distance-linear.svg>