我正在编写一个使用 levenshtein distance 的自动更正程序纠正 基于包含 8000 个单词的特定词典的不超过 64 个字符的短语。

字典的每一行都包含一对“Word word_frequency”。 我使用 DictionarEntry 对象来存储这些对。 Class Dictionar Entry 有两个字段: value : 存储单词字符串 freq :存储频率 字典存储为 LinkedList。 我从 stdin 读取了 64 个字符的字符串。 在处理它之前，我删除了所有空格。 “酷天气”->“酷天气” 我注意到在由 levenshtein 动态计算的矩阵的最后一行中计算每个前缀的 levenshtein 距离(参见维基百科示例) 它返回所有前缀的距离。

函数 lev 返回一个 vector ，其中包含从第二个参数字符串到所有第一个参数字符串(包括它自身)的 l.distance。

我的问题是我必须遵守一些额外的规则: 最低水平距离 -> 最小词数 -> 最大频率和 -> 最小词典顺序 这可以解释为解决方案的总数大于 1 我们采用最少单词数的那些。如果仍然不止一个，我们将遵循规则列表。

我应用的动力类似于背包动力。 我不知道如何实现最小字数规则(最大频率非常相似)

这是我到目前为止尝试过的 失败的输入/输出示例: "sore reserved"答案应该这么矜持，我得到的居然这么矜持 我选择了这种方法，因为它更有效。 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;
  }

我应该在哪里实现规则以及如何实现(理想情况下以比使用矩阵更有效的方式实现)？

如果有任何问题或我有什么不清楚的地方，请随时提问

最佳答案

您不能使用现有库(如 Apache Lucene)的任何原因？它支持fuzzy queries使用 Levenshtein 距离。

除此之外，您可能还需要考虑 Suffix Trees加快部分字符串搜索

关于java - 文本自动更正的动态算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10042898/