package com.ruzhoukj.sms.util; import java.util.*; import org.apache.commons.collections4.CollectionUtils; // 用于Jaccard算法(需添加依赖) // 注意:使用编辑距离和余弦相似度的实现如下,无需额外库。 public class MostSimilarStringFinder { /** * 在给定集合中查找与目标字符串最相似的一个元素 * @param input 目标字符串 * @param candidates 待比较的字符串集合 * @param algorithm 使用的算法("JACCARD", "LEVENSHTEIN", "COSINE") * @return 集合中最相似的字符串 */ public static String findMostSimilar(String input, List candidates, String algorithm) { if (candidates == null || candidates.isEmpty()) { return null; // 处理空集合 } String mostSimilar = null; double maxSimilarity = -1.0; // 相似度初始化为最小值 for (String candidate : candidates) { double currentSimilarity = 0.0; switch (algorithm.toUpperCase()) { case "JACCARD": currentSimilarity = calculateJaccardSimilarity(input, candidate); break; case "LEVENSHTEIN": currentSimilarity = calculateLevenshteinSimilarity(input, candidate); break; case "COSINE": currentSimilarity = calculateCosineSimilarity(input, candidate); break; default: throw new IllegalArgumentException("不支持的算法: " + algorithm); } // 更新找到的最相似字符串 if (currentSimilarity > maxSimilarity) { maxSimilarity = currentSimilarity; mostSimilar = candidate; } } System.out.println("使用 " + algorithm + " 算法,最高相似度为: " + maxSimilarity); return mostSimilar; } // 1. Jaccard 相似度计算 public static double calculateJaccardSimilarity(String strA, String strB) { // 将字符串转换为字符集合 Set setA = new HashSet<>(); for (char c : strA.toCharArray()) { setA.add(c); } Set setB = new HashSet<>(); for (char c : strB.toCharArray()) { setB.add(c); } // 计算交集和并集 Set intersection = new HashSet<>(setA); intersection.retainAll(setB); Set union = new HashSet<>(setA); union.addAll(setB); if (union.isEmpty()) { return 0.0; // 避免除以零 } return (double) intersection.size() / union.size(); } // 2. 基于编辑距离的相似度计算 (归一化到0-1) public static double calculateLevenshteinSimilarity(String s1, String s2) { int editDistance = computeLevenshteinDistance(s1, s2); int maxLength = Math.max(s1.length(), s2.length()); if (maxLength == 0) { return 1.0; // 两个空字符串定义为完全相似 } return 1.0 - ((double) editDistance / maxLength); // 将距离转换为相似度 } private static int computeLevenshteinDistance(String s1, String s2) { int len1 = s1.length(); int len2 = s2.length(); int[][] dp = new int[len1 + 1][len2 + 1]; for (int i = 0; i <= len1; i++) { for (int j = 0; j <= len2; j++) { if (i == 0) { dp[i][j] = j; } else if (j == 0) { dp[i][j] = i; } else { int cost = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? 0 : 1; dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + cost); } } } return dp[len1][len2]; } // 3. 余弦相似度计算 public static double calculateCosineSimilarity(String text1, String text2) { // 将字符串转换为词频向量 Map vector1 = getTermFrequency(text1); Map vector2 = getTermFrequency(text2); // 获取所有不重复的词汇 Set vocabulary = new HashSet<>(); vocabulary.addAll(vector1.keySet()); vocabulary.addAll(vector2.keySet()); // 计算点积 double dotProduct = 0.0; for (String word : vocabulary) { int freq1 = vector1.getOrDefault(word, 0); int freq2 = vector2.getOrDefault(word, 0); dotProduct += freq1 * freq2; } // 计算模长 double normA = calculateNorm(vector1); double normB = calculateNorm(vector2); if (normA == 0 || normB == 0) { return 0.0; // 避免除以零 } return dotProduct / (normA * normB); } // 辅助方法:计算词频 private static Map getTermFrequency(String text) { // 简单分词:转为小写,按非字母数字分割 String[] words = text.toLowerCase().split("\\W+"); Map freqMap = new HashMap<>(); for (String word : words) { if (!word.isEmpty()) { freqMap.put(word, freqMap.getOrDefault(word, 0) + 1); } } return freqMap; } // 辅助方法:计算向量的模长(欧几里得范数) private static double calculateNorm(Map vector) { double sumSquares = 0.0; for (int freq : vector.values()) { sumSquares += Math.pow(freq, 2); } return Math.sqrt(sumSquares); } // 测试示例 public static void main(String[] args) { List stringCollection = Arrays.asList( "Where is the restroom?", "Can you tell me where the bathroom is?", "How do I get to the nearest toilet?", "Where is the front desk?" ); String inputString = "Can you help me find the bathroom?"; // 使用不同的算法进行匹配 String resultByJaccard = findMostSimilar(inputString, stringCollection, "JACCARD"); System.out.println("Jaccard 最相似: " + resultByJaccard + "\n"); String resultByLevenshtein = findMostSimilar(inputString, stringCollection, "LEVENSHTEIN"); System.out.println("编辑距离最相似: " + resultByLevenshtein + "\n"); String resultByCosine = findMostSimilar(inputString, stringCollection, "COSINE"); System.out.println("余弦最相似: " + resultByCosine); } }