Jak zaimplementować w pobliżu dopasowania ciągów w java?

Question

Witajcie inni programiści,

Chciałbym poprosić o pomoc w odniesieniu do bliskich meczów strun.

Obecnie mam program, który przechowuje ciągi opisu, użytkownicy mogą wyszukiwać opis, wpisując go całkowicie lub częściowo.

Chciałbym zaimplementować wyszukiwanie w pobliżu meczu. Na przykład rzeczywisty opis to "cześć świat", ale użytkownik błędnie wpisuje "cześć e-świat". Programy powinny zwracać użytkownikowi "Witaj świecie".

Próbowałem przeglądać wzorzec i dopasowania, aby go zaimplementować, ale wymaga to dopasowania do ciągów, dzięki czemu mój opis nie ma regularnego wzorca. Próbowałem również string.contains, ale i tak nie działa. Poniżej znajduje się część kodu, który próbowałem zaimplementować.

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

Czy inni programiści mogą mi w tym pomóc?

Answer 1

Można użyć LCS (Najdłuższy wspólny podciąg) zobaczyć te: 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(); 

    } 

} 

Inne rozwiązanie jest Aho–Corasick string matching algorithm zobaczyć: Fast algorithm for searching for substrings in a string

Answer 2

Levenstein Distance może być użyteczna dla tego problemu. Apache Commons Lang StringUtils ma implementację.
Również metoda difference z StringUtils może być interesująca, jeśli chcesz się dowiedzieć, jak różnią się łańcuchy.

Answer 3

Levenshtein distance jest w stanie zakwalifikować się różnicę między dwa ciągi

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