elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Trabajando con las ramas de git (tercera parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Calculo de frecuencias de palabras usando dispersio con tabla HASH cerrada
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Calculo de frecuencias de palabras usando dispersio con tabla HASH cerrada  (Leído 2,598 veces)
falcao999

Desconectado Desconectado

Mensajes: 2


Ver Perfil
Calculo de frecuencias de palabras usando dispersio con tabla HASH cerrada
« 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;


En línea

cypascal

Desconectado Desconectado

Mensajes: 42


Ver Perfil WWW
Re: Calculo de frecuencias de palabras usando dispersio con tabla HASH cerrada
« Respuesta #1 en: 4 Diciembre 2012, 21:52 pm »

Si, ya estamos todos trabajando para resolverte el programa. En cuanto lo tengamos lo ponemos.

Salu10!


En línea

Problemas interesantes de programación en C/C++ y Pascal en:
BLOG C/C++


WWW.CYPASCAL.BLOGSPOT.COM.ES
falcao999

Desconectado Desconectado

Mensajes: 2


Ver Perfil
Re: Calculo de frecuencias de palabras usando dispersio con tabla HASH cerrada
« Respuesta #2 en: 5 Diciembre 2012, 18:17 pm »

Muchas gracias!!!!espero vuestra solucion con mucha inquietud x saber como implementar el programa.
En línea

0xDani


Desconectado Desconectado

Mensajes: 1.077



Ver Perfil
Re: Calculo de frecuencias de palabras usando dispersio con tabla HASH cerrada
« Respuesta #3 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.
En línea

I keep searching for something that I never seem to find, but maybe I won't, because I left it all behind!

I code for $$$
Hago trabajos en C/C++
Contactar por PM
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
(SOLUCIONADO) Ayuda para reemplazar palabras en un .txt con batch usando Sed « 1 2 »
Scripting
miguel088 14 7,006 Último mensaje 11 Noviembre 2013, 15:42 pm
por miguel088
tabla hash
Programación C/C++
gloomyfairy 1 1,062 Último mensaje 3 Abril 2014, 12:14 pm
por Eternal Idol
Como calculo la resta y la division usando for?
Programación C/C++
Reyes2209 2 1,409 Último mensaje 20 Noviembre 2015, 22:08 pm
por DarK_FirefoX
Tabla de distribución de frecuencias
Programación Visual Basic
Ahinoam 0 2,466 Último mensaje 6 Junio 2016, 20:34 pm
por Ahinoam
Funcion Hash para un diccionario de palabras.
Programación C/C++
NextByte 4 1,481 Último mensaje 14 Mayo 2019, 17:37 pm
por Serapis
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines