Fuzzy JS Search

by soundjewel

HTML

<script src="https://cdnjs.cloudflare.com/ajax/libs/angular.js/1.4.7/angular.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/angular.js/1.5.0-beta.1/angular-sanitize.min.js"></script>
<div ng-controller="MyCtrl">
    <h2>Part 5: Search Optimizations</h2>
    <div>Search: <input type="text" ng-model="textIn"></input></div>
    <div>Context (#)<input type="number" ng-model="context" default=1></input></div>
    <div>Fuzziness (#)<input type="number" ng-model="fuzziness" default=1></input></div>
    <div>
        <table>
            <caption>Search Results</caption>
            <tr>
                <th>Context</th>
                <th>Score</th>
            </tr>
            <tr ng-repeat="result in results">
                <td data-ng-bind-html="result.highlighted"></td>
                <td>{{::result.score | number:1}}</td>
            </tr>
        </table>
        <table>
            <caption>Matching Words</caption>
            <tr>
                <th>Search Result:</th>
                <th>Distance:</th>
                <th>Context</th>
            </tr>
            <tr ng-repeat="word in matches">
                <td>{{::word.value}} | {{::word.position}}</td>
                <td>{{::word.distance}}</td>
                <td></td>
            </tr>
        </table>
    </div>
</div>

CSS

h2 {
    font-size: 150%;
}

table {
    margin-top: 10px;
    border: 1px solid #ccc;
    width: 100%;
}

table th {
    font-weight: bold;
}

em {
    font-style:italic;
}

JavaScript

var myApp = angular.module('myApp',['ngSanitize']);

myApp.controller('MyCtrl', function($scope) {
    // Compute NGrams
    var computeNGrams = function(dict) {    
        $scope.dict = dict.split(' ');
        return $scope.dict.reduce(ngramize, {});
    };
    
    // NGramize a word
    var ngramize = function(hash, word, index) {
        for (var i = 2; i < word.length+1; i++) {
            var s = word.substring(i - 2, i);
            if (!hash.hasOwnProperty(s)) {
                hash[s] = [new Word(word, index, 0)];
            } else {
                hash[s].push(new Word(word, index, 0));
            }
        }
        return hash;
    };
    
    // Compute fuzziness matches based on levenshtein distance = fuzziness
    var computeFuzz = function(hash, fuzziness) {
        var ngrams = Object.keys(hash);
		$scope.fuzzMap = ngrams.reduce(function(fuzzMap, key) {
            fuzzMap[key] = ngrams.filter(function(k) {
                return getEditDistance(k, key) <= fuzziness;
            });
            return fuzzMap;
        }, {});
    };
    
    var merge = function(arrays) {
        var returnArray = [];
        if (!arrays) return [];
        var base = arrays.pop();
        var intersected = arrays.reduce(intersect, base);
        return intersected || [];
    };
    
    var search = function(textIn) {
        function keyOnHash(ngram) { return $scope.hash[ngram] || []; };
        function keyOnFuzzy(ngram) { return $scope.fuzzMap[ngram] || [ngram]; };
        function getRankedWords(word) {
            var ngrams = Object.keys(ngramize({}, word, 0));
            var fuzzyNGrams = ngrams.map(keyOnFuzzy)
            						.flatten()
            						.unique()
            						.filter(function(ngram) { 
                                        return ngrams.indexOf(ngram) === -1; 
                                    }); //only take unique fuzzy ngrams
            var exact = ngrams.map(keyOnHash);
            var fuzzy =...