Author: britter
Date: Thu Jan 23 16:27:51 2014
New Revision: 1560727

URL: http://svn.apache.org/r1560727
Log:
LANG-944: Add the Jaro-Winkler string distance algorithm to StringUtils - 
partially applying the patch by Rekha Joshi as submitted for further refinement

Modified:
    commons/proper/lang/trunk/src/changes/changes.xml
    
commons/proper/lang/trunk/src/main/java/org/apache/commons/lang3/StringUtils.java
    
commons/proper/lang/trunk/src/test/java/org/apache/commons/lang3/StringUtilsTest.java

Modified: commons/proper/lang/trunk/src/changes/changes.xml
URL: 
http://svn.apache.org/viewvc/commons/proper/lang/trunk/src/changes/changes.xml?rev=1560727&r1=1560726&r2=1560727&view=diff
==============================================================================
--- commons/proper/lang/trunk/src/changes/changes.xml [utf-8] (original)
+++ commons/proper/lang/trunk/src/changes/changes.xml [utf-8] Thu Jan 23 
16:27:51 2014
@@ -22,6 +22,7 @@
   <body>
 
   <release version="3.3" date="TBA" description="Bugfix and Feature release">
+    <action issue="LANG-944" type="add" dev="britter" due-to="Rekha Joshi">Add 
the Jaro-Winkler string distance algorithm to StringUtils</action>
     <action issue="LANG-936" type="fix" dev="bayard" due-to="Yaniv Kunda, Eli 
Lindsey">StringUtils.getLevenshteinDistance with too big of a threshold returns 
wrong result</action>
     <action issue="LANG-943" type="fix" dev="kinow">Test 
DurationFormatUtilsTest.testEdgeDuration fails in JDK 1.6, 1.7 and 1.8, BRST 
time zone</action>
     <action issue="LANG-613" type="fix" 
dev="mbenson">ConstructorUtils.getAccessibleConstructor() Does Not Check the 
Accessibility of Enclosing Classes</action>

Modified: 
commons/proper/lang/trunk/src/main/java/org/apache/commons/lang3/StringUtils.java
URL: 
http://svn.apache.org/viewvc/commons/proper/lang/trunk/src/main/java/org/apache/commons/lang3/StringUtils.java?rev=1560727&r1=1560726&r2=1560727&view=diff
==============================================================================
--- 
commons/proper/lang/trunk/src/main/java/org/apache/commons/lang3/StringUtils.java
 (original)
+++ 
commons/proper/lang/trunk/src/main/java/org/apache/commons/lang3/StringUtils.java
 Thu Jan 23 16:27:51 2014
@@ -17,6 +17,7 @@
 package org.apache.commons.lang3;
 
 import java.io.UnsupportedEncodingException;
+
 import java.nio.charset.Charset;
 import java.text.Normalizer;
 import java.util.ArrayList;
@@ -6974,7 +6975,205 @@ public class StringUtils {
         }
         return -1;
     }
+    
+    /**
+     * <p>Find the Jaro Winkler Distance which indicates the similarity score 
between two Strings.</p>
+     *
+     * <p>The Jaro measure is the weighted sum of percentage of matched 
characters from each file and transposed characters. 
+     * Winkler increased this measure for matching initial characters</p>
+     *
+     * <p>This implementation is based on the Jaro Winkler similarity algorithm
+     * from <a 
href="http://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance";>http://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance</a></p>
+     * 
+     * <pre>
+     * StringUtils.getJaroWinklerDistance(null, null)          = 
IllegalArgumentException
+     * StringUtils.getJaroWinklerDistance("","")               = 0.0
+     * StringUtils.getJaroWinklerDistance("","a")              = 0.0
+     * StringUtils.getJaroWinklerDistance("aaapppp", "")       = 0.0
+     * StringUtils.getJaroWinklerDistance("frog", "fog")       = 0.93
+     * StringUtils.getJaroWinklerDistance("fly", "ant")        = 0.0
+     * StringUtils.getJaroWinklerDistance("elephant", "hippo") = 0.44
+     * StringUtils.getJaroWinklerDistance("hippo", "elephant") = 0.44
+     * StringUtils.getJaroWinklerDistance("hippo", "zzzzzzzz") = 0.0
+     * StringUtils.getJaroWinklerDistance("hello", "hallo")    = 0.88
+     * StringUtils.getJaroWinklerDistance("ABC Corporation", "ABC Corp") = 0.91
+     * StringUtils.getJaroWinklerDistance("D N H Enterprises Inc", "D & H 
Enterprises, Inc.") = 0.93
+     * StringUtils.getJaroWinklerDistance("My Gym Children's Fitness Center", 
"My Gym. Childrens Fitness") = 0.94
+     * StringUtils.getJaroWinklerDistance("PENNSYLVANIA", "PENNCISYLVNIA")    
= 0.9
+     * </pre>
+     *
+     * @param s  the first String, must not be null
+     * @param t  the second String, must not be null
+     * @return result distance
+     * @throws IllegalArgumentException if either String input {@code null}
+     */
+    public static double getJaroWinklerDistance(CharSequence first, 
CharSequence second){
+      double matchScore = 0.0;
+      final double DEFAULT_SCALING_FACTOR = 0.1;
+      
+      if (first == null || second == null)
+        throw new IllegalArgumentException("Strings must not be null");
+      
+      try {
+        double jaro = score(first,second);
+        int cl = commonPrefixLength(first, second);
+        matchScore = Math.round((jaro + (DEFAULT_SCALING_FACTOR * cl * (1.0 - 
jaro))) *100.0)/100.0;
+        //System.out.format("The score is %f for %s and %s ", matchScore,s1, 
s2);
+
+        return  matchScore;
+
+      } catch (Exception e) {
+
+      }
+      return matchScore;
+    }
+
+    /**
+     * This method returns the jarowinkler score for string matching.
+     * @param strings to be matched
+     * @return matching score without scaling factor impact
+     */
+    private static double score(CharSequence first, CharSequence second) {
+      String shorter;
+      String longer;
+
+      // Determine which String is longer.
+      if (first.length() > second.length())
+      {
+        longer = first.toString().toLowerCase();
+        shorter = second.toString().toLowerCase();
+      }
+      else
+      {
+        longer = second.toString().toLowerCase();
+        shorter = first.toString().toLowerCase();
+      }
+
+      // Calculate the half length() distance of the shorter String.
+      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.
+      String m1 = getSetOfMatchingCharacterWithin(shorter, longer, halflength);
+      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 transposition between the two sets
+      // of common characters.
+      int transpositions = transpositions(m1, m2);
+
+      // Calculate the distance.
+      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.
+     * 
+     * @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.
+     * @remarks 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.
+     */
+    private static String getSetOfMatchingCharacterWithin(CharSequence first, 
CharSequence second, int limit)
+    {
+
+      StringBuilder common = new StringBuilder();
+      StringBuilder copy = new StringBuilder(second);
+      for (int i = 0; i < first.length(); i++)
+      {
+        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 transposition between two strings.
+     * @param first The first string.
+     * @param second The second string.
+     * @return The number of transposition between the two strings.
+     */
+    private static int transpositions(CharSequence first, CharSequence second)
+    {
+      int transpositions = 0;
+      for (int i = 0; i < first.length(); i++)
+      {
+        if (first.charAt(i) != second.charAt(i))
+        {
+          transpositions++;
+        }
+      }
+      transpositions /= 2;
+      return transpositions;
+    }
+    
+    /**
+     * Calculates the number of characters from the beginning of the strings 
that match exactly one-to-one, 
+     * up to a maximum of four (4) characters.
+     * @param first The first string.
+     * @param second The second string.
+     * @return A number between 0 and 4.
+     */
+    private static int commonPrefixLength(CharSequence first, CharSequence 
second)
+    {
+        String shorter;
+        String longer;
+
+        // Determine which String is longer.
+        if (first.length() > second.length())
+        {
+            longer = first.toString().toLowerCase();
+            shorter = second.toString().toLowerCase();
+        }
+        else
+        {
+            longer = second.toString().toLowerCase();
+            shorter = first.toString().toLowerCase();
+        }
+
+        int result = 0;
+
+        // Iterate through the shorter string.
+        for (int i = 0; i < shorter.length(); i++)
+        {
+            if (shorter.charAt(i) != longer.charAt(i))
+            {
+                break;
+            }
+            result++;
+        }
+
+        // Limit the result to 4.
+        return result > 4? 4: result;
+    }
+    
     // startsWith
     //-----------------------------------------------------------------------
 

Modified: 
commons/proper/lang/trunk/src/test/java/org/apache/commons/lang3/StringUtilsTest.java
URL: 
http://svn.apache.org/viewvc/commons/proper/lang/trunk/src/test/java/org/apache/commons/lang3/StringUtilsTest.java?rev=1560727&r1=1560726&r2=1560727&view=diff
==============================================================================
--- 
commons/proper/lang/trunk/src/test/java/org/apache/commons/lang3/StringUtilsTest.java
 (original)
+++ 
commons/proper/lang/trunk/src/test/java/org/apache/commons/lang3/StringUtilsTest.java
 Thu Jan 23 16:27:51 2014
@@ -1918,6 +1918,45 @@ public class StringUtilsTest {
             // empty
         }
     }
+    
+    @Test
+    public void testGetJaroWinklerDistance_StringString() {
+      
+      assertEquals(0.93d, StringUtils.getJaroWinklerDistance("frog", "fog"), 
0.0d);
+      assertEquals(0.0d, StringUtils.getJaroWinklerDistance("fly", "ant"), 
0.0d);
+      assertEquals(0.44d, StringUtils.getJaroWinklerDistance("elephant", 
"hippo"), 0.0d);
+      assertEquals(0.91d, StringUtils.getJaroWinklerDistance("ABC 
Corporation", "ABC Corp"), 0.0d);
+      assertEquals(0.93d, StringUtils.getJaroWinklerDistance("D N H 
Enterprises Inc", "D & H Enterprises, Inc."), 0.0d);
+      assertEquals(0.94d, StringUtils.getJaroWinklerDistance("My Gym 
Children's Fitness Center", "My Gym. Childrens Fitness"), 0.0d);
+      assertEquals(0.9d, StringUtils.getJaroWinklerDistance("PENNSYLVANIA", 
"PENNCISYLVNIA"), 0.0d);
+      // exceptions
+      try {
+          @SuppressWarnings("unused")
+          final
+          double d = StringUtils.getJaroWinklerDistance(null, null);
+          fail("expecting IllegalArgumentException");
+      } catch (final IllegalArgumentException ex) {
+          // empty
+      }
+      
+      try {
+        @SuppressWarnings("unused")
+        final
+        double d = StringUtils.getJaroWinklerDistance(" ", null);
+        fail("expecting IllegalArgumentException");
+      } catch (final IllegalArgumentException ex) {
+        // empty
+      }
+      try {
+        @SuppressWarnings("unused")
+        final
+        double d = StringUtils.getJaroWinklerDistance(null, "clear");
+        fail("expecting IllegalArgumentException");
+      } catch (final IllegalArgumentException ex) {
+        // empty
+      }
+ 
+    }
 
     @Test
     public void testGetLevenshteinDistance_StringStringInt() {


Reply via email to