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

Question

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

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是最终的，所以不能扩展它）：

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;
  }
}

不过，我认为您想要做的是在尝试定义isSimiland方法之前定义similation。

Answer 2

有很多方法可以确定两个字符串的相似性。其中最常见的是编辑距离，Levenstein距离就是一个例子（有几种变体和其他方法——看看维基百科上的类别：字符串相似性度量）。

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

JAVA是一种编程语言JAVA是一种编程语言X

具有两个编辑距离：将"E"更改为"，并插入"X"。

小猫坐

具有3的编辑距离："k"到"s"，"e"到"i"，并插入"g"。

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

如果您正在对单个字符串进行多次比较，您可能会考虑构建一个Levenstein自动机，这是一种特殊类型的有限自动机，如果字符串在构建aotma自动机的字符串的某个编辑距离内，它就会接受字符串。

Answer 3

在java中没有set函数可以做到这一点，所以您必须自己构建一个。你解决这个问题的方法完全取决于你想去的相似性的限制。

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

创建某种比率以使失败或通过，正如我上面所说，这将取决于你希望它有多相似

如果您不了解如何在java中使用Strings，请浏览此处。

编辑：在另一个线程中，您可能会对其他不同的算法感兴趣，这里有一个更具体的例子，说明One正在使用