edlib

README

Go-edlib : Edit distance and string comparison library

Golang string comparison and edit distance algorithms library featuring : Levenshtein, LCS, Hamming, Damerau levenshtein (OSA and Adjacent transpositions algorithms), Jaro-Winkler, Cosine, etc...

---

Table of Contents

• Requirements
• Introduction
• Features
• Installation
• Benchmarks
• Documentation
• Examples
• Author
• Contributing
• License

---

Requirements

• Go (v1.13+)

Introduction

Golang open-source library which includes most (and soon all) edit-distance and string comparision algorithms with some extra!
Designed to be fully compatible with Unicode characters!
This library is 100% test covered 😁

Features

• Levenshtein
• LCS (Longest common subsequence) with edit distance, backtrack and diff functions
• Hamming
• Damerau-Levenshtein, with following variants:
  • OSA (Optimal string alignment)
  • Adjacent transpositions
• Jaro & Jaro-Winkler similarity algorithms
• Cosine Similarity
• Jaccard Index
• QGram
• Sorensen-Dice
• Computed similarity percentage functions based on all available edit distance algorithms in this lib
• Fuzzy search functions based on edit distance with unique or multiples strings output
• Unicode compatibility 🥳

Benchmarks

You can check an interactive Google chart with few benchmark cases for all similarity algorithms in this library through StringsSimilarity function here

However, if you want or need more details, you can also viewing benchmark raw output here, which also includes memory allocations and test cases output (similarity result and errors).

If you are on Linux and want to run them on your setup, you can run ./tests/benchmark.sh script.

Installation

Open bash into your project folder and run:

go get github.com/hbollon/go-edlib

And import it into your project:

import (
	"github.com/hbollon/go-edlib"
)

Run tests

If you are on Linux and want to run all unit tests just run ./tests/tests.sh script.

For Windows users you can run:

go test ./... # Add desired parameters to this command if you want

Documentation

You can find all the documentation here : Documentation

Examples

Calculate string similarity index between two string

You can use StringSimilarity(str1, str2, algorithm) function. algorithm parameter must one of the following constants:

// Algorithm identifiers
const (
	Levenshtein Algorithm = iota
	DamerauLevenshtein
	OSADamerauLevenshtein
	Lcs
	Hamming
	Jaro
	JaroWinkler
	Cosine
)

Example with levenshtein:

res, err := edlib.StringsSimilarity("string1", "string2", edlib.Levenshtein)
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("Similarity: %f", res)
}

Execute fuzzy search based on string similarity algorithm

1. Most matching unique result without threshold

You can use FuzzySearch(str, strList, algorithm) function.

strList := []string{"test", "tester", "tests", "testers", "testing", "tsting", "sting"}
res, err := edlib.FuzzySearch("testnig", strList, edlib.Levenshtein)
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("Result: %s", res)
}

Result: testing 

2. Most matching unique result with threshold

You can use FuzzySearchThreshold(str, strList, minSimilarity, algorithm) function.

strList := []string{"test", "tester", "tests", "testers", "testing", "tsting", "sting"}
res, err := edlib.FuzzySearchThreshold("testnig", strList, 0.7, edlib.Levenshtein)
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("Result for 'testnig': %s", res)
}

res, err = edlib.FuzzySearchThreshold("hello", strList, 0.7, edlib.Levenshtein)
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("Result for 'hello': %s", res)
}

Result for 'testnig': testing
Result for 'hello':

3. Most matching result set without threshold

You can use FuzzySearchSet(str, strList, resultQuantity, algorithm) function.

strList := []string{"test", "tester", "tests", "testers", "testing", "tsting", "sting"}
res, err := edlib.FuzzySearchSet("testnig", strList, 3, edlib.Levenshtein)
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("Results: %s", strings.Join(res, ", "))
}

Results: testing, test, tester 

4. Most matching result set with threshold

You can use FuzzySearchSetThreshold(str, strList, resultQuantity, minSimilarity, algorithm) function.

strList := []string{"test", "tester", "tests", "testers", "testing", "tsting", "sting"}
res, err := edlib.FuzzySearchSetThreshold("testnig", strList, 3, 0.5, edlib.Levenshtein)
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("Result for 'testnig' with '0.5' threshold: %s", strings.Join(res, " "))
}

res, err = edlib.FuzzySearchSetThreshold("testnig", strList, 3, 0.7, edlib.Levenshtein)
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("Result for 'testnig' with '0.7' threshold: %s", strings.Join(res, " "))
}

Result for 'testnig' with '0.5' threshold: testing test tester
Result for 'testnig' with '0.7' threshold: testing

Get raw edit distance (Levenshtein, LCS, Damerau–Levenshtein, Hamming)

You can use one of the following function to get an edit distance between two strings :

• LevenshteinDistance(str1, str2)
• DamerauLevenshteinDistance(str1, str2)
• OSADamerauLevenshteinDistance(str1, str2)
• LCSEditDistance(str1, str2)
• HammingDistance(str1, str2)

Example with Levenshtein distance:

res := edlib.LevenshteinDistance("kitten", "sitting")
fmt.Printf("Result: %d", res)

Result: 3

LCS, LCS Backtrack and LCS Diff

1. Compute LCS(Longuest Common Subsequence) between two strings

You can use LCS(str1, str2) function.

lcs := edlib.LCS("ABCD", "ACBAD")
fmt.Printf("Length of their LCS: %d", lcs)

Length of their LCS: 3

2. Backtrack their LCS

You can use LCSBacktrack(str1, str2) function.

res, err := edlib.LCSBacktrack("ABCD", "ACBAD")
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("LCS: %s", res)
}

LCS: ABD

3. Backtrack all their LCS

You can use LCSBacktrackAll(str1, str2) function.

res, err := edlib.LCSBacktrackAll("ABCD", "ACBAD")
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("LCS: %s", strings.Join(res, ", "))
}

LCS: ABD, ACD

4. Get LCS Diff between two strings

You can use LCSDiff(str1, str2) function.

res, err := edlib.LCSDiff("computer", "houseboat")
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("LCS: \n%s\n%s", res[0], res[1])
}

LCS Diff: 
 h c o m p u s e b o a t e r
 + -   - -   + + + + +   - -

Author

👤 Hugo Bollon

• Github: @hbollon
• LinkedIn: @Hugo Bollon
• Portfolio: hugobollon.me

🤝 Contributing

Contributions, issues and feature requests are welcome!
Feel free to check issues page.

Show your support

Give a ⭐️ if this project helped you!

📝 License

Copyright © 2020 Hugo Bollon.
This project is MIT License licensed.

Documentation

Index

• func CosineSimilarity(str1, str2 string, splitLength int) float32
• func DamerauLevenshteinDistance(str1, str2 string) int
• func FuzzySearch(str string, strList []string, algo Algorithm) (string, error)
• func FuzzySearchSet(str string, strList []string, quantity int, algo Algorithm) ([]string, error)
• func FuzzySearchSetThreshold(str string, strList []string, quantity int, minSim float32, algo Algorithm) ([]string, error)
• func FuzzySearchThreshold(str string, strList []string, minSim float32, algo Algorithm) (string, error)
• func HammingDistance(str1, str2 string) (int, error)
• func JaccardSimilarity(str1, str2 string, splitLength int) float32
• func JaroSimilarity(str1, str2 string) float32
• func JaroWinklerSimilarity(str1, str2 string) float32
• func LCS(str1, str2 string) int
• func LCSBacktrack(str1, str2 string) (string, error)
• func LCSBacktrackAll(str1, str2 string) ([]string, error)
• func LCSDiff(str1, str2 string) ([]string, error)
• func LCSEditDistance(str1, str2 string) int
• func LevenshteinDistance(str1, str2 string) int
• func OSADamerauLevenshteinDistance(str1, str2 string) int
• func QgramDistance(str1, str2 string, splitLength int) int
• func QgramDistanceCustomNgram(splittedStr1, splittedStr2 map[string]int) int
• func QgramSimilarity(str1, str2 string, splitLength int) float32
• func Shingle(s string, k int) map[string]int
• func ShingleSlice(s string, k int) []string
• func SorensenDiceCoefficient(str1, str2 string, splitLength int) float32
• func StringsSimilarity(str1 string, str2 string, algo Algorithm) (float32, error)
• type Algorithm

Functions

func CosineSimilarity

func CosineSimilarity(str1, str2 string, splitLength int) float32

CosineSimilarity use cosine algorithm to return a similarity index between string vectors Takes two strings as parameters, a split length which define the k-gram single length (if zero split string on whitespaces) and return an index.

func DamerauLevenshteinDistance

func DamerauLevenshteinDistance(str1, str2 string) int

DamerauLevenshteinDistance calculate the distance between two string This algorithm computes the true Damerau–Levenshtein distance with adjacent transpositions Allowing insertions, deletions, substitutions and transpositions to change one string to the second Compatible with non-ASCII characters

func FuzzySearch

func FuzzySearch(str string, strList []string, algo Algorithm) (string, error)

FuzzySearch realize an approximate search on a string list and return the closest one compared to the string input

func FuzzySearchSet

func FuzzySearchSet(str string, strList []string, quantity int, algo Algorithm) ([]string, error)

FuzzySearchSet realize an approximate search on a string list and return a set composed with x strings compared to the string input sorted by similarity with the base string. Takes the a quantity parameter to define the number of output strings desired (For example 3 in the case of the Google Keyboard word suggestion).

func FuzzySearchSetThreshold

func FuzzySearchSetThreshold(str string, strList []string, quantity int, minSim float32, algo Algorithm) ([]string, error)

FuzzySearchSetThreshold realize an approximate search on a string list and return a set composed with x strings compared to the string input sorted by similarity with the base string. Take a similarity threshold in parameter. Takes the a quantity parameter to define the number of output strings desired (For example 3 in the case of the Google Keyboard word suggestion). Takes also a threshold parameter for similarity with base string.

func FuzzySearchThreshold

func FuzzySearchThreshold(str string, strList []string, minSim float32, algo Algorithm) (string, error)

FuzzySearchThreshold realize an approximate search on a string list and return the closest one compared to the string input. Takes a similarity threshold in parameter.

func HammingDistance

func HammingDistance(str1, str2 string) (int, error)

HammingDistance calculate the edit distance between two given strings using only substitutions Return edit distance integer and an error

func JaccardSimilarity

func JaccardSimilarity(str1, str2 string, splitLength int) float32

JaccardSimilarity compute the jaccard similarity coeffecient between two strings Takes two strings as parameters, a split length which define the k-gram single length (if zero split string on whitespaces) and return an index.

func JaroSimilarity

func JaroSimilarity(str1, str2 string) float32

JaroSimilarity return a similarity index (between 0 and 1) It use Jaro distance algorithm and allow only transposition operation

func JaroWinklerSimilarity

func JaroWinklerSimilarity(str1, str2 string) float32

JaroWinklerSimilarity return a similarity index (between 0 and 1) Use Jaro similarity and after look for a common prefix (length <= 4)

func LCS

func LCS(str1, str2 string) int

LCS takes two strings and compute their LCS(Longuest Common Subsequence)

func LCSBacktrack

func LCSBacktrack(str1, str2 string) (string, error)

LCSBacktrack returns all choices taken during LCS process

func LCSBacktrackAll

func LCSBacktrackAll(str1, str2 string) ([]string, error)

LCSBacktrackAll returns an array containing all common substrings between str1 and str2

func LCSDiff

func LCSDiff(str1, str2 string) ([]string, error)

LCSDiff will backtrack through the lcs matrix and return the diff between the two sequences

func LCSEditDistance

func LCSEditDistance(str1, str2 string) int

LCSEditDistance determines the edit distance between two strings using LCS function (allow only insert and delete operations)

func LevenshteinDistance

func LevenshteinDistance(str1, str2 string) int

LevenshteinDistance calculate the distance between two string This algorithm allow insertions, deletions and substitutions to change one string to the second Compatible with non-ASCII characters

func OSADamerauLevenshteinDistance

func OSADamerauLevenshteinDistance(str1, str2 string) int

OSADamerauLevenshteinDistance calculate the distance between two string Optimal string alignment distance variant that use extension of the Wagner-Fisher dynamic programming algorithm Doesn't allow multiple transformations on a same substring Allowing insertions, deletions, substitutions and transpositions to change one string to the second Compatible with non-ASCII characters

func QgramDistance

func QgramDistance(str1, str2 string, splitLength int) int

QgramDistance compute the q-gram similarity between two strings Takes two strings as parameters, a split length which defines the k-gram shingle length

func QgramDistanceCustomNgram

func QgramDistanceCustomNgram(splittedStr1, splittedStr2 map[string]int) int

QgramDistanceCustomNgram compute the q-gram similarity between two custom set of individuals Takes two n-gram map as parameters

func QgramSimilarity

func QgramSimilarity(str1, str2 string, splitLength int) float32

QgramSimilarity compute a similarity index (between 0 and 1) between two strings from a Qgram distance Takes two strings as parameters, a split length which defines the k-gram shingle length

func Shingle

func Shingle(s string, k int) map[string]int

Shingle Find the k-gram of a string for a given k Takes a string and an integer as parameters and return a map. Returns an empty map if the string is empty or if k is 0

func ShingleSlice

func ShingleSlice(s string, k int) []string

ShingleSlice Find the k-gram of a string for a given k Takes a string and an integer as parameters and return a slice. Returns an empty slice if the string is empty or if k is 0

func SorensenDiceCoefficient

func SorensenDiceCoefficient(str1, str2 string, splitLength int) float32

SorensenDiceCoefficient computes the Sorensen-Dice coefficient between two strings Takes two strings as parameters, a split length which defines the k-gram shingle length

func StringsSimilarity

func StringsSimilarity(str1 string, str2 string, algo Algorithm) (float32, error)

StringsSimilarity return a similarity index [0..1] between two strings based on given edit distance algorithm in parameter. Use defined Algorithm type. Through this function, Cosine and Jaccard algorithms are used with Shingle split method with a length of 2.

Types

type Algorithm

type Algorithm uint8

Algorithm is an Integer type used to identify edit distance algorithms

const (
	Levenshtein Algorithm = iota
	DamerauLevenshtein
	OSADamerauLevenshtein
	Lcs
	Hamming
	Jaro
	JaroWinkler
	Cosine
	Jaccard
	SorensenDice
	Qgram
)

Algorithm identifiers