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.