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; 020import java.util.Objects; 021 022/** 023 * A similarity algorithm indicating the percentage of matched characters between two character sequences. 024 * 025 * <p> 026 * The Jaro measure is the weighted sum of percentage of matched characters from each file and transposed characters. Winkler increased this measure for 027 * matching initial characters. 028 * </p> 029 * <p> 030 * This implementation is based on the Jaro Winkler similarity algorithm from <a href="https://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance"> 031 * https://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance</a>. 032 * </p> 033 * <p> 034 * This code has been adapted from Apache Commons Lang 3.3. 035 * </p> 036 * 037 * @since 1.7 038 */ 039public class JaroWinklerSimilarity implements SimilarityScore<Double> { 040 041 /** 042 * Singleton instance. 043 */ 044 static final JaroWinklerSimilarity INSTANCE = new JaroWinklerSimilarity(); 045 046 /** 047 * Computes the Jaro-Winkler string matches, half transpositions, prefix array. 048 * 049 * @param first the first input to be matched. 050 * @param second the second input to be matched. 051 * @return mtp array containing: matches, half transpositions, and prefix. 052 */ 053 protected static int[] matches(final CharSequence first, final CharSequence second) { 054 return matches(SimilarityInput.input(first), SimilarityInput.input(second)); 055 } 056 057 /** 058 * Computes the Jaro-Winkler string matches, half transpositions, prefix array. 059 * 060 * @param <E> The type of similarity score unit. 061 * @param first the first input to be matched. 062 * @param second the second input to be matched. 063 * @return mtp array containing: matches, half transpositions, and prefix. 064 * @since 1.13.0 065 */ 066 protected static <E> int[] matches(final SimilarityInput<E> first, final SimilarityInput<E> second) { 067 final SimilarityInput<E> max; 068 final SimilarityInput<E> min; 069 if (first.length() > second.length()) { 070 max = first; 071 min = second; 072 } else { 073 max = second; 074 min = first; 075 } 076 final int range = Math.max(max.length() / 2 - 1, 0); 077 final int[] matchIndexes = new int[min.length()]; 078 Arrays.fill(matchIndexes, -1); 079 final boolean[] matchFlags = new boolean[max.length()]; 080 int matches = 0; 081 for (int mi = 0; mi < min.length(); mi++) { 082 final E c1 = min.at(mi); 083 for (int xi = Math.max(mi - range, 0), xn = Math.min(mi + range + 1, max.length()); xi < xn; xi++) { 084 if (!matchFlags[xi] && c1.equals(max.at(xi))) { 085 matchIndexes[mi] = xi; 086 matchFlags[xi] = true; 087 matches++; 088 break; 089 } 090 } 091 } 092 final Object[] ms1 = new Object[matches]; 093 final Object[] ms2 = new Object[matches]; 094 for (int i = 0, si = 0; i < min.length(); i++) { 095 if (matchIndexes[i] != -1) { 096 ms1[si] = min.at(i); 097 si++; 098 } 099 } 100 for (int i = 0, si = 0; i < max.length(); i++) { 101 if (matchFlags[i]) { 102 ms2[si] = max.at(i); 103 si++; 104 } 105 } 106 int halfTranspositions = 0; 107 for (int mi = 0; mi < ms1.length; mi++) { 108 if (!ms1[mi].equals(ms2[mi])) { 109 halfTranspositions++; 110 } 111 } 112 int prefix = 0; 113 for (int mi = 0; mi < Math.min(4, min.length()); mi++) { 114 if (!first.at(mi).equals(second.at(mi))) { 115 break; 116 } 117 prefix++; 118 } 119 return new int[] { matches, halfTranspositions, prefix }; 120 } 121 122 /** 123 * Creates a new instance. 124 */ 125 public JaroWinklerSimilarity() { 126 // empty 127 } 128 129 /** 130 * Computes the Jaro Winkler Similarity between two character sequences. 131 * 132 * <pre> 133 * sim.apply(null, null) = IllegalArgumentException 134 * sim.apply("foo", null) = IllegalArgumentException 135 * sim.apply(null, "foo") = IllegalArgumentException 136 * sim.apply("", "") = 1.0 137 * sim.apply("foo", "foo") = 1.0 138 * sim.apply("foo", "foo ") = 0.94 139 * sim.apply("foo", "foo ") = 0.91 140 * sim.apply("foo", " foo ") = 0.87 141 * sim.apply("foo", " foo") = 0.51 142 * sim.apply("", "a") = 0.0 143 * sim.apply("aaapppp", "") = 0.0 144 * sim.apply("frog", "fog") = 0.93 145 * sim.apply("fly", "ant") = 0.0 146 * sim.apply("elephant", "hippo") = 0.44 147 * sim.apply("hippo", "elephant") = 0.44 148 * sim.apply("hippo", "zzzzzzzz") = 0.0 149 * sim.apply("hello", "hallo") = 0.88 150 * sim.apply("ABC Corporation", "ABC Corp") = 0.91 151 * sim.apply("D N H Enterprises Inc", "D & H Enterprises, Inc.") = 0.95 152 * sim.apply("My Gym Children's Fitness Center", "My Gym. Childrens Fitness") = 0.92 153 * sim.apply("PENNSYLVANIA", "PENNCISYLVNIA") = 0.88 154 * </pre> 155 * 156 * @param left the first input, must not be null. 157 * @param right the second input, must not be null. 158 * @return result similarity. 159 * @throws IllegalArgumentException if either CharSequence input is {@code null}. 160 */ 161 @Override 162 public Double apply(final CharSequence left, final CharSequence right) { 163 return apply(SimilarityInput.input(left), SimilarityInput.input(right)); 164 } 165 166 /** 167 * Computes the Jaro Winkler Similarity between two character sequences. 168 * 169 * <pre> 170 * sim.apply(null, null) = IllegalArgumentException 171 * sim.apply("foo", null) = IllegalArgumentException 172 * sim.apply(null, "foo") = IllegalArgumentException 173 * sim.apply("", "") = 1.0 174 * sim.apply("foo", "foo") = 1.0 175 * sim.apply("foo", "foo ") = 0.94 176 * sim.apply("foo", "foo ") = 0.91 177 * sim.apply("foo", " foo ") = 0.87 178 * sim.apply("foo", " foo") = 0.51 179 * sim.apply("", "a") = 0.0 180 * sim.apply("aaapppp", "") = 0.0 181 * sim.apply("frog", "fog") = 0.93 182 * sim.apply("fly", "ant") = 0.0 183 * sim.apply("elephant", "hippo") = 0.44 184 * sim.apply("hippo", "elephant") = 0.44 185 * sim.apply("hippo", "zzzzzzzz") = 0.0 186 * sim.apply("hello", "hallo") = 0.88 187 * sim.apply("ABC Corporation", "ABC Corp") = 0.91 188 * sim.apply("D N H Enterprises Inc", "D & H Enterprises, Inc.") = 0.95 189 * sim.apply("My Gym Children's Fitness Center", "My Gym. Childrens Fitness") = 0.92 190 * sim.apply("PENNSYLVANIA", "PENNCISYLVNIA") = 0.88 191 * </pre> 192 * 193 * @param <E> The type of similarity score unit. 194 * @param left the first input, must not be null. 195 * @param right the second input, must not be null. 196 * @return result similarity. 197 * @throws IllegalArgumentException if either CharSequence input is {@code null}. 198 * @since 1.13.0 199 */ 200 public <E> Double apply(final SimilarityInput<E> left, final SimilarityInput<E> right) { 201 final double defaultScalingFactor = 0.1; 202 if (left == null || right == null) { 203 throw new IllegalArgumentException("CharSequences must not be null"); 204 } 205 if (Objects.equals(left, right)) { 206 return 1d; 207 } 208 final int[] mtp = matches(left, right); 209 final double m = mtp[0]; 210 if (m == 0) { 211 return 0d; 212 } 213 final double j = (m / left.length() + m / right.length() + (m - (double) mtp[1] / 2) / m) / 3; 214 return j < 0.7d ? j : j + defaultScalingFactor * mtp[2] * (1d - j); 215 } 216 217}