0

Is there a way or a tool to get percentage of difference between two strings (no new line characters, no files)?

For example, if there are 2 strings and each of them is 10 characters long and differ only in 1 character, then the difference should be 10%.

The strings may have different lengths and can hardly become longer than 30 characters.

  • What should be the percentage value for supercalifragilisticexpialidocious vs ssupercalifragilisticexpialidociou? – Stéphane Chazelas Aug 22 '17 at 16:56
  • @StéphaneChazelas The strings (each 34 characters long) differ in 2 characters. The percentage would be 2*100/34 = 5,88...% In general, I think it would make sense to compare the longest string against the shortest one. If the shortest string is contained in the longest, then remaining characters should be considered as difference. – ka3ak Aug 23 '17 at 12:09
  • but if you compare character to character, they're all different, which would make a 100% difference. Maybe you'd want to get the ratio of the Levenshtein distance to the average length. – Stéphane Chazelas Aug 23 '17 at 12:36
  • You're right character-by-character analysis won't work in this case. I'm not familiar with Levenshtein distance, but I'll take a look at it. There should be a way to find the longest match in a string and count all the other characters as difference. – ka3ak Aug 23 '17 at 13:14
2

The Levenshtein distance is a useful metric to give an idea of the amount of difference between two strings. It measures the number of insertions, deletions and substitutions needed to get from one string to the other.

For instance, if you compare abcdef and bcdef, all characters are different if you compare them one to one, but only one deletion is need to get from one to the other.

So you could make your percentage like: 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"

Or in 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"

That would give 100 for a vs b or bc, but 50 for ab vs ac or a or b or abcd. Beware you'll get a division-by-zero error if you try to compare the empty string against itself.

Those are limited by the maximum length of a command argument (128KiB on modern Linux systems), though you could work around that by getting the strings some other way (like reading them from a file) if need be.

A different metric that you may want to consider is the Damerau-Levenshtein distance (Text::Levenshtein::Damerau module in perl). That's the same as the the Levenshtein distance, except that transposition of contiguous characters (as in ab vs ba) counts as 1 instead of 2.

That's the distance used for instance by zsh approximate matching (as in [[ abcd = (#a2)acbe ]] to check that abcd is the same of acbe within a maximum distance of 2) and is common when it comes to consider human misspellings or DNA mutations.

  • What I don't understand, if the input to your awk program are two strings "abcd" and "dabc" the result is 50 However if I append a character to the second string (say "dabcx") the result will be even less than than the first one. Only 40. There is 1 insertion and 1 deletion In the first comparison. It the second comparison there is 1 insertion and 1 substitution. Is the cost of substitution less than the one of insertion or deletion? – ka3ak Aug 24 '17 at 9:41
  • @ka3ak, abcd vs dabc is 1 insertion (d at the start), 1 deletion (d at the end), so 2 in total compared to 4 the longest string (so 2/4*100 == 50). abcd vs dabcx is 1 insertion (d at the start), 1 substitution (x for d) compared to 5 the longest string (so 2/5*100 == 40). – Stéphane Chazelas Aug 24 '17 at 9:58
  • Ah ok. I see. I also want to minimize the difference. So I can interpret the result in this way. I compare "dabcx" vs. "abcd" and to get the second string from the first there is 1 deletion and 1 substitution necessary. 2 operations / length of the string to which operations were applied (5) * 100 = 40 – ka3ak Aug 24 '17 at 10:20
  • @ka3ak You can change the max(length(ARGV[1]), length(ARGV[2]) to length(ARGV[1]) if you want. But that would mean that if you compare a to xyz, you'd get a 300% difference and division by zero for "" to anything (infinitly different) – Stéphane Chazelas Aug 24 '17 at 10:30
  • Distance between abc and cdef equals 4. lev / max(3, 4) equals 1 like you have absolutely different strings, but LCS is c. So you are wrong. We need maximum amount of levenshtein operations. I don't know how to count it, but it should depends on LCS length at least. – puchu Jun 20 '18 at 22:08
0
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") }' <<< ""

output:

20% difference

The above example assumed that both variables ram and ram1 are always the same size in length. We pass both variables to awk and check each character one by one against the one in the other string, tracking the differences with a count variable.

At the end, we work out the percentage of the string that is different.

0

Using only shell functionality:

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))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.