Hackage :: [Package]

levenshtein: Calculate the edit distance between two foldables.

[ bsd3, library, tools ] [ Propose Tags ]

A package to determine the edit distance between two Foldables. These are converted to lists, and the Levenshtein distance determine how many additions, removals and changes are necessary to change the first list into the second list.

[Skip to Readme]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

Versions [RSS] 0.1.0.0, 0.1.1.0, 0.1.2.0, 0.1.3.0, 0.2.0.0, 0.2.1.0
Change log CHANGELOG.md
Dependencies base (>=4.7 && <5), binary (>=0.2), data-default-class (>=0.0.1), deepseq (>=1.4.3.0), hashable (>=1.2.7.0), QuickCheck [details]
License BSD-3-Clause
Copyright 2021 Willem Van Onsem
Author Willem Van Onsem
Maintainer hapytexteu+gh@gmail.com
Category tools
Home page https://github.com/hapytex/levenshtein#readme
Source repo head: git clone https://github.com/hapytex/levenshtein
Uploaded by wvanonsem90 at 2022-07-27T22:34:21Z
Distributions NixOS:0.2.1.0
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 654 total (31 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2022-07-27 [all 1 reports]

Readme for levenshtein-0.2.1.0

[back to package description]

levenshtein

Build Status of the package by GitHub actions Build Status of the package by Hackage Hackage version badge

Usage

The module Data.Foldable.Levenshtein exports a data type Edit that represent the possible ways to edit a list by Adding an element, Removing an element, Copying (do nothing with the element), and Swap with a new value.

One can apply such edits to a list with the applyEdits function, for example:

Prelude> applyEdits [Copy 1,Swap 3 4,Swap 0 2,Swap 2 5] [1,3,0,2]
Just [1,4,2,5]

We can also calculate the minimal list of edits necessary to turn one list into another one, for example:

Prelude> levenshtein [1,3,0,2] [1,4,2,5]
(3,[Copy 1,Swap 3 4,Swap 0 2,Swap 2 5])

here it means that the smallest edit distance is three, and that in order to transform [1,3,0,2] to [1,4,2,5] we copy 1 change 3 for 4, change 0 for 2, and change 2 for 5.

Package structure

The package contains one module: Data.Foldable.Levenshtein. This module provides functions to determine the edit distance and a list of edits to turn one Foldable of items to another Foldable of items. The foldables are first converted to a list, so the edits always eventually produce a list of edits, even if (one of) the Foldables is for example a Tree, Maybe, etc.

Besides the Edit object, the module exports three types of functions:

  1. functions that return the edit distance together with a list of reversed edits;
  2. functions that return the edit distance with a list of edits (not reversed); and
  3. functions that only calculate the edit distance, not the edits itself.

The third type is more an optimized version of the first two types since it will take less memory and finish slightly faster.

Some functions allow to specify the penalty for an insertion, deletion, and replacement, and this even per item.

In the table below, we show the different implementations to determine the Levenshtein distance:

Edits Eq Equality function Eq
penalty functions default
Normal genericLevenshtein genericLevenshtein' levenshtein' levenshtein
Reversed genericReversedLevenshtein genericReversedLevenshtein' reversedLevenshtein' reversedLevenshtein
Without genericLevenshteinDistance genericLevenshteinDistance' levenshteinDistance' levenshteinDistance

levenshtein is safe Haskell

The levenshtein package does not work with arrays, vectors, etc. but only vanilla lists, making this a safe package.

Contribute

You can contribute by making a pull request on the GitHub repository.

You can contact the package maintainer by sending a mail to hapytexeu+gh@gmail.com.