levenshtein_test.go 2.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119
  1. // Copyright (c) 2014 Couchbase, Inc.
  2. //
  3. // Licensed under the Apache License, Version 2.0 (the "License");
  4. // you may not use this file except in compliance with the License.
  5. // You may obtain a copy of the License at
  6. //
  7. // http://www.apache.org/licenses/LICENSE-2.0
  8. //
  9. // Unless required by applicable law or agreed to in writing, software
  10. // distributed under the License is distributed on an "AS IS" BASIS,
  11. // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12. // See the License for the specific language governing permissions and
  13. // limitations under the License.
  14. package search
  15. import (
  16. "testing"
  17. )
  18. func TestLevenshteinDistance(t *testing.T) {
  19. tests := []struct {
  20. a string
  21. b string
  22. dist int
  23. }{
  24. {
  25. "water",
  26. "atec",
  27. 2,
  28. },
  29. {
  30. "water",
  31. "aphex",
  32. 4,
  33. },
  34. }
  35. for _, test := range tests {
  36. actual := LevenshteinDistance(test.a, test.b)
  37. if actual != test.dist {
  38. t.Errorf("expected %d, got %d for %s and %s", test.dist, actual, test.a, test.b)
  39. }
  40. }
  41. }
  42. func TestLevenshteinDistanceMax(t *testing.T) {
  43. tests := []struct {
  44. a string
  45. b string
  46. max int
  47. dist int
  48. exceeded bool
  49. }{
  50. {
  51. a: "water",
  52. b: "atec",
  53. max: 1,
  54. dist: 1,
  55. exceeded: true,
  56. },
  57. {
  58. a: "water",
  59. b: "christmas",
  60. max: 3,
  61. dist: 3,
  62. exceeded: true,
  63. },
  64. {
  65. a: "water",
  66. b: "water",
  67. max: 1,
  68. dist: 0,
  69. exceeded: false,
  70. },
  71. }
  72. for _, test := range tests {
  73. actual, exceeded := LevenshteinDistanceMax(test.a, test.b, test.max)
  74. if actual != test.dist || exceeded != test.exceeded {
  75. t.Errorf("expected %d %t, got %d %t for %s and %s", test.dist, test.exceeded, actual, exceeded, test.a, test.b)
  76. }
  77. }
  78. }
  79. // 5 terms that are less than 2
  80. // 5 terms that are more than 2
  81. var benchmarkTerms = []string{
  82. "watex",
  83. "aters",
  84. "wayer",
  85. "wbter",
  86. "yater",
  87. "christmas",
  88. "waterwaterwater",
  89. "watcatdogfish",
  90. "q",
  91. "couchbase",
  92. }
  93. func BenchmarkLevenshteinDistance(b *testing.B) {
  94. a := "water"
  95. for i := 0; i < b.N; i++ {
  96. for _, t := range benchmarkTerms {
  97. LevenshteinDistance(a, t)
  98. }
  99. }
  100. }
  101. func BenchmarkLevenshteinDistanceMax(b *testing.B) {
  102. a := "water"
  103. for i := 0; i < b.N; i++ {
  104. for _, t := range benchmarkTerms {
  105. LevenshteinDistanceMax(a, t, 2)
  106. }
  107. }
  108. }