agnivade/levenshtein agnivade/levenshtein

Text Processing
  • Stars
    star
    339
  • Rank 124,632 (Top 3 %)
  • Language
    Go
  • License
    MIT License
  • Created over 10 years ago
  • Updated 5 months ago
Twitter logo Share LinkedIn logo Share Facebook logo Share
agnivade/levenshtein
github

agnivade

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Go implementation to calculate Levenshtein Distance.

levenshtein Build Status Go Report Card PkgGoDev

Go package to calculate the Levenshtein Distance

The library is fully capable of working with non-ascii strings. But the strings are not normalized. That is left as a user-dependant use case. Please normalize the strings before passing it to the library if you have such a requirement.

Limitation

As a performance optimization, the library can handle strings only up to 65536 characters (runes). If you need to handle strings larger than that, please pin to version 1.0.3.

Install

go get github.com/agnivade/levenshtein

Example

package main

import (
	"fmt"
	"github.com/agnivade/levenshtein"
)

func main() {
	s1 := "kitten"
	s2 := "sitting"
	distance := levenshtein.ComputeDistance(s1, s2)
	fmt.Printf("The distance between %s and %s is %d.\n", s1, s2, distance)
	// Output:
	// The distance between kitten and sitting is 3.
}

Benchmarks

name              time/op
Simple/ASCII-4     330ns ± 2%
Simple/French-4    617ns ± 2%
Simple/Nordic-4   1.16µs ± 4%
Simple/Tibetan-4  1.05µs ± 1%

name              alloc/op
Simple/ASCII-4     96.0B ± 0%
Simple/French-4     128B ± 0%
Simple/Nordic-4     192B ± 0%
Simple/Tibetan-4    144B ± 0%

name              allocs/op
Simple/ASCII-4      1.00 ± 0%
Simple/French-4     1.00 ± 0%
Simple/Nordic-4     1.00 ± 0%
Simple/Tibetan-4    1.00 ± 0%

Comparisons with other libraries

name                     time/op
Leven/ASCII/agniva-4      353ns ± 1%
Leven/ASCII/arbovm-4      485ns ± 1%
Leven/ASCII/dgryski-4     395ns ± 0%
Leven/French/agniva-4     648ns ± 1%
Leven/French/arbovm-4     791ns ± 0%
Leven/French/dgryski-4    682ns ± 0%
Leven/Nordic/agniva-4    1.28µs ± 1%
Leven/Nordic/arbovm-4    1.52µs ± 1%
Leven/Nordic/dgryski-4   1.32µs ± 1%
Leven/Tibetan/agniva-4   1.12µs ± 1%
Leven/Tibetan/arbovm-4   1.31µs ± 0%
Leven/Tibetan/dgryski-4  1.16µs ± 0%

More Repositories

1

funnel

A minimalistic 12 factor log router written in Go
Go
312
star
2

wasmbrowsertest

Run WASM tests inside your browser
Go
186
star
3

shimmer

Image transformation in wasm using Go
JavaScript
143
star
4

frodo

Demo API to play with io_uring in Go
Go
62
star
5

easy-scrypt

This is a nice and simple wrapper in Go over the scrypt password based key derivation algorithm.
Go
23
star
6

pgm

A Go implementation of the PGM index
Go
14
star
7

sqlargs

A vet analyzer which checks sql queries for correctness
Go
9
star
8

perseus

Multiplex connections
Go
9
star
9

agnivade.github.io

Personal space
HTML
3
star
10

youremote

Play songs in your speaker from anywhere in your home !
JavaScript
3
star
11

mdns

A helper library to refactor some boilerplate code for publishing mdns services
Go
2
star
12

go2go

Playground for generics
2
star
13

whisper-wasi

A prototype trying to get whisper work in wasi
Go
2
star
14

demo

Go
2
star
15

migro

Automated migration checker
Go
2
star
16

chatwebsocket

A websocket chat app
Go
1
star
17

threejs-app

Threejs demo
JavaScript
1
star
18

atan2-vfmadd

vfmadd test with atan2
Go
1
star
19

quictionary

A small and concise dictionary interface built using React + Material UI
JavaScript
1
star
20

GetHeaders

A Google Chrome Extension to view the HTTP response headers of any website.
JavaScript
1
star
21

Wordfall

A css animation that makes words fall like rain
JavaScript
1
star
22

adda

Forum software - Full client side. Offline capable. 🔌 Elegant. ✨
Vue
1
star