用於文本自動糾正的動態算法

Question

我正在編寫一個自動糾正程序，它使用levenshtein distance糾正 基於特定字典（包含8000個單詞）的不超過64個字符的短語。

該字典在每行上都包含「Word word_frequency」對。 我使用DictionarEntry對象來存儲這些對。 Class Dictionar Entry有兩個字段： value：存儲單詞字符串 freq：存儲頻率 字典存儲爲LinkedList。 我從stdin讀取了64個字符的字符串。 處理它之前，我刪除所有的空格。 「Coo lweather」 - >「Coolweather」 我注意到，在由levenshtein動態計算的矩陣的最後一行中，計算每個前綴的levenshtein距離，參見 它返回所有前綴的距離。

函數lev返回一個包含從第二個參數字符串到所有第一個前綴（包括自身）的l.distance的向量。

我的問題是，我必須尊重一些附加規則： min lev。距離 - >最小字數 - >最大頻率和 - >最小字典 這將被解釋爲如果解決方案的總數大於1 我們採用最少的字數。如果仍然有不止一個，我們會遵循規則列表。

我應用的動態類似於揹包動態。 我不知道如何實現的話規則的最小數量（最高頻率一個非常類似）

這裏是我試過到目前爲止 輸入/輸出例子，其中失敗： 「瘡保留」答案應該是如此保留，我所得到的實際上是如此服務 我選擇了這種方法，因爲它更有效率。 Java的時間限制是2秒。

更新：4月7日。我找到了解決我的問題的辦法，但是CPU時間太長，所以我需要優化它。 它不應該高於2000毫秒，它目前在6000毫秒左右。所以現在我的主要焦點是優化它。

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

我應該在哪裏實施規則以及如何（理想情況下以比使用矩陣更有效的方式）？

的情況下有任何疑問或我留下的東西不清楚，請隨時提出

Answer 1

任何理由，你爲什麼不能使用現有的庫像Apache Lucene？它支持使用Levenshtein距離的fuzzy queries。

以外，你可能要考慮Suffix Trees加快部分字符串搜索