edit-distance-0.2.2.1: Levenshtein and restricted Damerau-Levenshtein edit distances

Copyright | (C) 2010-2015 Maximilian Bolingbroke
License | BSD-3-Clause (see the file LICENSE)
Maintainer | Oleg Grenrus <oleg.grenrus@iki.fi>
Safe Haskell | Safe
Language | Haskell98

Text.EditDistance

Description

Computing the edit distances between strings

Synopsis

- data Costs a
  - = ConstantCost !Int
  - | VariableCost (a -> Int)
- data EditCosts = EditCosts {
  - deletionCosts :: Costs Char
  - insertionCosts :: Costs Char
  - substitutionCosts :: Costs (Char, Char)
  - transpositionCosts :: Costs (Char, Char)
  }
- defaultEditCosts :: EditCosts
- levenshteinDistance :: EditCosts -> String -> String -> Int
- restrictedDamerauLevenshteinDistance :: EditCosts -> String -> String -> Int

# Documentation

data Costs a Source #

Constructors

ConstantCost !Int |
VariableCost (a -> Int) |

data EditCosts Source #

Constructors

EditCosts |

Fields

- deletionCosts :: Costs Char

  Cost of deleting the specified character from the left string

- insertionCosts :: Costs Char

  Cost of inserting the specified characters into the right string

- substitutionCosts :: Costs (Char, Char)

  Cost of substituting a character from the left string with one from the right string -- with arguments in that order.

- transpositionCosts :: Costs (Char, Char)

  Cost of moving one character backwards and the other forwards -- with arguments in that order.

defaultEditCosts :: EditCosts Source #

levenshteinDistance :: EditCosts -> String -> String -> Int Source #

Find the Levenshtein edit distance between two strings. That is to say, the number of deletion, insertion and substitution operations that are required to make the two strings equal. Note that this algorithm therefore does not make use of the `transpositionCost` field of the costs. See also: http://en.wikipedia.org/wiki/Levenshtein_distance.

restrictedDamerauLevenshteinDistance :: EditCosts -> String -> String -> Int Source #

Find the "restricted" Damerau-Levenshtein edit distance between two strings. This algorithm calculates the cost of the so-called optimal string alignment, which does not always equal the appropriate edit distance. The cost of the optimal string alignment is the number of edit operations needed to make the input strings equal under the condition that no substring is edited more than once. See also: http://en.wikipedia.org/wiki/Damerau-Levenshtein_distance.