Post by daniel_arvNo entiendo mucho tu estrategia y no es porque este mal pero todavía
no lo relaciono con el textopedictivo, me gustaría que fueras mas
detallado(si pudiera ser?), perdóname pero me doy cuenta de que sabes
Ok, me he bajado tu archivo, aunque ya había bajado este:
http://www.obout.com/editor_new/site_dictionaries/es-ES.zip
que es más compacto porque agrupa las terminaciones de las palabras, pero
entiendo que tu problema es un problema que te han puesto en tus
estudios, entonces mejor lo haces como te dijeron.
La primera solucion que di, o quise dar, usando un archivo
auxiliar de índices y busqueda binaria, que requiere 17 accesos
para esa cantidad de palabras, te lo puedo describir con más detalle,
aunque hay otros más rápidos organizando los índices en un arbol
con más ramas colgando de cada nodo (una solucion complicada
pero muy rápida sería "tantas ramas como letras en el alfabeto")
El arbol binario:
Primeramente tienes que generar el fichero de índices,
es decir recorres secuencialmente el fichero de palabras
y almacenas el offset donde comienza cada palabra en el fichero,
para cada palabra obtienes un entero de 32 bits. Cuando
termines ordenas este array por ejemplo empleando qsort
y lo grabas en un fichero. Esto es un trabajo previo y que
solo se hace una vez (hay que recorrer el fichero
de palabras secuencialemnte para obtener los índices pero
es de suponer que esto no cuenta, es solo una vez y se
puede ejecutar en un PC, no en la máquina destino de
la aplicacion final)
Entonces tienes ya un fichero de indices ordenado.
Para buscar una palabra lees primero en el fichero de indices
y luego en el de palabras. Ejemplo:
FILE *indices; //fichero ya abierto modo "rb"
FILE *palabras; //fichero ya abierto modo "rb"
char encontrada[64]; //ultima palabra leída
void busca_una(unsigned idx)
{
unsigned offset;
//lee el indice que está en la posicion idx
fseek(indices, idx << 2, SEEK_SET);
fread(&offset, sizeof(offset), 1, indices);
//lee la pabra correspondiente a ese indice
fseek(palabras, offset, , SEEK_SET);
fread(encontrada, 1, sizeof(encontrada), palabras);
*strchr(encontrada, 13) = 0; //esto corta la palabra en \r
}
Para buscar una palabras en todo el fichero aplicas el sistema de "partir
por la mitad" cada busqueda, a mi me gusta hacerlo aprovechando que
los numeros se almacenan en binario ;-)
#define MAXIMO_ALGORIMO 0x80000 //nunca más de medio millon de palabras
unsigned total_palabras; //previamente inicializada, palabras en el fichero
unsigned busca_esto(char *palabra)
{
int b = 0;
unsigned indice = 0;
unsigned mascara = MAXIMO_ALGORIMO;
for(; mascara; mascara >>= 1){
if(indice + mascara >= total_palabras) continue;
busca_una(indice + mascara);
b = strcmp(palabra, encontrada);
if(b >= 0) indice += mascara;
if(b == 0) return indice;
}
return indice + 1;
}
Con esto tienes solucionada la búsqueda de cualquier palabra,
la respuesta de busca_esto es el indice de la primera palabra
igual o mayor, y con busca_una puedes leer secuencialmente
las siguientes palabras mayores, todo ello a partir
del ínidce devuelto por busca_esto. (aunque hay un caso especial
si se busca una palabra menor que la primera que se puede
solucionar añadiendo un índice ficticio como primero en
la lista de índices)
Ahora tienes que ver el modo de operar cada vez que se pulse una
tecla
- lees la palabra tecleada por el usuario
- la buscas usando: busca_esto
- rellenas una lista con N palabras a partir de esa,
para lo cual puedes:
- lees secuencialmente N palabras usando busca_una
empezando con el índice obtenido antes.
- para cada palabra comprueba que es coíncidente,
puedes usar para eso strncmp (por si no hubiera N
palabras coincidentes)
- La vas metiendo a la lista de palabras posibles
Supongo que todo esto realmente deberías haberlo pensado tu solo,
ya que te lo exigen en tus estudios (no será para que lo
preguntes, será para que lo resuelvas).
Por otro lado cuando alguien "está de exámenes", no es forzosamente
que está examinandose, a lo mejor está corrigiendo exámenes:-)
Esperemos que tu profesor no esté por aquí leyendo. Había
un chiste sobre eso, pero es un poco largo para contarlo aqui.
Saludos :-) -Pedro-
http://www.maicas.net/
e-mail en www.maicas.net