algoritmo dinamico per il testo di correzione automatica

Question

Sto scrivendo un programma di correzione automatica che utilizza il levenshtein distance per correggere una frase di non più di 64 charcters a base di un dizionario specifico che contiene 8000 parole.

Il dizionario contiene in ogni riga della coppia "word_frequency Parola". Io uso gli oggetti DictionarEntry per memorizzare quelle coppie. Classe Dictionar Entry ha due campi: valore: memorizza la stringa parola freq: memorizza la frequenza di Il dizionario viene memorizzata come LinkedList. Ho letto da stdin la stringa di 64 caratteri. prima di elaborarlo rimuovo tutti gli spazi. "Coo lweather" -> "Coolweather" Ho notato che calcola la distanza di levenshtein per ogni prefisso, nell'ultima riga della matrice calcolata dalla dinamica di levenshtein (vedi esempio di wikipedia) restituisce le distanze per tutti i prefissi .

Funzione lev restituisce un vettore contenente il l.distance dalla seconda stringa di parametri a tutti i prefissi del primo, compreso se stesso.

Il mio problema è che devo rispettare alcune regole aggiuntive: min Lev. distanza -> numero minimo di parole -> somma massima frequenza -> minimo lessicografico Questo sarebbe spiegato come se il numero totale di soluzioni sia maggiore di 1 prendiamo quelle con il numero minimo di parole. Se ce ne sono ancora più di uno seguiamo l'elenco delle regole.

La dinamica che sto applicando è qualcosa di simile a una dinamica dello zaino. Non so come implementare il numero minimo di parole regola (quella massima frequenza è molto simile)

Ecco quello che ho provato finora di ingresso/uscita esempi in cui questo non riesce: "mal di riservato" la risposta dovrebbe essere così riservata, quello che ottengo è in realtà così servito ancora Ho scelto questo metodo perché è più efficiente. Il limite di tempo è di 2 secondi per Java.

Aggiornamento

: 7 aprile. Ho trovato la soluzione al mio problema, tuttavia il tempo di CPU è troppo grande, quindi ho bisogno di ottimizzarlo. Non dovrebbe essere superiore a 2000 ms e attualmente si trova a circa 6000 ms. Quindi ora il mio obiettivo principale diventa ottimizzarlo.

public static String guess (String input, LinkedList<DictionarEntry> Dictionar){ 
     String curent = new String(); 
     String output = new String(); 

     int costMatrix[][][] = new int [input.length()][8000][input.length()];   
    int index[] = new int[128]; 
    int prev[]= new int[128]; 
     int d[]=new int [128]; 
     int freq[]= new int[128]; 
     int wcount[]=new int[128]; 
     String values[] = new String[128]; 
     for (int i=0 ; i < 128 ; i++){ 
       d[i]=127; 
       freq[i]=0; 
       wcount[i]=1; 
       values[i]=""; 
     }   
    d[0]=0; 
    freq[0]=0; 

     for (int i = 0 ; i <input.length(); ++i){ 

      curent=input.subSequence(i, input.length()).toString(); 
      long start =System.currentTimeMillis(); 
       for (int j = 0 ; j < Dictionar.size();++j){ 

        costMatrix[i][j]=lev(Dictionar.get(j).value,curent); 
        for(int k=1;k<costMatrix[i][j].length;++k){ 

         if(d[i]+costMatrix[i][j][k]<d[i+k]){ 
          d[i+k]= d[i]+costMatrix[i][j][k]; 
           values[i+k]=values[i]+Dictionar.get(j).value; 
           freq[i+k]=freq[i]+Dictionar.get(j).freq; 
           index[i+k]=j; 
           prev[i+k]=i; 
           wcount[i+k]=wcount[i]+1; 
         } 
         else if ((d[i]+costMatrix[i][j][k])==d[i+k]) 
             if((wcount[i]+1) <wcount[i+k]){ 
           values[i+k]=values[i]+Dictionar.get(j).value; 
           freq[i+k]=freq[i]+Dictionar.get(j).freq; 
           index[i+k]=j; 
           prev[i+k]=i; 
           wcount[i+k]=wcount[i]+1;  
             } 
             else if ((wcount[i]+1)==wcount[i+k]) 
             if((freq[i]+Dictionar.get(j).freq)>freq[i+k]){ 
              values[i+k]=values[i]+Dictionar.get(j).value; 
              freq[i+k]=freq[i]+Dictionar.get(j).freq; 
              index[i+k]=j; 
              prev[i+k]=i; 
              wcount[i+k]=wcount[i]+1;  
             } 
             else if ((freq[i]+Dictionar.get(j).freq)==freq[i+k]){ 
              if((values[i]+Dictionar.get(j).value).compareTo(values[i+k])>0){ 
               values[i+k]=values[i]+Dictionar.get(j).value; 
               freq[i+k]=freq[i]+Dictionar.get(j).freq; 
               index[i+k]=j; 
               prev[i+k]=i; 
               wcount[i+k]=wcount[i]+1; 
              } 
             } 
        }  
       } 
       long finished =System.currentTimeMillis(); 
        System.out.println((finished-start)); 

     output=""; 

     } 

      int itr=input.length(); 
        while(itr!=0){ 
     output = Dictionar.get(index[itr]).value + " " + output; 
     itr=prev[itr]; 
    } 
    return output; 
    } 

Dove dovrei attuare le regole e come (idealmente in un modo più efficiente rispetto all'utilizzo di una matrice)?

Nel caso in cui ci sono domande o mi hanno lasciato qualche dubbio non esitate a chiedere

Answer 1

Qual è il motivo per cui non è possibile utilizzare una libreria esistente come Apache Lucene? Supporta fuzzy queries che utilizzano la distanza di Levenshtein.

Diverso da quello che si potrebbe desiderare di prendere in considerazione Suffix Trees per velocizzare la ricerca stringa parziale