1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 package org.apache.commons.text.similarity; 18 19 import java.util.Locale; 20 21 /** 22 * A matching algorithm that is similar to the searching algorithms implemented in editors such 23 * as Sublime Text, TextMate, Atom and others. 24 * 25 * <p> 26 * One point is given for every matched character. Subsequent matches yield two bonus points. A higher score 27 * indicates a higher similarity. 28 * </p> 29 * 30 * <p> 31 * This code has been adapted from Apache Commons Lang 3.3. 32 * </p> 33 * 34 * @since 1.0 35 */ 36 public class FuzzyScore { 37 38 /** 39 * Locale used to change the case of text. 40 */ 41 private final Locale locale; 42 43 /** 44 * This returns a {@link Locale}-specific {@link FuzzyScore}. 45 * 46 * @param locale The string matching logic is case insensitive. 47 A {@link Locale} is necessary to normalize both Strings to lower case. 48 * @throws IllegalArgumentException 49 * This is thrown if the {@link Locale} parameter is {@code null}. 50 */ 51 public FuzzyScore(final Locale locale) { 52 if (locale == null) { 53 throw new IllegalArgumentException("Locale must not be null"); 54 } 55 this.locale = locale; 56 } 57 58 /** 59 * Find the Fuzzy Score which indicates the similarity score between two 60 * Strings. 61 * 62 * <pre> 63 * score.fuzzyScore(null, null) = IllegalArgumentException 64 * score.fuzzyScore("not null", null) = IllegalArgumentException 65 * score.fuzzyScore(null, "not null") = IllegalArgumentException 66 * score.fuzzyScore("", "") = 0 67 * score.fuzzyScore("Workshop", "b") = 0 68 * score.fuzzyScore("Room", "o") = 1 69 * score.fuzzyScore("Workshop", "w") = 1 70 * score.fuzzyScore("Workshop", "ws") = 2 71 * score.fuzzyScore("Workshop", "wo") = 4 72 * score.fuzzyScore("Apache Software Foundation", "asf") = 3 73 * </pre> 74 * 75 * @param term a full term that should be matched against, must not be null 76 * @param query the query that will be matched against a term, must not be 77 * null 78 * @return result score 79 * @throws IllegalArgumentException if the term or query is {@code null} 80 */ 81 public Integer fuzzyScore(final CharSequence term, final CharSequence query) { 82 if (term == null || query == null) { 83 throw new IllegalArgumentException("CharSequences must not be null"); 84 } 85 86 // fuzzy logic is case insensitive. We normalize the Strings to lower 87 // case right from the start. Turning characters to lower case 88 // via Character.toLowerCase(char) is unfortunately insufficient 89 // as it does not accept a locale. 90 final String termLowerCase = term.toString().toLowerCase(locale); 91 final String queryLowerCase = query.toString().toLowerCase(locale); 92 93 // the resulting score 94 int score = 0; 95 96 // the position in the term which will be scanned next for potential 97 // query character matches 98 int termIndex = 0; 99 100 // index of the previously matched character in the term 101 int previousMatchingCharacterIndex = Integer.MIN_VALUE; 102 103 for (int queryIndex = 0; queryIndex < queryLowerCase.length(); queryIndex++) { 104 final char queryChar = queryLowerCase.charAt(queryIndex); 105 106 boolean termCharacterMatchFound = false; 107 for (; termIndex < termLowerCase.length() 108 && !termCharacterMatchFound; termIndex++) { 109 final char termChar = termLowerCase.charAt(termIndex); 110 111 if (queryChar == termChar) { 112 // simple character matches result in one point 113 score++; 114 115 // subsequent character matches further improve 116 // the score. 117 if (previousMatchingCharacterIndex + 1 == termIndex) { 118 score += 2; 119 } 120 121 previousMatchingCharacterIndex = termIndex; 122 123 // we can leave the nested loop. Every character in the 124 // query can match at most one character in the term. 125 termCharacterMatchFound = true; 126 } 127 } 128 } 129 130 return score; 131 } 132 133 /** 134 * Gets the locale. 135 * 136 * @return The locale 137 */ 138 public Locale getLocale() { 139 return locale; 140 } 141 142 }