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.Locale; 020 021/** 022 * A matching algorithm that is similar to the searching algorithms implemented in editors such 023 * as Sublime Text, TextMate, Atom and others. 024 * 025 * <p> 026 * One point is given for every matched character. Subsequent matches yield two bonus points. A higher score 027 * indicates a higher similarity. 028 * </p> 029 * 030 * <p> 031 * This code has been adapted from Apache Commons Lang 3.3. 032 * </p> 033 * 034 * @since 1.0 035 */ 036public class FuzzyScore { 037 038 /** 039 * Locale used to change the case of text. 040 */ 041 private final Locale locale; 042 043 044 /** 045 * This returns a {@link Locale}-specific {@link FuzzyScore}. 046 * 047 * @param locale The string matching logic is case insensitive. 048 A {@link Locale} is necessary to normalize both Strings to lower case. 049 * @throws IllegalArgumentException 050 * This is thrown if the {@link Locale} parameter is {@code null}. 051 */ 052 public FuzzyScore(final Locale locale) { 053 if (locale == null) { 054 throw new IllegalArgumentException("Locale must not be null"); 055 } 056 this.locale = locale; 057 } 058 059 /** 060 * Find the Fuzzy Score which indicates the similarity score between two 061 * Strings. 062 * 063 * <pre> 064 * score.fuzzyScore(null, null) = IllegalArgumentException 065 * score.fuzzyScore("not null", null) = IllegalArgumentException 066 * score.fuzzyScore(null, "not null") = IllegalArgumentException 067 * score.fuzzyScore("", "") = 0 068 * score.fuzzyScore("Workshop", "b") = 0 069 * score.fuzzyScore("Room", "o") = 1 070 * score.fuzzyScore("Workshop", "w") = 1 071 * score.fuzzyScore("Workshop", "ws") = 2 072 * score.fuzzyScore("Workshop", "wo") = 4 073 * score.fuzzyScore("Apache Software Foundation", "asf") = 3 074 * </pre> 075 * 076 * @param term a full term that should be matched against, must not be null 077 * @param query the query that will be matched against a term, must not be 078 * null 079 * @return result score 080 * @throws IllegalArgumentException if the term or query is {@code null} 081 */ 082 public Integer fuzzyScore(final CharSequence term, final CharSequence query) { 083 if (term == null || query == null) { 084 throw new IllegalArgumentException("CharSequences must not be null"); 085 } 086 087 // fuzzy logic is case insensitive. We normalize the Strings to lower 088 // case right from the start. Turning characters to lower case 089 // via Character.toLowerCase(char) is unfortunately insufficient 090 // as it does not accept a locale. 091 final String termLowerCase = term.toString().toLowerCase(locale); 092 final String queryLowerCase = query.toString().toLowerCase(locale); 093 094 // the resulting score 095 int score = 0; 096 097 // the position in the term which will be scanned next for potential 098 // query character matches 099 int termIndex = 0; 100 101 // index of the previously matched character in the term 102 int previousMatchingCharacterIndex = Integer.MIN_VALUE; 103 104 for (int queryIndex = 0; queryIndex < queryLowerCase.length(); queryIndex++) { 105 final char queryChar = queryLowerCase.charAt(queryIndex); 106 107 boolean termCharacterMatchFound = false; 108 for (; termIndex < termLowerCase.length() 109 && !termCharacterMatchFound; termIndex++) { 110 final char termChar = termLowerCase.charAt(termIndex); 111 112 if (queryChar == termChar) { 113 // simple character matches result in one point 114 score++; 115 116 // subsequent character matches further improve 117 // the score. 118 if (previousMatchingCharacterIndex + 1 == termIndex) { 119 score += 2; 120 } 121 122 previousMatchingCharacterIndex = termIndex; 123 124 // we can leave the nested loop. Every character in the 125 // query can match at most one character in the term. 126 termCharacterMatchFound = true; 127 } 128 } 129 } 130 131 return score; 132 } 133 134 /** 135 * Gets the locale. 136 * 137 * @return The locale 138 */ 139 public Locale getLocale() { 140 return locale; 141 } 142 143}