Título: Calculo de frecuencias de palabras usando dispersio con tabla HASH cerrada Publicado por: falcao999 en 4 Diciembre 2012, 19:42 pm Haber si alguien me echa una mano con esto lo agradeceria mucho x favor.
Para implementar un corrector ortográfico o un contador de términos sería interesante utilizar una estructura de datos muy eficiente para buscar palabras, por ejemplo las tablas hash. Supongamos que queremos contabilizar la frecuencia de palabras que aparece en el Quijote, en este caso cada término del Quijote debe comprobarse si está o no en el diccionario, y en tal caso incrementar el contador de frecuencia. Para realizar el ejercicio se pide realizar los siguientes pasos: Implementar la clase DispCerrada<T> que implemente la funcionalidad sobre una tabla hash cerrada, y que maneje exploración cuadrática. El tipo T se instanciará a FrecuenciaTermino: struct FrecuenciaTermino{ string termino; unsigned ocurrencias; } Implementar la clase FrecuenciaTexto del modo siguiente: class FrecuenciaTexto{ DispCerrada<FrecuenciaTermino> tablaDisp; unsigned djb2(char *palabra); set<string> inexistentes; public: FrecuenciaTexto(char *diccionario, unsigned tamTablaDisp); void compruebaTexto(char *texto); vector<string> verInexistentes(); vector<FrecuenciaTermino> verFrecuencias();} • La clave es de tipo string pero se pasa a numérica mediante la función de dispersión djb2 del modo: h(x) = (dbj2(x) + i2)%tamaT abla. • El constructor crea la tabla hash con el fichero de un diccionario castellano y con la frecuencia de cada término inicialmente igual a 0. Para calcular un tamaño razonable de la tabla se realizarán experimentos con distintos tamaños (que sean primos) hasta que la inserción de ningún dato genere más de 20 colisiones. • La función compruebaTexto() toma el nombre de un fichero de texto (quijote.txt) y busca cada término en tablaDisp, actualizando su frecuencia. Si un termino no existe, se añade al conjunto de inexistentes. • La operación verFrecuencias() devuelve un vector sólo con las entradas que aparecen en el texto, ordenadas de mayor a menor frecuencia. Para ordenar el vector usar la función sort() de STL utilizando una clase de comparación a medida. • Crear un programa de prueba (main.cpp) que muestre las 10 palabras más comunes en el quijote y la lista de palabras no existentes en el diccionario de castellano. Comparación de tiempo con el AVL • Para comprobar que la tabla hash es más rápida que otra buena estructura de datos vamos a comparar el tiempo de la operación compruebaTexto( ) si se utiliza un árbol AVL o la tabla hash propuesta anteriormente. • Para ello implementar la clase FrecuenciaTexto2 del mismo modo pero utilizando un árbol AVL en vez de la tabla hash. • Medir los tiempos de las funciones FrecuenciaTexto::compruebaTexto( ) y FrecuenciaTexto2::compruebaTexto( ) del modo: #include <ctime> .... clock_t t_ini, t_fin; t_ini = clock(); // llamar aquí a la función t_fin = clock(); secs = (double)(t_fin - t_ini) / CLOCKS_PER_SEC; cout < < "Tiempo en ms " < < secs < < " ms. " < < endl; Título: Re: Calculo de frecuencias de palabras usando dispersio con tabla HASH cerrada Publicado por: cypascal en 4 Diciembre 2012, 21:52 pm Si, ya estamos todos trabajando para resolverte el programa. En cuanto lo tengamos lo ponemos.
Salu10! Título: Re: Calculo de frecuencias de palabras usando dispersio con tabla HASH cerrada Publicado por: falcao999 en 5 Diciembre 2012, 18:17 pm Muchas gracias!!!!espero vuestra solucion con mucha inquietud x saber como implementar el programa.
Título: Re: Calculo de frecuencias de palabras usando dispersio con tabla HASH cerrada Publicado por: 0xDani en 5 Diciembre 2012, 19:13 pm Muchas gracias!!!!espero vuestra solucion con mucha inquietud x saber como implementar el programa. Jaja que bueno xDDDDD. En una semana mas o menos estara listo, sigue esperando. Atentamente, El director del grupo de trabajo para resolver el problema de ivaneti999. PD: Mods borren esto si quieren, es que no me podia aguantar. |