Search Part IV: Fuzziness

Contextual search and optimizations

HTML

<script src="https://cdnjs.cloudflare.com/ajax/libs/angular.js/1.4.7/angular.min.js"></script>
<div ng-controller="MyCtrl">
    <h2>Part 4: Fuzzy Search</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>
            <tr>
                <th>Search Result</th>
                <th>Distance</th>
                <th>Context</th>
            </tr>
            <tr ng-repeat="word in results" ng-cloak>
                <td>
                {{word.value}}:{{word.position}}
                </td>
                <td>{{word.distance}}</td>
                <td><em>
                    {{dict.slice(word.position - context, word.position + context).join(' ')}}</em>
                </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;
    border: 1px solid #ddd;
    padding: 2px;
}

table td {
    border: 1px solid #ddd;
    padding: 2px;
}

em {
    font-style:italic;
}

JavaScript

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

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 = 3; i < word.length+1; i++) {
            var s = word.substring(i - 3, 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] = select(ngrams, 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] || []; }
        if (!textIn || textIn.length < 3) return [];
        var ngrams = Object.keys(ngramize({}, textIn, 0));
        var fuzzyNGrams = select(unique(flatten(ngrams.map(function(trigram) {
                return $scope.fuzzMap[trigram] || [trigram];
            }))), function(ngram) {
            return ngrams.indexOf(ngram) === -1;
        });
        var exact = ngrams.map(keyOnHash);
        var fuzzy = fuzzyNGrams.map(keyOnHash);
        return rank(exact, fuzzy, textIn);
    };
    
    // Rank the results by distance
    var rank = function(exact, fuzzy, textIn) {
        var...