找到最相似值的有效方法
Efficient Way to find most similar value
我有一个值,例如 Color,以及一个字符串列表:{Colour,Color,Main Color, Main Colour, Theme, Brand, Subject ..... etc}
我想得到最相似的字符串,除了搜索到的字符串本身。在此示例中,期望获得颜色。 (不是颜色)
我正在整理清单
我正在使用以下规则并对规则进行排名:
- 过滤相同的值
- 检查大小写
- 删除空格。 trim
- 使用 Levenshtein 距离
- 字符串顺序:主色 = 主色
- 检查首字母缩略词:HP - Hewlett Packard
浏览一份包含 1000 名相关候选人的名单需要花费大量时间。而且我还有很多候选人要检查
还有其他有效的方法吗?
原码:
public static List findSimilarity(String word, List candidates) {
List recommendations = new ArrayList();
if (!word.equals("")) {
for (String candidate : candidates) {
if (!word.equals(candidate)) { //1. same token , lower/upper cases , ignore white spaces
if (StringUtils.deleteWhitespace(word).equalsIgnoreCase(StringUtils.deleteWhitespace(candidate))) {
recommendations.add(candidate);
}
//2. same tokens diff order
else if (candidate.split(" ").length == word.split(" ").length) {
String[] candidatearr = candidate.split(" ");
String[] wordarr = word.split(" ");
boolean status = true;
SortIgnoreCase icc = new SortIgnoreCase();
Arrays.sort(candidatearr, icc);
Arrays.sort(wordarr, icc);
for (int i = 0; i < candidatearr.length; i++) {
if (!(candidatearr[i] == null ? wordarr[i] == null : wordarr[i].equalsIgnoreCase(candidatearr[i])))
status = false;
}
if (status) {
recommendations.add(candidate);
}
}
}
}
//3. distance between words
if (recommendations.size() == 0) {
for (String candidate : candidates) {
if (!word.equals(candidate)) {
String[] candidatearr = candidate.split(" ");
String[] wordarr = word.split(" ");
//check for acronym
if ((wordarr.length == 1 && candidatearr.length > 1) || (wordarr.length > 1 && candidatearr.length == 1)) {
String acronym = "";
if (wordarr.length > candidatearr.length) {
for (String tmp : wordarr) {
if (!tmp.equals("")) {
acronym = acronym + tmp.substring(0, 1);
}
}
if (acronym.equalsIgnoreCase(candidatearr[0])) {
recommendations.add(candidate);
}
} else {
for (String tmp : candidatearr) {
if (!tmp.equals("")) {
acronym = acronym + tmp.substring(0, 1);
}
}
if (acronym.equalsIgnoreCase(wordarr[0])) {
recommendations.add(candidate);
}
}
}
}
}
}
if (recommendations.size() == 0) {
for (String candidate : candidates) {
if (!word.equals(candidate)) {
int dist = 0;
String check = "";
if (word.length() > candidate.length()) {
check = candidate;
} else {
check = word;
}
if (check.length() <= 3) {
dist = 0;
} else if (check.length() > 3 && check.length() <= 5) {
dist = 1;
} else if (check.length() > 5) {
dist = 2;
}
if (StringUtils.getLevenshteinDistance(word, candidate) <= dist) {
//if(Levenshtein.distance(word,candidate) <= dist){
recommendations.add(candidate);
}
}
}
}
if (recommendations.size() == 0) {
for (String candidate : candidates) {
if (!word.equals(candidate)) {
String[] candidatearr = candidate.split(" ");
String[] wordarr = word.split(" ");
for (String cand : candidatearr) {
for (String wor : wordarr) {
if (cand.equals(wor) && cand.length() > 4) {
recommendations.add(candidate);
}
}
}
}
}//for
if (recommendations.size() > 4) {
recommendations.clear();
}
}
//4. low priority - starts with
if (recommendations.size() == 0) {
for (String candidate : candidates) {
if (!word.equals(candidate)) {
if (candidate.startsWith(word) || word.startsWith(candidate)) {
recommendations.add(candidate);
}
}
}
if (recommendations.size() > 4) {
recommendations.clear();
}
}
//5. low priority - contain word
if (recommendations.size() == 0) {
for (String candidate : candidates) {
if (!word.equals(candidate)) {
if (candidate.contains(word) || word.contains(candidate)) {
recommendations.add(candidate);
}
}
}
if (recommendations.size() > 4) {
recommendations.clear();
}
}
}
return recommendations;
}
谢谢,
M.
已编辑
我将 Bohemian 给出的答案封装到您的原始代码的上下文中,以便您更好地理解。
行 .map(term -> Arrays.stream(term.split(" ")).sorted().collect(Collectors.joining(" ")))
拆分 multi-word 个术语,排序并再次合并以消除相同单词的排列。这是对 "main color" 和 "color main".
等术语的置换平等挑战的回答
但是,在此问题的上下文中捕捉任务的所有业务需求没有意义。通过这个答案,您已经大致了解了解决方案。效率问题得到解决。您的管道中可能需要更多阶段,但那是另一回事。该方法的优势在于所有阶段都是分离的,因此您可以针对每个阶段独立提问和寻求帮助。
public static String findSimilarity(String word, List<String> candidatesList) {
// Populating the set with distinct values of the input terms
Set<String> candidates = candidatesList.stream()
.map(String::toLowerCase)
.map(term -> Arrays.stream(term.split(" ")).sorted().collect(Collectors.joining(" "))) // eliminates permutations
.collect(Collectors.toSet());
Map<String, Integer> cache = new ConcurrentHashMap<>();
return candidates.parallelStream()
.map(String::trim)
// add more mappers if needed
.filter(s -> !s.equalsIgnoreCase(word))
// add more filters if needed
.min((a, b) -> Integer.compare(
cache.computeIfAbsent(a, k -> getLevenshteinDistance(word, k)),
cache.computeIfAbsent(b, k -> getLevenshteinDistance(word, k))))
.get(); // get the closest match
}
您的问题是时间复杂度之一。 Collections.sort() 是一个 O(n log n) 操作,这是调用比较方法的次数。问题是 Levenshtein 是一个 "expensive" 计算。
您可以找到一种方法来提高排序性能,方法是为每个项目精确计算一次,使 Levenshtein 计算成为 O(n) 操作,然后根据存储的计算距离进行排序。
我做了一个测试,使用各种列表大小对随机整数列表进行排序,compare()
的实际调用次数非常接近 n log2 n,所以对于1000个左右String的列表,会快10倍左右,因为log2(1000)大约是10.
您可以通过 不排序 来进一步提高性能,而只是获取指定相同比较器的 最小值 项。
另一个改进是避免 distinct()
调用(这是相对昂贵的),通过使用 Set(强制唯一性)来保存候选人。
如果可以,用 已经 训练和小写的值填充候选,这样你就可以避免每隔 运行 修剪和小写和小写。做同样的输入,所以你可以使用 equals()
而不是较慢的 equalsIgnoreCase()
.
这是一种方法:
import static org.apache.commons.lang.StringUtils.getLevenshteinDistance;
String search; // your input
Set<String> candidates = new HashSet<>(); // populate this with lots of values
Map<String, Integer> cache = new ConcurrentHashMap<>();
String closest = candidates.parallelStream()
.map(String::trim)
.filter(s -> !s.equalsIgnoreCase(search))
.min((a, b) -> Integer.compare(
cache.computeIfAbsent(a, k -> getLevenshteinDistance(search, k)),
cache.computeIfAbsent(b, k -> getLevenshteinDistance(search, k))))
.get();
此代码对 1000 个随机候选人执行大约 50 毫秒,对 100 万个候选人执行大约 1 秒。
我有一个值,例如 Color,以及一个字符串列表:{Colour,Color,Main Color, Main Colour, Theme, Brand, Subject ..... etc}
我想得到最相似的字符串,除了搜索到的字符串本身。在此示例中,期望获得颜色。 (不是颜色)
我正在整理清单 我正在使用以下规则并对规则进行排名:
- 过滤相同的值
- 检查大小写
- 删除空格。 trim
- 使用 Levenshtein 距离
- 字符串顺序:主色 = 主色
- 检查首字母缩略词:HP - Hewlett Packard
浏览一份包含 1000 名相关候选人的名单需要花费大量时间。而且我还有很多候选人要检查
还有其他有效的方法吗?
原码:
public static List findSimilarity(String word, List candidates) {
List recommendations = new ArrayList();
if (!word.equals("")) {
for (String candidate : candidates) {
if (!word.equals(candidate)) { //1. same token , lower/upper cases , ignore white spaces
if (StringUtils.deleteWhitespace(word).equalsIgnoreCase(StringUtils.deleteWhitespace(candidate))) {
recommendations.add(candidate);
}
//2. same tokens diff order
else if (candidate.split(" ").length == word.split(" ").length) {
String[] candidatearr = candidate.split(" ");
String[] wordarr = word.split(" ");
boolean status = true;
SortIgnoreCase icc = new SortIgnoreCase();
Arrays.sort(candidatearr, icc);
Arrays.sort(wordarr, icc);
for (int i = 0; i < candidatearr.length; i++) {
if (!(candidatearr[i] == null ? wordarr[i] == null : wordarr[i].equalsIgnoreCase(candidatearr[i])))
status = false;
}
if (status) {
recommendations.add(candidate);
}
}
}
}
//3. distance between words
if (recommendations.size() == 0) {
for (String candidate : candidates) {
if (!word.equals(candidate)) {
String[] candidatearr = candidate.split(" ");
String[] wordarr = word.split(" ");
//check for acronym
if ((wordarr.length == 1 && candidatearr.length > 1) || (wordarr.length > 1 && candidatearr.length == 1)) {
String acronym = "";
if (wordarr.length > candidatearr.length) {
for (String tmp : wordarr) {
if (!tmp.equals("")) {
acronym = acronym + tmp.substring(0, 1);
}
}
if (acronym.equalsIgnoreCase(candidatearr[0])) {
recommendations.add(candidate);
}
} else {
for (String tmp : candidatearr) {
if (!tmp.equals("")) {
acronym = acronym + tmp.substring(0, 1);
}
}
if (acronym.equalsIgnoreCase(wordarr[0])) {
recommendations.add(candidate);
}
}
}
}
}
}
if (recommendations.size() == 0) {
for (String candidate : candidates) {
if (!word.equals(candidate)) {
int dist = 0;
String check = "";
if (word.length() > candidate.length()) {
check = candidate;
} else {
check = word;
}
if (check.length() <= 3) {
dist = 0;
} else if (check.length() > 3 && check.length() <= 5) {
dist = 1;
} else if (check.length() > 5) {
dist = 2;
}
if (StringUtils.getLevenshteinDistance(word, candidate) <= dist) {
//if(Levenshtein.distance(word,candidate) <= dist){
recommendations.add(candidate);
}
}
}
}
if (recommendations.size() == 0) {
for (String candidate : candidates) {
if (!word.equals(candidate)) {
String[] candidatearr = candidate.split(" ");
String[] wordarr = word.split(" ");
for (String cand : candidatearr) {
for (String wor : wordarr) {
if (cand.equals(wor) && cand.length() > 4) {
recommendations.add(candidate);
}
}
}
}
}//for
if (recommendations.size() > 4) {
recommendations.clear();
}
}
//4. low priority - starts with
if (recommendations.size() == 0) {
for (String candidate : candidates) {
if (!word.equals(candidate)) {
if (candidate.startsWith(word) || word.startsWith(candidate)) {
recommendations.add(candidate);
}
}
}
if (recommendations.size() > 4) {
recommendations.clear();
}
}
//5. low priority - contain word
if (recommendations.size() == 0) {
for (String candidate : candidates) {
if (!word.equals(candidate)) {
if (candidate.contains(word) || word.contains(candidate)) {
recommendations.add(candidate);
}
}
}
if (recommendations.size() > 4) {
recommendations.clear();
}
}
}
return recommendations;
}
谢谢, M.
已编辑
我将 Bohemian 给出的答案封装到您的原始代码的上下文中,以便您更好地理解。
行 .map(term -> Arrays.stream(term.split(" ")).sorted().collect(Collectors.joining(" ")))
拆分 multi-word 个术语,排序并再次合并以消除相同单词的排列。这是对 "main color" 和 "color main".
但是,在此问题的上下文中捕捉任务的所有业务需求没有意义。通过这个答案,您已经大致了解了解决方案。效率问题得到解决。您的管道中可能需要更多阶段,但那是另一回事。该方法的优势在于所有阶段都是分离的,因此您可以针对每个阶段独立提问和寻求帮助。
public static String findSimilarity(String word, List<String> candidatesList) {
// Populating the set with distinct values of the input terms
Set<String> candidates = candidatesList.stream()
.map(String::toLowerCase)
.map(term -> Arrays.stream(term.split(" ")).sorted().collect(Collectors.joining(" "))) // eliminates permutations
.collect(Collectors.toSet());
Map<String, Integer> cache = new ConcurrentHashMap<>();
return candidates.parallelStream()
.map(String::trim)
// add more mappers if needed
.filter(s -> !s.equalsIgnoreCase(word))
// add more filters if needed
.min((a, b) -> Integer.compare(
cache.computeIfAbsent(a, k -> getLevenshteinDistance(word, k)),
cache.computeIfAbsent(b, k -> getLevenshteinDistance(word, k))))
.get(); // get the closest match
}
您的问题是时间复杂度之一。 Collections.sort() 是一个 O(n log n) 操作,这是调用比较方法的次数。问题是 Levenshtein 是一个 "expensive" 计算。
您可以找到一种方法来提高排序性能,方法是为每个项目精确计算一次,使 Levenshtein 计算成为 O(n) 操作,然后根据存储的计算距离进行排序。
我做了一个测试,使用各种列表大小对随机整数列表进行排序,compare()
的实际调用次数非常接近 n log2 n,所以对于1000个左右String的列表,会快10倍左右,因为log2(1000)大约是10.
您可以通过 不排序 来进一步提高性能,而只是获取指定相同比较器的 最小值 项。
另一个改进是避免 distinct()
调用(这是相对昂贵的),通过使用 Set(强制唯一性)来保存候选人。
如果可以,用 已经 训练和小写的值填充候选,这样你就可以避免每隔 运行 修剪和小写和小写。做同样的输入,所以你可以使用 equals()
而不是较慢的 equalsIgnoreCase()
.
这是一种方法:
import static org.apache.commons.lang.StringUtils.getLevenshteinDistance;
String search; // your input
Set<String> candidates = new HashSet<>(); // populate this with lots of values
Map<String, Integer> cache = new ConcurrentHashMap<>();
String closest = candidates.parallelStream()
.map(String::trim)
.filter(s -> !s.equalsIgnoreCase(search))
.min((a, b) -> Integer.compare(
cache.computeIfAbsent(a, k -> getLevenshteinDistance(search, k)),
cache.computeIfAbsent(b, k -> getLevenshteinDistance(search, k))))
.get();
此代码对 1000 个随机候选人执行大约 50 毫秒,对 100 万个候选人执行大约 1 秒。