24
25
export function scoreFuzzy(target: string, query: string, queryLower: string, allowNonContiguousMatches: boolean): FuzzyScore {
27
return NO_SCORE; // return early if target or query are undefined
28
}
30
>
const targetLength = target.length;
31
>
const queryLength = query.length;
32
>
33
>
if (targetLength < queryLength) {
34
return NO_SCORE; // impossible for query to be contained in target
35
}
37
>
// if (DEBUG) {
38
>
// console.group(`Target: ${target}, Query: ${query}`);
39
>
// }
40
>
41
>
const targetLower = target.toLowerCase();
42
>
const res = doScoreFuzzy(query, queryLower, queryLength, target, targetLower, targetLength, allowNonContiguousMatches);
43
>
44
>
// if (DEBUG) {
45
>
// console.log(`%cFinal Score: ${res[0]}`, 'font-weight: bold');
46
>
// console.groupEnd();
47
>
// }
48
>
49
>
return res;
50
>
}
51
52
>
function doScoreFuzzy(query: string, queryLower: string, queryLength: number, target: string, targetLower: string, targetLength: number, allowNonContiguousMatches: boolean): FuzzyScore {
fuzzyScorer.ts
53
>
const scores: number[] = [];
54
>
const matches: number[] = [];
55
>
56
>
//
57
>
// Build Scorer Matrix:
58
>
//
59
>
// The matrix is composed of query q and target t. For each index we score
60
>
// q[i] with t[i] and compare that with the previous score. If the score is
61
>
// equal or larger, we keep the match. In addition to the score, we also keep
62
>
// the length of the consecutive matches to use as boost for the score.
63
>
//
64
>
// t a r g e t
65
>
// q
66
>
// u
67
>
// e
68
>
// r
69
>
// y
70
>
//
71
>
for (let queryIndex = 0; queryIndex < queryLength; queryIndex++) {
72
>
const queryIndexOffset = queryIndex * targetLength;
73
>
const queryIndexPreviousOffset = queryIndexOffset - targetLength;
74
>
75
>
const queryIndexGtNull = queryIndex > 0;
76
>
77
>
const queryCharAtIndex = query[queryIndex];
78
>
const queryLowerCharAtIndex = queryLower[queryIndex];
79
>
80
>
for (let targetIndex = 0; targetIndex < targetLength; targetIndex++) {
81
>
const targetIndexGtNull = targetIndex > 0;
82
>
83
>
const currentIndex = queryIndexOffset + targetIndex;
84
>
const leftIndex = currentIndex - 1;
85
>
const diagIndex = queryIndexPreviousOffset + targetIndex - 1;
86
>
87
>
const leftScore = targetIndexGtNull ? scores[leftIndex] : 0;
88
>
const diagScore = queryIndexGtNull && targetIndexGtNull ? scores[diagIndex] : 0;
89
>
90
>
const matchesSequenceLength = queryIndexGtNull && targetIndexGtNull ? matches[diagIndex] : 0;
91
>
92
>
// If we are not matching on the first query character any more, we only produce a
93
>
// score if we had a score previously for the last query index (by looking at the diagScore).
94
>
// This makes sure that the query always matches in sequence on the target. For example
95
>
// given a target of "ede" and a query of "de", we would otherwise produce a wrong high score
96
>
// for query[1] ("e") matching on target[0] ("e") because of the "beginning of word" boost.
97
>
let score: number;
98
>
if (!diagScore && queryIndexGtNull) {
99
>
score = 0;
100
>
} else {
101
>
score = computeCharScore(queryCharAtIndex, queryLowerCharAtIndex, target, targetLower, targetIndex, matchesSequenceLength);
102
>
}
103
>
104
>
// We have a score and its equal or larger than the left score
105
>
// Match: sequence continues growing from previous diag value
106
>
// Score: increases by diag score value
107
>
const isValidScore = score && diagScore + score >= leftScore;
108
>
if (isValidScore && (
109
>
// We don't need to check if it's contiguous if we allow non-contiguous matches
110
>
allowNonContiguousMatches ||
111
// We must be looking for a contiguous match.
112
// Looking at an index higher than 0 in the query means we must have already