テキストの自動修正のための動的アルゴリズム

Question

私はlevenshtein distanceを使用して、8000語を含む特定の辞書に基づいて のフレーズを修正するために、自動修正プログラムを作成しています。

ディクショナリには、各行に "word word_frequency"のペアが含まれています。 DictionarEntryオブジェクトを使用してこれらのペアを保存します。 Class Dictionar Entryには2つのフィールドがあります。 value：単語列を格納します freq：周波数を格納 辞書はLinkedListとして保存されます。 私はstdinから64文字の文字列を読みました。処理する前に 私はすべてのスペースを削除します。 "Coo lweather" - > "Coolweather" levenshtein dynamic（wikipediaの例を参照）で計算された行列の最後の行にあるすべての接頭辞のlevenshtein距離を計算する際に、その接頭辞に気づいたのは、すべての接頭辞の距離を返します。

機能LEV自体などの最初の接頭辞、の全てに第2のパラメータ文字列からl.distanceを含むベクトルを返します。 分LEV：

私の問題は、私はいくつかの追加のルールを尊重しなければならないということです。距離 - >最小単語数 - >最大周波数合計 - >最小辞書辞書 これは、解の総数が最小単語数で1を取るように説明される。 まだ複数ある場合は、ルールのリストに従います。

私が適用しているダイナミックは、ナップザックダイナミックに類似しています。私はここで（最大周波数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を検討する必要があります