24

É muito comum compararmos strings, que normalmente é feito comparando a igualdade. No entanto, hoje me surgiu a necessidade de comparar a semelhança entre duas strings, de forma que eu possa comparar o quão semelhantes são.

Por exemplo:

"Cidade" é diferente de "cidade", mas é semelhante (considere c != C).

"Cdade" é diferente de "cidade", mas é semelhante (supondo que o usuário digitou errado).

"ciddade" é diferente de "cidade", mas é semelhante (a mesma coisa).

A minha dúvida é: como faço para verificar a semelhança entre strings? Há algum algoritmo pronto que faça isso?

Procuro uma forma de fazer isso:

if(checkSimilarity("cidade","cdade") > 0.8)
{
    // as duas strings são muito parecidas
    // sendo que checkSimilarity() retornando 1 para strings iguais
}

Não importa a linguagem de programação utilizada na resposta. Minha dúvida está mais relacionada ao algoritmo.

6
  • possível duplicata de Como fazer um algoritmo fonético para o português brasileiro? Commented 25/03/2014 às 0:56
  • Minha dúvida não é com relação a fonética. Somente a grafia e não necessariamente para o Português.
    – Lucas Lima
    Commented 25/03/2014 às 1:04
  • 1
    Vc quer apenas comparar se falta caracteres (somente)? asa = é aproximadamente 25% menor que casa? Commented 25/03/2014 às 1:12
  • 3
    Alguma coisa assim Distância Levenshtein? Commented 25/03/2014 às 1:17
  • Basicamente. Estou procurando uma forma de comparar strings que podem ter sido digitadas erradas pelo usuário e eu possa comparar a semelhança com um valor esperado.
    – Lucas Lima
    Commented 25/03/2014 às 1:17

6 Respostas 6

12

Acredito que o algoritmo de Levenshtein seja uma solução que atende bem o que você está pretendendo fazer, já que com ele é possível saber o número de modificações pelas quais uma palavra precisa passar até se igualar à outra.

Uma possível implementação do mesmo (em C++) seria:

#include <iostream.h>
#include <string.h>
#include <math.h>
#include <algorithm>

using namespace std;

int VerificarSimilaridade(string palavra1, string palavra2)
{
    int tam1 = palavra1.size();
    int tam2 = palavra2.size();
    int verif[tam1 + 1][tam2 + 1];

    // Se uma das palavras tiver coprimento igual a zero, é necessária uma modificação do tamanho da outra:
    if (tam1 == 0)
        return tam2;

    if (tam2 == 0)
        return tam1;

    // Atribuir ordem numérica resultante das palavras ao vetor de modo, respectivamente, "vertical" e "horizontal":
    int i = 0;
    while(i <= tam1)
        verif[i][0] = i++;

    int j = 0; 
    while(j <= tam2)
        verif[0][j] = j++;

    // Verificação:
    for (int i = 1; i <= tam1; i++)
    {
        for (int j = 1; j <= tam2; j++)
        {
            // Definindo custos de modificação (deleção, inserção e substituição):
            int custo = (palavra2[j - 1] == palavra1[i - 1]) ? 0 : 1;

            verif[i][j] = min(
                min(verif[i - 1][j] + 1, verif[i][j - 1] + 1), 
                verif[i - 1][j - 1] + custo);
        }
    }

    return verif[tam1][tam2];
 }

 int main()
 {
     string pala1, pala2;

     cout << "Informe a primeira palavra: " << endl;
     cin >> pala1;
     cout << "Informe a segunda palavra: " << endl;
     cin >> pala2;

     cout << "O numero de modificacoes necessarias para que as duas palavras se igualem e: " 
          << VerificarSimilaridade(pala1, pala2) << endl;

     system("pause");
     return 0;   
 }

Ademais, a partir do número de modificações você pode criar seu próprio critério para quantificar o nível de similaridade entre duas strings; algo interessante seria calcular a porcentagem de mudança de acordo com o comprimento das palavras, assim através de um grau de referência seria possível constatar que 5 modificações podem ter valor alto em uma string com 7 letras e, ao mesmo tempo, ínfimo em uma com 200 por exemplo.

2
9

Existe um artigo(How to Strike a Match) criado por Simon White relacionado a isso que você quer, ele escreveu um artigo sobre um algoritmo que compara pares de caracteres adjacentes que deve ser útil a você.

Algumas vantagens sobre outros algoritmos(como o Soundex, Levenshtein, entre outros, olhe aqui) são elas:

  1. Um verdadeiro reflexo da semelhança lexical - strings com pequenas diferenças devem ser reconhecidas como sendo similar.
  2. A robustez às mudanças de ordem de palavras - duas strings que contêm as mesmas palavras, mas em uma ordem diferente, deve ser reconhecido como sendo similar. Por outro lado, se uma cadeia é apenas um anagrama aleatório dos caracteres contidos na outra, então deve (geralmente) ser reconhecido como diferente.
  3. Independência de linguagem - o algoritmo deve trabalhar não só em Inglês, mas em muitas línguas diferentes.

Por exemplo, France deve ser semelhante a Français e República da França e República da França deve ser semelhante a ambos República Francesa e Republique Francaise. (Tradução livre)

Código abaixo desenvolvido em C#.

/// <summary>
/// This class implements string comparison algorithm
/// based on character pair similarity
/// Source: http://www.catalysoft.com/articles/StrikeAMatch.html
/// </summary>
public class SimilarityTool
{
    /// <summary>
    /// Compares the two strings based on letter pair matches
    /// </summary>
    /// <param name="str1"></param>
    /// <param name="str2"></param>
    /// <returns>The percentage match from 0.0 to 1.0 where 1.0 is 100%</returns>
    public double CompareStrings(string str1, string str2)
    {
        List<string> pairs1 = WordLetterPairs(str1.ToUpper());
        List<string> pairs2 = WordLetterPairs(str2.ToUpper());

        int intersection = 0;
        int union = pairs1.Count + pairs2.Count;

        for (int i = 0; i < pairs1.Count; i++)
        {
            for (int j = 0; j < pairs2.Count; j++)
            {
                if (pairs1[i] == pairs2[j])
                {
                    intersection++;
                    pairs2.RemoveAt(j);//Must remove the match to prevent "GGGG" from appearing to match "GG" with 100% success

                    break;
                }
            }
        }

        return (2.0 * intersection) / union;
    }

    /// <summary>
    /// Gets all letter pairs for each
    /// individual word in the string
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    private List<string> WordLetterPairs(string str)
    {
        List<string> AllPairs = new List<string>();

        // Tokenize the string and put the tokens/words into an array
        string[] Words = Regex.Split(str, @"\s");

        // For each word
        for (int w = 0; w < Words.Length; w++)
        {
            if (!string.IsNullOrEmpty(Words[w]))
            {
                // Find the pairs of characters
                String[] PairsInWord = LetterPairs(Words[w]);

                for (int p = 0; p < PairsInWord.Length; p++)
                {
                    AllPairs.Add(PairsInWord[p]);
                }
            }
        }

        return AllPairs;
    }

    /// <summary>
    /// Generates an array containing every 
    /// two consecutive letters in the input string
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    private string[] LetterPairs(string str)
    {
        int numPairs = str.Length - 1;

        string[] pairs = new string[numPairs];

        for (int i = 0; i < numPairs; i++)
        {
            pairs[i] = str.Substring(i, 2);
        }

        return pairs;
    }
}
7

Aqui está uma proposta de solução bastante simples (fiz em Java):

public class Teste {

    protected static float checkSimilarity(String sString1, String sString2) throws Exception {

        // Se as strings têm tamanho distinto, obtêm a similaridade de todas as
        // combinações em que tantos caracteres quanto a diferença entre elas são
        // inseridos na string de menor tamanho. Retorna a similaridade máxima
        // entre todas as combinações, descontando um percentual que representa
        // a diferença em número de caracteres.
        if(sString1.length() != sString2.length()) {
            int iDiff = Math.abs(sString1.length() - sString2.length());
            int iLen = Math.max(sString1.length(), sString2.length());
            String sBigger, sSmaller, sAux;

            if(iLen == sString1.length()) {
                sBigger = sString1;
                sSmaller = sString2;
            }
            else {
                sBigger = sString2;
                sSmaller = sString1;
            }

            float fSim, fMaxSimilarity = Float.MIN_VALUE;
            for(int i = 0; i <= sSmaller.length(); i++) {
                sAux = sSmaller.substring(0, i) + sBigger.substring(i, i+iDiff) + sSmaller.substring(i);
                fSim = checkSimilaritySameSize(sBigger,  sAux);
                if(fSim > fMaxSimilarity)
                    fMaxSimilarity = fSim;
            }
            return fMaxSimilarity - (1f * iDiff) / iLen;

        // Se as strings têm o mesmo tamanho, simplesmente compara-as caractere
        // a caractere. A similaridade advém das diferenças em cada posição.
        } else
            return checkSimilaritySameSize(sString1, sString2);
    }

    protected static float checkSimilaritySameSize(String sString1, String sString2) throws Exception {

        if(sString1.length() != sString2.length())
            throw new Exception("Strings devem ter o mesmo tamanho!");

        int iLen = sString1.length();
        int iDiffs = 0;

        // Conta as diferenças entre as strings
        for(int i = 0; i < iLen; i++)
            if(sString1.charAt(i) != sString2.charAt(i))
                iDiffs++;

        // Calcula um percentual entre 0 e 1, sendo 0 completamente diferente e
        // 1 completamente igual
        return 1f - (float) iDiffs / iLen;
    }

    public static void main(String[] args) {
        try {
            System.out.println("'ABCD' vs 'ab' = " + checkSimilarity("ABCD", "ab"));
            System.out.println("'cidade' vs 'cdade' = " + checkSimilarity("cidade", "cdade"));
            System.out.println("'cidade' vs 'ciDade' = " + checkSimilarity("cidade", "ciDade"));
            System.out.println("'cidade' vs 'cdiade' = " + checkSimilarity("cidade", "cdiade"));
            System.out.println("'cidade' vs 'edadic' = " + checkSimilarity("cidade", "edadic"));
            System.out.println("'cidade' vs 'CIDADE' = " + checkSimilarity("cidade", "CIDADE"));
            System.out.println("'cidade' vs 'CIdADE' = " + checkSimilarity("cidade", "CIdADE"));
            System.out.println("'cidade' vs 'CdADE' = " + checkSimilarity("cidade", "CdADE"));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

O princípio do algoritmo é bastante simples:

  • Se as strings tiverem exatamente o mesmo tamanho, o método checkSimilarity simplesmente invocará o método-base checkSimilaritySameSize, que compara as strings caractere a caractere (da esquerda para a direita), conta o número de erros (caracteres diferentes) e retorna um percentual de erros em relação ao tamanho das strings.
  • Se, por outro lado, as strings tiverem tamanhos distintos, o método checkSimilarity faz o mesmo teste para cada combinação possível em que tantos caracteres quanto a diferença são incluídos da string maior em todas as posições da string menor. Por exemplo, supondo a string 1 como "ABCD" (tamanho = 4) e a string 2 como "ab" (tamanho = 2), as combinações serão "ABab", "aBCb" e "abCD".
  • Dentre as similaridades calculadas entre as combinações e a string de maior tamanho (já que agora ambas têm o mesmo tamanho), o método escolhe a de valor máximo, porém desconta uma "taxa de erro" proporcional ao número de caracteres na diferença.

Assim, o resultado da execução do código dado é o seguinte para esses exemplos:

'ABCD' vs 'ab' = 0.0
'cidade' vs 'cdade' = 0.8333333
'cidade' vs 'ciDade' = 0.8333333
'cidade' vs 'cdiade' = 0.6666666
'cidade' vs 'edadic' = 0.0
'cidade' vs 'CIDADE' = 0.0
'cidade' vs 'CIdADE' = 0.16666669
'cidade' vs 'CdADE' = 0.16666664

Quanto mais próximo de 1, mais semelhante são as strings, e quanto mais próximo de 0 mais distintas elas são. Se você não quiser diferenciar maísculas de minúsculas (note exemplo na terceira linha), basta converter ambas as strings para maísculo (com String::toUpperCase()) antes de compará-las.

Note que essa solução é bem simples porque admite que os erros (se existentes) se devem à falta de um ou mais caracteres em sequência. Você pode melhorar o algoritmo para que ele considere todas as reais combinações possíveis de caracteres, mas provavelmente isso será como usar uma bazuca para matar uma formiga.

2

O algorítimo mais utilizado para isso é o famoso "soundex". Consiste basicamente em um código com uma letra e 3 números. Existem variações deste algorítimo, conforme a fonética de cada país. Taiti, por exemplo, que tem apenas 8 consoantes, terá dificuldade maior na comparação das palavras.

A seguinte representação xyyy, comum na implementação da língua inglesa, (uma consoante e três vogais) seria assim:

Primeiro escolha uma tabela a ser usada, ou crie a sua própria, baseada no idioma. Exemplo:

  • 1 B F P V
  • 2 C G J K
  • 2 Q S X Y
  • 3 D T
  • 4 L LH
  • 5 M N
  • 6 R RR

Outra tabela de exemplo (eu uso uma variação desta):

  • 1 T D
  • 2 N NH
  • 3 M
  • 4 R RR RH
  • 5 L LH
  • 6 G J
  • 7 C K
  • 8 F W V
  • 9 P B
  • 0 S SS SH

Agora, para somar, use os princípios abaixo:

  • toda constante terá um número correspondente;
  • toda vogal e pontuação serão ignorados;
  • a primeira letra encontrada será representada por x;
  • após serem preenchidas as 3 consoantes, as adicionais serão ignoradas;
  • consoantes duplicadas serão unificadas;
  • nomes curtos terão zeros adicionados até completarem a representação xyyy.

Feito isso, basta somar os valores.

Por exemplo, Americanas, terá o seguinte valor M-472. Por quê? As vogais são ignoradas: mrcns Primeira letra: M Próximas consoantes e seus valores: 4(R)7(C)2(N)

Se a pessoa digitar americcanos, terá o seguinte valor M-472: Vogais ignoradas: mrccns Primeira letra: M Próximas: 4(R)77(C, duas consoantes são transformadas em 1)2(N).

Ou seja, o som de americanas e americcanos, america, americanizado, são idênticos. Agora, basta criar sua própria variação, conforme sua necessidade.

2
  • 1
    Na mesma família de algoritmos fonéticos vale a pena mencionar as várias implementações do Metaphone, algoritmo tipicamente utilizado em corretores ortográficos. Commented 25/03/2014 às 3:39
  • Boa dica. Não conhecia o Metaphone
    – user3813
    Commented 25/03/2014 às 16:17
0

Em java você possui o método contains() da classe String faz a comparação para ver se uma string está presente na outra:

String a = "Teste123";
String b = "123";

if(a.contains(b) == true){
System.out.println("Encontrado!");
}

Outra alternativa seria você pegar todas as letras das Strings e comparar as letras separadamente:

String a = "Cidade";
String b = "idade";
int auxiliar;

for(int i = 0;i<a.lenght();i++){
if(existeLetra(a.substring(i),b)){
   auxiliar++;
}
}

if(a.lenght - auxiliar < 2){
System.out.println("Parecido!");
}

public boolean existeLetra(char letra,String palavra){
return palavra.contains(letra); // retorna true or false
}

Apenas para comparar diferença em letras maiúsculas e minusculas você pode usar o método ignoreCase().

String a = "Cidade";
String b = "cidade";

if(b.ignoreCase().equals(a.ignoreCase)){
   System.out.println("OK!");
}
3
  • seu sobre nome é Paganini de verdade ou é apenas um nick? Commented 1/04/2014 às 20:34
  • É paganini mesmo, porque?
    – Giovani
    Commented 1/04/2014 às 20:44
  • 1
    Por nada, é que me lembrou o compositor Nicolo Paganini, legal.. Commented 1/04/2014 às 20:46
0

Estava buscando algo semelhante a sua proposta, e não sabia muito bem como fazer. Acabei Fazendo o seguinte Estava procurando nome semelhante em uma lista, e devolvendo o encontrado.

[HttpGet]
[Route("author/{name}")]
public async Task<ActionResult<List<Author>>> GetByName([FromServices] DataContext context, string name)
        {
            var test = await context.Authors.Where(x => name == null ?
                true :
                x.Name.ToUpper()
                .Contains(name.ToUpper()))
                .AsNoTracking()
                .ToListAsync();

             return test;
        }

Estava fazendo uma WebApi em C#/dotnet.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .