Сравнение строк сходства в Java

Question

Сравнение строк сходства в Java

Я хочу сравнить несколько строк друг с другом и найти те, которые наиболее похожи. Мне было интересно, есть ли какая-либо библиотека, метод или наилучшая практика, которая вернула бы мне, какие строки больше похожи на другие строки. Например:

"Быстрый лис прыгнул" -> "Лис прыгнул"
"Быстрый лис прыгнул" -> "Лиса"

Это сравнение вернуло бы, что первое более похоже чем второе.

Я думаю, мне нужен какой-то метод, такой как:

double similarityIndex(String s1, String s2)

Есть ли где-нибудь такая вещь?

РЕДАКТИРОВАТЬ: Почему я это делаю? Я пишу сценарий, который сравнивает вывод файла MS Project с выводом какой-то устаревшей системы, которая обрабатывает задачи. Поскольку унаследованная система имеет очень ограниченную ширину поля, при добавлении значений описания сокращаются. Я хочу полуавтоматический способ узнать, какие записи из MS Project похожи на записи в системе, чтобы я мог получить сгенерированные ключи. У него есть недостатки, так как его нужно проверять вручную, но это сэкономит много работы.

147

java string-comparison

Источник

user2309 05 июн '09 в 09:54

12 ответов

Решение

Обычный способ вычисления сходства между двумя строками в режиме 0%-100%, используемый во многих библиотеках, состоит в том, чтобы измерить, сколько (в%) вам потребуется изменить более длинную строку, чтобы превратить ее в более короткую:

/**
 * Calculates the similarity (a number within 0 and 1) between two strings.
 */
public static double similarity(String s1, String s2) {
  String longer = s1, shorter = s2;
  if (s1.length() < s2.length()) { // longer should always have greater length
    longer = s2; shorter = s1;
  }
  int longerLength = longer.length();
  if (longerLength == 0) { return 1.0; /* both strings are zero length */ }
  return (longerLength - editDistance(longer, shorter)) / (double) longerLength;
}
// you can use StringUtils.getLevenshteinDistance() as the editDistance() function
// full copy-paste working code is below

Вычисление `editDistance()`:

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

Вот два варианта расчета расстояния редактирования:

Вы можете использовать реализацию Apache Commons Text для расстояния Левенштейна: apply(CharSequence left, CharSequence rightt)
Реализуйте это по-своему. Ниже вы найдете пример реализации.

Рабочий пример:

Смотрите онлайн демо здесь.

public class StringSimilarity {

  /**
   * Calculates the similarity (a number within 0 and 1) between two strings.
   */
  public static double similarity(String s1, String s2) {
    String longer = s1, shorter = s2;
    if (s1.length() < s2.length()) { // longer should always have greater length
      longer = s2; shorter = s1;
    }
    int longerLength = longer.length();
    if (longerLength == 0) { return 1.0; /* both strings are zero length */ }
    /* // If you have Apache Commons Text, you can use it to calculate the edit distance:
    LevenshteinDistance levenshteinDistance = new LevenshteinDistance();
    return (longerLength - levenshteinDistance.apply(longer, shorter)) / (double) longerLength; */
    return (longerLength - editDistance(longer, shorter)) / (double) longerLength;

  }

  // Example implementation of the Levenshtein Edit Distance
  // See http://rosettacode.org/wiki/Levenshtein_distance#Java
  public static int editDistance(String s1, String s2) {
    s1 = s1.toLowerCase();
    s2 = s2.toLowerCase();

    int[] costs = new int[s2.length() + 1];
    for (int i = 0; i <= s1.length(); i++) {
      int lastValue = i;
      for (int j = 0; j <= s2.length(); j++) {
        if (i == 0)
          costs[j] = j;
        else {
          if (j > 0) {
            int 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()];
  }

  public static void printSimilarity(String s, String t) {
    System.out.println(String.format(
      "%.3f is the similarity between \"%s\" and \"%s\"", similarity(s, t), s, t));
  }

  public static void main(String[] args) {
    printSimilarity("", "");
    printSimilarity("1234567890", "1");
    printSimilarity("1234567890", "123");
    printSimilarity("1234567890", "1234567");
    printSimilarity("1234567890", "1234567890");
    printSimilarity("1234567890", "1234567980");
    printSimilarity("47/2010", "472010");
    printSimilarity("47/2010", "472011");
    printSimilarity("47/2010", "AB.CDEF");
    printSimilarity("47/2010", "4B.CDEFG");
    printSimilarity("47/2010", "AB.CDEFG");
    printSimilarity("The quick fox jumped", "The fox jumped");
    printSimilarity("The quick fox jumped", "The fox");
    printSimilarity("kitten", "sitting");
  }

}

Выход:

1.000 is the similarity between "" and ""
0.100 is the similarity between "1234567890" and "1"
0.300 is the similarity between "1234567890" and "123"
0.700 is the similarity between "1234567890" and "1234567"
1.000 is the similarity between "1234567890" and "1234567890"
0.800 is the similarity between "1234567890" and "1234567980"
0.857 is the similarity between "47/2010" and "472010"
0.714 is the similarity between "47/2010" and "472011"
0.000 is the similarity between "47/2010" and "AB.CDEF"
0.125 is the similarity between "47/2010" and "4B.CDEFG"
0.000 is the similarity between "47/2010" and "AB.CDEFG"
0.700 is the similarity between "The quick fox jumped" and "The fox jumped"
0.350 is the similarity between "The quick fox jumped" and "The fox"
0.571 is the similarity between "kitten" and "sitting"

194

Источник

user1850609 15 апр '13 в 14:58

Я перевел алгоритм расстояния Левенштейна в JavaScript:

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];
};

16

Источник

user493744 01 ноя '10 в 15:33

Там действительно есть много мер сходства строк там:

Левенштейн редактировать расстояние;
Расстояние Дамерау-Левенштейн;
Сходство Яро-Винклера;
Расстояние редактирования самой длинной общей подпоследовательности;
Q-Gram (Укконен);
н-граммное расстояние (Кондрак);
Индекс Жакара;
Коэффициент Соренсена-Дайса;
Косинусное сходство;
...

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

14

Источник

user4770918 07 авг '15 в 11:26

Вы можете достичь этого с помощью библиотеки Java Apache Commons. Взгляните на эти две функции:
- getLevenshteinDistance
- getFuzzyDistance

14

Источник

user865643 10 апр '17 в 21:17

Вы можете использовать расстояние Левенштейна, чтобы вычислить разницу между двумя строками. http://en.wikipedia.org/wiki/Levenshtein_distance

11

Источник

user104976 05 июн '09 в 09:58

Спасибо первому ответчику, я думаю, что есть 2 вычисления computeEditDistance(s1, s2). Из-за больших затрат времени решил улучшить производительность кода. Так:

public class LevenshteinDistance {

public static int computeEditDistance(String s1, String s2) {
    s1 = s1.toLowerCase();
    s2 = s2.toLowerCase();

    int[] costs = new int[s2.length() + 1];
    for (int i = 0; i <= s1.length(); i++) {
        int lastValue = i;
        for (int j = 0; j <= s2.length(); j++) {
            if (i == 0) {
                costs[j] = j;
            } else {
                if (j > 0) {
                    int 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()];
}

public static void printDistance(String s1, String s2) {
    double similarityOfStrings = 0.0;
    int editDistance = 0;
    if (s1.length() < s2.length()) { // s1 should always be bigger
        String swap = s1;
        s1 = s2;
        s2 = swap;
    }
    int bigLen = s1.length();
    editDistance = computeEditDistance(s1, s2);
    if (bigLen == 0) {
        similarityOfStrings = 1.0; /* both strings are zero length */
    } else {
        similarityOfStrings = (bigLen - editDistance) / (double) bigLen;
    }
    //////////////////////////
    //System.out.println(s1 + "-->" + s2 + ": " +
      //      editDistance + " (" + similarityOfStrings + ")");
    System.out.println(editDistance + " (" + similarityOfStrings + ")");
}

public static void main(String[] args) {
    printDistance("", "");
    printDistance("1234567890", "1");
    printDistance("1234567890", "12");
    printDistance("1234567890", "123");
    printDistance("1234567890", "1234");
    printDistance("1234567890", "12345");
    printDistance("1234567890", "123456");
    printDistance("1234567890", "1234567");
    printDistance("1234567890", "12345678");
    printDistance("1234567890", "123456789");
    printDistance("1234567890", "1234567890");
    printDistance("1234567890", "1234567980");

    printDistance("47/2010", "472010");
    printDistance("47/2010", "472011");

    printDistance("47/2010", "AB.CDEF");
    printDistance("47/2010", "4B.CDEFG");
    printDistance("47/2010", "AB.CDEFG");

    printDistance("The quick fox jumped", "The fox jumped");
    printDistance("The quick fox jumped", "The fox");
    printDistance("The quick fox jumped",
            "The quick fox jumped off the balcany");
    printDistance("kitten", "sitting");
    printDistance("rosettacode", "raisethysword");
    printDistance(new StringBuilder("rosettacode").reverse().toString(),
            new StringBuilder("raisethysword").reverse().toString());
    for (int i = 1; i < args.length; i += 2) {
        printDistance(args[i - 1], args[i]);
    }


 }
}

5

Источник

user659077 18 окт '14 в 13:09

Для меня это звучит как искатель плагиата, если твоя строка превращается в документ. Возможно, поиск по этому термину принесет что-то хорошее.

"Программирование Коллективного Разума" имеет главу о том, чтобы определить, похожи ли два документа. Код написан на Python, но он чистый и его легко переносить.

3

Источник

user37213 05 июн '09 в 10:01

Теоретически вы можете сравнить расстояния редактирования.

3

Источник

user60188 05 июн '09 в 09:59

Обычно это делается с помощью измерения расстояния редактирования. Поиск "edit distance java" приводит к появлению нескольких библиотек, подобных этой.

3

Источник

user90848 05 июн '09 в 10:00

Вы можете использовать этот алгоритм «Расстояние Левенштейна» без какой-либо библиотеки:

       public static int getLevenshteinDistance(CharSequence s, CharSequence t) {
    if (s == null || t == null) {throw new IllegalArgumentException("Strings must not be null");}
    int n = s.length();
    int m = t.length();

    if (n == 0) {
            return m;
        }
    else if (m == 0) {
            return n;
        }

    if (n > m) {
            // swap the input strings to consume less memory
            final CharSequence tmp = s;
            s = t;
            t = tmp;
            n = m;
            m = t.length();
        }

    final int[] p = new int[n + 1];
    // indexes into strings s and t
    int i; // iterates through s
    int j; // iterates through t
    int upper_left;
    int upper;

    char t_j; // jth character of t
    int cost;

    for (i = 0; i <= n; i++) {
            p[i] = i;
        }

    for (j = 1; j <= m; j++) {
            upper_left = p[0];
            t_j = t.charAt(j - 1);
            p[0] = j;

            for (i = 1; i <= n; i++) {
                    upper = p[i];
                    cost = s.charAt(i - 1) == t_j ? 0 : 1;
                    // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
                    p[i] = Math.min(Math.min(p[i - 1] + 1, p[i] + 1), upper_left + cost);
                    upper_left = upper;
                }
        }

    return p[n];
   }

Отсюда

0

Источник

user11546366 14 авг '22 в 17:21

Вы также можете использовать алгоритм z, чтобы найти сходство в строке. Нажмите здесь https://teakrunch.com/2020/05/09/string-similarity-hackerrank-challenge/

-1

Источник

user13504487 10 май '20 в 12:11

Другие вопросы по тегам java string-comparison

user89266 05 июн '09 в 09:59 2009-06-05 09:59 · Accepted Answer · 2009-06-05 09:59

Да, есть много хорошо документированных алгоритмов, таких как:

Косинус сходство
Жаккар сходство
Коэффициент кости
Соответствие сходства
Перекрытие сходства
и т. д.

Или вы можете проверить это

Проверьте также эти проекты:

Сравнение строк сходства в Java

12 ответов

Вычисление editDistance():

Рабочий пример:

Вычисление `editDistance()`: