Comparação de strings de similaridade em Java

Quero comparar várias strings entre si e encontrar aquelas que são mais semelhantes. Eu queria saber se existe alguma biblioteca, método ou prática recomendada que me retornaria quais strings são mais semelhantes a outras strings. Por exemplo:

• "A raposa rápida saltou" -> "A raposa saltou"
• "A raposa rápida saltou" -> "A raposa"

Essa comparação retornaria que o primeiro é mais semelhante do que o segundo.

Acho que preciso de algum método como:

double similarityIndex(String s1, String s2)

Existe tal coisa em algum lugar?

EDIT: Por que estou fazendo isso? Estou escrevendo um script que compara a saída de um arquivo do MS Project com a saída de algum sistema legado que lida com tarefas. Como o sistema legado tem uma largura de campo muito limitada, quando os valores são adicionados, as descrições são abreviadas. Quero uma maneira semiautomática de descobrir quais entradas do MS Project são semelhantes às entradas do sistema para que eu possa obter as chaves geradas. Ele tem desvantagens, pois ainda precisa ser verificado manualmente, mas pouparia muito trabalho

Sim, existem muitos algoritmos bem documentados como:

• Similaridade de cosseno
• Similaridade de Jaccard
• Coeficiente de dados
• Similaridade correspondente
• Sobrepor similaridade
• etc etc

Um bom resumo ("Sam's String Metrics") pode ser encontrado aqui (link original inoperante, portanto, vincula ao Internet Archive)

Verifique também estes projetos:

• Simmetrics
• jtmt

A maneira comum de calcular a similaridade entre duas strings de 0% -100% , como usado em muitas bibliotecas, é medir quanto (em%) você teria que mudar a string mais longa para transformá-la na mais curta:

/**
 * 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

Calculando o editDistance():

A editDistance()função acima deve calcular a distância de edição entre as duas strings. Existem várias implementações para esta etapa, cada uma pode se adequar melhor a um cenário específico. O mais comum é o algoritmo de distância de Levenshtein e vamos usá-lo em nosso exemplo abaixo (para strings muito grandes, outros algoritmos provavelmente terão um desempenho melhor).

Aqui estão duas opções para calcular a distância de edição:

• Você pode usar a implementação de distância de Levenshtein do Apache Commons Text : apply(CharSequence left, CharSequence rightt)
• Implemente-o por conta própria. Abaixo você encontrará um exemplo de implementação.

Exemplo de trabalho:

Veja a demonstração online aqui.

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");
  }

}

Resultado:

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"

Eu traduzi o algoritmo de distância Levenshtein em 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];
};

Você pode usar a distância de Levenshtein para calcular a diferença entre duas cordas. http://en.wikipedia.org/wiki/Levenshtein_distance

De fato, existem muitas medidas de similaridade de string por aí:

• Levenshtein editar distância;
• Distância Damerau-Levenshtein;
• Semelhança Jaro-Winkler;
• Distância mais longa de edição comum subsequente;
• Q-Gram (Ukkonen);
• distância n-Gram (Kondrak);
• Índice de Jaccard;
• Coeficiente de Sorensen-Dice;
• Similaridade de cosseno;
• ...

Você pode encontrar a explicação e a implementação java deles aqui: https://github.com/tdebatty/java-string-similarity

Você pode conseguir isso usando a biblioteca java apache commons . Dê uma olhada nessas duas funções dentro dele:
- getLevenshteinDistance
- getFuzzyDistance

Teoricamente, você pode comparar distâncias de edição .

Isso normalmente é feito usando uma medida de distância de edição . Pesquisar por "editar distância java" mostra várias bibliotecas, como esta .

Soa como um localizador de plágio para mim se sua string se transforma em um documento. Talvez pesquisar com esse termo resulte em algo bom.

"Programando Inteligência Coletiva" tem um capítulo sobre como determinar se dois documentos são semelhantes. O código está em Python, mas é limpo e fácil de transportar.

Graças ao primeiro respondente, acho que existem 2 cálculos de computeEditDistance (s1, s2). Devido ao grande dispêndio de tempo dele, decidiu melhorar a performance do código. Assim:

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


 }
}

Você também pode usar o algoritmo z para encontrar similaridade na string. Clique aqui https://teakrunch.com/2020/05/09/string-similarity-hackerrank-challenge/