lsdp

README

go-lsd-parametrized

Calculate Leveshtein Distance by specific parameters written in Go.

godoc

Usage

package main

import (
    "fmt"

    . "github.com/deltam/go-lsd-parametrized"
)

func main() {
    a, b := "kitten", "shitting"
    fmt.Printf("compare string: %s, %s\n", a, b)

    // standard
    fmt.Printf("standard = %d\n", Lsd(a, b))

    // weighted
    wd := Weights{Insert: 0.1, Delete: 1, Replace: 0.01}
    fmt.Printf("weighted = %f\n", wd.Distance(a, b))

    // weighted and normalized
    nd := Normalized(wd)
    fmt.Printf("normalized = %f\n", nd.Distance(a, b))

    // weighted by rune
    wr := ByRune(&Weights{1, 1, 1}).
        Insert("g", 0.1).
        Insert("h", 0.01).
        Replace("k", "s", 0.001).
        Replace("e", "i", 0.0001)
    fmt.Printf("rune weight = %f\n", wr.Distance(a, b))
}

$ go run main.go
compare string: kitten, shitting
standard = 4
weighted = 0.220000
normalized = 0.027500
rune weight = 0.111100

Custom Distance

type LengthDiff struct{}

func (_ LengthDiff) Distance(a, b string) float64 {
    d := utf8.RuneCountInString(a) - utf8.RuneCountInString(b)
    return math.Abs(float64(d))
}

func main() {
    d := LengthDiff{}
    fmt.Println(d.Distance("kitten", "shitting"))
    // Output:
    // 2

    group := []string{"", "a", "ab", "abc"}
    s, dist := lsdp.Nearest(d, "xx", group)
    fmt.Println(s, dist)
    // Output:
    // ab 0
}

Use Case

• Clastering error messages

License

MIT License

Documentation

Overview

Package lsdp is a Levenshtein distance and its extended interface

Index

• func DistanceAll(dm DistanceMeasurer, orig string, strs []string) []float64
• func Lsd(a, b string) int
• func Nearest(dm DistanceMeasurer, raw string, subjects []string) (nearest string, distance float64)
• type DistanceMeasurer
  • func Normalized(dm DistanceMeasurer) DistanceMeasurer
• type EditCounts
  • func CountEdit(a, b string) (int, EditCounts)
  • func (ec EditCounts) Get(t EditType) int
• type EditType
• type LevenshteinParam
  • func (p LevenshteinParam) Distance(a, b string) float64
• type Weights
  • func (w Weights) Distance(a, b string) float64
• type WeightsByRune
  • func ByRune(w *Weights) *WeightsByRune
  • func (wr *WeightsByRune) Delete(runeGroup string, delCost float64) *WeightsByRune
  • func (wr *WeightsByRune) Distance(a, b string) float64
  • func (wr *WeightsByRune) Insert(runeGroup string, insCost float64) *WeightsByRune
  • func (wr *WeightsByRune) Replace(runeGroupSrc, runeGroupDest string, repCost float64) *WeightsByRune

Examples

• ByRune
• DistanceAll
• Nearest
• Weights.Distance

Functions

func DistanceAll

func DistanceAll(dm DistanceMeasurer, orig string, strs []string) []float64

DistanceAll returns slice of distance orig to each strs

Example

std := lsdp.Weights{1, 1, 1}
group := []string{"apple", "orange", "lemon", "melon"}
fmt.Println(lsdp.DistanceAll(std, "lon", group))

Output:
[5 5 2 2]

func Lsd

func Lsd(a, b string) int

Lsd returns standard Levenshtein distance

func Nearest

func Nearest(dm DistanceMeasurer, raw string, subjects []string) (nearest string, distance float64)

Nearest returns the nearest string in the specified distance measurer

Example

std := lsdp.Weights{1, 1, 1}
group := []string{"apple", "orange", "lemon", "melon"}
fmt.Println(lsdp.Nearest(std, "lon", group))

Output:
melon 2

Types

type DistanceMeasurer

type DistanceMeasurer interface {
	Distance(string, string) float64
}

DistanceMeasurer provides measurement of the distance between 2 strings

func Normalized

func Normalized(dm DistanceMeasurer) DistanceMeasurer

Normalized returns what wrapped the DistanceMeasurer with nomalize by string length

type EditCounts

type EditCounts [4]int

EditCounts represents aggregating by editing types

func CountEdit

func CountEdit(a, b string) (int, EditCounts)

CountEdit aggregates the minimum number of edits to change from a to b

func (EditCounts) Get

func (ec EditCounts) Get(t EditType) int

Get the number of specified edit

type EditType

type EditType int

EditType represents authorized editing means in Levenshtein distance

const (
	INSERT EditType = iota
	DELETE
	REPLACE
	NONE
)

Authorized editing means: insert, delete, replace, none

type LevenshteinParam

type LevenshteinParam struct {
	Insert  float64
	Delete  float64
	Replace float64
}

LevenshteinParam represents Levenshtein distance parameters for weighted by edit counts

func (LevenshteinParam) Distance

func (p LevenshteinParam) Distance(a, b string) float64

Distance returns Levenshtein distance

type Weights

type Weights struct {
	Insert  float64
	Delete  float64
	Replace float64
}

Weights represents cost parameters for weighted Levenshtein distance

func (Weights) Distance

func (w Weights) Distance(a, b string) float64

Distance returns weighted Levenshtein distance

Example

wd := lsdp.Weights{Insert: 0.1, Delete: 1, Replace: 0.01}
fmt.Println(wd.Distance("kitten", "shitting"))

Output:
0.22

type WeightsByRune

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

WeightsByRune represents weighted levenshtein distance by rune

func ByRune

func ByRune(w *Weights) *WeightsByRune

ByRune returns weighted levenshtein distance by rune

Example

wr := lsdp.ByRune(&lsdp.Weights{1, 1, 1}).
	Insert("a", 0.1).
	Delete("b", 0.01).
	Replace("c", "d", 0.001)
fmt.Println(wr.Distance("bc", "ad"))

Output:
0.111

func (*WeightsByRune) Delete

func (wr *WeightsByRune) Delete(runeGroup string, delCost float64) *WeightsByRune

Delete specify cost by delete rune

func (*WeightsByRune) Distance

func (wr *WeightsByRune) Distance(a, b string) float64

Distance returns weighted levenshtein distance by rune

func (*WeightsByRune) Insert

func (wr *WeightsByRune) Insert(runeGroup string, insCost float64) *WeightsByRune

Insert specify cost by insert rune

func (*WeightsByRune) Replace

func (wr *WeightsByRune) Replace(runeGroupSrc, runeGroupDest string, repCost float64) *WeightsByRune

Replace specify cost by replace rune