Ανάλυση κειμένου στη C

[jimmy213]

Στα πλαίσια εκμάθησης της C, ασχολούμαι με τη δημιουργία προγράμματος για ανάλυση κειμένου. Μέχρι στιγμής το πρόγραμμα διαβάζει ένα αρχείο .txt και μετρά πόσους χαρακτήρες και πόσες λέξεις έχει.

Τώρα θέλω να μετρά από πόσες διαφορετικές λέξεις αποτελείται το αρχείο και να εισάγει αυτές τις λέξεις σε ένα αρχείο λεξιλογίου, π.χ vocabulary.txt. Πώς μπορεί να υλοποιηθεί κάτι τέτοιο; Δοκίμασα κάποια πράγματα αλλά χωρίς αποτέλεσμα. Όποιος μπορεί ας βοηθήσει. Ευχαριστώ.

 

 

>#include <stdio.h>

int main(){
   FILE *fpl;
   char oneword[10];
   char filename[30];
   char c;
   
   while(1){
            printf("Enter filename or ctrl+z to exit.\n\n> ");
            scanf("%s", filename);
            if(!feof(stdin)){
                             fpl=fopen(filename, "r");
                             check_file(fpl);
                             }
            else
                break;
               }
}

 

>#include <stdio.h>

void char_count(FILE *fp){
     char c;
     int i=0;
     
     if (fp==NULL) 
        printf("\nFile doesn't exist!\n");
     else {
          while(c!=EOF){
              c = getc(fp);/* get one character from the file*/
              if(c!=' ' && c!='\n')
              i++;
              }
          printf("\nNumber of characters in the file: %d", i);
          }
     fclose(fp);
printf("\n\n");
}

 

>#include <stdio.h>

void check_file(FILE *fp){
    int i=1;
    
    while(i==1){
             if(fp==NULL){
             printf("\n\tCould not find the requested file!!\n");
             printf("\tBe sure that the file is in the program's folder.\n\n");
             break;
             }
             else{
                  word_count(fp);
                  char_count(fp);
                  i++;
                  }
             }
}

 

>#include <stdio.h>

void word_count(FILE *fp){
   FILE *vo;
   char oneword[10];
   char c;
   int i=0;
   
   vo=fopen("vocabulary.txt", "a");
   while(c!=EOF){
                 c=fscanf(fp, "%s", oneword);
                 i++;
                 }
   printf("\nNumber of words in the file: %d", i-1);
   fseek(fp, 1, SEEK_SET);
}

 

 

Υ.Γ.: Χρησιμοποιώ dev-cpp και όλα τα παραπάνω αρχεία βρίσκονται σε κοινό έργο.

[bnvdarklord]

Θα πρεπει καθε λεξη που συναντάς πρώτη φορά να την αποθηκευσεις σε κάποια δομή με καλή αναζήτηση, ώστε για καθε λεξη που διαβαζεις να βλεπεις γρήγορα αν υπάρχει ήδη στην δομή σου. Αν προκειται για μικρά αρχεία η δομή αυτή θα μπορουσε να ναι ακόμα και πίνακας και να κανεις γραμμική αναζήτηση.

[computeras13]

Η καλύτερη λύση για τέτοιου είδους δουλειές είναι η χρήση hastable. Δυστυχώς όμως η c δεν υποστηρίζει κάποια τέτοια δομή από μόνη της (δεν ξέρω γενικώς αν υπάρχει στην c υποστήριξη δομών από την γλώσσα αλλά αυτό είναι άλλο θέμα).

 

Μια λύση για να προσπεράσεις αυτό το πρόβλημα είναι να χρησιμοποιήσεις μια εξωτερική βιβλιοθήκη. Προσωπικά έχω χρησιμοποιήσει αυτή σε ένα project που μου χρειάστηκε. Εφόσον όμως είσαι στα πλαίσια της εκμάθησης μπορέι να μην σε βολέψει αν δεν θέλεις να χρησιμοποιήσεις εξωτερικές βιβλιοθήκες.

[jimmy213]

Θα δοκιμάσω ξανά μήπως καταφέρω κάτι. Αν όχι θα επανέλθω με πιο συγκεκριμένο κώδικα.

[migf1]

Δεν ξέρω το γνωσικό σου επίπεδό, αλλά είναι εύκολο να φτιάξεις ένα απλό hash-table με μια απλή hash συνάρτηση. Π.χ. το άθροισμα των ASCII-codes του κάθε γράμματος της λέξης σου, modulo το πλήθος των στοιχείων του hash table.

 

Το hash table μπορεί να αποτελείται από απλές linked lists of strings, για την περίπτωση collisions.

 

Για παράδειγμα, αν έχεις ένα hash-table από Ν στοιχεία (linked lists) όσες λέξεις σου δίνουν ίδιο άθροισμα % Ν, θα μπαίνουν στην ίδια λίστα, την οποία και θα σκανάρεις για να βρεις αν μια λέξη είναι ήδη αποθηκευμένη ή όχι.

 

Αντί για άθροισμα ascii-codes μπορείς να χρησιμοποιήσεις κάποια από τις πολλές έτοιμες hash-functions που κυκλοφορούν, οι οποίες και δοκιμασμένες είναι και πετυχαίνουν ομοιόμορφη κατανομή των λέξεων στις λίστες του hash-table.

 

Εδώ π.χ. μπορείς να κατεβάσεις σε ένα zip πολλές έτοιμες hash-functions για strings: http://www.partow.net/programming/hashfunctions/

Εδώ λίγη θεωρία: http://burtleburtle.net/bob/hash/evahash.html

Γενικώς θα βρεις άπειρο info και κώδικα αν το ψάξεις.

 

Ιδανικά θα ήθελες perfect-hashing, αλλά από τη στιγμή που οι λέξεις στα κείμενα σου είναι τυχαίες, αναγκαστικά θα πρέπει να υλοποιήσεις αντιμετώπιση των collisions (όπως π.χ. οι linked-lists που σου έγραψα παραπάνω.

 

Αντί για hash-table μπορείς να χρησιμοποιήσεις άλλες δομές... π.χ. balanced binary tree αν θέλεις οι λέξεις να αποθηκεύονται ταξινομημένες.

[computeras13]

@migf1 έχω την εντύπωση οτι το perfect hashing δε υφίσταται παρά μόνο στην θεωρία. Μου διαφεύγει κάτι;

[migf1]

@migf1 έχω την εντύπωση οτι το perfect hashing δε υφίσταται παρά μόνο στην θεωρία. Μου διαφεύγει κάτι;

Δεν υπάρχει μόνο στην θεωρία, απλώς προϋποθέτει πως είναι γνωστά εκ των προτέρων & πεπερασμένα τα κλειδιά. Χρησιμοποιείται ευρέως π.χ. από compilers για τα keywords της γλώσσας.

[computeras13]

ΟΚ, για σταθερό αριθμό λέξεων ναι υφίσταται, το γνωρίζω. Αναφέρομαι σε γενικότερο μοντέλο.

[nilosgr]

@migf1 έχω την εντύπωση οτι το perfect hashing δε υφίσταται παρά μόνο στην θεωρία. Μου διαφεύγει κάτι;

Συμφωνώ, αφού με το hashtable βάζουμε Ν στοιχεία σε Μ θέσεις με Ν >> Μ, εκτός αν perfect είναι η απόλυτα ομοιόμορφη κατανομή, δηλαδή κάθε θέση το να έχει Ν/Μ στοιχεία.

 

 

Σχετικά με το φίλο μας ας προσπαθήσει να κάνει ένα απλό hashtable πχ με linked list όπως του είπατε

[migf1]

Με τυχαίο input είναι λογικό να μην μπορεί να δουλέψει.

 

Συμφωνώ, αφού με το hashtable βάζουμε Ν στοιχεία σε Μ θέσεις με Ν >> Μ, εκτός αν perfect είναι η απόλυτα ομοιόμορφη κατανομή, δηλαδή κάθε θέση το να έχει Ν/Μ στοιχεία.

...

 

http://burtleburtle.net/bob/hash/perfect.html

[παπι]

Με ενα B-Tree θα ειναι κομπλε IMO

[migf1]

Με ενα B-Tree θα ειναι κομπλε IMO

Τα πάντα εξαρτώνται από το τι ακριβώς θέλει να κάνει, με τι input και με τι προτεραιότητες Π.χ. για bounded input μπορεί να χρησιμοποιήσει και Trie, ή μπορεί να χρησιμοπιήσει και Splay Tree... ακόμα και Cookoo Hashing (αν το γράφω σωστα... αυτό με τα 2 hash-tables και τα 2 hash-functions που αλλάζουν δυναμικά).

 

Νομίζω όμως πως ο φίλος μας είναι ακόμα στην αρχή, οπότε ένα απλό hash-table είναι σίγουρα πιο εύκολο να το υλοποιήσει και να το συντηρήσει.

[computeras13]

Είναι "Cuckoo hashing" (κοντά έπεσες) και σαν τεχνική μου αρέσει πολύ ο τρόπος λειτουργίας του η αλήθεια είναι. Δεν είναι όμως για κάποιον αρχάριο πιστεύω.

[jimmy213]

Θα κοιτάξω τα όσα μου προτείνετε. Σας ευχαριστώ όλους για τις απαντήσεις σας.

[jimmy213]

Για τις διαφορετικές λέξεις, σκέφτηκα να φτιάξω ένα πίνακα words στον οποίο θα εισάγονται όλες οι λέξεις του αρχείου και έπειτα, με κάποιο έλεγχο, να περνούν σε ένα πίνακα diff οι διαφορετικές λέξεις, έτσι ώστε να τις περάσω στο αρχείο λεξιλογίου. Μέχρι τώρα όμως δεν τα καταφέρνω. Τι πρέπει να κάνω; Ευχαριστώ.

 

 

>#include <stdio.h>
#include <string.h>

void word_count(FILE *fp){
   char oneword[10];
   char words[10][100];
   char diff[10][100];
   char c;
   int i=0,j=1,k=0,g,found=0,count=0;
   
   while(c!=EOF){
                 c=fscanf(fp, "%s", oneword);
                 i++;
                 if(c!=EOF){
                            strcpy(words[k], oneword);
                            k++;
                            }
                 }
printf("\nNumber of words in the file: %d\n\n", i-1);
fseek(fp, 1, SEEK_SET);


strcpy(diff[0],words[0]);
while(count<k){
               if(diff[j]==NULL){
                                for(g=1; g<k; g++){
                                         if(strcmp(diff[g-1],words[j])!=0){
                                                                           strcpy(diff[j],words[j]);
                                                                           found++;
                                                                           }
                                         else
                                             break;
                                         }
                                j++;
                                }
               count++;
               }
                         
/*for(j=0; j<k; j++){
        found=0;
        for(g=0; g<k && !found; g++){
                 if(strcmp(words[j],diff[g])!=0){
                              strcpy(diff[g],words[j]);
                              count++;
                              }
                 }
        }*/
//printf("\nNumber of different words: %d", count);
//vocab(words, k);
for(i=0; i<found; i++)
        printf("diff[%d]= %s\n",i, diff[i]);
printf("found= %d", found);
}

>#include <stdio.h>

void vocab(char words[10][100], int k){
    int j=0;
    FILE *vo;
    
    vo=fopen("vocabulary.txt", "a");
    printf("\n");
    for(j; j<k; j++){
           fprintf(vo, "%s\n", words[j]);
           }
}

Άφησα τον κώδικα έτσι μήπως βοηθήσει. Επίσης διάβασα τις απαντήσεις προηγουμένως, αλλά δεν μπορώ να βγάλω κάποια άκρη...