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

Ответ 1

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

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

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

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

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

1. Longest Common Substring distance: минимальное количество символов, которое необходимо удалить в обеих строках, пока результирующие подстроки не будут идентичны.

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

3. Расстояние по Джакарте : 1 мин. Отношение общих N-грамм и всех наблюдаемых N-грамм.

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

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

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

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

Ответ 2

Я попытался использовать существующие нечеткие библиотеки, такие как 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}]

Ответ 3

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

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

Также есть fiddle

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

Ответ 4

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

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

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

Ответ 5

(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/

Ответ 6

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

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