各位程序员大家好,
我想就字符串的近似匹配寻求一些帮助。
目前,我有一个存储描述字符串的程序,用户可以通过完整或部分输入来搜索描述。
我想实现近似匹配搜索。例如,实际描述是“hello world”,但用户错误地输入了搜索“hello eorld”。程序应该能够向用户返回“hello world”。
我已经尝试查看模式和匹配来实现它,但它需要一个正则表达式来匹配字符串,因此我的描述没有常规模式。我也尝试过 string.contains,但它似乎也不起作用。以下是我尝试实现的部分代码。
ArrayList <String> list = new ArrayList<String>();
list.add("hello world");
list.add("go jogging at london");
list.add("go fly kite");
Scanner scan = new Scanner(System.in);
for(int i = 0; i < list.size(); i++){
if(list.get(i).contains(scan.next())) {
System.out.println(list.get(i));
}
}
其他程序员可以帮我解决这个问题吗??
最佳答案
Levenshtein distance能够限定两个字符串之间的差异
这是一个实现 taken form here :
public class LevenshteinDistance {
private static int minimum(int a, int b, int c) {
return Math.min(Math.min(a, b), c);
}
public static int computeLevenshteinDistance(
CharSequence str1,
CharSequence str2 )
{
int[][] distance = new int[str1.length() + 1][str2.length() + 1];
for (int i = 0; i <= str1.length(); i++)
distance[i][0] = i;
for (int j = 1; j <= str2.length(); j++)
distance[0][j] = j;
for (int i = 1; i <= str1.length(); i++)
for (int j = 1; j <= str2.length(); j++)
distance[i][j] =
minimum(
distance[i - 1][j] + 1,
distance[i][j - 1] + 1,
distance[i - 1][j - 1] +
((str1.charAt(i - 1) == str2.charAt(j - 1)) ? 0 : 1));
return distance[str1.length()][str2.length()];
}
}
关于java - 如何在java中实现字符串的近似匹配?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13196964/