Light

xrash / smetrics Goto Github PK

View Code? Open in Web Editor NEW

223.0 5.0 27.0 1.77 MB

String metrics library written in Go.

License: MIT License

Go 99.47% Makefile 0.53%

levenshtein-distance distance jaro soundex go winkler jarowinkler ukkonen string-metrics algorithm

smetrics's Introduction

smetrics

smetrics is "string metrics".

Package smetrics provides a bunch of algorithms for calculating the distance between strings.

There are implementations for calculating the popular Levenshtein distance (aka Edit Distance or Wagner-Fischer), as well as the Jaro distance, the Jaro-Winkler distance, and more.

How to import

import "github.com/xrash/smetrics"

Documentation

Go to https://pkg.go.dev/github.com/xrash/smetrics for complete documentation.

Example

package main

import (
	"github.com/xrash/smetrics"
)

func main() {
	smetrics.WagnerFischer("POTATO", "POTATTO", 1, 1, 2)
	smetrics.WagnerFischer("MOUSE", "HOUSE", 2, 2, 4)

	smetrics.Ukkonen("POTATO", "POTATTO", 1, 1, 2)
	smetrics.Ukkonen("MOUSE", "HOUSE", 2, 2, 4)

	smetrics.Jaro("AL", "AL")
	smetrics.Jaro("MARTHA", "MARHTA")

	smetrics.JaroWinkler("AL", "AL", 0.7, 4)
	smetrics.JaroWinkler("MARTHA", "MARHTA", 0.7, 4)

	smetrics.Soundex("Euler")
	smetrics.Soundex("Ellery")

	smetrics.Hamming("aaa", "aaa")
	smetrics.Hamming("aaa", "aab")
}

smetrics's People

Contributors

Stargazers

Watchers

smetrics's Issues

WagnerFischer doesn't handle asymmetric operation costs

smetrics.WagnerFischer("abc", "xy", 2, 3, 5) returns 10, but it should return 13 (3 deletions at cost 3 + 2 insertions at cost 2).

multibyte UTF-8 characters

All algorithms are ranging over the bytes of strings, which leads to different results for multibyte and singlebyte UTF-8 characters.

Example using WagnerFischer(a, b, 1, 1, 1):

"szellemhaj" - "szellemhajo" distance is 1
"szellemhaj" - "szellemhajó" distance is 2

Ranging over runes of strings would result 1,1 distance.
It's is slower but more accurate for non-ascii characters.

Jaro's implementation doesn't match with reference implementations

Hi,

Thanks for your work on these implementations!

Recently I've been tinkering with several distancing algorithms but I have inconsistent results when using xrash/smetrics compared to other Jaro implementations.

I've compared the result with:

https://github.com/masatana/go-textdistance (Go)
https://github.com/Simmetrics/simmetrics (Java)
https://pypi.org/project/jaro-winkler/ (Python)

And on at least the following values it differs:

"DIXON" vs. "DICKSONX" (smetrics.Jaro scores lower with 0.683333, reference implementations all score: 0.766667)
"gmilcon" vs. "gmilno" (smetrics.Jaro scores lower with 0.849206, reference implementations all score: 0.896825)

Will you accept a PR? I'm not sure if I find the time to figure out why the implementation is off, but I'd thought to first reach out and get a sign of life :-)

Please add a LICENSE file

I believe the license is BSD like Go and many of the libraries from the community, but please add an explicit LICENSE file

if A and B have no match, Jaro[Winkler] returns NaN

To test:

smetrics.Jaro("abc", "x") -> NaN

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.