tdl

README

Damerau-Levenshtein

Calculate and return the True Damerau–Levenshtein distance of string A and B.

See Issue #2 for a list of research papers used as a reference when implementing the algorithm and a minor struggle trying to verify the results.

Example

Install package:

    go get github.com/lmas/Damerau-Levenshtein

Get distance between string A and B:

    package main

    import (
            "fmt"
            tdl "github.com/lmas/Damerau-Levenshtein"
    )

    func main() {
            dist := tdl.Distance("CA", "ABC")
            fmt.Println(dist)
    }

Or if you want more performant code and want to avoid memory allocations:

    func main() {
            // Set a max length of 100 characters for strings A and B
            t := tdl.New(100)
            dist := t.Distance("CA", "ABC")
            fmt.Println(dist)
            dist := t.Distance("AC", "ABC")
            fmt.Println(dist)
    }

Take a look at the tests for more examples.

License

MIT License, see the LICENSE file.

Documentation

Overview

Package tdl implements the true Damerau–Levenshtein distance.

Reference: https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance#Distance_with_adjacent_transpositions

Index

• func Distance(a, b string) int
• type TrueDamerauLevenshtein
  • func New(maxSize int) *TrueDamerauLevenshtein
  • func (t *TrueDamerauLevenshtein) Distance(a, b string) int

Functions

func Distance

func Distance(a, b string) int

Distance is a shortcut func for doing a quick and dirty calculation, without having to set up your own struct and stuff. Not thread safe!

Types

type TrueDamerauLevenshtein

type TrueDamerauLevenshtein struct {
	// contains filtered or unexported fields
}

TrueDamerauLevenshtein is a struct that allocates memory only once, which is used when running Distance(). This whole struct and associated functions are not thread safe in any way, that will be the callers responsibility! At least for now...

func New

func New(maxSize int) *TrueDamerauLevenshtein

New initializes a new struct which allocates memory only once, to be used by Distance(). maxSize sets an upper limit for both input strings used in Distance().

func (*TrueDamerauLevenshtein) Distance

func (t *TrueDamerauLevenshtein) Distance(a, b string) int

Distance calculates and returns the true Damerau–Levenshtein distance of string A and B. It's the caller's responsibility if he wants to trim whitespace or fix lower/upper cases.

If either of string A or B is too large for the internal memory matrix, we will allocate a bigger matrix on the fly. If not, Distance() won't cause any other allocs.