SoloCodigo

Programación General => C/C++ => Mensaje iniciado por: JoRDi-18 en Domingo 28 de Noviembre de 2004, 21:28

Título: Algoritmos De Búsqueda/ordenación De Ficheros
Publicado por: JoRDi-18 en Domingo 28 de Noviembre de 2004, 21:28
Hola:

---> Para buscar en ficheros <---
En el caso en el que me encuentro, en el que trabajo con un "fichero-diccionario", se me ha ocurrido una forma para buscar una determinada palabra cuando se solicite. Se trata de "indexar" de alguna forma el fichero. Es decir, hay un fichero auxiliar que guarda el número de palabras para cada letra del abecedario: para la letra 'A' hay x1 palabras, para la 'B' hay x2 palabras, etc. Os contaré que tal funciona.
¿Sabéis alguna otra forma de buscar una palabra (una entrada/registro) en un fichero?


---> Para ordenar ficheros <---
Aquí ya estoy más perdido... He pensado en aprovechar lo anterior para ir más rápido, pero a partir de ahí ya estoy perdido. Me interesa colocar una palabra entre otras dos (todo el mundo sabe cómo funciona un diccionario).
Si alguien me pudiera decir alguna forma de hacer esto con un algoritmo no excesivamente complejo, le estaría muy agradecido!


Muchas gracias por adelantado!
Título: Re: Algoritmos De Búsqueda/ordenación De Ficheros
Publicado por: LeGatoRojo en Lunes 29 de Noviembre de 2004, 08:39
Hola, pues puedes ordenar con strcmp(cad,cad1), para abrir el dato te recomiendo fseek(), ya que esta funcion te abre el archivo desde el lugar que quieras, y para leer fseek, usa la ayuda de c++, para ver como se utilizan estas funciones.
Título: Re: Algoritmos De Búsqueda/ordenación De Ficheros
Publicado por: CiRRuS en Lunes 29 de Noviembre de 2004, 10:21
Citar
---> Para buscar en ficheros <---

Para buscar en ficheros tienes muchas formas, encontraras muchas en algun manual de desarrollo de bases de datos.

La que tu comentas es el uso de indices para el acceso a la base de datos. Tienes muchos tipos de indices (creo que eran cuatro) y dependen de si la base de datos esta ordenada o no. Podrias empaparte un poco con informacion relacionada para hacer tu algoritmo mas eficiente. Si quieres mas informacion ya sabes.

Citar
---> Para ordenar ficheros <---

Para ordenacion, uffff, metodos unos cuantos, burbuja, shell... los que toca enfrentarse en los cursos de algoritmos.

Pero como siempre, el mas utilizado y visto como el mas eficiente es el quicksort. Aunque la mayoria de las implementaciones ordenan un array, y mantener tu diccionario en un array puede ser un poco peligroso (si son muchas palabras).

Creo que uniendo la informacion del fichero indice que quieres crear y la idea de ordenar el fichero, puedes implementar un algoritmo muy eficiente. En el fichero indice tienes el numero de palabras que comienzan por una determinada letra, asi que, si este indice esta ordenado, tienes el camino ya del todo hecho.

Bueno, vaya palique, ya nos comentas vale?

Nos vemos :hola:
Título: Re: Algoritmos De Búsqueda/ordenación De Ficheros
Publicado por: JoRDi-18 en Lunes 29 de Noviembre de 2004, 23:55
OK, verás, el fichero en el que quiero buscar palabras estaría ya ordenado. Si pudieras indicarme algunos enlaces donde informarme acerca de esto te lo agradecería muchísimo.


Luego, respecto a la ordenación, ya me comentaron que el quicksort era quizás la mejor de las alternativas, pero no me convence mucho, ya que también me interesaría tener expresiones en el diccionario... Aunque si no hay otro remedio tendre que intentarlo a ver qué sale...

El fichero de los índices está ordenado, por supuesto. Va a serme de gran ayuda, seguro, pero aún queda buscar la forma de ordenar "bloques" de palabras (según la letra por la que empiece).



Gracias!
Título: Re: Algoritmos De Búsqueda/ordenación De Ficheros
Publicado por: CiRRuS en Martes 30 de Noviembre de 2004, 00:19
Enlaces de internet poco te puedo dar pq no he recurrido a la web para encontrar explicaciones, mas bien me las daban en la asignatura de bases de datos ;). De todas formas bibliografia si te puedo dar, mira a ver si puedes localizar el libro "Fundamentos de Sistemas de Bases de Datos" de Elmasri, Navathe. Ahi solucione siempre todas mis dudas acerca de la asignatura.

La cuestion que tu planteas es el uso de indices en un sistema de bases de datos. Corresponde al nivel fisico de la base de datos y existen 4 tipos, dependiendo de si el indice esta ordenado o no, y si el el indice se aplica sobre un campo de la base de datos que marca la ordenacion del fichero de almacenamiento.

Si no consigues informacion puedo intentar escribirte algun resumen. Intenta buscar en google a ver si pillas algo.

En cuanto a las expresiones que comentas del diccionario no termino de entender, ¿no se supone que vas a buscar a partir de un determinado termino?

Si el fichero de indices esta ordenado ¡que maravilla!. Pero como bien dices primero deberas implementar alguna funcion que te diga cuando una palabra va antes que otra. Creo que ahi deberias implementarte una funcion que compare caracter a caracter y descarte la que tenga el codigo assci mayor (o menor). Bueno, son solo ideas.

Ya nos cuentas :hola:
Título: Re: Algoritmos De Búsqueda/ordenación De Ficheros
Publicado por: patitofeo en Martes 30 de Noviembre de 2004, 16:40
Una umilde opinion:

 :hola:

No soy experto en algoritmos.

Simplemente os digo como afrontaria yo el problema.

Si el diccionario no es muy extenso y no tienes límite de espacio lo que haría sería definir un tamaño fijo para los registros. Esto puede ser, que cada regstro tenga una longitud fija de 64 caracteres. Vale para expresiones cortas ¿no?

la palabra asignada a ese registro ocuparía los primeros bytes del mismo y el resto (hasta 64) serían ocupados por algún caracter raro como '·', '$', '%'...
no espacios para poder incluir expresiones.

De esta forma al moverte en el fichero con seek (por ejemplo) sabes que el offset que apunta al principio de la palabra es siempre [indice_de_entrada]*64.

Si quieres posicionarte en la 3ª palabra, 2*64 (la primera es el 0) y así.

Si el tamaño es reducido, entonces se obliga a que las palabras tengan un tamaño variable. En ese caso yo construiria los registros de una forma por ejemplo:

[caracter de control][entero con el número de caracteres de la palabra][palabra]

por ejemplo:

#(4)casa#(11)helicoptero#(5)perro#......

Luego para posicionarte, aría una busqueda recurrente sumando los offsets con seek hasta encontrar la palabra.

Un indice con el offset que corresponde a la primera letra del diccionario también ayuda mucho:

a(0)b(15)c(32).... ->en la posicion 0 empiezan las 'aes', en la 15 las 'bes', etc.

todo esto ayuda a moverse por el fichero.

A la hora de hacer la busqueda y la insercción yo utilizaría un analisis por niveles.
buscaría la concordancia con la primera letra, luego la segunda y así sucesivamente, almacenando en dos variables el apuntador que me vaya reducciendo el intervalo de busqueda por encima y por debajo. Cuando las variables apunten a dos palabras consecutivas "PREMIO".

Para la insercción. Si es como imagino que lo haces palabra a palabra, solo tienes que mirar la posición en la que la debes guardar con el algoritmo anterior, desplazar todo el resto del fichero hacia delante para guardar sitio (No se si existe alguna función que desplace el fichero mientras escribes para no comertelo) y luedo escribir tu palabra en el hueco. Esta última es la parte más pesada y engorrosa yo creo.

Bueno, me he dado cuenta que te he escrito demasiado.

Como digo, es solo como yo lo resolvería a si a priori.

Espero no haberte dado mucho la lata.

Cualquier crítica será bien recibida.

 :blink:
Título: Re: Algoritmos De Búsqueda/ordenación De Ficheros
Publicado por: JoRDi-18 en Domingo 5 de Diciembre de 2004, 02:53
Aquí estoy otra vez!

Ya he acabado el programa, pero no funciona... Le tengo que hacer algunos retoques, y empiezo por el primero; a ver si me podéis ayudar.

Se trata del fichero de índices:

Código: Text
  1.  
  2.          // Para actualizar el fichero de índices
  3.                   a=registro.palabra1[0]-65;  
  4.                   fseek(findex,a*sizeof(struct index),SEEK_SET);   // Busca posicion
  5.                   fread(&entrada, sizeof(struct index), 1, findex);  // Lee índice
  6.                   entrada.cantidad++;   // incrementa
  7.                   fseek(findex,a*sizeof(struct index),SEEK_SET);   // Vuelve a la posición
  8.                   fwrite(&entrada, sizeof(struct index), 1, findex);   // Actualiza el índice
  9.          //
  10.  
  11.  

El problema es que el programa sólo sabe incrementar de 0 a 1. Si escribes dos palabras que empiecen por la misma letra, el valor máximo de 'A' en el fichero es 1. No sé por qué... He probado a cambiar el modo de apertura del fichero de índices, pero nada.


Bueno, adjunto dos zips para quien les quiera echar un ojo. En el primero de ellos está el programa "básico" (sin la implementación de ordenación), y en el segundo está el programa "acabado".


A ver si me podéis ayudar a solucionar el problema de los índices!! El resto del programa creo que funcionará si funciona bien el fichero de índices, o en cualquier caso, si está mal, será fácil retocarlo para que funcione.

Adioss!!
Título: Re: Algoritmos De Búsqueda/ordenación De Ficheros
Publicado por: CiRRuS en Domingo 5 de Diciembre de 2004, 12:22
Buenassss!!! Estaba a punto de postear un msg pa ver como te iba. Buenas de nuevo.

Le he estado echando un vistazo al codigo y he comprobado el error que comentas, efectivamente, dentro de una misma ejecucion el valor cantidad de la estructura index de tu variable no se incrementa, solo pasa de valor 0 a 1.

He estado probando tu programa y hay veces que se me queda pillado, por ejemplo, si introduzco una palabra que ya esta en la base de datos (siempre probaba con "a" en ingles y "a" en español ;)) me pregunta que si quiero redefinirla, y da igual que responda que si o que no, se queda pillado. Ademas, probe a introducir la pabra "as" con traduccion "as" y se me quedo pillado, dandome un error de memoria :blink:, y hay veces que al meter palabras nuevas se me queda pillado. Asi que no pude depurar del todo tu programa.

Bueno, vayamos al lio. La primera ejecucion paso lo que te he comentado, no incrementa mas de 1. Sin embargo, cuando ejecute por segunda vez el programa consegui ver que el valor sí se incrementaba, asi que lo primero que se me ocurre es que no cierras el descriptor del fichero. En tu codigo tienes:

<!--xc1--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>XCODE </td></tr><tr><td id='XCODE'><!--exc1-->

         a=registro.palabra1[0]-65;  
         fseek(findex,asizeof(struct index),SEEK_SET);  
         fread(&indice, sizeof(struct index), 1, findex);  
         printf (hola%d, indice.cantidad);
         indice.cantidad++;    incrementa
         printf (adios%d, indice.cantidad);
         fseek(findex,asizeof(struct index),SEEK_SET);  
         fwrite(&indice, sizeof(struct index), 1, findex);  
                  
         do{                  
            fflush(stdin);
            printf (nnA%cadir nuevo registro [SN] , ene);
            scanf (%c,&SoN);      
         }while (tolower(SoN) != 's' && tolower(SoN) != 'n');    
                                                              
         if (tolower(SoN) == 's'){
            system(CLS);
            add(fich);
         }
         fclose(findex);
<!--xc2--></td></tr></table><div class='postcolor'><!--exc2-->

Fijate en el fclose(findex), lo tienes al final, sin embargo, puede ocurrir que si el usuario quiere añadir otra entrada, se llame de nuevo a add(fich) y el descriptor permanece abierto. Prueba a cerrarlo antes de realizar la pregunta, justo despues del fwrite, al fin y al cabo, en ese punto ya has modificado el fichero de indice como querias y puedes confirmar las modificaciones fisicamente en el fichero.

Yo lo he puesto pero no he podido comprobarlo pq hay veces que se me queda pillado, como te he comentado antes. No se si el problema esta ahi, pero si te puedo asegurar que en una de la ejecuciones pude ver "hola1hola2" :D, y eso significa que guardo bien las cosas!!!!

Bueno, espero que te sirva de algo, para cualquier cosa ya sabes.

PD: Lo he estado probando en windows con Dev-C++.
Título: Re: Algoritmos De Búsqueda/ordenación De Ficheros
Publicado por: JoRDi-18 en Domingo 5 de Diciembre de 2004, 12:44
A esa misma conclusión llegué yo ayer a las 3 y pico de la mañana... Efectivamente era eso, no sabía que se tenía que cerrar el fichero para que se actualizara. Así que eso ya está arreglado.

Respecto a los fallos, te agradezco mucho que los dijeras, ya que hay alguno que no tenía ni idea. Pero bueno, ahora que tengo bien los índices voy a ponerme a depurarlo. Espero tenerlo para hoy, ya os contaré.

Adios!!
Título: Re: Algoritmos De Búsqueda/ordenación De Ficheros
Publicado por: CiRRuS en Domingo 5 de Diciembre de 2004, 13:01
Ok, me alegro haber acertado, aunq un poco tarde ;).

Mucho animo!!!!

Nos vemos :hola:
Título: Re: Algoritmos De Búsqueda/ordenación De Ficheros
Publicado por: JoRDi-18 en Domingo 5 de Diciembre de 2004, 17:59
Bueno! Espero que esta sea la última duda porque me estoy desesperando.

He hecho la traza del algoritmo de ordenación retocado y parece que funciona bastante bien, pero me ha surgido otro problema, que es prácticamente el mismo que el anterior.

Necesito abrir y cerrar el fichero DB.dat (Base de Datos) al mismo tiempo que el de índices, para actualizarlo entre inclusiónes de palabras.

He probado con los tres tipos de apertura de ficheros, y con los tres me da el mismo error. Escribo 3 o 4 palabras en una misma ejecución, y el fichero de índices se comporta bien; pero el de la base de datos no: al finalizar el programa sólo tiene la última palabra introducida.

Adjunto el código básico (sin el algoritmo de ordenación) y bastante depurado.


Graciass!
Título: Re: Algoritmos De Búsqueda/ordenación De Ficheros
Publicado por: CiRRuS en Domingo 5 de Diciembre de 2004, 22:24
He estado mirando tu codigo, he visto que los descriptores para el fichero de indices asi como para el fichero de datos los cierras en la funcion Add(). No veo claramente donde puede estar el problema.

He localizado un descriptor que no cierrras, en la funcion addFile() abres el fichero de indices pero no lo cierras. Aunque tambien es cierto que es solo para lectura, no deberia dar problemas.

Solo se me ocurre, que cierres los descriptores (tanto del fichero de indices como de la base de datos) despues de añadir una entrada. No pospongas el fclose hasta que el usuario no quiera meter mas palabras. Prueba con eso.

Ya nos cuentas

Nos vemos :hola:
Título: Re: Algoritmos De Búsqueda/ordenación De Ficheros
Publicado por: JoRDi-18 en Lunes 6 de Diciembre de 2004, 21:41
Bueno!! Esto esta ya casi visto para sentencia. Aún tiene algunos fallos.
--> Si añades en una misma ejecución palabras de una misma letra NO REPETIDAS, funciona.
--> Si añades en varias ejecuciones palabras de una misma letra NO REPETIDAS, funciona.

En los demás casos, pasan cosas extrañas.

A ver si alguien me ayuda a testarlo! Yo tengo dos fallos, y me gustaria que me dijeseis algunso más; especialmente tú, Cirrus, que parece que eres el único que está viendo los avances del programa.


Muchas gracias!!
Título: Re: Algoritmos De Búsqueda/ordenación De Ficheros
Publicado por: CiRRuS en Miércoles 8 de Diciembre de 2004, 19:37
¿¿?? Se ha perdido mi ultimo mensaje, pues ya te habia respondido, no se si me leiste ya.

No me acuerdo mucho lo que te contaba, pero mas o menos:

- Probe con "house" y "home" y aquello iba bien

- Algunas veces me daba error al meter palabras iguales y otras.

- Cuando se daba cuenta de que estaba metiendo una palabra que ya estaba, me decia si queria redefinirla, si decia que no, me obligaba a tener que meter una, ¿no se podría volver de alguna forma al menu principal?.

- Despues de introducir una palabra y aceptarla, cuando el programa te pregunta si quieres meter otra, de repente me suelta que la palabra ya estaba en la base de datos ¿¿?? :blink:

Bueno, mas o menos descubri eso. Poco a poco. Supongo que habran algunas cosas que estan en el aire y por eso exsiten comportamiento extraños. Pero como todo, es cuestion de depurar. Animo!

Nos vemos :hola:
Título: Re: Algoritmos De Búsqueda/ordenación De Ficheros
Publicado por: CiRRuS en Miércoles 8 de Diciembre de 2004, 19:43
Efectivamente, hubo un error en el servidor, mi mensaje se perdio en la inmensidad... vamos, que al quemarse el servidor se quemo todo, ;)
Título: Re: Algoritmos De Búsqueda/ordenación De Ficheros
Publicado por: JoRDi-18 en Miércoles 8 de Diciembre de 2004, 21:37
Sí! Ya lo vi antes de que se borrara.

Bueno, ya se me ha acabado el tiempo, ahora hasta que no tenga otro rato no lo volveré a retomar, aunque está prácticamente acabado.

El único problema se encuentra en la "bisección sobre una semirrecta de enteros", que no encuentro un algoritmo bueno (y mira que he probado). He posteao el problema del algoritmo en un par de páginas de Mates, y si no le preguntaré a algún profesor de mi facultad.

Te dejo el programa hasta donde he llegado. Y en cuanto lo finalice postearé el programa completo, que seguro que no tiene desperdicio jeje. Pero tengo que ver como "dividir" el archivo en trozos más pequeños por que tal y como está se me hace ilegible algunas veces hasta a mí.


Muchas gracias!!
Título: Re: Algoritmos De Búsqueda/ordenación De Ficheros
Publicado por: CiRRuS en Miércoles 8 de Diciembre de 2004, 22:01
Ok, cuando pueda le echo un vistazo.

Para lo que quieras aqui me tienes. En cuanto a lo de dividir el archivo, si te refieres al fuente, tampoco es tan grande, pero si necesitas ayuda para saber como hacerlo, ya sabes ;).

Mucho animo!!

Nos vemos :hola: