# All files / src/utils fuzzy.js

95.08% Statements 58/61
75% Branches 24/32
100% Functions 3/3
98.31% Lines 58/59

    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
    12417x

    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;
    };