檢查一個字符串是否與另一個字符串相似

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自動機與...一起構建。