File size: 3,292 Bytes
4e23b01 | 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 138 | /**
* Fuzzy matching utilities.
* Matches if all query characters appear in order (not necessarily consecutive).
* Lower score = better match.
*/
export interface FuzzyMatch {
matches: boolean;
score: number;
}
export function fuzzyMatch(query: string, text: string): FuzzyMatch {
const queryLower = query.toLowerCase();
const textLower = text.toLowerCase();
const matchQuery = (normalizedQuery: string): FuzzyMatch => {
if (normalizedQuery.length === 0) {
return { matches: true, score: 0 };
}
if (normalizedQuery.length > textLower.length) {
return { matches: false, score: 0 };
}
let queryIndex = 0;
let score = 0;
let lastMatchIndex = -1;
let consecutiveMatches = 0;
for (let i = 0; i < textLower.length && queryIndex < normalizedQuery.length; i++) {
if (textLower[i] === normalizedQuery[queryIndex]) {
const isWordBoundary = i === 0 || /[\s\-_./:]/.test(textLower[i - 1]!);
// Reward consecutive matches
if (lastMatchIndex === i - 1) {
consecutiveMatches++;
score -= consecutiveMatches * 5;
} else {
consecutiveMatches = 0;
// Penalize gaps
if (lastMatchIndex >= 0) {
score += (i - lastMatchIndex - 1) * 2;
}
}
// Reward word boundary matches
if (isWordBoundary) {
score -= 10;
}
// Slight penalty for later matches
score += i * 0.1;
lastMatchIndex = i;
queryIndex++;
}
}
if (queryIndex < normalizedQuery.length) {
return { matches: false, score: 0 };
}
if (normalizedQuery === textLower) {
score -= 100;
}
return { matches: true, score };
};
const primaryMatch = matchQuery(queryLower);
if (primaryMatch.matches) {
return primaryMatch;
}
const alphaNumericMatch = queryLower.match(/^(?<letters>[a-z]+)(?<digits>[0-9]+)$/);
const numericAlphaMatch = queryLower.match(/^(?<digits>[0-9]+)(?<letters>[a-z]+)$/);
const swappedQuery = alphaNumericMatch
? `${alphaNumericMatch.groups?.["digits"] ?? ""}${alphaNumericMatch.groups?.["letters"] ?? ""}`
: numericAlphaMatch
? `${numericAlphaMatch.groups?.["letters"] ?? ""}${numericAlphaMatch.groups?.["digits"] ?? ""}`
: "";
if (!swappedQuery) {
return primaryMatch;
}
const swappedMatch = matchQuery(swappedQuery);
if (!swappedMatch.matches) {
return primaryMatch;
}
return { matches: true, score: swappedMatch.score + 5 };
}
/**
* Filter and sort items by fuzzy match quality (best matches first).
* Supports whitespace- and slash-separated tokens: all tokens must match.
*/
export function fuzzyFilter<T>(items: T[], query: string, getText: (item: T) => string): T[] {
if (!query.trim()) {
return items;
}
const tokens = query
.trim()
.split(/[\s/]+/)
.filter((t) => t.length > 0);
if (tokens.length === 0) {
return items;
}
const results: { item: T; totalScore: number }[] = [];
for (const item of items) {
const text = getText(item);
let totalScore = 0;
let allMatch = true;
for (const token of tokens) {
const match = fuzzyMatch(token, text);
if (match.matches) {
totalScore += match.score;
} else {
allMatch = false;
break;
}
}
if (allMatch) {
results.push({ item, totalScore });
}
}
results.sort((a, b) => a.totalScore - b.totalScore);
return results.map((r) => r.item);
}
|