3
\$\begingroup\$

String Similarity

String similarity is basically a ratio of how similar one string is to another. This can be calculated in many ways, and there are various algorithms out there for implementing a ratio calculation for string similarity, some being more accurate than others. It's actually very useful to use these methods in diff algorithms for the calculation of how similar one document or string is to one another.

A couple of the most popular algorithms are:

In practice, calculating all three and taking the average works very well for most purposes. However, to keep the challenge more simple, I am not going to over-ask. For the purpose of this challenge, you must implement the Jaro-Winkler algorithm.

Rules

  • Built ins are welcome, but must be marked non-competing, (E.G. .L - 05AB1E)
  • Your input must only be 2 strings f(a,b).
  • The comparison should be Case insensitive, that is to say: f('aBc','aBC')=f('abc','Abc')=f('abc','abc')=1.0
    In other words, convert the strings to lower case before the comparison or something like that.
  • Your output must be a double, float or ratio appropriately expressed in the language of your choice; as long as the output is obviously interpreted, it's fine.
  • This is code-golf, shortest answer wins.

Examples

  • jw(a,b) represents Jaro-Winkler similarity.

Example Algorithm in Java

/**
 * Calculates the similarity score of objects, where 0.0 implies absolutely
 * no similarity and 1.0 implies absolute similarity.
 * 
 * @param first
 *            The first string to compare.
 * @param second
 *            The second string to compare.
 * @return A number between 0.0 and 1.0.
 */
public static final double jaroSimilarity(final String first,
        final String second) {
    final String shorter;
    final String longer;

    // Determine which String is longer.
    if (first.length() > second.length()) {
        longer = first.toLowerCase();
        shorter = second.toLowerCase();
    } else {
        longer = second.toLowerCase();
        shorter = first.toLowerCase();
    }

    // Calculate the half length() distance of the shorter String.
    final int halflength = (shorter.length() / 2) + 1;

    // Find the set of matching characters between the shorter and longer
    // strings. Note that
    // the set of matching characters may be different depending on the
    // order of the strings.
    final String m1 = getSetOfMatchingCharacterWithin(shorter, longer,
            halflength);
    final String m2 = getSetOfMatchingCharacterWithin(longer, shorter,
            halflength);

    // If one or both of the sets of common characters is empty, then
    // there is no similarity between the two strings.
    if (m1.length() == 0 || m2.length() == 0)
        return 0.0;

    // If the set of common characters is not the same size, then
    // there is no similarity between the two strings, either.
    if (m1.length() != m2.length())
        return 0.0;

    // Calculate the number of transpositions between the two sets
    // of common characters.
    final int transpositions = transpositions(m1, m2);

    // Calculate the distance.
    final double dist = (m1.length() / ((double) shorter.length())
            + m2.length() / ((double) longer.length()) + (m1.length() - transpositions)
            / ((double) m1.length())) / 3.0;
    return dist;

}

/**
 * Gets a set of matching characters between two strings. Two characters
 * from the first string and the second string are considered matching if
 * the character's respective positions are no farther than the limit value.
 * 
 * @param first
 *            The first string.
 * @param second
 *            The second string.
 * @param limit
 *            The maximum distance to consider.
 * @return A string contain the set of common characters.
 */
private static final String getSetOfMatchingCharacterWithin(
        final String first, final String second, final int limit) {

    final StringBuilder common = new StringBuilder();
    final StringBuilder copy = new StringBuilder(second);
    for (int i = 0; i < first.length(); i++) {
        final char ch = first.charAt(i);
        boolean found = false;

        // See if the character is within the limit positions away from the
        // original position of that character.
        for (int j = Math.max(0, i - limit); !found
                && j < Math.min(i + limit, second.length()); j++) {
            if (copy.charAt(j) == ch) {
                found = true;
                common.append(ch);
                copy.setCharAt(j, '*');
            }
        }
    }
    return common.toString();
}

/**
 * Calculates the number of transpositions between two strings.
 * 
 * @param first
 *            The first string.
 * @param second
 *            The second string.
 * @return The number of transpositions between the two strings.
 */
private static final int transpositions(final String first,
        final String second) {
    int transpositions = 0;
    for (int i = 0; i < first.length(); i++) {
        if (first.charAt(i) != second.charAt(i)) {
            transpositions++;
        }
    }
    transpositions /= 2;
    return transpositions;
}

Here's all my test cases, if you want another one, ask me.

jw ('abc','AbC')=1.0
jw ('i walked to the store','the store walked to i')=0.7553688141923436
jw ('seers','sears')=0.8666666666666667
jw ('banana','bandana')=0.9523809523809524
jw ('abc','xyz')=0.0
jw ('1234567890qwertyuiopasdfghjklzxcvbnm','mnbvcxzlkjhgfdsapoiuytrewq0987654321')=0.5272904483430799
jw ('#faceroll:j4565j6eekty;fyuolkidsujkr79tp[8yiusyweryhjrn7ktgm9k,u[pk7jf6trhvgag5vhbdtnfymghu,','#faceroll:ezbrytnmugof7ihdgsyftwacvegybrnftiygihdugs5ya4tsyrdu6htifj7yif')=0.6512358338650381
\$\endgroup\$
  • \$\begingroup\$ Related \$\endgroup\$ – DLosc Oct 7 '16 at 19:19
  • 7
    \$\begingroup\$ You should specify the actual algorithm to be used in the challenge instead of linking to external resources. Challenges should be self-contained. \$\endgroup\$ – Emigna Oct 7 '16 at 19:45
  • \$\begingroup\$ ^ (links tend to die over time) \$\endgroup\$ – mbomb007 Oct 7 '16 at 19:46
  • \$\begingroup\$ Wikipedia links? Fair enough though. Snippet posted. \$\endgroup\$ – Magic Octopus Urn Oct 7 '16 at 19:48
  • 1
    \$\begingroup\$ I'll clarify more on the other question to include that stipulation. \$\endgroup\$ – Magic Octopus Urn Oct 7 '16 at 20:20
2
\$\begingroup\$

Python 3, 351 350 347 346 bytes

l=len
r=range
a,b=input(),input()
x,y=(a.lower(),b.lower())[::1-2*(l(a)>l(b))]
h=l(y)//2+1
n=o=''
for a,b in(x,y),(y,x):
 for i in r(l(a)):
  for j in r(max(0,i-h),min(i+h,l(b))):
   if b[j]==a[i]:o+=a[i];b=b[:j]+'*'+b[j+1:];break
 n,o=o,n
q,z=l(n),l(o)
print(0if(any((n,o))-1or z!=q)else(z/l(y)+q/l(x)+(z-sum(n[i]!=o[i]for i in r(l(n)))/2)/z)/3)

Expects the two inputs on STDIN, newline-separated. Example run:

$ echo -e "seers\nsears" | python jaro.py
0.8666666666666667

Saved 1 byte thanks to @Shebang!

\$\endgroup\$
  • \$\begingroup\$ I know we're a way past when you posted this, but you can save 2 bytes by making the indent levels for the inner for group as SPACE TAB TAB+SPACE SPACE (I hope this makes sense). Also, you can do (a.lower(),b.lower())[::1+-2*(l(a)>l(b))] -> (b.lower(),a.lower())[::2*(l(a)>l(b))-1] to save another byte. \$\endgroup\$ – Kade Oct 28 '16 at 16:51
  • \$\begingroup\$ @Shebang Your first trick only works in Python 2, so I can't use it. Thanks for the other one, though! \$\endgroup\$ – Copper Oct 28 '16 at 19:48
0
\$\begingroup\$

Bash 4+, 450 bytes

Try it Online!

Assumes that string1 is equal or longer than string2.

x="${1,,}" y="${2,,}" h=$((${#y}/2+1))
r(){ k=${#1} l=${#2} g="$2" s=""
for((i=0;i<k;i++)){ p="${1:i:1}" v=$((i-h<0?0:i-h)) w=$((i+h>l?l:i+h))
for((j=v;j<w;j++)){ [[ $p = ${g:j:1} ]]&&{ s="$s$p";g="${g::j}.${g:j+1}";break;};};};echo $s;}
m=`r "$x" "$y"` n=`r "$y" "$x"` d=${#m} e=${#n}
[ $((d==0|e==0|d!=e?0:1)) = 0 ]&&{ echo 0.0;exit;}
for((i=0;i<d;i++)){ [ "${m:i:1}" != "${n:i:1}" ]&&((u++));};z=$((u/2))
bc -l<<<"($d/${#y}+$e/${#x}+($d-$z)/$d)/3"

All tests OK except 'i walked to the store' yields .69543650793650793650 for some reason

Ungolfed, commented version here: https://gist.github.com/roblogic/27ea1a4fd79623b295e16e0561fcb6d7

\$\endgroup\$

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.