Сравнить строки Возврат Javascript% вероятности

87

Я ищу функцию JavaScript, которая может сравнивать две строки и возвращать вероятность того, что они похожи. Я посмотрел на soundex, но это не очень хорошо для строк из нескольких слов или без имен. Я ищу такую ​​функцию, как:

function compare(strA,strB){

}

compare("Apples","apple") = Some X Percentage.

Функция будет работать со всеми типами строк, включая числа, многословные значения и имена. Может быть, я мог бы использовать простой алгоритм?

Ultimately none of these served my purpose so I used this:

 function compare(c, u) {
        var incept = false;
        var ca = c.split(",");
        u = clean(u);
        //ca = correct answer array (Collection of all correct answer)
        //caa = a single correct answer word array (collection of words of a single correct answer)
        //u = array of user answer words cleaned using custom clean function
        for (var z = 0; z < ca.length; z++) {
            caa = $.trim(ca[z]).split(" ");
            var pc = 0;
            for (var x = 0; x < caa.length; x++) {
                for (var y = 0; y < u.length; y++) {
                    if (soundex(u[y]) != null && soundex(caa[x]) != null) {
                        if (soundex(u[y]) == soundex(caa[x])) {
                            pc = pc + 1;
                        }
                    }
                    else {
                        if (u[y].indexOf(caa[x]) > -1) {
                            pc = pc + 1;
                        }
                    }
                }
            }
            if ((pc / caa.length) > 0.5) {
                return true;
            }
        }
        return false;
    }

    // create object listing the SOUNDEX values for each letter
    // -1 indicates that the letter is not coded, but is used for coding
    //  0 indicates that the letter is omitted for modern census archives
    //                              but acts like -1 for older census archives
    //  1 is for BFPV
    //  2 is for CGJKQSXZ
    //  3 is for DT
    //  4 is for L
    //  5 is for MN my home state
    //  6 is for R
    function makesoundex() {
        this.a = -1
        this.b = 1
        this.c = 2
        this.d = 3
        this.e = -1
        this.f = 1
        this.g = 2
        this.h = 0
        this.i = -1
        this.j = 2
        this.k = 2
        this.l = 4
        this.m = 5
        this.n = 5
        this.o = -1
        this.p = 1
        this.q = 2
        this.r = 6
        this.s = 2
        this.t = 3
        this.u = -1
        this.v = 1
        this.w = 0
        this.x = 2
        this.y = -1
        this.z = 2
    }

    var sndx = new makesoundex()

    // check to see that the input is valid
    function isSurname(name) {
        if (name == "" || name == null) {
            return false
        } else {
            for (var i = 0; i < name.length; i++) {
                var letter = name.charAt(i)
                if (!(letter >= 'a' && letter <= 'z' || letter >= 'A' && letter <= 'Z')) {
                    return false
                }
            }
        }
        return true
    }

    // Collapse out directly adjacent sounds
    // 1. Assume that surname.length>=1
    // 2. Assume that surname contains only lowercase letters
    function collapse(surname) {
        if (surname.length == 1) {
            return surname
        }
        var right = collapse(surname.substring(1, surname.length))
        if (sndx[surname.charAt(0)] == sndx[right.charAt(0)]) {
            return surname.charAt(0) + right.substring(1, right.length)
        }
        return surname.charAt(0) + right
    }

    // Collapse out directly adjacent sounds using the new National Archives method
    // 1. Assume that surname.length>=1
    // 2. Assume that surname contains only lowercase letters
    // 3. H and W are completely ignored
    function omit(surname) {
        if (surname.length == 1) {
            return surname
        }
        var right = omit(surname.substring(1, surname.length))
        if (!sndx[right.charAt(0)]) {
            return surname.charAt(0) + right.substring(1, right.length)
        }
        return surname.charAt(0) + right
    }

    // Output the coded sequence
    function output_sequence(seq) {
        var output = seq.charAt(0).toUpperCase() // Retain first letter
        output += "-" // Separate letter with a dash
        var stage2 = seq.substring(1, seq.length)
        var count = 0
        for (var i = 0; i < stage2.length && count < 3; i++) {
            if (sndx[stage2.charAt(i)] > 0) {
                output += sndx[stage2.charAt(i)]
                count++
            }
        }
        for (; count < 3; count++) {
            output += "0"
        }
        return output
    }

    // Compute the SOUNDEX code for the surname
    function soundex(value) {
        if (!isSurname(value)) {
            return null
        }
        var stage1 = collapse(value.toLowerCase())
        //form.result.value=output_sequence(stage1);

        var stage1 = omit(value.toLowerCase())
        var stage2 = collapse(stage1)
        return output_sequence(stage2);

    }

    function clean(u) {
        var u = u.replace(/\,/g, "");
        u = u.toLowerCase().split(" ");
        var cw = ["ARRAY OF WORDS TO BE EXCLUDED FROM COMPARISON"];
        var n = [];
        for (var y = 0; y < u.length; y++) {
            var test = false;
            for (var z = 0; z < cw.length; z++) {
                if (u[y] != "" && u[y] != cw[z]) {
                    test = true;
                    break;
                }
            }
            if (test) {
    //Don't use & or $ in comparison
                var val = u[y].replace("$", "").replace("&", "");
                n.push(val);
            }
        }
        return n;
    }
Брэд Рудерман
источник
Я тестирую это, но все еще не могу найти идеальный. Классический пример, который ломает их. Скажите, что вопрос: «Каковы первые два президента?» и кто-то отвечает "Адамс и Вашингтон". Сравнение строк с «Джорджем Вашингтоном и Джоном Адамсом» должно составлять примерно 50%.
Брэд Рудерман
oof, зависит от jQuery?
Шон Уинни

Ответы:

138

Вот ответ, основанный на расстоянии Левенштейна https://en.wikipedia.org/wiki/Levenshtein_distance

function similarity(s1, s2) {
  var longer = s1;
  var shorter = s2;
  if (s1.length < s2.length) {
    longer = s2;
    shorter = s1;
  }
  var longerLength = longer.length;
  if (longerLength == 0) {
    return 1.0;
  }
  return (longerLength - editDistance(longer, shorter)) / parseFloat(longerLength);
}

Для расчета расстояния редактирования

function editDistance(s1, s2) {
  s1 = s1.toLowerCase();
  s2 = s2.toLowerCase();

  var costs = new Array();
  for (var i = 0; i <= s1.length; i++) {
    var lastValue = i;
    for (var j = 0; j <= s2.length; j++) {
      if (i == 0)
        costs[j] = j;
      else {
        if (j > 0) {
          var newValue = costs[j - 1];
          if (s1.charAt(i - 1) != s2.charAt(j - 1))
            newValue = Math.min(Math.min(newValue, lastValue),
              costs[j]) + 1;
          costs[j - 1] = lastValue;
          lastValue = newValue;
        }
      }
    }
    if (i > 0)
      costs[s2.length] = lastValue;
  }
  return costs[s2.length];
}

Применение

similarity('Stack Overflow','Stack Ovrflw')

возвращает 0.8571428571428571


Вы можете поиграть с ним ниже:

повелитель1234
источник
Улучшение для нескольких слов: var Similarity2 = function (s1, s2) {var split1 = s1.split (''); вар split2 = s2.split (''); var sum = 0; var max = 0; var temp = 0; для (var я = 0; я <split1.length; я ++) {макс = 0; для (var j = 0; j <split2.length; j ++) {temp = подобие (split1 [i], split2 [j]); если (макс <температура) макс = температура; } console.log (макс.); сумма + = max / split1.length; } возвратная сумма; };
infinito84
@ overlord1234 Работает ли описанный выше метод для такой строки: 9e27dbb9ff6eea70821c02b4457cbc6b7eb8e12a64f46c192c3a05f1bc1519acd101193dac157c6233d9d773f9b364ca210bea6782b90f9d
hyperfkcb 05
Он работает со строками без привязки к семантике. Пожалуйста, попробуйте запустить встроенный фрагмент кода (спасибо Дэвиду). Когда я ввожу вышеупомянутые строки, я получаю сходство 0,17857142857142858.
overlord1234
@hyperfkcb он реализует алгоритм расстояния редактирования, который подсчитывает, сколько символов находится в неправильном положении (более или менее), поэтому для расчета процента он берет более длинное возможное значение расстояния редактирования (longLength) и делает (longLength - editDistance) / longLength.
infinito84
Однако для длинных струн он слишком медленный.
Upupming
14

Вот очень простая функция, которая выполняет сравнение и возвращает процент, основанный на эквивалентности. Хотя он не был протестирован для всех возможных сценариев, он может помочь вам начать работу.

function similar(a,b) {
    var equivalency = 0;
    var minLength = (a.length > b.length) ? b.length : a.length;    
    var maxLength = (a.length < b.length) ? b.length : a.length;    
    for(var i = 0; i < minLength; i++) {
        if(a[i] == b[i]) {
            equivalency++;
        }
    }
    

    var weight = equivalency / maxLength;
    return (weight * 100) + "%";
}
alert(similar("test","tes"));   // 75%
alert(similar("test","test"));  // 100%
alert(similar("test","testt")); // 80%
alert(similar("test","tess"));  // 75%
jmort253
источник
9
Проблема в том, что «atest» и «test» возвращают 0%, что, как мы знаем, неверно.
peresisUser
8

Использование этой библиотеки для поиска схожести строк сработало для меня как прелесть!

Вот пример -

var similarity = stringSimilarity.compareTwoStrings("Apples","apple");    // => 0.88
Тушар Вальзаде
источник
6
Это здорово, за исключением того, что у stringSimilarity есть зависимость под названием lodash, которая содержит более 1000 файлов, помещаемых в ваш проект, чтобы вы могли получить сходство строк.
GrumpyCrouton
2
Да, такое бывает при локальном добавлении пакета. Но вместо этого мы можем использовать CDN для меньшего размера пакета. Вот ссылки на CDN - jsdelivr.com/package/npm/lodash - jsdelivr.com/package/npm/string-similarity
Tushar Walzade
2
Они удалили большинство зависимостей, в том числе lodash
Løvenkrands
7

Я быстро написал только одно, которое может быть достаточно хорошим для ваших целей:

function Compare(strA,strB){
    for(var result = 0, i = strA.length; i--;){
        if(typeof strB[i] == 'undefined' || strA[i] == strB[i]);
        else if(strA[i].toLowerCase() == strB[i].toLowerCase())
            result++;
        else
            result += 4;
    }
    return 1 - (result + 4*Math.abs(strA.length - strB.length))/(2*(strA.length+strB.length));
}

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

Compare("Apple", "Apple")    // 1
Compare("Apples", "Apple")   // 0.8181818181818181
Compare("Apples", "apple")   // 0.7727272727272727
Compare("a", "A")            // 0.75
Compare("Apples", "appppp")  // 0.45833333333333337
Compare("a", "b")            // 0
Павел
источник
6
Не так точно: Compare ("Apple", "zApple") = 0,07, а Compare ("Apple", "Applez") = 0,84
Kousha
3
@Kousha, это позиционно. "Apple" и "zApple" имеют только одну общую букву (вторую p).
Пол
2
@Paulpro Apple и zApple логически имеют пять общих букв. Это ваша ошибка реализации. Apple, zApple, Applez похожи.
Kousha 05
2
@Kousha, zApple не похож по этому алгоритму, так как он позиционный. Это не делает алгоритм некорректным.
Пол
8
@Paulpro: Это не делает ваш алгоритм некорректным, но делает его плохим ответом на этот вопрос ...
MarcoS
6

Как насчет функции similar_textиз библиотеки PHP.js ?

Он основан на одноименной функции PHP .

function similar_text (first, second) {
    // Calculates the similarity between two strings  
    // discuss at: http://phpjs.org/functions/similar_text

    if (first === null || second === null || typeof first === 'undefined' || typeof second === 'undefined') {
        return 0;
    }

    first += '';
    second += '';

    var pos1 = 0,
        pos2 = 0,
        max = 0,
        firstLength = first.length,
        secondLength = second.length,
        p, q, l, sum;

    max = 0;

    for (p = 0; p < firstLength; p++) {
        for (q = 0; q < secondLength; q++) {
            for (l = 0;
            (p + l < firstLength) && (q + l < secondLength) && (first.charAt(p + l) === second.charAt(q + l)); l++);
            if (l > max) {
                max = l;
                pos1 = p;
                pos2 = q;
            }
        }
    }

    sum = max;

    if (sum) {
        if (pos1 && pos2) {
            sum += this.similar_text(first.substr(0, pos2), second.substr(0, pos2));
        }

        if ((pos1 + max < firstLength) && (pos2 + max < secondLength)) {
            sum += this.similar_text(first.substr(pos1 + max, firstLength - pos1 - max), second.substr(pos2 + max, secondLength - pos2 - max));
        }
    }

    return sum;
}
VisioN
источник
1
Возвращается ли сходство на основе совпадающего символа? Как оценивает сходство
hyperfkcb 05
3

Найти степень сходства между двумя строками; мы можем использовать более одного или двух методов, но я больше склоняюсь к использованию « коэффициента игральной кости » . что лучше! а в моем знании , чем при использовании « Левенштейн »

Используя этот пакет ' string-similarity ' от npm, вы сможете работать над тем, что я сказал выше.

несколько простых примеров использования:

var stringSimilarity = require('string-similarity');

var similarity = stringSimilarity.compareTwoStrings('healed', 'sealed'); 

var matches = stringSimilarity.findBestMatch('healed', ['edward', 'sealed', 'theatre']);

для получения дополнительной информации перейдите по указанной выше ссылке. Спасибо.

Леон Грин
источник
1
Ссылка на решение приветствуется, но убедитесь, что ваш ответ полезен и без нее: добавьте контекст вокруг ссылки, чтобы ваши друзья-пользователи имели некоторое представление, что это такое и почему оно есть, а затем процитируйте наиболее релевантную часть страницы, которую вы повторная ссылка на, если целевая страница недоступна. Ответы, которые представляют собой не более чем ссылку, могут быть удалены .
Дэвид Бак
1

fuzzyset - набор нечетких строк для javascript. fuzzyset - это структура данных, которая выполняет что-то вроде полнотекстового поиска по данным для определения вероятных ошибок написания и приблизительного сопоставления строк. Обратите внимание, что это javascript-порт библиотеки Python.

Октавио Диас
источник