A ocorrência de implementações que comparam duas strings em projetos é relativamente frequente, porem medir a distância de igualdade entre strings é pequena.

Mas o que de fato é medir a distância de igualdade?
R: É medir o quanto dois conjuntos de caracteres são semelhantes e resultar em uma pontuação.

Recentemente usamos um algorítimo para esta tarefa muito interessante, o Jaro-Winkler. A métrica de Jaro–Winkler distance estabelece que dada duas strings  e , sua distância  é:

Fórmula

Fórmula

  • é o número de correlações entre caracteres;
  • e  são os tamanhos das respectivas strings;
  • é a metade do número de transposições;

Cada carácter de  é comparado com todos os caracteres de O número de caracteres correspondentes (mas de ordem de sequência diferente) dividido por 2 define o número de transposições.

Exemplo:
Dadas duas strings:  PARMIGIANI e  MIGAN

  •  = 5
  •  = 10
  •  = 5
  •  = 2

Assim, chegamos a uma pontuação de semelhança:

Pontuação de semelhança

Pontuação de semelhança

A seguir código Java que implementa o algoritmo Jaro–Winkler distance, este exemplo foi retirado do site do projeto.

public class JaroDistance {
	public static double distance(String s, String t) {
		int s_len = s.length();
        int t_len = t.length();
 
        if (s_len == 0 && t_len == 0) return 1;
 
        int match_distance = Integer.max(s_len, t_len) / 2 - 1;
 
        boolean[] s_matches = new boolean[s_len];
        boolean[] t_matches = new boolean[t_len];

		int matches = 0;
		int transpositions = 0;

		for (int i = 0; i < s_len; i++) {
			int start = Integer.max(0, i - match_distance);
			int end = Integer.min(i + match_distance + 1, t_len);

			for (int j = start; j < end; j++) {
				if (t_matches[j])
					continue;
				if (s.charAt(i) != t.charAt(j))
					continue;
				s_matches[i] = true;
				t_matches[j] = true;
				matches++;
				break;
			}
		}

		if (matches == 0)
			return 0;

		int k = 0;
		for (int i = 0; i < s_len; i++) {
			if (!s_matches[i])
				continue;
			while (!t_matches[k])
				k++;
			if (s.charAt(i) != t.charAt(k))
				transpositions++;
			k++;
		}

		return (((double) matches / s_len) + ((double) matches / t_len)
				+ (((double) matches - transpositions / 2.0) / matches)) / 3.0;
	}

	public static void main(String[] args) {
		System.out.println(distance("PARMIGIANI", "MIGAN"));
	}
}

Teste, altere, brinque e divirtam-se.

Por enquanto é isso, até o próximo post

Deixe um comentário

Campos obrigatórios são marcados *

Post Navigation