Как оптимизировать эту синхронную функцию «нечеткого поиска» и превратить ее в асинхронную функцию? - PullRequest
Новая
       0

Как оптимизировать эту синхронную функцию «нечеткого поиска» и превратить ее в асинхронную функцию?

0 голосов
/ 02 июня 2018

Проблема

Я пытаюсь реализовать какой-то "нечеткий поиск" в моем проекте на базе Node.js.

Нечеткий поиск - это поиск, который возвращает результаты, даже если строка не совпадает точно.

Я нашел этот код в другом стеке потока нить .Код ниже.

Это довольно хорошо, но проблема в том, что он синхронный. Он замедляет всю программу при поиске в большом массиве.

Вопрос

ES6 методы приветствуются.Должен работать только в последней версии Chrome, поэтому будут работать любые методы JS.

  • Существуют ли новые методы JS, которые оптимизируют эту функцию?

  • Я что-то не так делаю, что делает его еще медленнее?

  • Могу ли я превратить эту функцию в асинхронную функцию, которая возвращает обещание?Не перестанет ли оно зависать во время поиска?

  • Есть ли какие-нибудь лучшие реализации "нечеткого поиска", о которых вы знаете?(Я нашел модуль с именем fuzzysort , но не могу сказать, намного ли он лучше, он не вернет "folder test", если вы введете "test folder" (неправильный порядок), поэтому он не так хорош)

Код

Вызов функции поиска

searchArray - это массив путей, по которым он ищет, например: ["C:\\test", "C:\\file.txt"...] (0.5- 5 миллионов путей)

searchQuery - строка без пробелов, например: filetxt

search () {
  const fuzzySearch = this.fuzzySearch(this.searchQuery.toLowerCase(), this.searchArray) 
  let result = fuzzySearch.filter(element => element.relevance >= 0.3)
  // sort by relevance
  var sortedResults = result.sort((a, b) => parseFloat(b.relevance) - parseFloat(a.relevance)).map(item => item.name);

  this.searchResults = sortedResults
},

Функция нечеткого поиска 

fuzzySearch (searchQuery, searchArray) {
  const get_bigrams = function(string) {
  const s = string.toLowerCase();
  const v = new Array(s.length - 1);
  for (let i = 0, end = v.length; i <= end; i++) {
      v[i] = s.slice(i, i + 2);
  }
  return v;
  };

  const string_similarity = function(str1, str2) {
      if ((str1.length > 0) && (str2.length > 0)) {
          const pairs1 = get_bigrams(str1);
          const pairs2 = get_bigrams(str2);
          const union = pairs1.length + pairs2.length;
          let hit_count = 0;
          for (let x of Array.from(pairs1)) {
              for (let y of Array.from(pairs2)) {
                  if (x === y) {
                      hit_count++;
                  }
              }
          }
          if (hit_count > 0) {
              return ((2.0 * hit_count) / union);
          }
      }
      return 0.0;
  };

  let results = [];
  for (let name of searchArray) {
    // I added .match to use only the base filename (name+ext) not the whole path, and removed all characters
    let filteredPath = name.match(/[^\\\/]+$/)[0].replace(/[^A-Za-z0-9.]+/g, '')

    const relevance = string_similarity(searchQuery, filteredPath);
    const obj = {name, relevance};
    results.push(obj);
  }
  return results
},
...