Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 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 | 17x 60x 60x 60x 60x 60x 60x 60x 60x 60x 330x 60x 330x 60x 698x 698x 698x 698x 60x 60x 60x 9x 9x 9x 2x 60x 60x 60x 60x 161x 161x 161x 515x 277x 238x 515x 161x 161x 161x 161x 161x 161x 3104x 3104x 1225x 1879x 3104x 11x 11x 11x 11x 11x 9x 2x 161x 60x 101x 60x | module.exports = function (text, pattern, options) {
// Aproximately where in the text is the pattern expected to be found?
var Match_Location = options.location || 0
//Determines how close the match must be to the fuzzy location (specified above). An exact letter match which is 'distance' characters away from the fuzzy location would score as a complete mismatch. A distance of '0' requires the match be at the exact location specified, a threshold of '1000' would require a perfect match to be within 800 characters of the fuzzy location to be found using a 0.8 threshold.
var Match_Distance = options.distance || 100
// At what point does the match algorithm give up. A threshold of '0.0' requires a perfect match (of both letters and location), a threshold of '1.0' would match anything.
var Match_Threshold = options.threshold || 0.4
Iif (pattern === text) return true // Exact match
Iif (pattern.length > 32) return false // This algorithm cannot be used
// Set starting location at beginning text and initialise the alphabet.
var loc = Match_Location,
s = (function () {
var q = {},
i
for (i = 0; i < pattern.length; i++) {
q[pattern.charAt(i)] = 0
}
for (i = 0; i < pattern.length; i++) {
q[pattern.charAt(i)] |= 1 << (pattern.length - i - 1)
}
return q
})()
// Compute and return the score for a match with e errors and x location.
// Accesses loc and pattern through being a closure.
function match_bitapScore_(e, x) {
var accuracy = e / pattern.length,
proximity = Math.abs(loc - x)
Iif (!Match_Distance) {
// Dodge divide by zero error.
return proximity ? 1.0 : accuracy
}
return accuracy + proximity / Match_Distance
}
var score_threshold = Match_Threshold, // Highest score beyond which we give up.
best_loc = text.indexOf(pattern, loc) // Is there a nearby exact match? (speedup)
if (best_loc != -1) {
score_threshold = Math.min(match_bitapScore_(0, best_loc), score_threshold)
// What about in the other direction? (speedup)
best_loc = text.lastIndexOf(pattern, loc + pattern.length)
if (best_loc != -1) {
score_threshold = Math.min(match_bitapScore_(0, best_loc), score_threshold)
}
}
// Initialise the bit arrays.
var matchmask = 1 << (pattern.length - 1)
best_loc = -1
var bin_min, bin_mid
var bin_max = pattern.length + text.length
var last_rd
for (var d = 0; d < pattern.length; d++) {
// Scan for the best match; each iteration allows for one more error.
// Run a binary search to determine how far from 'loc' we can stray at this
// error level.
bin_min = 0
bin_mid = bin_max
while (bin_min < bin_mid) {
if (match_bitapScore_(d, loc + bin_mid) <= score_threshold) {
bin_min = bin_mid
} else {
bin_max = bin_mid
}
bin_mid = Math.floor((bin_max - bin_min) / 2 + bin_min)
}
// Use the result from this iteration as the maximum for the next.
bin_max = bin_mid
var start = Math.max(1, loc - bin_mid + 1)
var finish = Math.min(loc + bin_mid, text.length) + pattern.length
var rd = Array(finish + 2)
rd[finish + 1] = (1 << d) - 1
for (var j = finish; j >= start; j--) {
// The alphabet (s) is a sparse hash, so the following line generates
// warnings.
var charMatch = s[text.charAt(j - 1)]
if (d === 0) {
// First pass: exact match.
rd[j] = ((rd[j + 1] << 1) | 1) & charMatch
} else {
// Subsequent passes: fuzzy match.
rd[j] = (((rd[j + 1] << 1) | 1) & charMatch) | (((last_rd[j + 1] | last_rd[j]) << 1) | 1) | last_rd[j + 1]
}
if (rd[j] & matchmask) {
var score = match_bitapScore_(d, j - 1)
// This match will almost certainly be better than any existing match.
// But check anyway.
Eif (score <= score_threshold) {
// Told you so.
score_threshold = score
best_loc = j - 1
if (best_loc > loc) {
// When passing loc, don't exceed our current distance from loc.
start = Math.max(1, 2 * loc - best_loc)
} else {
// Already passed loc, downhill from here on in.
break
}
}
}
}
// No hope for a (better) match at greater error levels.
if (match_bitapScore_(d + 1, loc) > score_threshold) {
break
}
last_rd = rd
}
return best_loc < 0 ? false : true
}
|