[C]Programa Eficiente De Processamento De Hashtags

[Berhart]

# 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

Hashtag.rar