aboutsummaryrefslogtreecommitdiffstats
path: root/vendor/github.com/agnivade/levenshtein
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/github.com/agnivade/levenshtein')
-rw-r--r--vendor/github.com/agnivade/levenshtein/.gitignore5
-rw-r--r--vendor/github.com/agnivade/levenshtein/.travis.yml7
-rw-r--r--vendor/github.com/agnivade/levenshtein/License.txt21
-rw-r--r--vendor/github.com/agnivade/levenshtein/Makefile13
-rw-r--r--vendor/github.com/agnivade/levenshtein/README.md57
-rw-r--r--vendor/github.com/agnivade/levenshtein/go.mod1
-rw-r--r--vendor/github.com/agnivade/levenshtein/levenshtein.go71
7 files changed, 175 insertions, 0 deletions
diff --git a/vendor/github.com/agnivade/levenshtein/.gitignore b/vendor/github.com/agnivade/levenshtein/.gitignore
new file mode 100644
index 00000000..345780a4
--- /dev/null
+++ b/vendor/github.com/agnivade/levenshtein/.gitignore
@@ -0,0 +1,5 @@
+coverage.txt
+fuzz/fuzz-fuzz.zip
+fuzz/corpus/corpus/*
+fuzz/corpus/suppressions/*
+fuzz/corpus/crashes/*
diff --git a/vendor/github.com/agnivade/levenshtein/.travis.yml b/vendor/github.com/agnivade/levenshtein/.travis.yml
new file mode 100644
index 00000000..06b3ba55
--- /dev/null
+++ b/vendor/github.com/agnivade/levenshtein/.travis.yml
@@ -0,0 +1,7 @@
+language: go
+
+go:
+- 1.8.x
+- 1.9.x
+- 1.10.x
+- tip
diff --git a/vendor/github.com/agnivade/levenshtein/License.txt b/vendor/github.com/agnivade/levenshtein/License.txt
new file mode 100644
index 00000000..54b51f49
--- /dev/null
+++ b/vendor/github.com/agnivade/levenshtein/License.txt
@@ -0,0 +1,21 @@
+The MIT License (MIT)
+
+Copyright (c) 2015 Agniva De Sarker
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/vendor/github.com/agnivade/levenshtein/Makefile b/vendor/github.com/agnivade/levenshtein/Makefile
new file mode 100644
index 00000000..4bef27dd
--- /dev/null
+++ b/vendor/github.com/agnivade/levenshtein/Makefile
@@ -0,0 +1,13 @@
+all: test install
+
+install:
+ go install
+
+lint:
+ gofmt -l -s -w . && go tool vet -all . && golint
+
+test:
+ go test -race -v -coverprofile=coverage.txt -covermode=atomic
+
+bench:
+ go test -run=XXX -bench=. -benchmem
diff --git a/vendor/github.com/agnivade/levenshtein/README.md b/vendor/github.com/agnivade/levenshtein/README.md
new file mode 100644
index 00000000..b0fd81df
--- /dev/null
+++ b/vendor/github.com/agnivade/levenshtein/README.md
@@ -0,0 +1,57 @@
+levenshtein [![Build Status](https://travis-ci.org/agnivade/levenshtein.svg?branch=master)](https://travis-ci.org/agnivade/levenshtein) [![Go Report Card](https://goreportcard.com/badge/github.com/agnivade/levenshtein)](https://goreportcard.com/report/github.com/agnivade/levenshtein) [![GoDoc](https://godoc.org/github.com/agnivade/levenshtein?status.svg)](https://godoc.org/github.com/agnivade/levenshtein)
+===========
+
+[Go](http://golang.org) package to calculate the [Levenshtein Distance](http://en.wikipedia.org/wiki/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.
+- https://blog.golang.org/normalization
+
+Install
+-------
+
+ go get github.com/agnivade/levenshtein
+
+Example
+-------
+
+```go
+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 537ns ± 2%
+Simple/French-4 956ns ± 0%
+Simple/Nordic-4 1.95µs ± 1%
+Simple/Tibetan-4 1.53µs ± 2%
+
+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%
+```
diff --git a/vendor/github.com/agnivade/levenshtein/go.mod b/vendor/github.com/agnivade/levenshtein/go.mod
new file mode 100644
index 00000000..b2921fb3
--- /dev/null
+++ b/vendor/github.com/agnivade/levenshtein/go.mod
@@ -0,0 +1 @@
+module github.com/agnivade/levenshtein
diff --git a/vendor/github.com/agnivade/levenshtein/levenshtein.go b/vendor/github.com/agnivade/levenshtein/levenshtein.go
new file mode 100644
index 00000000..e215813f
--- /dev/null
+++ b/vendor/github.com/agnivade/levenshtein/levenshtein.go
@@ -0,0 +1,71 @@
+// Package levenshtein is a Go implementation to calculate Levenshtein Distance.
+//
+// Implementation taken from
+// https://gist.github.com/andrei-m/982927#gistcomment-1931258
+package levenshtein
+
+// ComputeDistance computes the levenshtein distance between the two
+// strings passed as an argument. The return value is the levenshtein distance
+//
+// Works on runes (Unicode code points) but does not normalize
+// the input strings. See https://blog.golang.org/normalization
+// and the golang.org/x/text/unicode/norm pacage.
+func ComputeDistance(a, b string) int {
+ if a == b {
+ return 0
+ }
+
+ // We need to convert to []rune if the strings are non-ascii.
+ // This could be avoided by using utf8.RuneCountInString
+ // and then doing some juggling with rune indices.
+ // The primary challenge is keeping track of the previous rune.
+ // With a range loop, its not that easy. And with a for-loop
+ // we need to keep track of the inter-rune width using utf8.DecodeRuneInString
+ s1 := []rune(a)
+ s2 := []rune(b)
+
+ // swap to save some memory O(min(a,b)) instead of O(a)
+ if len(s1) > len(s2) {
+ s1, s2 = s2, s1
+ }
+ lenS1 := len(s1)
+ lenS2 := len(s2)
+
+ // init the row
+ x := make([]int, lenS1+1)
+ for i := 0; i <= lenS1; i++ {
+ x[i] = i
+ }
+
+ // fill in the rest
+ for i := 1; i <= lenS2; i++ {
+ prev := i
+ var current int
+
+ for j := 1; j <= lenS1; j++ {
+
+ if s2[i-1] == s1[j-1] {
+ current = x[j-1] // match
+ } else {
+ current = min(x[j-1]+1, prev+1, x[j]+1)
+ }
+ x[j-1] = prev
+ prev = current
+ }
+ x[lenS1] = prev
+ }
+ return x[lenS1]
+}
+
+func min(a, b, c int) int {
+ if a < b {
+ if a < c {
+ return a
+ }
+ } else {
+ if b < c {
+ return b
+ }
+ }
+ return c
+}