检查一个字符串是否与另一个字符串相似

Question

我已经做了一些研究，并且发现主题将检查字符串是否是字符串中的子字符串，并选择与指定字符串最接近的字符串，但是如何我检查一个字符串是否与另一个字符串相似并提供true/false响应？即：

String 1: JAVA IS A PROGRAMMING LANGUAGE 
String 2: JAVA IS A PROGRAMMING LANGUAG X 

这将返回一个 “真”

String 1: JAVA IS A PROGRAMMING LANGUAGE 
String 2: I ATE THE CAKE 

这将返回 “假”

感谢。

Answer 1

你在问什么是有点不平凡的。你的答案的核心是另一个问题：

你如何定义“类似”？

您需要指定一些规则来管理这个规则，以及一些与规则相关的阈值，我不确定你甚至已经考虑过了。例如，下面是一个简单的解决方案（在我的漂亮或效率上简单易行，我只是把它们放在一起非常快，所以代码可能有点凌乱......我更关心的是回答问题...你可以自己重构它，如果你想）。有一个％75的阈值，在这个阈值中，我检查了较小字符串中的字符数是否与较大字符串的％75匹配（注意：java.lang.String是final的，所以不能扩展它） ：

import java.util.HashMap; 
import java.util.Iterator; 
import java.util.Map; 
import java.util.Set; 
import java.util.logging.Level; 
import java.util.logging.Logger; 

public class MyString{ 
    private static final float THRESHOLD = (float) 0.75; 

    private final Logger logger = Logger.getLogger(MyString.class.getName()); 

    private String str; 
    private Map <Character, Integer> strMap; 

    public MyString(String str){ //java.lang.String is final... 
    this.str = str; 
    this.strMap = this.generateCharMap(str); 
    } 

    public void executeTestForSophiaZhuang(){ 
    { 
     MyString str1 = new MyString("JAVA IS A PROGRAMMING LANGUAGE"); 
     String str2 = "JAVA IS A PROGRAMMING LANGUAG X"; 
     logger.log(Level.INFO, "String {0}.isSimilar({1}) == {2}", new Object[]{ 
     str1.toString(), str2, str1.isSimilar(str2)}); 
    } 
    { 
     MyString str1 = new MyString("JAVA IS A PROGRAMMING LANGUAG X"); 
     String str2 = "JAVA IS A PROGRAMMING LANGUAGE"; 
     logger.log(Level.INFO, "String {0}.isSimilar({1}) == {2}", new Object[]{ 
     str1.toString(), str2, str1.isSimilar(str2)}); 
    } 
    { 
     MyString str1 = new MyString("JAVA IS A PROGRAMMING LANGUAGE"); 
     String str2 = "I ATE THE CAKE"; 
     logger.log(Level.INFO, "String {0}.isSimilar({1}) == {2}", new Object[]{ 
     str1.toString(), str2, str1.isSimilar(str2)}); 
    } 
    { 
     MyString str1 = new MyString("I ATE THE CAKE"); 
     String str2 = "JAVA IS A PROGRAMMING LANGUAGE"; 
     logger.log(Level.INFO, "String {0}.isSimilar({1}) == {2}", new Object[]{ 
     str1.toString(), str2, str1.isSimilar(str2)}); 
    } 
    } 

    @Override 
    public String toString(){ 
    return this.str; 
    } 

    private Map <Character, Integer> generateCharMap(String str){ 
    Map <Character, Integer> map = new HashMap<>(); 
    Integer currentChar; 
    for(char c: str.toCharArray()){ 
     currentChar = map.get(c); 
     if(currentChar == null){ 
     map.put(c, 1); 
     } else { 
     map.put(c, currentChar+1); 
     } 
    } 
    return map; 
    } 

    public boolean isSimilar(String compareStr){ 
    Map <Character, Integer> compareStrMap = this.generateCharMap(compareStr); 
    Set <Character> charSet = compareStrMap.keySet(); 
    int similarChars = 0; 
    int totalStrChars = this.str.length(); 
    float thisThreshold; 

    if(totalStrChars < compareStrMap.size()){ 
     totalStrChars = compareStr.length(); 
    } 

    Iterator it = charSet.iterator(); 
    char currentChar; 
    Integer currentCountStrMap; 
    Integer currentCountCompareStrMap; 
    while(it.hasNext()){ 
     currentChar = (Character)it.next(); 
     currentCountStrMap = strMap.get(currentChar); 
     if(currentCountStrMap != null){ 
     currentCountCompareStrMap = compareStrMap.get(currentChar); 
     if (currentCountCompareStrMap >= currentCountStrMap){ 
      similarChars += currentCountStrMap; 
     } else { 
      similarChars += currentCountCompareStrMap; 
     } 
     } 
    } 

    thisThreshold = ((float) similarChars)/((float) totalStrChars); 
    Logger.getLogger(MyString.class.getName()).log(Level.INFO, "similarChars: {0}, totalStrChars: {1}, thisThreshold: {2}", new Object[]{similarChars, totalStrChars, thisThreshold}); 
    if(thisThreshold > THRESHOLD){ 
     return true; 
    } 
    return false; 
    } 
} 

我想你会想要做的是定义类似之前，你尝试定义isSimilar方法，虽然。

Answer 2

在java中没有这样做的设置函数，所以你将不得不自己构建一个函数。你解决这个问题的方式完全取决于你想要达到的相似之处的限制。

我会采取的方法是利用java提供的分割函数，以便可以迭代句子中的每个单词。然后，简单地将每个字符与另一个句子中的每个单词进行比较。

创建某种比例来使失败或通过，这将如我上面所说的那样取决于你想要的相似程度。如果你不懂如何在java中使用Strings，请浏览Here。

编辑：也有不同的算法，你可能会感兴趣提到in another thread，这里是One in use

Answer 3

一个更具体的例子有很多方法来确定两个字符串的相似性。其中最常见的是edit distance，其中Levenshtein distance是一个例子（并且有几种变化和其他方法 - 请浏览维基百科上的Category:String similarity measures）。

Levenshtein距离计算将一个字符串更改为另一个字符串所需的更改次数。例如：

 
JAVA IS A PROGRAMMING LANGUAGE 
JAVA IS A PROGRAMMING LANGUAG X 

编辑距离为2：'E'变为''并且'X'被插入。

 
kitten 
sitting 

编辑距离为3：'k'为's'，'e'为'i'并插入'g'。

然后，您将在编写的函数将可能会有一个boolean similar(int threshold, String foo, String bar)的原型，其中阈值是允许的最大改变数目，而foo和bar是您正在比较的两个字符串。

如果你正在做很多针对单个的字符串比较，你可能会考虑构建一个Levenshtein automaton这是接受一个字符串的一种特殊类型有限自动机的，如果它是字符串的一些编辑距离内aotma自动机与...一起构建。