[C] Programma per contare occorrenze di parole.

[Relegal]

Ciao a tutti, sto incontrando non poche difficoltà a scrivere un programma in C che letto un file, crei un istogramma per le frequenze delle 10 parole che si ripetono più spesso nel testo.
So che il file di input non contiene più di 1000 caratteri per riga e ogni parola ( intesa come sottosequenza massimale di caratteri alfabetici (cioè per i quali isalpha() restituisce un valore vero)) è lunga al più venti. Inoltre nel testo non compaiono più di 10000 parole distinte.
Io ho pensato di leggere il file riga per riga in questo modo:
#include
#include

int main() {
FILE *fp;
char buf[1000];
char *riga;


/* apro il file */
fp=fopen("input.txt", "r");
if( fp==NULL ) {
printf("Errore in apertura del file");

}


/* leggo e stampo righe del file */
while(1) {
riga=fgets(buf, 1000, fp);
if( riga==NULL )
break;
printf("%s", buf);
}


/* chiudo il file */
fclose(fp);
system("pause");
return 0;
}

Non riesco però a organizzare le idee per individuare le parole e contare la loro frequenza. Fatto questo passaggio che è il più corposo del programma, pensavo di riempire una struttura con le dieci parole più frequenti e le rispettive frequenze e a quel punto disegnare su un file di output l'istogramma.
C'è qualcuno in grado di darmi una mano ?

[apatriarca]

Se ho capito bene, quello che vorresti fare è una specie di selection sort in cui ti fermi dopo i primi 10 elementi. La tua idea (e molte altre) sono discusse in questa pagina. Una cosa importante per far funzionare correttamente la tua idea è quella di spostare gli elementi già selezionati nelle prime posizioni dell'array in modo da essere facilmente estraibili e ignorabili. In quella pagina trovi implementata l'idea in pseudocodice.

Vediamo ora qualche alternativa:
1. Ordinare tutto l'array. Sinceramente non credo sia una buona idea perché non è molto più semplice da implementare e, a meno di implementare il radix sort, ha complessità maggiore del semplice selection sort applicato 10 volte.
2. Scorrere l'array e mantenere un array ordinato degli indici dei 10 elementi con frequenza maggiore trovati. Ha la stessa complessità del selection sort ma potresti trovarlo un po' più complicato da implementare.
3. Usare un algoritmo specifico di quelli descritti nell'articolo. Sono un po' come implementare un quicksort e sinceramente non la considero una cosa semplice da fare.

Io farei probabilmente 1 con radix sort se fossi interessato ad ottenere un algoritmo efficiente, oppure implementerei il tuo algoritmo o il 2 a seconda dell'umore del momento (quello che mi viene in mente prima principalmente) se fossi interessato a fare qualcosa di semplice. Ti consiglierei insomma di provare a mettere a posto il tuo codice.

[Relegal]

Grazie del consiglio, ora provo a scorrere la pagina che mi hai linkato.
Dopo aver fallito nel sistemare il codice che ho postato, per ragioni di tempo ho adottato un metodo "schiacciasassi" reso possibile dalla piccola dimensione della struttura isto: Ho fatto dieci passaggi distinti ciascuno dei quali composto da queste azioni:
1) Cerca la parola più frequente
2) Copiala insieme alla sua frequenza in isto.
3) Azzera la frequenza di questa parola nella struttura contenente tutte le parole presenti nel testo.
4) Azzera il contatore che ha memorizzato la massima frequenza riscontrata

Comunque ora provo a vedere se riesco ad usare un algoritmo di ordinamento per rendere il programma un pelo più carino !
Grazie ancora per tutto l'aiuto che mi hai offerto.

[Umby2]

"Relegal":

.....

Non mi piace molto, perchè cosi facendo se hai ad esempio 3 parole con la stessa frequenza da posizionare in 9^ 10^ 11 ^ posizione del vettore, che fai ?
Ne metti 2 delle 3 ? in questo caso quali delle 2 ? le prime 2 che incontri ?
Oppure ti fermi a 8, e non posizioni manco la 9^ e la 10^ ?


Ovviamente scrivendo un programma, sono proprio queste condizioni "limite" da controllare bene.

[apatriarca]

A me sembra abbastanza chiaro come si comporti l'algoritmo di Relegal in questa situazione. Prendi le prime due parole con la stessa frequenza e ignora l'ultima. È comunque il comportamento che credo più sensato in questo caso. È lo stesso comportamento che si avrebbe ordinando il vettore con un algoritmo di ordinamento stabile. Secondo me va benissimo fatto in questo modo.

[Relegal]

Sì, è esatto quanto affermato da apatriarca. Non l'ho specificato in precedenza, ma in caso un certo numero di parole si presentino con la stessa frequenza all'interno del testo, l'ordine con cui compaiono all'interno dell'istogramma di output non è rilevante.

[Umby2]

"apatriarca":A me sembra abbastanza chiaro come si comporti l'algoritmo di Relegal in questa situazione. Prendi le prime due parole con la stessa frequenza e ignora l'ultima. È comunque il comportamento che credo più sensato in questo caso. È lo stesso comportamento che si avrebbe ordinando il vettore con un algoritmo di ordinamento stabile. Secondo me va benissimo fatto in questo modo.

Infatti, proprio perchè l'algoritmo non controllava questa situazione, l'avevo messo in evidenza.

[Umby2]

"Relegal":Sì, è esatto quanto affermato da apatriarca. Non l'ho specificato in precedenza, ma in caso un certo numero di parole si presentino con la stessa frequenza all'interno del testo, l'ordine con cui compaiono all'interno dell'istogramma di output non è rilevante.

Avevo evidenziato una altro aspetto, simile a quello che hai menzionato ma non uguale:

pensa che hai le parole "il" "la" "le" con frequenza uguale e si posizionano in 9^ 10 ^ 11^ posizione. Considerato che hai il vettore di 10 elementi, ne metti 2 e ne escludi una terza.
Mi son posto questo problema, poi se non ha alcune rilevanza, vabbè.... va bene cosi'.