如何在java中實現近乎匹配的字符串？

Question

你好同胞程序員，

我想問一些關於字符串匹配的問題。

目前，我有一個存儲描述字符串的程序，用戶可以通過完全或部分地鍵入它來搜索描述。

我想實施一個近似匹配搜索。例如，實際的描述是「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)); 
     } 
    } 

難道其他程序員可以幫助我嗎？

Answer 1

您可以使用LCS（最長公共子序列）看到這些： http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

public class LCS { 

    public static void main(String[] args) { 
     String x = StdIn.readString(); 
     String y = StdIn.readString(); 
     int M = x.length(); 
     int N = y.length(); 

     // opt[i][j] = length of LCS of x[i..M] and y[j..N] 
     int[][] opt = new int[M+1][N+1]; 

     // compute length of LCS and all subproblems via dynamic programming 
     for (int i = M-1; i >= 0; i--) { 
      for (int j = N-1; j >= 0; j--) { 
       if (x.charAt(i) == y.charAt(j)) 
        opt[i][j] = opt[i+1][j+1] + 1; 
       else 
        opt[i][j] = Math.max(opt[i+1][j], opt[i][j+1]); 
      } 
     } 

     // recover LCS itself and print it to standard output 
     int i = 0, j = 0; 
     while(i < M && j < N) { 
      if (x.charAt(i) == y.charAt(j)) { 
       System.out.print(x.charAt(i)); 
       i++; 
       j++; 
      } 
      else if (opt[i+1][j] >= opt[i][j+1]) i++; 
      else         j++; 
     } 
     System.out.println(); 

    } 

} 

其他解決方案Aho–Corasick string matching algorithm看到這一點： Fast algorithm for searching for substrings in a string

Answer 2

的Levenstein Distance可能對這個問題很有用。 Apache Commons Lang StringUtils有一個實現它。
此外，如果您想了解字符串的不同方式，則StringUtils中的difference方法可能會很有趣。

Answer 3

的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()]; 
    } 
}