come implementare vicino alle partite di stringhe in java?

Question

Ciao colleghi programmatori,

Vorrei chiedere aiuto per quanto riguarda le partite vicine di archi.

Attualmente, ho un programma che memorizza stringhe di descrizione, gli utenti possono cercare la descrizione digitandola completamente o parzialmente.

Vorrei implementare una ricerca per corrispondenza ravvicinata. Ad esempio la descrizione effettiva è "ciao mondo" ma l'utente erroneamente inserisce una ricerca "ciao mondo". I programmi dovrebbero essere in grado di restituire "Ciao mondo" all'utente.

Ho provato a cercare pattern e corrispondenze per implementarlo, ma richiede una regex per far corrispondere le stringhe, per cui la mia descrizione non ha uno schema regolare. Ho anche provato string.contains, ma non sembra funzionare neanche. Di seguito è riportato parte del codice che ho provato ad implementare.

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

I programmatori possono aiutarmi con questo ??

Answer 1

È possibile utilizzare LCS (Longest Common Subsequence) vedi questi: 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(); 

    } 

} 

altra soluzione è Aho–Corasick string matching algorithm vedono questo: Fast algorithm for searching for substrings in a string

Answer 2

Il Levenstein Distance potrebbe essere utile per questo problema. Apache Commons Lang StringUtils ha un'implementazione per questo.
Inoltre, il metodo difference da StringUtils potrebbe essere interessante, se si desidera scoprire come le stringhe differiscono.

Answer 3

Il Levenshtein distance è in grado di qualificare la differenza tra due stringhe

Ecco un'implementazione 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()]; 
    } 
}