DOCSEARCHbyAlgolia
Submit Docs

go-edlib

repository·master·Indexed 20 days ago

https://github.com/hbollon/go-edlib

A Golang library for string comparison and edit distance algorithms, designed to be fully Unicode compatible. It supports various metrics including Levenshtein, Damerau-Levenshtein, OSA Damerau-Levenshtein, Hamming, Jaro-Winkler, Cosine similarity, Jaccard similarity, and Sorensen-Dice coefficient. The library provides tools for fuzzy searching, Longest Common Subsequence (LCS) operations, and k-gram shingling.

Tokens
5.3K
Snippets
27
Records
28
Agent score
66%

What's inside go-edlib

  1. Run tests and benchmarks

    master

    Running Unit Tests

    • Linux: Run ./tests/tests.sh.
    • Windows: Run go test ./....

    Running Benchmarks

    • Linux: Run ./tests/benchmark.sh to run benchmarks on your local setup.
    • Interactive Charts: View benchmark cases for similarity algorithms here.

  2. Install go-edlib

    master

    To install the library, run the following command in your project folder:

    go get github.com/hbollon/go-edlib

    Then, import it into your Go files:

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

    Requirements:

    • Go v1.13 or higher
    go get github.com/hbollon/go-edlib

  3. Calculate string similarity index

    master

    Use the StringsSimilarity(str1, str2, algorithm) function to get a similarity score between two strings. The algorithm parameter must be one of the following Algorithm constants:

    • Levenshtein
    • DamerauLevenshtein
    • OSADamerauLevenshtein
    • Lcs
    • Hamming
    • Jaro
    • JaroWinkler
    • Cosine
    res, err := edlib.StringsSimilarity("string1", "string2", edlib.Levenshtein)
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("Similarity: %f", res)
}

  4. Get raw edit distance

    master

    To get the integer distance between two strings without a similarity percentage, use the following functions:

    • LevenshteinDistance(str1, str2)
    • DamerauLevenshteinDistance(str1, str2)
    • OSADamerauLevenshteinDistance(str1, str2)
    • LCSEditDistance(str1, str2)
    • HammingDistance(str1, str2)
    res := edlib.LevenshteinDistance("kitten", "sitting")
fmt.Printf("Result: %d", res) // Output: 3

  5. Execute fuzzy search

    master

    The library provides several ways to perform fuzzy searches against a list of strings (strList) using a target string (str).

    1. Most matching unique result (no threshold)

    Use FuzzySearch(str, strList, algorithm) to find the single best match.

    2. Most matching unique result (with threshold)

    Use FuzzySearchThreshold(str, strList, minSimilarity, algorithm) to find the best match only if its similarity is at least minSimilarity (e.g., 0.7).

    3. Most matching result set (no threshold)

    Use FuzzySearchSet(str, strList, resultQuantity, algorithm) to return a slice of the top resultQuantity matches.

    4. Most matching result set (with threshold)

    Use FuzzySearchSetThreshold(str, strList, resultQuantity, minSimilarity, algorithm) to return up to resultQuantity matches that meet the minSimilarity requirement.

    // Example: Most matching unique result with threshold
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: %s", res)
}

  6. Use LCS (Longest Common Subsequence) functions

    master

    The library provides several tools for working with the Longest Common Subsequence:

    • LCS(str1, str2): Returns the length of the LCS.
    • LCSBacktrack(str1, str2): Returns the first LCS string found.
    • LCSBacktrackAll(str1, str2): Returns all possible LCS strings.
    • LCSDiff(str1, str2): Returns a diff representation showing additions and deletions between the two strings.
    // Example: LCS Backtrack
res, err := edlib.LCSBacktrack("ABCD", "ACBAD")
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("LCS: %s", res)
}

  7. Calculate Jaro-Winkler similarity

    master

    Use JaroWinklerSimilarity to get a similarity index between 0.0 and 1.0. This builds upon the Jaro similarity by giving more weight to strings that share a common prefix (up to a maximum prefix length of 4).

    • Returns: float32 (1.0 for exact matches, 0.0 for no matches, or a value in between).
    • Behavior: It first calculates the Jaro similarity. If the similarity is not 0 or 1, it identifies the common prefix length (capped at 4) and applies Winkler's adjustment formula.
    import "github.com/hbollon/go-edlib"

score := edlib.JaroWinklerSimilarity("dwayne", "duane")
// score will be a float32 representing similarity

  8. Calculate Optimal String Alignment (OSA) Damerau-Levenshtein distance

    master

    Use OSADamerauLevenshteinDistance to calculate the distance between two strings using the Optimal String Alignment variant. This allows insertions, deletions, substitutions, and transpositions (swapping adjacent characters), but it does not allow multiple transformations on the same substring.

    This implementation is compatible with non-ASCII characters.

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

dist := edlib.OSADamerauLevenshteinDistance("ca", "abc")

  9. Calculate string similarity with CosineSimilarity

    master

    The CosineSimilarity function calculates a similarity index between two strings using the cosine algorithm. It treats the strings as vectors based on their components (either words or k-grams).

    Parameters:

    • str1 (string): The first string to compare.
    • str2 (string): The second string to compare.
    • splitLength (int): Defines the k-gram length for the shingle algorithm.
      • If splitLength is 0, the strings are split by whitespace (treating them as sets of words).
      • If splitLength is greater than 0, the strings are processed using the ShingleSlice algorithm with the specified length.

    Returns:

    • float32: A similarity index. If either input string is empty, it returns 0.
    package main

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

func main() {
    // Example 1: Splitting by whitespace (splitLength = 0)
    sim1 := edlib.CosineSimilarity("hello world", "hello earth", 0)
    
    // Example 2: Using k-grams/shingles (splitLength > 0)
    sim2 := edlib.CosineSimilarity("hello world", "hello earth", 3)
}

  10. Calculate Jaro similarity

    master

    Use JaroSimilarity to get a similarity index between 0.0 and 1.0 based on the Jaro distance algorithm. This algorithm accounts for matching characters and transpositions. The function is compatible with non-ASCII characters as it operates on runes.

    • Returns: float32 (1.0 for exact matches, 0.0 for no matches, or a value in between).
    • Behavior: If either string is empty, it returns 0.0. If strings are identical, it returns 1.0.
    import "github.com/hbollon/go-edlib"

score := edlib.JaroSimilarity("martha", "marhta")
// score will be a float32 representing similarity

  11. Retrieve the Longest Common Subsequence string

    master

    Use LCSBacktrack(str1, str2 string) (string, error) to retrieve the actual subsequence string found by the LCS algorithm.

    Errors: Returns an error if either input string is empty.

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

subsequence, err := edlib.LCSBacktrack("abcde", "ace")
if err != nil {
    // handle error
}
// subsequence is "ace"

  12. Calculate string similarity with StringsSimilarity

    master

    Use StringsSimilarity to get a similarity index between 0.0 and 1.0 for two strings. The index is calculated based on the provided Algorithm.

    Note that for certain algorithms like Cosine, Jaccard, SorensenDice, and Qgram, the function internally uses a Shingle split method with a length of 2.

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

similarity, err := edlib.StringsSimilarity("string1", "string2", edlib.Levenshtein)
if err != nil {
    // handle error
}
// similarity is a float32 between 0.0 and 1.0