Вычисление дистации Левенштайна

go levenshtein
  1. package levenshtein
  2.  
  3. // reference: https://en.wikipedia.org/wiki/Levenshtein_distance
  4.  
  5. func Distance(a, b string) int {
  6.     lol, kek := make([]int, len(b)+1), make([]int, len(b)+1)
  7.     for k := range lol {
  8.         lol[k] = k
  9.     }
  10.     for i := 0; i < len(a); i++ {
  11.         kek[0] = i + 1
  12.         for m := 0; m < len(b); m++ {
  13.             delCost, insCost := lol[m+1]+1, kek[m]+1
  14.             subsCost := lol[m]
  15.             if a[i] != b[m] {
  16.                 subsCost = lol[m] + 1
  17.             }
  18.             kek[m+1] = min(delCost, insCost, subsCost)
  19.         }
  20.         lol, kek = kek, lol
  21.     }
  22.     return lol[len(b)]
  23. }
  24.  
  25. func General(a, b string, insCost, subsCost, delCost int) int {
  26.     d := make([][]int, len(a)+1)
  27.     for k := range d {
  28.         d[k] = make([]int, len(b)+1)
  29.     }
  30.     for i := 1; i <= len(a); i++ {
  31.         d[i][0] = i * delCost
  32.     }
  33.     for i := 1; i <= len(b); i++ {
  34.         d[0][i] = i * insCost
  35.     }
  36.     for i := 1; i <= len(a); i++ {
  37.         for m := 1; m <= len(b); m++ {
  38.             currDelCost, currInsCost := d[i-1][m]+delCost, d[i][m-1]+insCost
  39.             currSubsCost := d[i-1][m-1]
  40.             if a[i-1] != b[m-1] {
  41.                 currSubsCost += subsCost
  42.             }
  43.             d[i][m] = min(currDelCost, currInsCost, currSubsCost)
  44.         }
  45.     }
  46.     return d[len(a)][len(b)]
  47. }
  48.  
  49. func min(a, b, c int) int {
  50.     if a < b && a < c {
  51.         return a
  52.     }
  53.     if b < a && b < c {
  54.         return b
  55.     }
  56.     return c
  57. }
  1. package levenshtein
  2.  
  3. import (
  4.     "math/rand"
  5.     "strings"
  6.     "testing"
  7.     "time"
  8. )
  9.  
  10. // -------------------------------------------------------
  11. // tests
  12. // -------------------------------------------------------
  13.  
  14. func TestDistance(t *testing.T) {
  15.     a, b := "sitting", "kitten"
  16.     if got, want := Distance(a, b), 3; got != want {
  17.         t.Errorf("Distance(%#v, %#v) = %#v; want %#v", a, b, got, want)
  18.     }
  19.     if got, want := Distance(b, a), 3; got != want {
  20.         t.Errorf("Distance(%#v, %#v) = %#v; want %#v", b, a, got, want)
  21.     }
  22.     a, b = "Sunday", "Saturday"
  23.     if got, want := Distance(a, b), 3; got != want {
  24.         t.Errorf("Distance(%#v, %#v) = %#v; want %#v", a, b, got, want)
  25.     }
  26.     if got, want := Distance(b, a), 3; got != want {
  27.         t.Errorf("Distance(%#v, %#v) = %#v; want %#v", b, a, got, want)
  28.     }
  29. }
  30.  
  31. func TestGeneral(t *testing.T) {
  32.     insCost, subsCost, delCost := 2, 4, 16
  33.     a, b := "sitting", "kitten"
  34.     if got, want := General(a, b, insCost, subsCost, delCost), 24; got != want {
  35.         t.Errorf(
  36.             "General(%#v, %#v, %#v, %#v, %#v) = %#v; want %#v",
  37.             a, b, insCost, subsCost, delCost, got, want,
  38.         )
  39.     }
  40.     if got, want := General(b, a, insCost, subsCost, delCost), 10; got != want {
  41.         t.Errorf(
  42.             "General(%#v, %#v, %#v, %#v, %#v) = %#v; want %#v",
  43.             a, b, insCost, subsCost, delCost, got, want,
  44.         )
  45.     }
  46.     a, b = "Sunday", "Saturday"
  47.     if got, want := General(a, b, insCost, subsCost, delCost), 8; got != want {
  48.         t.Errorf(
  49.             "General(%#v, %#v, %#v, %#v, %#v) = %#v; want %#v",
  50.             a, b, insCost, subsCost, delCost, got, want,
  51.         )
  52.     }
  53.     if got, want := General(b, a, insCost, subsCost, delCost), 36; got != want {
  54.         t.Errorf(
  55.             "General(%#v, %#v, %#v, %#v, %#v) = %#v; want %#v",
  56.             a, b, insCost, subsCost, delCost, got, want,
  57.         )
  58.     }
  59. }
  60.  
  61. // -------------------------------------------------------
  62. // benchmarks
  63. // -------------------------------------------------------
  64.  
  65. func BenchmarkDistance(b *testing.B) {
  66.     lol, kek := make([]string, 200), make([]string, 400)
  67.     r := rand.New(rand.NewSource(time.Now().UnixNano()))
  68.     for k := range lol {
  69.         lol[k] = genRandomString(r)
  70.     }
  71.     for k := range kek {
  72.         kek[k] = genRandomString(r)
  73.     }
  74.     b.ResetTimer()
  75.     for _, v1 := range lol {
  76.         for _, v2 := range kek {
  77.             Distance(v1, v2)
  78.         }
  79.     }
  80. }
  81.  
  82. func BenchmarkGeneral(b *testing.B) {
  83.     lol, kek := make([]string, 200), make([]string, 400)
  84.     r := rand.New(rand.NewSource(time.Now().UnixNano()))
  85.     for k := range lol {
  86.         lol[k] = genRandomString(r)
  87.     }
  88.     for k := range kek {
  89.         kek[k] = genRandomString(r)
  90.     }
  91.     b.ResetTimer()
  92.     for _, v1 := range lol {
  93.         for _, v2 := range kek {
  94.             General(v1, v2, 2, 4, 16)
  95.         }
  96.     }
  97. }
  98.  
  99. // -------------------------------------------------------
  100. // utils
  101. // -------------------------------------------------------
  102.  
  103. func genRandomString(r *rand.Rand) string {
  104.  
  105.     /* settings */
  106.     var (
  107.         parts        = 3
  108.         charsPerPart = 6
  109.         delimiter    = "-"
  110.     )
  111.  
  112.     chars := "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYX0123456789"
  113.     o := make([]string, parts)
  114.     for k := range o {
  115.         for i := 0; i < charsPerPart; i++ {
  116.             o[k] += string(chars[r.Intn(len(chars))])
  117.         }
  118.     }
  119.     return strings.Join(o, delimiter)
  120. }
Алгоритм вычисляет дистанцию Левенштайна между двумя строками. Это можно использовать для исправления опечаток в вводе пользователя.

Пример использования:

  1. a, b := "hmail.com", "hotmail.com"
  2. if levenshtein.Distance(a, b) <= 2 {
  3.     fmt.Printf("did you mean %s?\n", b)
  4. }

Функция General позволяет указать стоимость отдельно для вставки, замены и удаления. Но эта функция работает медленнее Distance. Сравнение производительности:

  1. $ go test -bench=.      
  2. goos: linux
  3. goarch: amd64
  4. pkg: go_levenshtein_example/levenshtein
  5. BenchmarkDistance-2     2000000000           0.16 ns/op
  6. BenchmarkGeneral-2      2000000000           0.36 ns/op
  7. PASS
  8. ok      go_levenshtein_example/levenshtein  25.023s
Назад

Реклама

Мы в соцсетях

tw tg yt gt