我正在编写一个自动更正程序，该程序使用levenshtein 距离根据包含 8000 个单词的特定词典来更正不超过 64 个字符的短语。
字典的每一行都包含一对“Word word_frequency”。我使用 DictionarEntry 对象来存储这些对。类 Dictionar Entry 有两个字段： value ：存储单词字符串 freq ：存储频率 字典存储为 LinkedList。我从标准输入中读取了 64 个字符的字符串。在处理它之前，我删除了所有空格。“Cool lweather”->“Coolweather”我注意到除了计算每个前缀的 levenshtein 距离之外，在由 levenshtein 动态计算的矩阵的最后一行（参见维基百科示例）它返回所有前缀的距离。
函数 lev 返回一个向量，其中包含从第二个参数字符串到所有第一个前缀的 l.distance，包括它自己。
我的问题是我必须遵守一些额外的规则：min lev。distance -> min number of words -> maximum frequency sum -> minimum lexicographic 这可以解释为好像解的总数大于 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;
}
我应该在哪里实施规则以及如何实施（理想情况下以比使用矩阵更有效的方式）？
如果有任何问题或我留下了不清楚的地方，请随时提问