レーベンシュタイン距離を使用して、8000 語を含む特定の辞書に基づいて 64 文字以下の句を修正する自動修正プログラムを作成しています。
辞書には、各行に " Word word_frequency" のペアが含まれています。これらのペアを格納するには、DictionarEntry オブジェクトを使用します。Class Dictionar Entry には 2 つのフィールドがあります。 value : 単語文字列を格納します freq : 頻度を格納します 辞書は LinkedList として格納されます。標準入力から 64 文字の文字列を読み取りました。処理する前に、すべてのスペースを削除します。"Coo lweather" -> "Coolweather" レーベンシュタイン ダイナミクスによって計算された行列の最後の行で、すべてのプレフィックスのレーベンシュタイン距離を計算するのではなく (ウィキペディアの例を参照)、すべてのプレフィックスの距離を返すことに気付きました。
関数 lev は、2 番目のパラメーター文字列から、それ自体を含む最初のすべてのプレフィックスまでの 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;
}
ルールをどこにどのように実装する必要がありますか (理想的には、マトリックスを使用するよりも効率的な方法で)?
ご不明な点やご不明な点がございましたら、お気軽にお問い合わせください