Как я могу измерить сходство строк между предложениями?

У меня есть следующая задача.

Данный список строк выглядит так:

        var strings = [
            'Steve jobs created the iPod when he was at Apple',
            'I really like the new Macbook by Apple',
            'Jony Ive was concerned being fired by Steve Jobs after his return to Apple',
            'The new Macbook has just one USB-C type connector',
            'I like bananas',
            'The brezels I can buy in my local store are much better than the ones in the supermarket',
            'the',
            'foo',
            'Steve'
        ];

Теперь я хочу сравнить каждую строку друг с другом, и для каждого сравнения я хочу выяснить, насколько они похожи друг на друга по шкале от 0 до 1 (или от 0 до 100%).

Итак, я немного погуглил и обнаружил следующее: Сравнение строк сходства в Java

Итак, я следовал инструкции там и портировал метод similarity(String s1, String s2) в JavaScript:

        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 - longer.LevenshteinDistance(shorter)) / longerLength;
        }

В качестве алгоритма сравнения я использовал Левенштейна:

        String.prototype.LevenshteinDistance = function (s2) {
            var array = new Array(this.length + 1);
            for (var i = 0; i < this.length + 1; i++)
                array[i] = new Array(s2.length + 1);

            for (var i = 0; i < this.length + 1; i++)
                array[i][0] = i;
            for (var j = 0; j < s2.length + 1; j++)
                array[0][j] = j;

            for (var i = 1; i < this.length + 1; i++) {
                for (var j = 1; j < s2.length + 1; j++) {
                    if (this[i - 1] == s2[j - 1]) array[i][j] = array[i - 1][j - 1];
                    else {
                        array[i][j] = Math.min(array[i][j - 1] + 1, array[i - 1][j] + 1);
                        array[i][j] = Math.min(array[i][j], array[i - 1][j - 1] + 1);
                    }
                }
            }
            return array[this.length][s2.length];
        };

Итак, в качестве теста я запустил полный цикл, сравнивая каждую строку друг с другом и печатая результат следующим образом:

            for (var i in strings){
                var s = strings[i];
                print('Checking string: "' + s + '"');
                for (var j in strings){
                    print('-----');
                    var s2 = strings[j];
                    print('vs "' + s2 + '"');
                    var sim = similarity(s, s2);
                    print('Similarity: ' + Math.round(sim*100) + '%');
                }
                print('<br>////// NEXT /////////////////////////////////////////////////<br>');
            }

Хорошо, теперь это результат: https://jsfiddle.net/wxksfa4w/

Теперь, глядя на результаты, я получаю несколько хороших совпадений, а также некоторые, которые совершенно не связаны друг с другом, например:

"Стив Джобс создал iPod, когда был в Apple", а "Я люблю бананы" соответствует 13%?

"Стив Джобс создал iPod, когда он был в Apple", и просто "Стив" соответствует всего 10%, хотя слово "Стив" используется точно так же, как и в первом предложении?

Как я могу получить лучшие семантические результаты? Левенштейн - неправильный алгоритм? Из того, что я понял, Левенштейн подсчитывает количество шагов, как изменить предложение 1 на предложение 2. Таким образом, длина строки, кажется, оказывает значительное влияние на результат, даже если есть семантическое сходство.

Любой совет?

Источник

3 ответа

Решение

Вы, вероятно, должны использовать присутствие слов в обоих предложениях как намек на сходство. Простой способ сделать это - использовать каждое предложение как пакет слов и использовать tf-idf.

Источник

SimMetrics имеет Java-код для алгоритма Смита Ватермана Гото, который отлично подходит для сравнения строковых предложений. Я обнаружил, что Smith Waterman Gotoh - лучший алгоритм для сравнения больших строк, таких как предложения и заголовки статей.

Источник

То, что вы могли бы использовать, - это нормализованное подобие самой длинной общей подпоследовательности (LCS): вы вычисляете длину самой длинной общей подпоследовательности, а затем делите ее на длину самой маленькой строки.

Кстати, самую длинную общую подпоследовательность не следует путать с самой длинной общей подстрокой: для двух строк "Это длинная строка" и "Это еще одна строка, на самом деле..."

Самая длинная общая подпоследовательность: "Это строка"
Самая длинная общая подстрока "Это"

И относительное сходство LCS составляет 16/21 = 0,76

Вы можете найти Java-реализацию сходства LCS здесь: https://github.com/tdebatty/java-string-similarity

А реализация Javascript доступна в вики-книгах: https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_subsequence

Источник
Другие вопросы по тегам