diff options
Diffstat (limited to 'fuse.js')
| -rw-r--r-- | fuse.js | 19 |
1 files changed, 19 insertions, 0 deletions
@@ -0,0 +1,19 @@ +/** + * Fuse - Lightweight fuzzy-search + * + * Copyright (c) 2012 Kirollos Risk <kirollos@gmail.com>. + * All Rights Reserved. Apache Software License 2.0 + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +(function(){function Searcher(pattern,options){options=options||{};var MATCH_LOCATION=options.location||0,MATCH_DISTANCE=options.distance||100,MATCH_THRESHOLD=options.threshold||.6,pattern=options.caseSensitive?pattern:pattern.toLowerCase(),patternLen=pattern.length;if(patternLen>32){throw new Error("Pattern length is too long")}var matchmask=1<<patternLen-1;var pattern_alphabet=function(){var mask={},i=0;for(i=0;i<patternLen;i++){mask[pattern.charAt(i)]=0}for(i=0;i<patternLen;i++){mask[pattern.charAt(i)]|=1<<pattern.length-i-1}return mask}();function match_bitapScore(e,x){var accuracy=e/patternLen,proximity=Math.abs(MATCH_LOCATION-x);if(!MATCH_DISTANCE){return proximity?1:accuracy}return accuracy+proximity/MATCH_DISTANCE}this.search=function(text){text=options.caseSensitive?text:text.toLowerCase();if(pattern===text){return{isMatch:true,score:0}}var textLen=text.length,score_threshold=MATCH_THRESHOLD,best_loc=text.indexOf(pattern,MATCH_LOCATION),d,j,bin_min,bin_mid,bin_max=patternLen+textLen,last_rd,start,finish,rd,charMatch,score=1;if(best_loc!=-1){score_threshold=Math.min(match_bitapScore(0,best_loc),score_threshold);best_loc=text.lastIndexOf(pattern,MATCH_LOCATION+patternLen);if(best_loc!=-1){score_threshold=Math.min(match_bitapScore(0,best_loc),score_threshold)}}best_loc=-1;for(d=0;d<patternLen;d++){bin_min=0;bin_mid=bin_max;while(bin_min<bin_mid){if(match_bitapScore(d,MATCH_LOCATION+bin_mid)<=score_threshold){bin_min=bin_mid}else{bin_max=bin_mid}bin_mid=Math.floor((bin_max-bin_min)/2+bin_min)}bin_max=bin_mid;start=Math.max(1,MATCH_LOCATION-bin_mid+1);finish=Math.min(MATCH_LOCATION+bin_mid,textLen)+patternLen;rd=Array(finish+2);rd[finish+1]=(1<<d)-1;for(j=finish;j>=start;j--){charMatch=pattern_alphabet[text.charAt(j-1)];if(d===0){rd[j]=(rd[j+1]<<1|1)&charMatch}else{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){score=match_bitapScore(d,j-1);if(score<=score_threshold){score_threshold=score;best_loc=j-1;if(best_loc>MATCH_LOCATION){start=Math.max(1,2*MATCH_LOCATION-best_loc)}else{break}}}}if(match_bitapScore(d+1,MATCH_LOCATION)>score_threshold){break}last_rd=rd}return{isMatch:best_loc>=0,score:score}}}function Fuse(list,options){options=options||{};var keys=options.keys;this.search=function(pattern){var searcher=new Searcher(pattern,options),i,j,item,text,dataLen=list.length,bitapResult,rawResults=[],rawResultsLen,existingResult,results=[],compute=null;function analyzeText(text,entity,index){if(text!==undefined&&text!==null&&typeof text==="string"){bitapResult=searcher.search(text);if(bitapResult.isMatch){existingResult=rawResults[index];if(existingResult){existingResult.score=Math.min(existingResult.score,bitapResult.score)}else{rawResults.push({item:entity,score:bitapResult.score})}}}}if(typeof list[0]==="string"){for(i=0;i<dataLen;i++){analyzeText(list[i],i,i)}}else{for(i=0;i<dataLen;i++){item=list[i];for(j=0;j<keys.length;j++){analyzeText(item[keys[j]],item,i)}}}rawResults.sort(function(a,b){return a.score-b.score});rawResultsLen=rawResults.length;for(i=0;i<rawResultsLen;i++){results.push(options.id?rawResults[i].item[options.id]:rawResults[i].item)}return results}}if(typeof module!=="undefined"){if(typeof module.setExports==="function"){module.setExports(Fuse)}else if(module.exports){module.exports=Fuse}}else{window.Fuse=Fuse}})();
\ No newline at end of file |