1package cache
2
3import (
4 "math"
5 "sort"
6 "strings"
7 "sync"
8 "time"
9)
10
11// Fuzzy search constants
12const (
13 prefixMatchBonus = 0.9 // Score bonus for prefix matches
14 prefixLength = 4 // Maximum prefix length to check
15 recencyDecayDays = 30.0 // Days over which recency score decays
16 maxVisitNormal = 1000.0 // Maximum visits for normalization
17)
18
19// FuzzySearcher provides high-performance fuzzy search capabilities.
20type FuzzySearcher struct {
21 config *CacheConfig
22 resultPool sync.Pool
23}
24
25// NewFuzzySearcher creates a new fuzzy searcher with the given config.
26func NewFuzzySearcher(config *CacheConfig) *FuzzySearcher {
27 fs := &FuzzySearcher{
28 config: config,
29 }
30
31 // Initialize result pool for zero-allocation queries
32 fs.resultPool = sync.Pool{
33 New: func() interface{} {
34 return &FuzzyResult{
35 Matches: make([]FuzzyMatch, 0, config.MaxResults),
36 }
37 },
38 }
39
40 return fs
41}
42
43// Search performs a fuzzy search on the cache and returns ranked results.
44func (c *DmenuFuzzyCache) Search(query string, config *CacheConfig) *FuzzyResult {
45 if len(query) == 0 {
46 return c.getTopEntries(config)
47 }
48
49 startTime := time.Now()
50
51 // Get result object from pool
52 searcher := NewFuzzySearcher(config)
53 result := searcher.resultPool.Get().(*FuzzyResult)
54 result.Reset()
55
56 c.mu.RLock()
57 defer c.mu.RUnlock()
58
59 // Phase 1: Fast candidate selection using indices
60 candidates := c.getAllCandidates(query)
61
62 // Phase 2: Score candidates using fuzzy algorithms
63 matches := make([]FuzzyMatch, 0, len(candidates))
64
65 if len(candidates) == 0 {
66 // Fallback: search all entries (should be rare)
67 candidates = make([]uint32, len(c.entries))
68 for i := range c.entries {
69 candidates[i] = uint32(i)
70 }
71 }
72
73 // Limit candidates to avoid excessive computation
74 if len(candidates) > 1000 {
75 candidates = candidates[:1000]
76 }
77
78 for _, entryID := range candidates {
79 if int(entryID) >= len(c.entries) {
80 continue
81 }
82
83 match := searcher.scoreEntry(query, &c.entries[entryID])
84 if match.Score >= config.ScoreThreshold {
85 matches = append(matches, match)
86 }
87 }
88
89 // Phase 3: Sort by score and apply limits
90 sort.Slice(matches, func(i, j int) bool {
91 return matches[i].Score > matches[j].Score
92 })
93
94 if len(matches) > config.MaxResults {
95 matches = matches[:config.MaxResults]
96 }
97
98 result.Matches = matches
99 result.QueryTime = time.Since(startTime)
100
101 return result
102}
103
104// getTopEntries returns the top entries when no query is provided.
105func (c *DmenuFuzzyCache) getTopEntries(config *CacheConfig) *FuzzyResult {
106 c.mu.RLock()
107 defer c.mu.RUnlock()
108
109 startTime := time.Now()
110
111 // Use pre-sorted index for O(1) access to top entries
112 maxResults := config.MaxResults
113 if maxResults > len(c.sortedIndex) {
114 maxResults = len(c.sortedIndex)
115 }
116
117 matches := make([]FuzzyMatch, maxResults)
118 for i := 0; i < maxResults; i++ {
119 entryID := c.sortedIndex[i]
120 matches[i] = FuzzyMatch{
121 Entry: &c.entries[entryID],
122 Score: float64(c.entries[entryID].Score) / 65535.0, // Normalize to 0-1
123 RecencyScore: 1.0, // No query, so full recency weight
124 VisitScore: 1.0, // No query, so full visit weight
125 MatchType: MatchTypeExact,
126 }
127 }
128
129 return &FuzzyResult{
130 Matches: matches,
131 QueryTime: time.Since(startTime),
132 }
133}
134
135// scoreEntry calculates the fuzzy match score for a single entry.
136func (fs *FuzzySearcher) scoreEntry(query string, entry *CompactEntry) FuzzyMatch {
137 match := FuzzyMatch{
138 Entry: entry,
139 }
140
141 queryNorm := normalizeText(query)
142 urlNorm := normalizeText(entry.URL)
143 titleNorm := normalizeText(entry.Title)
144
145 // Calculate different types of similarity
146 match.URLScore = fs.calculateTextSimilarity(queryNorm, urlNorm)
147 match.TitleScore = fs.calculateTextSimilarity(queryNorm, titleNorm)
148
149 // Boost exact matches
150 if strings.Contains(urlNorm, queryNorm) {
151 match.URLScore = math.Max(match.URLScore, exactMatchBonus)
152 match.MatchType = MatchTypeExact
153 }
154 if strings.Contains(titleNorm, queryNorm) {
155 match.TitleScore = math.Max(match.TitleScore, exactMatchBonus)
156 match.MatchType = MatchTypeExact
157 }
158
159 // Boost prefix matches
160 if strings.HasPrefix(urlNorm, queryNorm) {
161 match.URLScore = math.Max(match.URLScore, prefixMatchBonus)
162 if match.MatchType != MatchTypeExact {
163 match.MatchType = MatchTypePrefix
164 }
165 }
166 if strings.HasPrefix(titleNorm, queryNorm) {
167 match.TitleScore = math.Max(match.TitleScore, prefixMatchBonus)
168 if match.MatchType != MatchTypeExact {
169 match.MatchType = MatchTypePrefix
170 }
171 }
172
173 // Calculate recency and visit scores
174 match.RecencyScore = fs.calculateRecencyScore(entry.LastVisit)
175 match.VisitScore = fs.calculateVisitScore(entry.VisitCount)
176
177 // Determine final match type if not already set
178 if match.MatchType == 0 {
179 if match.URLScore > 0.7 || match.TitleScore > 0.7 {
180 match.MatchType = MatchTypeFuzzy
181 } else {
182 match.MatchType = MatchTypeTrigram
183 }
184 }
185
186 // Calculate weighted final score
187 match.Score = fs.config.URLWeight*match.URLScore +
188 fs.config.TitleWeight*match.TitleScore +
189 fs.config.RecencyWeight*match.RecencyScore +
190 fs.config.VisitWeight*match.VisitScore
191
192 return match
193}
194
195// calculateTextSimilarity computes similarity between query and text using multiple algorithms.
196func (fs *FuzzySearcher) calculateTextSimilarity(query, text string) float64 {
197 if query == text {
198 return 1.0
199 }
200
201 if len(query) == 0 || len(text) == 0 {
202 return 0.0
203 }
204
205 // Use different algorithms based on text length for optimal performance
206 if len(query) <= 3 {
207 // For short queries, use substring matching
208 return fs.substringSimilarity(query, text)
209 } else if len(query) <= 10 {
210 // For medium queries, use Jaro-Winkler
211 return fs.jaroWinklerSimilarity(query, text)
212 }
213 // For long queries, use tokenized matching
214 return fs.tokenizedSimilarity(query, text)
215}
216
217// substringSimilarity calculates similarity based on substring matches with position weighting.
218func (fs *FuzzySearcher) substringSimilarity(query, text string) float64 {
219 index := strings.Index(text, query)
220 if index == -1 {
221 return 0.0
222 }
223
224 // Base score
225 baseScore := float64(len(query)) / float64(len(text))
226
227 // Position bonus (earlier matches are better)
228 positionBonus := 1.0
229 if index == 0 {
230 positionBonus = 1.5 // Start of string
231 } else if index < len(text)/3 {
232 positionBonus = 1.2 // First third
233 }
234
235 score := baseScore * positionBonus
236 if score > 1.0 {
237 score = 1.0
238 }
239
240 return score
241}
242
243// jaroWinklerSimilarity calculates Jaro-Winkler similarity (optimized version).
244func (fs *FuzzySearcher) jaroWinklerSimilarity(s1, s2 string) float64 {
245 if s1 == s2 {
246 return 1.0
247 }
248
249 len1, len2 := len(s1), len(s2)
250 if len1 == 0 || len2 == 0 {
251 return 0.0
252 }
253
254 // Calculate match window
255 matchWindow := (maxInt(len1, len2) / 2) - 1
256 if matchWindow < 0 {
257 matchWindow = 0
258 }
259
260 matches1 := make([]bool, len1)
261 matches2 := make([]bool, len2)
262 matches := 0
263
264 // Find matches
265 for i := 0; i < len1; i++ {
266 start := maxInt(0, i-matchWindow)
267 end := minInt(i+matchWindow+1, len2)
268
269 for j := start; j < end; j++ {
270 if matches2[j] || s1[i] != s2[j] {
271 continue
272 }
273 matches1[i] = true
274 matches2[j] = true
275 matches++
276 break
277 }
278 }
279
280 if matches == 0 {
281 return 0.0
282 }
283
284 // Count transpositions
285 transpositions := 0
286 k := 0
287 for i := 0; i < len1; i++ {
288 if !matches1[i] {
289 continue
290 }
291 for !matches2[k] {
292 k++
293 }
294 if s1[i] != s2[k] {
295 transpositions++
296 }
297 k++
298 }
299
300 // Calculate Jaro similarity
301 jaro := (float64(matches)/float64(len1) +
302 float64(matches)/float64(len2) +
303 float64(matches-transpositions/2)/float64(matches)) / 3.0
304
305 // Jaro-Winkler modification
306 if jaro < 0.7 {
307 return jaro
308 }
309
310 // Common prefix (up to 4 characters)
311 prefix := 0
312 for i := 0; i < minInt(minInt(len1, len2), prefixLength); i++ {
313 if s1[i] == s2[i] {
314 prefix++
315 } else {
316 break
317 }
318 }
319
320 return jaro + (0.1 * float64(prefix) * (1 - jaro))
321}
322
323// tokenizedSimilarity performs token-based matching for longer texts.
324func (fs *FuzzySearcher) tokenizedSimilarity(query, text string) float64 {
325 queryTokens := strings.Fields(query)
326 textTokens := strings.Fields(text)
327
328 if len(queryTokens) == 0 || len(textTokens) == 0 {
329 return 0.0
330 }
331
332 totalScore := 0.0
333 matchedTokens := 0
334
335 for _, queryToken := range queryTokens {
336 bestScore := 0.0
337 for _, textToken := range textTokens {
338 score := fs.jaroWinklerSimilarity(queryToken, textToken)
339 if score > bestScore {
340 bestScore = score
341 }
342 }
343 if bestScore >= 0.6 { // Token match threshold
344 totalScore += bestScore
345 matchedTokens++
346 }
347 }
348
349 if matchedTokens == 0 {
350 return 0.0
351 }
352
353 // Average score weighted by matched token ratio
354 avgScore := totalScore / float64(matchedTokens)
355 tokenRatio := float64(matchedTokens) / float64(len(queryTokens))
356
357 return avgScore * tokenRatio
358}
359
360// calculateRecencyScore calculates score based on how recently the entry was visited.
361func (fs *FuzzySearcher) calculateRecencyScore(lastVisitDays uint32) float64 {
362 now := time.Now()
363 lastVisit := TimeFromDays(lastVisitDays)
364 daysSince := now.Sub(lastVisit).Hours() / 24
365
366 // Exponential decay over 30 days
367 return math.Exp(-daysSince / recencyDecayDays)
368}
369
370// calculateVisitScore calculates score based on visit count with logarithmic scaling.
371func (fs *FuzzySearcher) calculateVisitScore(visitCount uint16) float64 {
372 if visitCount == 0 {
373 return 0.0
374 }
375
376 // Logarithmic scaling to prevent highly visited sites from dominating
377 score := math.Log1p(float64(visitCount)) / math.Log1p(maxVisitNormal)
378 if score > 1.0 {
379 score = 1.0
380 }
381
382 return score
383}
384
385// Helper functions
386func maxInt(a, b int) int {
387 if a > b {
388 return a
389 }
390 return b
391}
392
393func minInt(a, b int) int {
394 if a < b {
395 return a
396 }
397 return b
398}