Сравнение строк подобия в Java

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

• «Лисица прыгнула» -> «Лиса прыгнула»
• «Лисица прыгнула» -> «Лисица»

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

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

double similarityIndex(String s1, String s2)

Есть где-нибудь такое?

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

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

• Косинусное сходство
• Сходство Жаккара
• Коэффициент игральной кости
• Соответствующее сходство
• Сходство перекрытия
• и т.д.

Хорошее резюме ("Строковые показатели Сэма") можно найти здесь (исходная ссылка мертва, поэтому она ведет к Интернет-архиву)

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

• Симметрики
• jtmt

Обычный способ вычисления сходства между двумя строками по методу 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"

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

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

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

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

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

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

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

Обычно это делается с помощью меры расстояния редактирования . Поиск по запросу «редактировать расстояние java» обнаруживает несколько библиотек, например эту .

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

В «Программировании коллективного разума» есть глава, посвященная определению схожести двух документов. Код написан на Python, но он чист и легко переносится.

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


 }
}

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