Distance returns the edit distance between a and b using the Wagner-Fischer algorithm. A and B must be less than 255 characters long. maxDist is the maximum distance to consider. A value of -1 for maxDist means no maximum.
(a, b string, maxDist int)
| 26 | // maxDist is the maximum distance to consider. |
| 27 | // A value of -1 for maxDist means no maximum. |
| 28 | func Distance(a, b string, maxDist int) (int, error) { |
| 29 | if len(a) > 255 { |
| 30 | return 0, xerrors.Errorf("levenshtein: a must be less than 255 characters long") |
| 31 | } |
| 32 | if len(b) > 255 { |
| 33 | return 0, xerrors.Errorf("levenshtein: b must be less than 255 characters long") |
| 34 | } |
| 35 | // #nosec G115 - Safe conversion since we've checked that len(a) < 255 |
| 36 | m := uint8(len(a)) |
| 37 | // #nosec G115 - Safe conversion since we've checked that len(b) < 255 |
| 38 | n := uint8(len(b)) |
| 39 | |
| 40 | // Special cases for empty strings |
| 41 | if m == 0 { |
| 42 | return int(n), nil |
| 43 | } |
| 44 | if n == 0 { |
| 45 | return int(m), nil |
| 46 | } |
| 47 | |
| 48 | // Allocate a matrix of size m+1 * n+1 |
| 49 | d := make([][]uint8, 0) |
| 50 | var i, j uint8 |
| 51 | for i = 0; i < m+1; i++ { |
| 52 | di := make([]uint8, n+1) |
| 53 | d = append(d, di) |
| 54 | } |
| 55 | |
| 56 | // Source prefixes |
| 57 | for i = 1; i < m+1; i++ { |
| 58 | d[i][0] = i |
| 59 | } |
| 60 | |
| 61 | // Target prefixes |
| 62 | for j = 1; j < n; j++ { |
| 63 | d[0][j] = j // nolint:gosec // this cannot overflow |
| 64 | } |
| 65 | |
| 66 | // Compute the distance |
| 67 | for j = 0; j < n; j++ { |
| 68 | for i = 0; i < m; i++ { |
| 69 | var subCost uint8 |
| 70 | // Equal |
| 71 | if a[i] != b[j] { |
| 72 | subCost = 1 |
| 73 | } |
| 74 | // Don't forget: matrix is +1 size |
| 75 | d[i+1][j+1] = minOf( |
| 76 | d[i][j+1]+1, // deletion |
| 77 | d[i+1][j]+1, // insertion |
| 78 | d[i][j]+subCost, // substitution |
| 79 | ) |
| 80 | // check maxDist on the diagonal |
| 81 | // #nosec G115 - Safe conversion as maxDist is expected to be small for edit distances |
| 82 | if maxDist > -1 && i == j && d[i+1][j+1] > uint8(maxDist) { |
| 83 | return int(d[i+1][j+1]), ErrMaxDist |
| 84 | } |
| 85 | } |