001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.text.similarity; 018 019import java.util.Arrays; 020 021/** 022 * A similarity algorithm indicating the percentage of matched characters between two character sequences. 023 * 024 * <p> 025 * The Jaro measure is the weighted sum of percentage of matched characters 026 * from each file and transposed characters. Winkler increased this measure 027 * for matching initial characters. 028 * </p> 029 * 030 * <p> 031 * This implementation is based on the Jaro Winkler similarity algorithm 032 * from <a href="http://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance"> 033 * http://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance</a>. 034 * </p> 035 * 036 * <p> 037 * This code has been adapted from Apache Commons Lang 3.3. 038 * </p> 039 * 040 * @since 1.0 041 */ 042public class JaroWinklerDistance implements SimilarityScore<Double> { 043 044 /** 045 * Represents a failed index search. 046 */ 047 public static final int INDEX_NOT_FOUND = -1; 048 049 /** 050 * Find the Jaro Winkler Distance which indicates the similarity score 051 * between two CharSequences. 052 * 053 * <pre> 054 * distance.apply(null, null) = IllegalArgumentException 055 * distance.apply("","") = 0.0 056 * distance.apply("","a") = 0.0 057 * distance.apply("aaapppp", "") = 0.0 058 * distance.apply("frog", "fog") = 0.93 059 * distance.apply("fly", "ant") = 0.0 060 * distance.apply("elephant", "hippo") = 0.44 061 * distance.apply("hippo", "elephant") = 0.44 062 * distance.apply("hippo", "zzzzzzzz") = 0.0 063 * distance.apply("hello", "hallo") = 0.88 064 * distance.apply("ABC Corporation", "ABC Corp") = 0.93 065 * distance.apply("D N H Enterprises Inc", "D & H Enterprises, Inc.") = 0.95 066 * distance.apply("My Gym Children's Fitness Center", "My Gym. Childrens Fitness") = 0.92 067 * distance.apply("PENNSYLVANIA", "PENNCISYLVNIA") = 0.88 068 * </pre> 069 * 070 * @param left the first CharSequence, must not be null 071 * @param right the second CharSequence, must not be null 072 * @return result distance 073 * @throws IllegalArgumentException if either CharSequence input is {@code null} 074 */ 075 @Override 076 public Double apply(final CharSequence left, final CharSequence right) { 077 final double defaultScalingFactor = 0.1; 078 079 if (left == null || right == null) { 080 throw new IllegalArgumentException("CharSequences must not be null"); 081 } 082 083 final int[] mtp = matches(left, right); 084 final double m = mtp[0]; 085 if (m == 0) { 086 return 0D; 087 } 088 final double j = ((m / left.length() + m / right.length() + (m - mtp[1]) / m)) / 3; 089 final double jw = j < 0.7D ? j : j + Math.min(defaultScalingFactor, 1D / mtp[3]) * mtp[2] * (1D - j); 090 return jw; 091 } 092 093 /** 094 * This method returns the Jaro-Winkler string matches, transpositions, prefix, max array. 095 * 096 * @param first the first string to be matched 097 * @param second the second string to be matched 098 * @return mtp array containing: matches, transpositions, prefix, and max length 099 */ 100 protected static int[] matches(final CharSequence first, final CharSequence second) { 101 CharSequence max, min; 102 if (first.length() > second.length()) { 103 max = first; 104 min = second; 105 } else { 106 max = second; 107 min = first; 108 } 109 final int range = Math.max(max.length() / 2 - 1, 0); 110 final int[] matchIndexes = new int[min.length()]; 111 Arrays.fill(matchIndexes, -1); 112 final boolean[] matchFlags = new boolean[max.length()]; 113 int matches = 0; 114 for (int mi = 0; mi < min.length(); mi++) { 115 final char c1 = min.charAt(mi); 116 for (int xi = Math.max(mi - range, 0), xn = Math.min(mi + range + 1, max.length()); xi < xn; xi++) { 117 if (!matchFlags[xi] && c1 == max.charAt(xi)) { 118 matchIndexes[mi] = xi; 119 matchFlags[xi] = true; 120 matches++; 121 break; 122 } 123 } 124 } 125 final char[] ms1 = new char[matches]; 126 final char[] ms2 = new char[matches]; 127 for (int i = 0, si = 0; i < min.length(); i++) { 128 if (matchIndexes[i] != -1) { 129 ms1[si] = min.charAt(i); 130 si++; 131 } 132 } 133 for (int i = 0, si = 0; i < max.length(); i++) { 134 if (matchFlags[i]) { 135 ms2[si] = max.charAt(i); 136 si++; 137 } 138 } 139 int transpositions = 0; 140 for (int mi = 0; mi < ms1.length; mi++) { 141 if (ms1[mi] != ms2[mi]) { 142 transpositions++; 143 } 144 } 145 int prefix = 0; 146 for (int mi = 0; mi < min.length(); mi++) { 147 if (first.charAt(mi) == second.charAt(mi)) { 148 prefix++; 149 } else { 150 break; 151 } 152 } 153 return new int[] {matches, transpositions / 2, prefix, max.length()}; 154 } 155 156}