# diff percentage between two strings

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

## 3 Answers

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, ARGV) / max(length(ARGV), length(ARGV))
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), length(ARGV)` to `length(ARGV)` 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
``````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.

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