fork(258) download 
  1. /* package whatever; // don't place package name! */
  2.  
  3. class StringSimilarity {
  4.  
  5.     /**
  6.      * Calculates the similarity (a number within 0 and 1) between two strings.
  7.      */
  8.     public static double similarity(String s1, String s2) {
  9.         String longer = s1, shorter = s2;
  10.         if (s1.length() < s2.length()) { // longer should always have greater length
  11.             longer = s2; shorter = s1;
  12.         }
  13.         int longerLength = longer.length();
  14.         if (longerLength == 0) { return 1.0; /* both strings are zero length */ }
  15.         /* // If you have StringUtils, you can use it to calculate the edit distance:
  16.         return (longerLength - StringUtils.getLevenshteinDistance(longer, shorter)) /
  17.                                                              (double) longerLength; */
  18.         return (longerLength - editDistance(longer, shorter)) / (double) longerLength;
  19.  
  20.     }
  21.  
  22.     // Example implementation of the Levenshtein Edit Distance
  23.     // See http://r...content-available-to-author-only...e.org/wiki/Levenshtein_distance#Java
  24.     public static int editDistance(String s1, String s2) {
  25.         s1 = s1.toLowerCase();
  26.         s2 = s2.toLowerCase();
  27.  
  28.         int[] costs = new int[s2.length() + 1];
  29.         for (int i = 0; i <= s1.length(); i++) {
  30.             int lastValue = i;
  31.             for (int j = 0; j <= s2.length(); j++) {
  32.                 if (i == 0)
  33.                     costs[j] = j;
  34.                 else {
  35.                     if (j > 0) {
  36.                         int newValue = costs[j - 1];
  37.                         if (s1.charAt(i - 1) != s2.charAt(j - 1))
  38.                             newValue = Math.min(Math.min(newValue, lastValue),
  39.                                     costs[j]) + 1;
  40.                         costs[j - 1] = lastValue;
  41.                         lastValue = newValue;
  42.                     }
  43.                 }
  44.             }
  45.             if (i > 0)
  46.                 costs[s2.length()] = lastValue;
  47.         }
  48.         return costs[s2.length()];
  49.     }
  50.  
  51.     public static void printSimilarity(String s, String t) {
  52.         System.out.println(String.format(
  53.             "%.3f is the similarity between \"%s\" and \"%s\"", similarity(s, t), s, t));
  54.     }
  55.  
  56.     public static void main(String[] args) {
  57.         printSimilarity("", "");
  58.         printSimilarity("1234567890", "1");
  59.         printSimilarity("1234567890", "123");
  60.         printSimilarity("1234567890", "1234567");
  61.         printSimilarity("1234567890", "1234567890");
  62.         printSimilarity("1234567890", "1234567980");
  63.         printSimilarity("47/2010", "472010");
  64.         printSimilarity("47/2010", "472011");
  65.         printSimilarity("47/2010", "AB.CDEF");
  66.         printSimilarity("47/2010", "4B.CDEFG");
  67.         printSimilarity("47/2010", "AB.CDEFG");
  68.         printSimilarity("The quick fox jumped", "The fox jumped");
  69.         printSimilarity("The quick fox jumped", "The fox");
  70.         printSimilarity("The quick fox jumped", "The quick fox jumped off the balcany");
  71.         printSimilarity("kitten", "sitting");
  72.     }
  73.  
  74. }
Success #stdin #stdout 0.08s 380352KB
comments (?)
stdin 
Standard input is empty
stdout 
1.000 is the similarity between "" and ""
0.100 is the similarity between "1234567890" and "1"
0.300 is the similarity between "1234567890" and "123"
0.700 is the similarity between "1234567890" and "1234567"
1.000 is the similarity between "1234567890" and "1234567890"
0.800 is the similarity between "1234567890" and "1234567980"
0.857 is the similarity between "47/2010" and "472010"
0.714 is the similarity between "47/2010" and "472011"
0.000 is the similarity between "47/2010" and "AB.CDEF"
0.125 is the similarity between "47/2010" and "4B.CDEFG"
0.000 is the similarity between "47/2010" and "AB.CDEFG"
0.700 is the similarity between "The quick fox jumped" and "The fox jumped"
0.350 is the similarity between "The quick fox jumped" and "The fox"
0.556 is the similarity between "The quick fox jumped" and "The quick fox jumped off the balcany"
0.571 is the similarity between "kitten" and "sitting"
https://ideone.com/oOVWYj
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!