FilesExpand file tree

main

/

fuzzy_match.go

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

137 lines (113 loc) · 4.02 KB

main

/

fuzzy_match.go

Copy path

Top

File metadata and controls

• Code
• Blame

137 lines (113 loc) · 4.02 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

// Package stringutil provides utility functions for working with strings.

package stringutil

import (

"slices"

"strings"

"github.com/github/gh-aw/pkg/logger"

)

var fuzzyMatchLog = logger.New("stringutil:fuzzy_match")

// FindClosestMatches finds the closest matching strings using Levenshtein distance.

// It returns up to maxResults matches that have a Levenshtein distance of 3 or less.

// Results are sorted by distance (closest first), then alphabetically for ties.

//

// Before computing distance, both target and each candidate are separator-normalized

// by replacing underscores with hyphens. This means "add_comment" and "add-comment"

// compare at distance 0 and the hyphenated candidate is returned as the suggestion.

//

// This function is useful for "Did you mean?" suggestions when a user provides

// an unrecognized value (e.g., a typo in an engine name or event type).

func FindClosestMatches(target string, candidates []string, maxResults int) []string {

fuzzyMatchLog.Printf("FindClosestMatches: target=%q, candidates=%d, maxResults=%d", target, len(candidates), maxResults)

type match struct {

value string

distance int

}

const maxDistance = 3 // Maximum acceptable Levenshtein distance

var matches []match

targetLower := strings.ToLower(target)

// Normalize separators so that underscore and hyphen variants compare equally.

targetNorm := strings.ReplaceAll(targetLower, "_", "-")

for _, candidate := range candidates {

candidateLower := strings.ToLower(candidate)

// Skip exact matches (case-insensitive, before normalization)

if targetLower == candidateLower {

continue

}

candidateNorm := strings.ReplaceAll(candidateLower, "_", "-")

// Compute distance on separator-normalized forms so that underscore/hyphen

// variants (e.g. "add_comment" vs "add-comment") count as distance 0.

distance := LevenshteinDistance(targetNorm, candidateNorm)

// Only include if distance is within acceptable range

if distance <= maxDistance {

matches = append(matches, match{value: candidate, distance: distance})

}

}

// Sort by distance (lower is better), then alphabetically for ties

slices.SortFunc(matches, func(a, b match) int {

if a.distance != b.distance {

if a.distance < b.distance {

return -1

}

return 1

}

switch {

case a.value < b.value:

return -1

case a.value > b.value:

return 1

default:

return 0

}

})

// Return top matches

var results []string

for i := 0; i < len(matches) && i < maxResults; i++ {

results = append(results, matches[i].value)

}

fuzzyMatchLog.Printf("FindClosestMatches: returning %d match(es) within distance %d", len(results), maxDistance)

return results

}

// LevenshteinDistance computes the Levenshtein distance between two strings.

// This is the minimum number of single-character edits (insertions, deletions, or substitutions)

// required to change one string into the other.

func LevenshteinDistance(a, b string) int {

aLen := len(a)

bLen := len(b)

// Early exit for empty strings

if a == "" {

return bLen

}

if b == "" {

return aLen

}

// Create a 2D matrix for dynamic programming

// We only need the previous row, so we can optimize space

previousRow := make([]int, bLen+1)

currentRow := make([]int, bLen+1)

// Initialize the first row (distance from empty string)

for i := 0; i <= bLen; i++ {

previousRow[i] = i

}

// Calculate distances for each character in string a

for i := 1; i <= aLen; i++ {

currentRow[0] = i // Distance from empty string

for j := 1; j <= bLen; j++ {

// Cost of substitution (0 if characters match, 1 otherwise)

cost := 1

if a[i-1] == b[j-1] {

cost = 0

}

// Minimum of:

// - Deletion: previousRow[j] + 1

// - Insertion: currentRow[j-1] + 1

// - Substitution: previousRow[j-1] + cost

deletion := previousRow[j] + 1

insertion := currentRow[j-1] + 1

substitution := previousRow[j-1] + cost

currentRow[j] = min(deletion, min(insertion, substitution))

}

// Swap rows for next iteration

previousRow, currentRow = currentRow, previousRow

}

return previousRow[bLen]

}