Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.Vector.Distance

Contents

Types
Operations
Example

Description

This module implements a variation on the Wagner-Fischer algorithm to find the shortest sequences of operations which transforms one vector of values into another.

Synopsis

data Params v o c = Params {
- equivalent :: v -> v -> Bool
- delete :: Int -> v -> o
- insert :: Int -> v -> o
- substitute :: Int -> v -> v -> o
- cost :: o -> c
- positionOffset :: o -> Int
}
type ChangeMatrix o c = Vector (c, [o])
leastChanges :: (Monoid c, Ord c) => Params v o c -> Vector v -> Vector v -> (c, [o])
allChanges :: (Monoid c, Ord c) => Params v o c -> Vector v -> Vector v -> ChangeMatrix o c
strParams :: Params Char (String, Int, Char) (Sum Int)

Types

data Params v o c Source #

Operations invoked by the Wagner-Fischer algorithm.

The parameters to this type are as follows:

v is the type of values being compared,
o is the type representing operations,
c is the type representing costs.

The chief restrictions on these type parameters is that the cost type c must have instances of Monoid and Ord. A good default choice might be the type (Sum Int).

Constructors

Params
Fields equivalent :: v -> v -> Bool Are two values equivalent? delete :: Int -> v -> o Delete the element at an index. insert :: Int -> v -> o Insert an element at an index. substitute :: Int -> v -> v -> o Substitute an element at an index. cost :: o -> c Cost of a change. positionOffset :: o -> Int Positions to advance after a change. E.g. `0` for a deletion.

type ChangeMatrix o c = Vector (c, [o]) Source #

Matrix of optimal edit scripts and costs for all prefixes of two vectors.

This is a representation of the n * m dynamic programming matrix constructed by the algorithm. The matrix is stored in a Vector in row-major format with an additional row and column corresponding to the empty prefix of the source and destination Vectors.

Operations

leastChanges Source #

Arguments

:: (Monoid c, Ord c)
=> Params v o c
-> Vector v	"Source" vector.
-> Vector v	"Destination" vector.
-> (c, [o])

O(nm). Find the cost and optimal edit script to transform one Vector into another.

allChanges Source #

Arguments

:: (Monoid c, Ord c)
=> Params v o c
-> Vector v	"Source" vector.
-> Vector v	"Destination" vector.
-> ChangeMatrix o c

O(nm). Calculate the complete matrix of edit scripts and costs between two vectors.

Example

strParams :: Params Char (String, Int, Char) (Sum Int) Source #

Example Params to compare (Vector Char) values.

The algorithm will produce edit distances in terms of (Sum Int) and edit scripts containing (String, Int, Char) values.

The first component of each operation is either "delete", "insert", or "replace".