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

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

  • "Быстрая лиса прыгнула" → "Лиса прыгнула"
  • "Быстрая лиса подпрыгнула" → "Лиса"

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

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

double similarityIndex(String s1, String s2)

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

EDIT: Почему я это делаю? Я пишу script, который сравнивает вывод файла MS Project с выходом какой-либо старой системы, которая обрабатывает задачи. Поскольку унаследованная система имеет очень ограниченную ширину поля, при добавлении значений описания сокращаются. Мне нужен полуавтоматический способ найти, какие записи из MS Project похожи на записи в системе, поэтому я могу получить сгенерированные ключи. У этого есть недостатки, поскольку он должен быть все еще проверен вручную, но это сэкономит много работы.

Ответы

Ответ 1

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

  • Косинус сходства
  • сходство с Jaccard
  • Коэффициент кости
  • Соответствие подобия
  • Сходство над перекрытием
  • и т.д.

В качестве альтернативы вы можете проверить это

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

Ответ 2

Общий способ вычисления сходства между двумя строками в формате 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(), описанная выше, рассчитает расстояние редактирования между двумя строками. На этом этапе несколько реализаций, каждый из них может соответствовать конкретному сценарию лучше. Наиболее распространенным является алгоритм расстояния Levenshtein, и мы будем использовать его в нашем примере ниже (для очень больших строк, другие алгоритмы, скорее всего, будут работать лучше).

Здесь два варианта вычисления расстояния редактирования:

  • Вы можете использовать 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"

Ответ 4

Я перевел алгоритм расстояния Levenshtein в 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];
};

Ответ 5

На самом деле существует множество мер сходства строк:

  • Расстояние редактирования Левенштейна;
  • расстояние Дамерау-Левенштейна;
  • сходство Яро-Винклера;
  • Дальнейшее редактирование расстояний;
  • Q-Gram (Ukkonen);
  • n-грамм (Кондрак);
  • индекс Jaccard;
  • Коэффициент Sorensen-Dice;
  • сходство с косинусом;
  • ...

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

Ответ 8

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

Ответ 9

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

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

Ответ 10

Спасибо первому ответчику, я думаю, что есть 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]);
    }


 }
}