Как рассчитать сходство текста между двумя строками?

алгоритм

предисловие

В последнее время я давно не писал статьи.Последняя статья была написана 11 сентября.С тех пор прошло два месяца.В этот период я ​​был занят какой-то работой.У меня сегодня наконец-то появилось немного свободного времени , вот я и написал об этом статью.Расслабьтесь.

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

Сходство Жаккара

Первый — это коэффициент подобия Жаккара, а следующее — его определение и формула расчета в Википедии.

The Jaccard index, also known as Intersection over Union and the Jaccard similarity coefficient (originally given the French name coefficient de communauté by Paul Jaccard), is a statistic used for gauging the similarity and diversity of sample sets. The Jaccard coefficient measures similarity between finite sample sets, and is defined as the size of the intersection divided by the size of the union of the sample sets:

2019-11-12-15-55-54

На самом деле, это можно выразить одним предложением:Отношение пересечения множеств к объединению множеств.

Java-код реализован следующим образом:

    public static float jaccard(String a, String b) {
        if (a == null && b == null) {
            return 1f;
        }
        // 都为空相似度为 1
        if (a == null || b == null) {
            return 0f;
        }
        Set<Integer> aChar = a.chars().boxed().collect(Collectors.toSet());
        Set<Integer> bChar = b.chars().boxed().collect(Collectors.toSet());
        // 交集数量
        int intersection = SetUtils.intersection(aChar, bChar).size();
        if (intersection == 0) return 0;
        // 并集数量
        int union = SetUtils.union(aChar, bChar).size();
        return ((float) intersection) / (float)union;
    }

Коэффициент подобия костей Соренсена

Подобно Жаккару, коэффициент Дайса также является способом вычисления сходства между простыми множествами. В отличие от Жаккара расчет немного отличается. Ниже приведено его определение.

Коэффициент Серенсена-Дайса (другие названия см. ниже) — это статистический показатель, используемый для оценки подобия двух образцов. соответственно.

2019-11-12-15-58-18

Следует отметить, что он:2 раза пересечение наборов, деленное на сумму двух наборов. не союз.

Java-код реализован следующим образом:

    public static float SorensenDice(String a, String b) {
        if (a == null && b == null) {
            return 1f;
        }
        if (a == null || b == null) {
            return 0F;
        }
        Set<Integer> aChars = a.chars().boxed().collect(Collectors.toSet());
        Set<Integer> bChars = b.chars().boxed().collect(Collectors.toSet());
        // 求交集数量
        int intersect = SetUtils.intersection(aChars, bChars).size();
        if (intersect == 0) {
            return 0F;
        }
        // 全集，两个集合直接加起来
        int aSize = aChars.size();
        int bSize = bChars.size();
        return (2 * (float) intersect) / ((float) (aSize + bSize));
    }

Levenshtein

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

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

Код реализации Java выглядит следующим образом:

    public static float Levenshtein(String a, String b) {
        if (a == null && b == null) {
            return 1f;
        }
        if (a == null || b == null) {
            return 0F;
        }
        int editDistance = editDis(a, b);
        return 1 - ((float) editDistance / Math.max(a.length(), b.length()));
    }

    private static int editDis(String a, String b) {

        int aLen = a.length();
        int bLen = b.length();

        if (aLen == 0) return aLen;
        if (bLen == 0) return bLen;

        int[][] v = new int[aLen + 1][bLen + 1];
        for (int i = 0; i <= aLen; ++i) {
            for (int j = 0; j <= bLen; ++j) {
                if (i == 0) {
                    v[i][j] = j;
                } else if (j == 0) {
                    v[i][j] = i;
                } else if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    v[i][j] = v[i - 1][j - 1];
                } else {
                    v[i][j] = 1 + Math.min(v[i - 1][j - 1], Math.min(v[i][j - 1], v[i - 1][j]));
                }
            }
        }
        return v[aLen][bLen];
    }

Решение расстояния редактирования в коде использует классический решатель динамического программирования.

Мы использовали ** 1 - (расстояние редактирования/максимальная длина двух строк) ** для представления сходства, чтобы мы могли получить сходство, соответствующее нашей семантике.

Расстояние Хэмминга

Расстояние Хэмминга является частным случаем расстояния редактирования и используется только для подсчета количества несовместимых символов в двух строках одинаковой длины.

Следовательно, расстояние Хэмминга не нужно учитывать сложение и удаление, а нужно только сравнивать, поэтому реализация относительно проста.

мы можем использоватьsimilarity=汉明距离/长度для представления сходства двух строк.

Java-код выглядит следующим образом:

    public static float hamming(String a, String b) {
        if (a == null || b == null) {
            return 0f;
        }
        if (a.length() != b.length()) {
            return 0f;
        }

        int disCount = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                disCount++;
            }
        }
        return (float) disCount / (float) a.length();
    }

Вот тестовый пример:

        Assert.assertEquals(0.0f, StringSimilarity.hamming("java 开发", "大过年的干啥"), 0f);
        Assert.assertEquals(0.6666667f, StringSimilarity.hamming("大过年的吃肉", "大过年的干啥"), 0f);

косинусное сходство

Во-первых, это определение косинусного подобия:

Косинусное сходство измеряет сходство между двумя векторами путем измерения косинуса их угла. Косинус угла 0 градусов равен 1, а косинус любого другого угла не больше 1, а его минимальное значение равно -1. Таким образом, косинус угла между двумя векторами определяет, указывают ли два вектора примерно в одном направлении. Когда два вектора имеют одинаковое направление, значение косинусного сходства равно 1; когда угол между двумя векторами равен 90°, значение косинусного сходства равно 0; когда два вектора указывают в совершенно противоположных направлениях, значение косинусного сходства равно значение равно -1. Этот результат не зависит от длины вектора, он связан только с направлением вектора. Косинусное сходство обычно используется в положительных пространствах, поэтому ему присваивается значение от 0 до 1.

Рассчитывается следующим образом:

2019-11-12-15-57-05

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

Сначала мы векторизуем строки, а затем можем найти косинус угла между их векторами в плоском пространстве.

Как сделать векторизацию строк? Привожу простой пример:

A: 呼延十二
B: 呼延二十三

他们的并集 [呼，延，二，十，三]

向量就是并集中的每个字符在各自中出现的频率。
A 的向量：[1,1,1,1,0]
B 的向量：[1,1,1,1,1]

然后调用上面的公式计算即可。

Java-код реализован следующим образом:

    public static float cos(String a, String b) {
        if (a == null || b == null) {
            return 0F;
        }
        Set<Integer> aChar = a.chars().boxed().collect(Collectors.toSet());
        Set<Integer> bChar = b.chars().boxed().collect(Collectors.toSet());

        // 统计字频
        Map<Integer, Integer> aMap = new HashMap<>();
        Map<Integer, Integer> bMap = new HashMap<>();
        for (Integer a1 : aChar) {
            aMap.put(a1, aMap.getOrDefault(a1, 0) + 1);
        }
        for (Integer b1 : bChar) {
            bMap.put(b1, bMap.getOrDefault(b1, 0) + 1);
        }

        // 向量化
        Set<Integer> union = SetUtils.union(aChar, bChar);
        int[] aVec = new int[union.size()];
        int[] bVec = new int[union.size()];
        List<Integer> collect = new ArrayList<>(union);
        for (int i = 0; i < collect.size(); i++) {
            aVec[i] = aMap.getOrDefault(collect.get(i), 0);
            bVec[i] = bMap.getOrDefault(collect.get(i), 0);
        }

        // 分别计算三个参数
        int p1 = 0;
        for (int i = 0; i < aVec.length; i++) {
            p1 += (aVec[i] * bVec[i]);
        }

        float p2 = 0f;
        for (int i : aVec) {
            p2 += (i * i);
        }
        p2 = (float) Math.sqrt(p2);

        float p3 = 0f;
        for (int i : bVec) {
            p3 += (i * i);
        }
        p3 = (float) Math.sqrt(p3);

        return ((float) p1) / (p2 * p3);
    }

Запустив тестовый пример с приведенным выше кодом, мы видим, что он в основном соответствует нашим ожиданиям.

        Assert.assertEquals(0.70710677f, StringSimilarity.cos("apple", "app"), 0f);
        Assert.assertEquals(0.8944272f, StringSimilarity.cos("呼延十二", "呼延二十三"), 0f);
        Assert.assertEquals(0.0f, StringSimilarity.cos("数据工程", "日本旅游"), 0f);

Суммировать

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

Справочная статья

Википедия


Заканчивать.

ChangeLog

2019-11-10 Завершено

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

Добро пожаловать на перепечатку, пожалуйста, подпишите и сохраните исходную ссылку.

Контактный адрес электронной почты: huyanshi2580@gmail.com

Дополнительные заметки об обучении см. в личном блоге или подпишитесь на общедоступную учетную запись WeChat ------>Хуян тен

Категории