diff porcentagem entre duas strings

Question

Existe uma maneira ou uma ferramenta para obter porcentagem de diferença entre duas strings (sem novos caracteres de linha, sem arquivos)?

Por exemplo, se houver 2 strings e cada uma delas tiver 10 caracteres e diferirem apenas em 1 caractere, a diferença deverá ser de 10%.

As strings podem ter comprimentos diferentes e dificilmente podem ter mais de 30 caracteres.

    

Answer 1

A distância Levenshtein é uma métrica útil para dar uma idéia da quantidade de diferença entre duas strings. Ele mede o número de inserções, exclusões e substituições necessárias para ir de uma string para outra.

Por exemplo, se você comparar abcdef e bcdef , todos os caracteres serão diferentes se você os comparar um a um, mas somente uma exclusão precisará passar de um para o outro.

Assim, você pode aumentar sua porcentagem como: distance / max_length:

perl -MList::Util=max -MText::LevenshteinXS -le '
  ($x, $y) = @ARGV
  print 100 * distance($x, $y) / max(length $x , length $x)
  ' -- "$string1" "$string2"

Ou em awk :

awk '
    function min(x, y) {
      return x < y ? x : y
    }
    function max(x, y) {
      return x > y ? x : y
    }
    function lev(s,t) {
      m = length(s)
      n = length(t)

      for(i=0;i<=m;i++) d[i,0] = i
      for(j=0;j<=n;j++) d[0,j] = j

      for(i=1;i<=m;i++) {
        for(j=1;j<=n;j++) {
          c = substr(s,i,1) != substr(t,j,1)
          d[i,j] = min(d[i-1,j]+1,min(d[i,j-1]+1,d[i-1,j-1]+c))
        }
      }

      return d[m,n]
    }

    BEGIN {
      print 100 * lev(ARGV[1], ARGV[2]) / max(length(ARGV[1]), length(ARGV[2]))
      exit
    }' "$string1" "$string2"

Isso daria 100 para a vs b ou bc , mas 50% para ab vs ac ou a ou b ou abcd . Cuidado, você receberá um erro de divisão por zero se tentar comparar a string vazia contra si mesma.

Eles são limitados pelo comprimento máximo de um argumento de comando (128KiB em sistemas Linux modernos), embora você possa contornar isso obtendo as strings de outra maneira (como lê-las de um arquivo) se necessário.

Uma métrica diferente que você pode considerar é a distância Damerau-Levenshtein ( Text::Levenshtein::Damerau module em perl ). Isso é o mesmo que a distância de Levenshtein, exceto que a transposição de caracteres contíguos (como em ab vs ba ) conta como 1 em vez de 2.

Essa é a distância usada, por exemplo, pela% aproximada zsh (como em [[ abcd = (#a2)acbe ]] para verificar se abcd é igual a acbe em uma distância máxima de 2) e é comum quando se trata de considerar humano erros ortográficos ou mutações no DNA.

    

Answer 2

ram="rambo"

ram1="rimbo"

awk -v ram=$ram -v ram1=$ram1 '{ for (i=1;i<=length(ram);i++) { if (substr(ram,i,1) != substr(ram1,i,1)) { count++ } }} END { print (count/length(ram)*100"% difference") }' <<< ""

saída:

20% difference

O exemplo acima assumiu que as duas variáveis ram e ram1 são sempre do mesmo tamanho em comprimento. Passamos as duas variáveis para awk e verificamos cada caractere um por um em relação ao da outra, rastreando as diferenças com uma variável de contagem.

No final, calculamos a porcentagem da string que é diferente.

    

Answer 3

Usando apenas a funcionalidade do shell:

s1=ka3ak
s2=Raman

maxlen=${#s1}
diffs=0
[[ ${#s2} -gt $maxlen ]] && maxlen=${#s2}
for((i=0; i < maxlen; i++))
do
  [[ ${s1:i:1} == ${s2:i:1} ]] || ((++diffs))
done
echo $((100 * diffs / maxlen))