homepage: https://github.com/0xd34df00d/edit-distance-linear#readme
changelog-type: markdown
hash: 6b559d984a32aca47d44f2df8076239e479d542afb7ad16d13fe081bfa34499f
test-bench-deps:
  bytestring: -any
  edit-distance: -any
  base: ! '>=4.7 && <5'
  hspec: -any
  text: -any
  criterion: -any
  array: -any
  text-metrics: -any
  edit-distance-linear: -any
  QuickCheck: -any
maintainer: 0xd34df00d@gmail.com
synopsis: Efficient implementation Levenshtein distance in linear memory.
changelog: |
  # Changelog for edit-distance-linear

  ## v0.2.0.1

  * Made the test executable and the LLVM codegen optional.

  ## v0.2.0.0

  * Reimplemented with mutable arrays and rather low-level optimizations.

  ## v0.1.0.0

  * Initial implementation with Data.Vector.
basic-deps:
  bytestring: -any
  base: ! '>=4.7 && <5'
  array: -any
  edit-distance-linear: -any
all-versions:
- 0.2.0.1
author: Georg Rudoy
latest: 0.2.0.1
description-type: markdown
description: |
  # edit-distance-linear

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

  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>
license-name: BSD-3-Clause

Update from Hackage at 2019-12-07T22:57:31Z
Update from Hackage at 2019-12-07T22:57:31Z
