edit-distance-vector: Calculate edit distances and edit scripts between vectors.

[ algorithms, bsd3, data, data-structures, library ] [ Propose Tags ]

An implementation of the Wagner–Fischer dynamic programming algorithm to find the optimal edit script and cost between two sequences.

The implementation in this package is specialised to sequences represented with Data.Vector but is otherwise agnostic to:

  • The type of values in the vectors;

  • The type representing edit operations; and

  • The type representing the cost of operations.


[Skip to Readme]

Modules

[Index]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 1.0, 1.0.0.1, 1.0.0.2, 1.0.0.3, 1.0.0.4
Change log CHANGELOG.md
Dependencies base (>=4.7 && <4.8), vector (>=0.8) [details]
License BSD-3-Clause
Copyright (c) 2015 Thomas Sutton and others.
Author Thomas Sutton
Maintainer me@thomas-sutton.id.au
Category Data, Data Structures, Algorithms
Home page https://github.com/thsutton/edit-distance-vector
Source repo head: git clone https://github.com/thsutton/edit-distance-vector
Uploaded by ThomasSutton at 2015-04-03T09:22:04Z
Distributions Arch:1.0.0.4, Debian:1.0.0.4, LTSHaskell:1.0.0.4, NixOS:1.0.0.4, Stackage:1.0.0.4
Reverse Dependencies 3 direct, 8 indirect [details]
Downloads 6782 total (41 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2015-04-03 [all 1 reports]

Readme for edit-distance-vector-1.0

[back to package description]

Edit Distance: Vector

Build Status

This is a small library for calculating the edit distance and edit script between two vectors. It is generic enough that you should be able to use it with vectors containing values of any type you like, with changes described by any type you like, and with costs represented by any type you like (with a few restrictions).

Installing

The edit-distance-vector package is a normal Haskell library and can be installed using the Cabal package management tool.

cabal update
cabal install edit-distance-vector

Usage

The interface to edit-distance-vector is very small; just import Data.Vector.Distance, create a Params value with the correct operations to deal with your types, and pass this to leastChanges along with your Vectors.

import qualified Data.Vector as V
import           Data.Vector.Distance

-- | Editing vectors of 'Char' values, with '(String, Int, Char)' describing
--   changes, and the additive monoid of 'Int' describing costs.
str :: Params Char (String, Int, Char) (Sum Int)
str = Params
    { equivalent = (==)
    , delete i c = ("delete", i, c)
    , insert i c = ("insert", i, c)
    , substitute i c c' = ("replace", i, c')
    , cost _ = 1
    , positionOffset (op,_,_) | op == "delete" = 0
                              | otherwise      = 1
    }

main :: IO ()
main = do
    print $ leastChanges str (V.fromList "I am thomas")
                             (V.fromList "My name is Thomas")