1package parser
2
3import (
4 "database/sql"
5 "math"
6 "sort"
7 "strings"
8 "time"
9 "unicode/utf8"
10
11 "github.com/bnema/dumber/internal/db"
12)
13
14// FuzzyMatcher implements efficient fuzzy string matching algorithms.
15type FuzzyMatcher struct {
16 config *FuzzyConfig
17}
18
19// NewFuzzyMatcher creates a new FuzzyMatcher with the given configuration.
20func NewFuzzyMatcher(config *FuzzyConfig) *FuzzyMatcher {
21 return &FuzzyMatcher{
22 config: config,
23 }
24}
25
26// SearchHistory performs fuzzy search on history entries and returns ranked matches.
27func (fm *FuzzyMatcher) SearchHistory(query string, history []*db.History) []FuzzyMatch {
28 if len(history) == 0 || query == "" {
29 return nil
30 }
31
32 query = strings.ToLower(strings.TrimSpace(query))
33 matches := make([]FuzzyMatch, 0)
34
35 for _, entry := range history {
36 match := fm.matchHistoryEntry(query, entry)
37 if match.Score >= fm.config.MinSimilarityThreshold {
38 matches = append(matches, match)
39 }
40 }
41
42 // Sort by score (descending)
43 sort.Slice(matches, func(i, j int) bool {
44 return matches[i].Score > matches[j].Score
45 })
46
47 // Limit results
48 if len(matches) > fm.config.MaxResults {
49 matches = matches[:fm.config.MaxResults]
50 }
51
52 return matches
53}
54
55// matchHistoryEntry calculates fuzzy match score for a history entry.
56func (fm *FuzzyMatcher) matchHistoryEntry(query string, entry *db.History) FuzzyMatch {
57 match := FuzzyMatch{
58 HistoryEntry: entry,
59 }
60
61 url := strings.ToLower(entry.Url)
62 title := ""
63 if entry.Title.Valid {
64 title = strings.ToLower(entry.Title.String)
65 }
66
67 // Calculate URL similarity
68 match.URLScore = fm.calculateSimilarity(query, url)
69 urlSubstring := fm.substringMatch(query, url)
70 if urlSubstring > match.URLScore {
71 match.URLScore = urlSubstring
72 }
73
74 // Calculate title similarity
75 if title != "" {
76 match.TitleScore = fm.calculateSimilarity(query, title)
77 titleSubstring := fm.substringMatch(query, title)
78 if titleSubstring > match.TitleScore {
79 match.TitleScore = titleSubstring
80 }
81 }
82
83 // Calculate recency score
84 match.RecencyScore = fm.calculateRecencyScore(entry.LastVisited)
85
86 // Calculate visit count score
87 match.VisitScore = fm.calculateVisitScore(entry.VisitCount)
88
89 // Determine matched field
90 if match.URLScore >= match.TitleScore {
91 match.MatchedField = "url"
92 if match.URLScore > 0 && match.TitleScore > 0 {
93 match.MatchedField = "both"
94 }
95 } else {
96 match.MatchedField = "title"
97 }
98
99 // Calculate weighted final score
100 match.Score = fm.config.URLWeight*match.URLScore +
101 fm.config.TitleWeight*match.TitleScore +
102 fm.config.RecencyWeight*match.RecencyScore +
103 fm.config.VisitWeight*match.VisitScore
104
105 return match
106}
107
108// calculateSimilarity computes similarity using Jaro-Winkler distance.
109func (fm *FuzzyMatcher) calculateSimilarity(s1, s2 string) float64 {
110 if s1 == s2 {
111 return 1.0
112 }
113
114 if len(s1) == 0 || len(s2) == 0 {
115 return 0.0
116 }
117
118 // Use Jaro-Winkler distance for better results
119 return fm.jaroWinklerSimilarity(s1, s2)
120}
121
122// substringMatch calculates substring match score with position weighting.
123func (fm *FuzzyMatcher) substringMatch(query, text string) float64 {
124 if query == "" || text == "" {
125 return 0.0
126 }
127
128 // Check for exact substring match
129 index := strings.Index(text, query)
130 if index == -1 {
131 return 0.0
132 }
133
134 // Base score for substring match
135 baseScore := float64(len(query)) / float64(len(text))
136
137 // Boost score if match is at the beginning
138 positionWeight := 1.0
139 if index == 0 {
140 positionWeight = 1.5
141 } else if index < len(text)/3 {
142 positionWeight = 1.2
143 }
144
145 score := baseScore * positionWeight
146 if score > 1.0 {
147 score = 1.0
148 }
149
150 return score
151}
152
153// jaroWinklerSimilarity calculates Jaro-Winkler similarity between two strings.
154func (fm *FuzzyMatcher) jaroWinklerSimilarity(s1, s2 string) float64 {
155 jaroSim := fm.jaroSimilarity(s1, s2)
156
157 if jaroSim < 0.7 {
158 return jaroSim
159 }
160
161 // Calculate common prefix length (up to 4 characters)
162 prefixLength := 0
163 maxPrefix := 4
164 minLen := len(s1)
165 if len(s2) < minLen {
166 minLen = len(s2)
167 }
168 if maxPrefix > minLen {
169 maxPrefix = minLen
170 }
171
172 for i := 0; i < maxPrefix; i++ {
173 if s1[i] == s2[i] {
174 prefixLength++
175 } else {
176 break
177 }
178 }
179
180 // Winkler modification
181 return jaroSim + (0.1 * float64(prefixLength) * (1 - jaroSim))
182}
183
184// jaroSimilarity calculates Jaro similarity between two strings.
185func (fm *FuzzyMatcher) jaroSimilarity(s1, s2 string) float64 {
186 len1 := utf8.RuneCountInString(s1)
187 len2 := utf8.RuneCountInString(s2)
188
189 if len1 == 0 && len2 == 0 {
190 return 1.0
191 }
192 if len1 == 0 || len2 == 0 {
193 return 0.0
194 }
195
196 // Convert to rune slices for proper Unicode handling
197 runes1 := []rune(s1)
198 runes2 := []rune(s2)
199
200 // Calculate match window
201 matchWindow := (maxInt(len1, len2) / 2) - 1
202 if matchWindow < 0 {
203 matchWindow = 0
204 }
205
206 // Track matches
207 matches1 := make([]bool, len1)
208 matches2 := make([]bool, len2)
209 matchCount := 0
210
211 // Find matches
212 for i := 0; i < len1; i++ {
213 start := maxInt(0, i-matchWindow)
214 end := minInt(i+matchWindow+1, len2)
215
216 for j := start; j < end; j++ {
217 if matches2[j] || runes1[i] != runes2[j] {
218 continue
219 }
220 matches1[i] = true
221 matches2[j] = true
222 matchCount++
223 break
224 }
225 }
226
227 if matchCount == 0 {
228 return 0.0
229 }
230
231 // Count transpositions
232 transpositions := 0
233 k := 0
234 for i := 0; i < len1; i++ {
235 if !matches1[i] {
236 continue
237 }
238 for !matches2[k] {
239 k++
240 }
241 if runes1[i] != runes2[k] {
242 transpositions++
243 }
244 k++
245 }
246
247 // Calculate Jaro similarity
248 return (float64(matchCount)/float64(len1) +
249 float64(matchCount)/float64(len2) +
250 float64(matchCount-transpositions/2)/float64(matchCount)) / 3.0
251}
252
253// calculateRecencyScore calculates score based on how recently the entry was visited.
254func (fm *FuzzyMatcher) calculateRecencyScore(lastVisited sql.NullTime) float64 {
255 if !lastVisited.Valid {
256 return 0.0
257 }
258
259 now := time.Now()
260 daysSince := now.Sub(lastVisited.Time).Hours() / 24
261
262 // Exponential decay based on days since last visit
263 decayRate := float64(fm.config.RecencyDecayDays)
264 score := math.Exp(-daysSince / decayRate)
265
266 return score
267}
268
269// calculateVisitScore calculates score based on visit count with logarithmic scaling.
270func (fm *FuzzyMatcher) calculateVisitScore(visitCount sql.NullInt64) float64 {
271 if !visitCount.Valid || visitCount.Int64 <= 0 {
272 return 0.0
273 }
274
275 // Logarithmic scaling to prevent highly visited sites from dominating
276 score := math.Log1p(float64(visitCount.Int64)) / math.Log1p(1000) // Normalize to max 1000 visits
277 if score > 1.0 {
278 score = 1.0
279 }
280
281 return score
282}
283
284// LevenshteinDistance calculates the Levenshtein distance between two strings.
285func (fm *FuzzyMatcher) LevenshteinDistance(s1, s2 string) int {
286 runes1 := []rune(s1)
287 runes2 := []rune(s2)
288
289 len1 := len(runes1)
290 len2 := len(runes2)
291
292 // Create a matrix to store distances
293 matrix := make([][]int, len1+1)
294 for i := range matrix {
295 matrix[i] = make([]int, len2+1)
296 }
297
298 // Initialize first row and column
299 for i := 0; i <= len1; i++ {
300 matrix[i][0] = i
301 }
302 for j := 0; j <= len2; j++ {
303 matrix[0][j] = j
304 }
305
306 // Fill the matrix
307 for i := 1; i <= len1; i++ {
308 for j := 1; j <= len2; j++ {
309 cost := 1
310 if runes1[i-1] == runes2[j-1] {
311 cost = 0
312 }
313
314 deletion := matrix[i-1][j] + 1
315 insertion := matrix[i][j-1] + 1
316 substitution := matrix[i-1][j-1] + cost
317
318 matrix[i][j] = minInt(deletion, minInt(insertion, substitution))
319 }
320 }
321
322 return matrix[len1][len2]
323}
324
325// LevenshteinSimilarity converts Levenshtein distance to similarity score (0.0-1.0).
326func (fm *FuzzyMatcher) LevenshteinSimilarity(s1, s2 string) float64 {
327 if s1 == s2 {
328 return 1.0
329 }
330
331 distance := fm.LevenshteinDistance(s1, s2)
332 maxLen := maxInt(utf8.RuneCountInString(s1), utf8.RuneCountInString(s2))
333
334 if maxLen == 0 {
335 return 1.0
336 }
337
338 return 1.0 - float64(distance)/float64(maxLen)
339}
340
341// TokenizedMatch performs token-based fuzzy matching for better phrase matching.
342func (fm *FuzzyMatcher) TokenizedMatch(query, text string) float64 {
343 queryTokens := strings.Fields(strings.ToLower(query))
344 textTokens := strings.Fields(strings.ToLower(text))
345
346 if len(queryTokens) == 0 || len(textTokens) == 0 {
347 return 0.0
348 }
349
350 totalScore := 0.0
351 matchedTokens := 0
352
353 for _, queryToken := range queryTokens {
354 bestScore := 0.0
355 for _, textToken := range textTokens {
356 score := fm.calculateSimilarity(queryToken, textToken)
357 if score > bestScore {
358 bestScore = score
359 }
360 }
361 if bestScore >= 0.5 { // Threshold for token match
362 totalScore += bestScore
363 matchedTokens++
364 }
365 }
366
367 if matchedTokens == 0 {
368 return 0.0
369 }
370
371 // Average score weighted by matched token ratio
372 avgScore := totalScore / float64(matchedTokens)
373 tokenRatio := float64(matchedTokens) / float64(len(queryTokens))
374
375 return avgScore * tokenRatio
376}
377
378// RankMatches re-ranks fuzzy matches based on additional criteria.
379func (fm *FuzzyMatcher) RankMatches(matches []FuzzyMatch, query string) []FuzzyMatch {
380 if len(matches) == 0 {
381 return matches
382 }
383
384 // Apply additional ranking factors
385 for i := range matches {
386 match := &matches[i]
387
388 // Boost exact matches
389 if strings.Contains(strings.ToLower(match.HistoryEntry.Url), strings.ToLower(query)) {
390 match.Score *= 1.2
391 }
392
393 // Boost domain matches
394 if fm.isDomainMatch(query, match.HistoryEntry.Url) {
395 match.Score *= 1.15
396 }
397
398 // Boost short URLs (likely more relevant)
399 if len(match.HistoryEntry.Url) < 50 {
400 match.Score *= 1.05
401 }
402 }
403
404 // Re-sort by updated scores
405 sort.Slice(matches, func(i, j int) bool {
406 return matches[i].Score > matches[j].Score
407 })
408
409 return matches
410}
411
412// isDomainMatch checks if the query matches the domain of the URL.
413func (fm *FuzzyMatcher) isDomainMatch(query, url string) bool {
414 query = strings.ToLower(strings.TrimSpace(query))
415
416 // Extract domain from URL
417 domain := url
418 if strings.HasPrefix(url, "http://") {
419 domain = url[7:]
420 } else if strings.HasPrefix(url, "https://") {
421 domain = url[8:]
422 }
423
424 // Remove path
425 if idx := strings.Index(domain, "/"); idx != -1 {
426 domain = domain[:idx]
427 }
428
429 // Remove port
430 if idx := strings.Index(domain, ":"); idx != -1 {
431 domain = domain[:idx]
432 }
433
434 domain = strings.ToLower(domain)
435
436 // Check for exact domain match
437 if domain == query {
438 return true
439 }
440
441 // Check if query is part of domain (e.g., "github" in "github.com" or "www.github.com")
442 if strings.HasSuffix(domain, "."+query) || strings.HasPrefix(domain, query+".") {
443 return true
444 }
445
446 // Check if query matches a significant part of domain (not just a substring)
447 // Split domain by dots and check if any part matches query
448 domainParts := strings.Split(domain, ".")
449 for _, part := range domainParts {
450 if part == query {
451 return true
452 }
453 }
454
455 return false
456}
457
458// Helper functions
459func minInt(a, b int) int {
460 if a < b {
461 return a
462 }
463 return b
464}
465
466func maxInt(a, b int) int {
467 if a > b {
468 return a
469 }
470 return b
471}