5119
Lh
lazy-history / files
lazy-history / internal / search / search.go
1.8 KB
1package search 2 3import ( 4 "sort" 5 "strings" 6 7 "github.com/samber/lo" 8) 9 10type SearchResult struct { 11 Value string 12 Distance int 13} 14 15func Search(slice []string, substring string) []string { 16 results := search(slice, substring) 17 18 return lo.Map(results, func(result SearchResult, _ int) string { 19 return result.Value 20 }) 21} 22 23// Search a slice of strings for a substring and sort by levenshtein distance. 24func search(slice []string, substring string) []SearchResult { 25 // search for the substring in the slice 26 matches := lo.Filter(slice, func(item string, _ int) bool { 27 return strings.Contains(item, substring) 28 }) 29 30 results := lo.Reduce(matches, func(agg []SearchResult, item string, index int) []SearchResult { 31 // Skip lines that already exist in the results 32 contains := lo.ContainsBy(agg, func(result SearchResult) bool { 33 return result.Value == item 34 }) 35 if contains { 36 return agg 37 } 38 distance := levenshteinDistance(item, substring) 39 agg = append(agg, SearchResult{Value: item, Distance: distance}) 40 41 return agg 42 }, []SearchResult{}) 43 44 sort.Slice(results, func(i, j int) bool { 45 return results[i].Distance < results[j].Distance 46 }) 47 48 return results 49} 50 51func levenshteinDistance(s, t string) int { 52 // Create matrix of size (lenS+1)*(lenT+1) 53 lenS := len(s) 54 lenT := len(t) 55 56 // Initialize the matrix 57 d := make([][]int, lenS+1) 58 for i := range d { 59 d[i] = make([]int, lenT+1) 60 d[i][0] = i // Fill first column 61 } 62 for j := range d[0] { 63 d[0][j] = j // Fill first row 64 } 65 66 // Fill the matrix 67 for i := 1; i <= lenS; i++ { 68 for j := 1; j <= lenT; j++ { 69 cost := 1 70 if s[i-1] == t[j-1] { 71 cost = 0 72 } 73 74 d[i][j] = min( 75 d[i-1][j]+1, // deletion 76 d[i][j-1]+1, // insertion 77 d[i-1][j-1]+cost, // substitution 78 ) 79 } 80 } 81 82 return d[lenS][lenT] 83}