lev

README

lev

Simple go package to calculate the Levenshtein Distance between two strings.

Usage examples

Calculate edit distance between two strings

package main

import(
	"fmt"
	"github.com/finkf/lev"
)

func main() {
	var l lev.Lev
	d := l.EditDistance("abc", "abd")
	fmt.Printf("distance between %q and %q = %d", "abc", "abd", d)
}

Calculate the trace between two strings

package main

import(
	"fmt"
	"github.com/finkf/lev"
)

func main() {
	var l lev.Lev
	_, b := l.Trace("abc", "abd")
	fmt.Printf("trace of %q and %q = %s", "abc", "abd", b)
}

Calculate the alignment between two strings

package main

import(
	"fmt"
	"github.com/finkf/lev"
)

func main() {
	var l lev.Lev
	a, _ := l.Alignment(l.Trace("abc", "abd"))
	fmt.Printf("%s\n%s\n%s\n", a.S1, a.Trace, a.S2)
}

Documentation

Index

• Constants
• type Alignment
  • func NewAlignment(s1, s2, trace string) (Alignment, error)
• type Lev
  • func (l *Lev) Alignment(d int, b Trace) (Alignment, error)
  • func (l *Lev) EditDistance(s1, s2 string) int
  • func (l *Lev) String() string
  • func (l *Lev) Trace(s1, s2 string) (int, Trace)
• type Trace
  • func (b Trace) String() string
  • func (b Trace) Validate() error

Constants

const (
	// Del marks a deletion in s2.
	Del = byte('-')
	// Sub marks a substitution.
	Sub = byte('#')
	// Ins marks a insertion in s1.
	Ins = byte('+')
	// Nop marks a non-edit operation.
	Nop = byte('|')
	// Mis marks a missing character in s1 or s2.
	Mis = byte('~')
)

Types

type Alignment

type Alignment struct {
	S1, S2   []rune
	Trace    Trace
	Distance int
}

Alignment captures the alignment of two strings with the accoriding trace of edit operations.

func NewAlignment

func NewAlignment(s1, s2, trace string) (Alignment, error)

NewAlignment creates a new Alignment from two and a given trace. The error distance is calculated using the trace directly.

type Lev

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

Lev holds two aligned strings and the weight matrix.

func (*Lev) Alignment

func (l *Lev) Alignment(d int, b Trace) (Alignment, error)

Alignment returns the given alignment strings and the according trace.

func (*Lev) EditDistance

func (l *Lev) EditDistance(s1, s2 string) int

EditDistance calculates the minimal edit distance between the two given strings.

func (*Lev) String

func (l *Lev) String() string

String returns the matrix format of the last calculated edit distance.

func (*Lev) Trace

func (l *Lev) Trace(s1, s2 string) (int, Trace)

Trace returns the edit distance between the two given strings and the trace of the according edit operations.

type Trace

type Trace []byte

Trace defines an array of edit operations.

func (Trace) String

func (b Trace) String() string

func (Trace) Validate

func (b Trace) Validate() error

Validate returns an error if the trace is not valid.