Динамический алгоритм автокоррекции текста

Я пишу программу автокоррекции, которая использует расстояние Левенштейнадля исправления фраза длиной не более 64 символов на основе специального словаря, содержащего 8000 слов.

Словарь содержит в каждой строке пару «Слово слово_частота». Я использую объекты DictionarEntry для хранения этих пар. Запись словаря класса имеет два поля: value : сохраняет строку слов freq: сохраняет частоту Словарь хранится как LinkedList. Я прочитал со стандартного ввода строку из 64 символов. перед обработкой я удаляю все пробелы. «Прохладная погода» -> «Прохладная погода» Я заметил, что вместо вычисления расстояния Левенштейна для каждого префикса в последней строке матрицы, рассчитанной по динамике Левенштейна (см. Пример из Википедии) он возвращает расстояния для всех префиксов.

Функция lev возвращает вектор, содержащий l.distance от второй строки параметров до всех префиксов первого, включая самого себя.

Проблема в том, что я должен соблюдать несколько дополнительных правил: мин лев. расстояние -> минимальное количество слов -> максимальная сумма частот -> минимальная лексикографическая Это можно было бы объяснить так, как будто общее количество решений больше 1. мы берем те, в которых минимальное количество слов. Если их все же больше одного, мы следуем списку правил.

Динамика, которую я применяю, чем-то похожа на динамику рюкзака.Я не знаю, как реализовать правило минимального количества слов (правило максимальной частоты очень похоже)

Вот что я пробовал до сих пор примеры ввода/вывода, где это не удается: "очень сдержанно" ответ должен быть настолько сдержанным, то, что я получаю, на самом деле так сдержано Я выбрал этот метод, потому что он более эффективен. Ограничение по времени составляет 2 секунды для Java.

обновление: 7 апреля. Я нашел решение своей проблемы, однако процессорное время слишком велико, поэтому мне нужно его оптимизировать. Оно должно быть не выше 2000 мс, а сейчас оно составляет около 6000 мс. Так что теперь моей основной задачей становится его оптимизация.

 public static String guess (String input, LinkedList 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 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;
  }

Где и как следует применять правила (в идеале более эффективным способом, чем использование матрицы)?

Если есть какие-либо вопросы или я оставил что-то неясным, пожалуйста, не стесняйтесь спрашивать