Fastest string distance algorithm

diego.bernardes · April 11, 2016, 10:07pm

Anyone know any good package for golang to do string distance calculation? I’m looking for nanosecond times comparing words.

It’s for a toy project, one of the requirements is to be fast, crazy fast.

jesusrmoreno · April 12, 2016, 7:18pm

What do you mean by distance?

cpalone · April 12, 2016, 10:25pm

https://github.com/arbovm/levenshtein looks pretty solid. It’s based on a fast algorithm, and is optimized. As always though, you should try a few solutions and profile.

jbowles · April 12, 2016, 11:38pm

there are a few packages out there doing string distance metrics. If you know the algorithm you want to use you could search for that. The two packages below have a few different string distance algorithms (edit distance, soundex, jarowinkler, etc…).

I linked to a specific edit distance implementation because it shows 4 different ways to do it, with varying trade-offs of accuracy and speed.

github.com

jbowles/disfun/blob/master/levenshtein.go

package disfun

import (
	"github.com/gonum/matrix/mat64"
)

//Levenshtein (edit distance) gives similarity metric by calcuating number of positions for substitution, insertion, and deletion.
//
//
//Currently bemchmarking 4 different implementations. One is a simple pass through (Lev), another (Leven) uses a struct and separate insertion, deletion, substitution functions with a handmade matrix called VectorCell. The third one (Levenshtein) uses the mat64 matrix package. The last one (EditDistance) is the fastest but I haven't checked it accuracy yet.
//
//	Row     == Height
//	Column  == Width
//
//	Demo here: http://andrew.hedges.name/experiments/levenshtein/
//
// Levenshtein is the most accurate but also the most costly due to building matrices. I can get this down but using dense matrices for this is not a good idea. The other two functions are about the same speed but they are not very readable and not the most accurate... see the tests for differences in accuracy between Leven, Lev, and Levenshtein.
type Levenshtein struct {
	Source       []rune
	Target       []rune

This file has been truncated. show original

system · July 11, 2016, 11:46pm

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.