Нечеткий поиск Javascript, который имеет смысл

Я ищу библиотеку JavaScript нечеткого поиска для фильтрации массива. Я пробовал использовать fuzzyset.js и fuse.js , но результаты ужасны (есть демонстрации, которые вы можете попробовать на связанных страницах).

После некоторого чтения о расстоянии Левенштейна мне показалось, что это плохое представление о том, что пользователи ищут при вводе текста. Для тех, кто не знает, система вычисляет, сколько вставок , удалений и замен необходимо, чтобы две строки совпали.

Один очевидный недостаток, который закреплен в модели Левенштейна-Demerau, что оба реветь и болвана считаются одинаково похожи на луковицы (каждый из которых требует две замены). Однако ясно, что луковица больше похожа на слюну, чем на слюну. болвана есть, и модель , которую я только что упомянул признает , что, позволяя транспозиций .

Я хочу использовать это в контексте завершения текста, поэтому, если у меня есть массив ['international', 'splint', 'tinder'], и мой запрос int , я думаю, что международный рейтинг должен быть выше, чем шина , даже если у первого есть оценка (выше = хуже) 10 по сравнению с последним 3.

Итак, то, что я ищу (и создам, если ее не существует), - это библиотека, которая выполняет следующие функции:

• Взвешивает различные манипуляции с текстом
• По-разному оценивает каждую манипуляцию в зависимости от того, где они появляются в слове (ранние манипуляции дороже, чем поздние)
• Возвращает список результатов, отсортированных по релевантности

Кто нибудь сталкивался с подобным? Я понимаю, что StackOverflow - не то место, где можно просить рекомендации по программному обеспечению, но подразумевается (уже не сейчас!) В приведенном выше: правильно ли я думаю об этом?

редактировать

Я нашел хорошую статью (pdf) по этой теме. Некоторые примечания и отрывки:

Аффинные функции расстояния редактирования назначают относительно низкую стоимость последовательности вставок или удалений

функция расстояния Монгера-Элкана (Monge & Elkan 1996), которая является аффинным вариантом функции расстояния Смита-Уотермана (Дурбан и др. 1998) с определенными параметрами стоимости

Для расстояния Смита-Ватермана (википедия) : «Вместо того, чтобы смотреть на полную последовательность, алгоритм Смита-Ватермана сравнивает сегменты всех возможных длин и оптимизирует меру сходства». Это подход n-грамм.

В целом похожая метрика, которая не основана на модели расстояния редактирования, - это метрика Яро (Jaro 1995; 1989; Winkler 1999). В литературе по связыванию записей хорошие результаты были получены с использованием вариантов этого метода, который основан на количестве и порядке общих символов между двумя строками.

Вариант этого из-за Винклера (1999) также использует длину P самого длинного общего префикса

(кажется, предназначены в первую очередь для коротких струн)

Для завершения текста подходы Monger-Elkan и Jaro-Winkler кажутся наиболее подходящими. Добавление Винклера к метрике Яро более серьезно влияет на начало слов. А аффинный аспект Monger-Elkan означает, что необходимость дополнить слово (которое представляет собой просто последовательность дополнений) не будет для него слишком неприятным.

Вывод:

рейтинг TFIDF показал лучшие результаты среди нескольких метрик расстояния на основе токенов, а настроенная метрика расстояния редактирования с аффинным разрывом, предложенная Монжем и Элканом, показала лучшие результаты среди нескольких метрик расстояния редактирования строки. Удивительно хорошая метрика расстояния - это быстрая эвристическая схема, предложенная Яро и позже расширенная Винклером. Это работает почти так же хорошо, как схема Монжа-Элкана, но на порядок быстрее. Один простой способ комбинировать метод TFIDF и метод Яро-Винклера - заменить точные совпадения токенов, используемые в TFIDF, приблизительными совпадениями токенов на основе схемы Яро-Винклера. Эта комбинация в среднем работает немного лучше, чем Jaro-Winkler или TFIDF, а иногда и намного лучше. По своим характеристикам он также близок к усвоенной комбинации нескольких лучших показателей, рассмотренных в этой статье.

Хороший вопрос! Но я считаю, что вместо того, чтобы пытаться модифицировать Левенштейна-Демерау, вам может быть лучше попробовать другой алгоритм или объединить / взвесить результаты двух алгоритмов.

Мне кажется, что точное или близкое совпадение с «начальным префиксом» - это то, чему Левенштейн-Демерау не придает особого значения, но ваши очевидные ожидания пользователей будут.

Я искал "лучше, чем Левенштейн" и, среди прочего, нашел следующее:

http://www.joyofdata.de/blog/comparison-of-string-distance-algorithms/

Здесь упоминается ряд мер «расстояния между строками». Три, которые выглядели особенно актуальными для вашего требования, были бы:

1. Наибольшее расстояние от общей подстроки: минимальное количество символов, которые необходимо удалить в обеих строках, пока результирующие подстроки не станут идентичными.

2. q-граммовое расстояние: сумма абсолютных разностей между векторами N-граммов обеих строк.

3. Расстояние Жаккара: 1 минута частное общих N-граммов и всех наблюдаемых N-граммов.

Может быть, вы могли бы использовать взвешенную комбинацию (или минимум) этих показателей с Левенштейном - общая подстрока, общая N-грамма или Жаккар все сильно предпочтут похожие строки - или, возможно, попробуйте просто использовать Жаккар?

В зависимости от размера вашего списка / базы данных эти алгоритмы могут быть умеренно дорогими. Для нечеткого поиска, который я реализовал, я использовал настраиваемое количество N-граммов в качестве «ключей поиска» из БД, а затем запустил дорогостоящую меру расстояния между строками, чтобы отсортировать их в порядке предпочтения.

Я написал несколько заметок о поиске нечетких строк в SQL. Увидеть:

• http://literatejava.com/sql/fuzzy-string-search-sql/

Я пробовал использовать существующие нечеткие библиотеки, такие как fuse.js, но также обнаружил, что они ужасны, поэтому я написал одну, которая ведет себя в основном как возвышенный поиск. https://github.com/farzher/fuzzysort

Единственная возможная опечатка - это транспонирование. Он довольно прочный (1к звезд, 0 проблем) , очень быстрый и легко справится с вашим делом:

fuzzysort.go('int', ['international', 'splint', 'tinder'])
// [{highlighted: '*int*ernational', score: 10}, {highlighted: 'spl*int*', socre: 3003}]

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

get_bigrams = (string) ->
    s = string.toLowerCase()
    v = new Array(s.length - 1)
    for i in [0..v.length] by 1
        v[i] = s.slice(i, i + 2)
    return v

string_similarity = (str1, str2) ->
    if str1.length > 0 and str2.length > 0
        pairs1 = get_bigrams(str1)
        pairs2 = get_bigrams(str2)
        union = pairs1.length + pairs2.length
        hit_count = 0
        for x in pairs1
            for y in pairs2
                if x is y
                    hit_count++
        if hit_count > 0
            return ((2.0 * hit_count) / union)
    return 0.0

Передайте две строки, в string_similarityкоторые вернет число от 0до1.0 зависимости от того, насколько они похожи. В этом примере используется Lo-Dash

Пример использования ....

query = 'jenny Jackson'
names = ['John Jackson', 'Jack Johnson', 'Jerry Smith', 'Jenny Smith']

results = []
for name in names
    relevance = string_similarity(query, name)
    obj = {name: name, relevance: relevance}
    results.push(obj)

results = _.first(_.sortBy(results, 'relevance').reverse(), 10)

console.log results

Также .... есть скрипка

Убедитесь, что ваша консоль открыта, иначе вы ничего не увидите :)

это моя короткая и компактная функция для нечеткого соответствия:

function fuzzyMatch(pattern, str) {
  pattern = '.*' + pattern.split('').join('.*') + '.*';
  const re = new RegExp(pattern);
  return re.test(str);
}

вы можете взглянуть на https://github.com/atom/fuzzaldrin/ lib от Atom .

он доступен на npm, имеет простой API и работал у меня нормально.

> fuzzaldrin.filter(['international', 'splint', 'tinder'], 'int');
< ["international", "splint"]

Обновление за ноябрь 2019 г. Я обнаружил, что у fuse есть довольно приличные улучшения. Однако я не мог заставить его использовать логические операторы (т.е. операторы ИЛИ, И и т.д.), а также не мог использовать интерфейс поиска API для фильтрации результатов.

Я обнаружил nextapps-de/flexsearch: https://github.com/nextapps-de/flexsearch, и я считаю, что он намного превосходит многие другие библиотеки поиска javascript, которые я пробовал, и имеет поддержкуbool , фильтрацию поиска и разбиение на страницы.

Вы можете ввести список объектов javascript для ваших данных поиска (т.е. хранилища), и API довольно хорошо документирован: https://github.com/nextapps-de/flexsearch#api-overview

На данный момент я проиндексировал около 10 000 записей, и мои поиски почти немедленные; т.е. незаметное количество времени на каждый поиск.

вот решение, предоставленное @InternalFX, но в JS (я использовал его для обмена):

function get_bigrams(string){
  var s = string.toLowerCase()
  var v = s.split('');
  for(var i=0; i<v.length; i++){ v[i] = s.slice(i, i + 2); }
  return v;
}

function string_similarity(str1, str2){
  if(str1.length>0 && str2.length>0){
    var pairs1 = get_bigrams(str1);
    var pairs2 = get_bigrams(str2);
    var union = pairs1.length + pairs2.length;
    var hits = 0;
    for(var x=0; x<pairs1.length; x++){
      for(var y=0; y<pairs2.length; y++){
        if(pairs1[x]==pairs2[y]) hits++;
    }}
    if(hits>0) return ((2.0 * hits) / union);
  }
  return 0.0
}

Я исправил проблемы с решением Bigram CoffeeScript от InternalFx и сделал его универсальным решением для n-граммов (вы можете настроить размер граммов).

Это TypeScript, но вы можете удалить аннотации типов, и он также отлично работает как обычный JavaScript.

/**
 * Compares the similarity between two strings using an n-gram comparison method. 
 * The grams default to length 2.
 * @param str1 The first string to compare.
 * @param str2 The second string to compare.
 * @param gramSize The size of the grams. Defaults to length 2.
 */
function stringSimilarity(str1: string, str2: string, gramSize: number = 2) {
  function getNGrams(s: string, len: number) {
    s = ' '.repeat(len - 1) + s.toLowerCase() + ' '.repeat(len - 1);
    let v = new Array(s.length - len + 1);
    for (let i = 0; i < v.length; i++) {
      v[i] = s.slice(i, i + len);
    }
    return v;
  }

  if (!str1?.length || !str2?.length) { return 0.0; }

  //Order the strings by length so the order they're passed in doesn't matter 
  //and so the smaller string's ngrams are always the ones in the set
  let s1 = str1.length < str2.length ? str1 : str2;
  let s2 = str1.length < str2.length ? str2 : str1;

  let pairs1 = getNGrams(s1, gramSize);
  let pairs2 = getNGrams(s2, gramSize);
  let set = new Set<string>(pairs1);

  let total = pairs2.length;
  let hits = 0;
  for (let item of pairs2) {
    if (set.delete(item)) {
      hits++;
    }
  }
  return hits / total;
}

Примеры:

console.log(stringSimilarity("Dog", "Dog"))
console.log(stringSimilarity("WolfmanJackIsDaBomb", "WolfmanJackIsDaBest"))
console.log(stringSimilarity("DateCreated", "CreatedDate"))
console.log(stringSimilarity("a", "b"))
console.log(stringSimilarity("CreateDt", "DateCreted"))
console.log(stringSimilarity("Phyllis", "PyllisX"))
console.log(stringSimilarity("Phyllis", "Pylhlis"))
console.log(stringSimilarity("cat", "cut"))
console.log(stringSimilarity("cat", "Cnut"))
console.log(stringSimilarity("cc", "Cccccccccccccccccccccccccccccccc"))
console.log(stringSimilarity("ab", "ababababababababababababababab"))
console.log(stringSimilarity("a whole long thing", "a"))
console.log(stringSimilarity("a", "a whole long thing"))
console.log(stringSimilarity("", "a non empty string"))
console.log(stringSimilarity(null, "a non empty string"))

Попробуйте это на игровой площадке TypeScript

(function (int) {
    $("input[id=input]")
        .on("input", {
        sort: int
    }, function (e) {
        $.each(e.data.sort, function (index, value) {
          if ( value.indexOf($(e.target).val()) != -1 
              && value.charAt(0) === $(e.target).val().charAt(0) 
              && $(e.target).val().length === 3 ) {
                $("output[for=input]").val(value);
          };
          return false
        });
        return false
    });
}(["international", "splint", "tinder"]))

jsfiddle http://jsfiddle.net/guest271314/QP7z5/

Проверьте мое дополнение к Google Таблицам под названием Flookup и используйте эту функцию:

Flookup (lookupValue, tableArray, lookupCol, indexNum, threshold, [rank])

Подробные сведения о параметрах:

1. lookupValue: ценность, которую вы ищете
2. tableArray: таблица, в которой нужно искать
3. lookupCol: столбец, в котором нужно выполнить поиск
4. indexNum: столбец, из которого должны быть возвращены данные
5. threshold: процент сходства, ниже которого данные не должны возвращаться
6. rank: n-е наилучшее совпадение (то есть, если первое совпадение вам не нравится)

Это должно удовлетворить ваши требования ... хотя я не уверен в пункте номер 2.

Узнайте больше на официальном сайте .