Fuzzy Search

fuzzySearch.js

function fuzzySearchFirstTry(array, input) {
  var halved = [].concat(array);
  var output = [].concat(array);

  for (var letter of input) {
    if (letter === ' ') {
      continue;
    }

    halved = halved
      .map((element, j) => {
        var i = element.indexOf(letter);
      
        if (i === -1) {
          output[j] = '';
          return '';
        }
      
        return element.slice(i + 1);
      });
    
    output = output.filter(Boolean);
    halved = halved.filter(Boolean);
  }
  
  return output.filter(Boolean);
}

function fuzzySearch(array, input) {  
  return array.filter((str) => {
    var sanitizedInput = input.replace(/\s/g, '');
    var offset = 0;

    for (var letter of sanitizedInput) {
      offset = str.indexOf(letter, offset);
      
      if (offset === -1) {
        return false;
      }
    }
    
    return true;
  });
}

function last(array) {
  return array[array.length - 1];
}

function highlight(str, offsets) {
  return str
    .split('')
    .map((x, i) => offsets.includes(i) ? x.toUpperCase() : x)
    .join('');
}

function getOffsets(str, search) {
  var output = [];

  for (var letter of search) {
    var index = str.indexOf(letter, last(output));
   
    if (index === -1) {
      return null;
    }
    
    output.push(index);
  }
  
  return output;
}

function fuzzySearchHighlight(array, search) { 
  var sanitizedSearch = search.replace(/\s/g, '');

  return array
    .map((str) => {
      var offsets = getOffsets(str, sanitizedSearch);
    
      return offsets ? highlight(str, offsets) : null;
    })
    .filter(Boolean);
}

var dirs = [
  '/projects/fuzzysearch/dist/index.js',
  '/projects/fuzzysearch/src/index.js',
  '/projects/api/src/server.js',
  '/projects/api/src/modules/users/router.js',
  '/projects/api/src/modules/users/controller.js',
  '/projects/api/src/modules/users/service.js',
  '/projects/api/src/modules/transactions/router.js',
  '/projects/api/src/modules/transactions/controller.js',
  '/projects/api/src/modules/transactions/service.js',
  '/projects/api/src/index.js'
];

console.log(fuzzySearch(dirs, 'projects dist js'));
console.log(fuzzySearchHighlight(dirs, 'api modules'));