用于文本自动纠正的动态算法

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加快部分字符串搜索