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

111

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

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

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

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

double similarityIndex(String s1, String s2)

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

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

Марио Ортегон
источник

Ответы:

82

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

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

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

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

DFA
источник
18
+1 Сайт simmetrics больше не работает. Однако я нашел код на sourceforge: sourceforge.net/projects/simmetrics Спасибо за указатель.
Майкл Мерчант,
7
Ссылка "вы можете проверить это" не работает.
Кирилл
1
Вот почему Майкл Мерчант разместил правильную ссылку выше.
emilyk
2
Баночка для simmetrics на sourceforge немного устарела, github.com/mpkorstanje/simmetrics - это обновленная страница github с артефактами maven
tom91136
Чтобы добавить в комментарий @MichaelMerchant, проект также доступен на github . Хотя и там не очень активно, но немного позже, чем sourceforge.
Ghurdyl
163

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

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


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

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

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"
acdcjunior
источник
11
Метод расстояния Левенштейна доступен в формате org.apache.commons.lang3.StringUtils.
Cleankod 05
@Cleankod Теперь это часть общего текста: commons.apache.org/proper/commons-text/javadocs/api-release/org/…
Луис
15

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

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

Флориан Фанкхаузер
источник
2
Левенштейн отлично подходит для нескольких строк, но не масштабируется для сравнения большого количества строк.
Спендер
Я успешно использовал Левенштейна на Java. Я не проводил сравнения огромных списков, поэтому производительность может снизиться. Кроме того, это немного просто и может потребоваться некоторая настройка, чтобы поднять порог для более коротких слов (например, 3 или 4 символа), которые, как правило, выглядят более похожими, чем должны (это всего 3 изменения от кошки к собаке). предлагаемые ниже - это почти то же самое - Левенштейн - это конкретная реализация расстояний редактирования.
Rhubarb
Вот статья, показывающая, как объединить Левенштейна с эффективным SQL-запросом: literatejava.com/sql/fuzzy-string-search-sql
Thomas W
10

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

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

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

Тибо Дебатти
источник
3

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

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

duffymo
источник
3

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


 }
}
Мохсен Абаси
источник