Estoy escribiendo un programa de autocorrección que usa levenshtein distance para corregir una frase de no más de 64 charcters basados en un diccionario específico que contiene 8000 palabras.Algoritmo dinámico para autocorrelación de texto
El diccionario contiene en cada línea el par "Word word_frequency". Uso los objetos DictionarEntry para almacenar esos pares. Class Dictionar Entry tiene dos campos: value: almacena la palabra cadena freq: almacena la frecuencia El diccionario se almacena como LinkedList. Leo desde stdin la cadena de 64 caracteres. antes de procesarlo Elimino todos los espacios. "Coo lweather" -> "Coolweather" Me di cuenta que insead de calcular la distancia levenshtein para cada prefijo, en la última fila de la matriz calculada por la dinámica levenshtein (ver ejemplo wikipedia) devuelve las distancias para todos los prefijos .
La función lev devuelve un vector que contiene la distancia l.distance de la cadena del segundo parámetro a todos los prefijos de la primera, incluido él mismo.
Mi problema es que tengo que respetar algunas reglas adicionales: min lev. distancia -> número mínimo de palabras -> suma de frecuencia máxima -> mínimo lexicográfico Eso se explicaría como si el número total de soluciones fuera mayor que 1 tomamos las que tienen un número mínimo de palabras. Si todavía hay más de uno, seguimos la lista de reglas.
La dinámica que estoy aplicando es algo similar a una dinámica de mochila. No sé cómo poner en práctica el número mínimo de palabras regla (la frecuencia máxima es muy similar)
Aquí es lo que he probado hasta ahora ejemplos de entrada/salida, donde esto no funciona: "dolor reservado" la respuesta debe ser tan reservada, lo que obtengo es realmente así. He elegido este método porque es más eficiente. El límite de tiempo es de 2 segundos para Java.
actualización: 7 de abril. He encontrado la solución a mi problema, sin embargo, el tiempo de la CPU es demasiado grande, así que necesito optimizarlo. No debe superar los 2000 ms y actualmente se encuentra en alrededor de 6000 ms. Así que ahora mi enfoque principal es optimizarlo.
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;
}
¿Dónde debería poner en práctica las reglas y cómo (a ser posible de una manera más eficiente que el uso de una matriz)?
por si hay alguna pregunta o me han dejado algo claro no dude en preguntar
* "lo que obtengo es en realidad lo que estás servido" * [sic] Para que quede claro: su diccionario de 8000 palabras tiene ", por lo "," re "," servido "y" reservado ", pero no tiene" dolor "? – TacticalCoder
tan reservado sería la respuesta correcta porque la distancia levenshtein entre dolor reservado y tan reservado es igual (si ignoras los espacios, lo cual hago) pero reservado tiene mayor frecuencia. – pAndrei
¿Tiene que ser un algo dinámico? ¿Puedes usar mapas java estándar, conjuntos, etc.? – Andrejs