Jump to content

[C]Programa Eficiente De Processamento De Hashtags


Berhart
 Share

Recommended Posts

# Boa tarde Comunidade #Apresento-vos aqui um programa realizado por mim cujo objectivo passa por contar o número de ocorrências de cada Hashtag num conjunto de mensagens dadas.

Como sabem as hashtags são hoje um popular termo para denominar palavras-chave ou referências a uma informação, tópico ou discussão que se deseja indexar de forma explícita. Popularizadas pelo Twitter, e posteriormente pelo Facebook, Google+ e Instagram, entre outros,

as hashtags são compostas pela palavra-chave do assunto antecedida por um cardinal (#).

Uma vez que as funcionalidades pretendidas são conceptualmente muito simples, pretende-se que o esforço seja dedicado à implementação de soluções computacionalmente eficientes.

No código realizado é utilizada a estrutura de dados HashTable(podem ser usadas outras estruturas como Árvores Binárias) para aumentar a eficiência de procura e

processamento bem como métodos de Alocação de memória dinâmica ( void *malloc(size_t size), void free(void *ptr) ) e Abstração de Dados.

O Código é composto por 5 ficheiros:

Estrutura de dados utilizada + funcionalidades da mesma: hash.c & hash.h

Abstração de dados: item.c & item.h

Código principal: main.c

No Enunciado que é fornecido em Anexo ( mais os casos-teste para debug pessoal ) são descritos

todos os pormenores que terão de usar na vossa implementação.

hash.c:

#include "hash.h"/*Funcao que inicializa a hashtable e a variavel global que guarda a hashtag mais popular*/void init(){ int i; HashPop = (Item)malloc(sizeof(struct hashtag)); HashPop->count = 0; HashPop->text = NULL; heads = (link*)malloc(M*sizeof(link)); for (i = 0; i < M; i++) heads = NULL;}/*Funcao que decide se existe ou nao a hashtag lida no sistema, conformeo resultado dessa avaliacao serao feitos certos comandos*/void adiciona(char * message){ link t; t = STsearch(message); if( t == NULL ){ /*Se a hashtag nao existir na hashtable*/ STinsert(message);/* insere a hashtag */ tag_count++; /* Aumenta-se o contador do nr de hashtags diferentes */ } else{ /*Se a hashtag existir*/ (t->p)->count ++; /* incrementa-se o contador de ocurrencias dessa hashtag*/ HashTagPop(message,(t->p)->count); /* Atualizar a hashtag mais popular se for o caso*/ } total_de_ht++; /*Aumenta-se o contador do nr de ocurrencias total de hashtags*/}/* Funcao que insere cada hashtag na hashtable de acordo com o indice dadopela funcao de dispersao */void STinsert(char* token) { int i = hash(token); heads = insertBeginList(heads, token);}/*Funcao que insere hashtags no inicio de cada lista ligada e retorna um ponteiro para a nova cabeca */link insertBeginList(link head, char* text){ link new = (link)malloc(sizeof(struct node)); Item h = NEW(text); HashTagPop(h->text, h->count); /* Atualizar a hashtag mais popular se for o caso*/ new->p = h; new->next = head; //FreeItem(h); return new;}/* Funcao de Dispersao */int hash(char *v) { int h, a = 31415, b = 27183; for (h = 0; *v != '\0'; v++, a = a*b % (M-1)) h = (a*h + *v) % M; return h; } /* Funcao que procura cada hashtag na hashtable de acordo com o indice dadopela funcao de dispersao */link STsearch(char *text) { int i = hash(text); return searchList(heads, text); } /*Funcao que procura hashtags numa lista ligada */link searchList(link head, char* text){ link t; for(t=head; t != NULL; t = t->next) if(strcmp((t->p)->text, text) == 0) return t; /*Se a hashtag tiver presente no sistema retorna o ponteiro para ela */ return NULL; /*Se a hashtag nao estiver no sistema*/}/*Funcao que atualiza as informacoes relativas a hashtag mais populardefenida como variavel global(ponteiro)*/void HashTagPop(char *text, int c){ if (c > HashPop->count){ HashPop->count = c; free(HashPop->text); HashPop->text = strdup(text); } else if (c == HashPop->count){ if ( strcmp(text, HashPop->text) < 0 ){ free(HashPop->text); HashPop->text = strdup(text); } }}/* Funcao que da free duma hashtable */void HashFree(link *h){ int i; for (i = 0; i < M; i++) FreeList(heads); free(heads);}/* Funcao recursiva que da free duma lista ligada */link FreeList(link j){ if (j == NULL) return NULL; j->next = FreeList(j->next); free((j->p)->text); free(j->p); free(j); return NULL;}

hash.h:

#ifndef HASH_H#define HASH_H#include "item.h"#include <stdio.h>#include <string.h>#include <stdlib.h>#include <ctype.h>#define MAX_MESSAGE 140 /*Tambem serve para os hashtags*/#define M 11261 /*Numero primo para a funcao hash*//*Estrutura usada: */typedef struct node{ Item p; struct node*next;}*link;extern link *heads; /*array de heads necessario para a hashtable*/extern int tag_count; /* contador de hashtags diferentes */extern int total_de_ht; /* contador que guarda quantas hashtags foram inseridas no sistema(hashtable)*/void init();void adiciona(char * message);int hash(char *v); void STinsert(char* token); link insertBeginList(link head, char* text);link STsearch(char *text);link searchList(link head, char* text);void HashTagPop(char *text, int c);void HashFree(link *h);link FreeList(link k);#endif

item.c:

#include "item.h" /*Funcao que cria um novo Item*/Item NEW(char* text){ Item h = (Item)malloc(sizeof(struct hashtag)); h->count = 1; h->text = strdup(text); return h;}/*Funcao que mostra o conteudo de um item*/void showItem(Item x){ printf("%s %d\n",x->text, x->count);} /* Funcao de comparacao necessaria para o quarto argumento do qsort Compara primeiro por ocorrencia, se a subtracao derdiferente de 0 tem de comparar alfabeticamente */int cmpItem(const void* a, const void* b){ int e; Item c = *(Item*) a; Item d = *(Item*) b; e = d->count - c->count; if (e != 0) return e; else{ return strcmp(c->text,d->text); }}/* Funcao que da free de um item */void FreeItem(Item k){ free(k->text); free(k);}

item.h:

#ifndef ITEM_H#define ITEM_H#include <stdio.h>#include <string.h>#include <stdlib.h>/*Estrutura usada*/typedef struct hashtag{ char *text; int count; }*Item; extern Item HashPop; /*Variavel(ponteiro) que guarda as informacoes da Hashtag mais popular*/Item NEW(char* text);void showItem(Item x);int cmpItem(const void* a, const void* b);void FreeItem(Item k);#endif

main.c:

#include "hash.h"#include "item.h"void func_a();void func_l();void split(char *line);void leLinha(char *text);link *heads; /* *array de heads necessario para a hashtable*/int tag_count = 0; /* contador de hashtags diferentes */int total_de_ht = 0; /* contador que guarda quantas hashtags foram inseridas no sistema(hashtable)*/Item HashPop; /*Variavel(ponteiro) que guarda as informacoes da Hashtag mais popular*/int main(){ char comando; init(); comando = getchar(); while (comando != 'x') { /*Processamento do comando*/ switch(comando){ case 'a': func_a(); break; case 's': printf("%d %d\n",tag_count, total_de_ht); getchar(); break; case 'm': if (tag_count != 0) showItem(HashPop); getchar(); break; case 'l': func_l(); getchar(); break; default: /* Caso o utilizador introduza um comando nao defenido */ printf("ERRO: Comando desconhecido\n"); } comando = getchar(); } /* Tem que se dar free de toda a memoria alocada*/ HashFree(heads); FreeItem(HashPop); /*O programa so chegara aqui caso algo anormal acontecer*/ return EXIT_SUCCESS;}/* Funcao que le a mensagem e adiciona hashtags a hashtable */void func_a(){ char *message; message = (char*) malloc(sizeof(char)*MAX_MESSAGE+1); getchar(); leLinha(message); /* leitura da mensagem */ split(message); /*Processamento da mensagem, retorna*/ free(message);}/*Funcao que lista todas hashtags referidas nas mensagens por ordem decrescente*/void func_l(){ link k; int i, j = 0; Item vec[tag_count]; for(i = 0; i < M; i++){ /*percorre a hashtable*/ /*Agora vamos copiar a hashtable para um vetor de ponteiros para hashtags*/ for(k = heads; k != NULL; k = k->next){ vec[j] = k->p; j++; } } size_t vec_len = sizeof(vec) / sizeof(Item); qsort(vec, vec_len , sizeof(Item), cmpItem); /* Algoritmo de ordenacao usado*/ /* Imprimir o vetor */ for (i = 0; i < tag_count; i++) printf("%s %d\n",vec->text, vec->count);}/* Funcao que le a mensagem */void leLinha(char *s){ int c, i = 0; while ((c = getchar()) != '\n' && c != EOF) s[i++] = c; s = '\0'; } /* Funcao que processa a mensagem */static const char separators[] = {' ','\t',',',';','.','?','!','"','\n',':','\0'};void split(char *line){ char *token = strtok(line, separators); int i; while(token != NULL) { i = 0; if (token[0] == '#'){ while( token ) { token = tolower(token); /*as maiusculas sao passadas para minusculas*/ i++; } adiciona(token);/*funcao que adiciona hashtags a hashtable*/ } token = strtok(NULL, separators); }}

#Cumprimentos

Hidden Content

    Give reaction to this post to see the hidden content.

Hidden Content

    Give reaction to this post to see the hidden content.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...