title: Dynamic algorithm for text auto-correct
body: <p>I am writing an auto-correct program that uses the <a href="http://en.wikipedia.org/wiki/Levenshtein_distance" rel="nofollow">levenshtein distance</a> to correct 
  a phrase of no more than 64 charcters based of a specific dictionary containing 8000 words. </p>
  
  <p>The dictionary contains on each line the pair " Word word_frequency".
  I use DictionarEntry objects to store those pairs. Class Dictionar Entry has  two fields :
  value : stores the word string
  freq  : stores the frequency
  The dictionary is stored as a LinkedList.
  I read from stdin the 64 character string.
  before processing it I remove all the spaces. 
  "Coo lweather" -> "Coolweather"
  I noticed that insead of calculating the levenshtein distance for every prefix , in the last row of the matrix calculated by the levenshtein dynamic( see wikipedia example )
  it returns the distances for all the prefixes.</p>
  
  <p>Function lev returns a vector containing the l.distance from second parameter string to all of the first's prefixes, including itself.</p>
  
  <p>My issue is that I have to respect a few additional rules : 
  min lev. distance -> min number of words -> maximum frequency sum -> minimum lexicographic 
   That would be explained as  if the total number of solutions is greater than 1 
  we take the ones with minimum number of words. If there are still more than one we follow the list of rules.</p>
  
  <p>The dynamic I am applying is something similar to a knapsack dynamic.
   I don't know how to implement the minimum number of words rule ( the maximum frequency one is very similar)</p>
  
  <p>Here is what I have tried so far 
  input/output examples where this fails:
  "sore reserved" the answer should be so reserved , what I obtain is actually so re served
   I have chosen this method because it is more efficient. The time limit is 2 seconds for Java.</p>
  
  <p>update : 7th of April . I have found the solution to my problem, however the cpu time is too large so I need to optimize it. 
  It should be no higher than 2000 ms and it currently is at around 6000 ms. So now my main focus becomes optimizing it.</p>
  
  <pre><code> public static String guess (String input, LinkedList&lt;DictionarEntry&gt; 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 &lt; 128 ; i++){
                  d[i]=127;
                  freq[i]=0;
                  wcount[i]=1;
                  values[i]="";
          }           
       d[0]=0;
       freq[0]=0;
  
           for (int i = 0 ; i &lt;input.length(); ++i){  
  
               curent=input.subSequence(i, input.length()).toString();
               long start =System.currentTimeMillis();
                for (int j = 0 ; j &lt; Dictionar.size();++j){
  
                    costMatrix[i][j]=lev(Dictionar.get(j).value,curent);
                    for(int k=1;k&lt;costMatrix[i][j].length;++k){
  
                        if(d[i]+costMatrix[i][j][k]&lt;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) &lt;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)&gt;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])&gt;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;
    }
  </code></pre>
  
  <p>Where should I implement the rules and how ( ideally in a more efficient way than using a matrix)?</p>
  
  <p>In case there are any questions or I have left something unclear please feel free to ask</p>