Jazyk C 2013 – 8. cvičenie [Počítanie frekvencií slov]

Textové súbory

Frekvencie slov v dokumente

Spočítajte výskyty jednotlivých slov v textovom súbore.

V Jave by sme použili:

  • Scanner na riadky
  • Scanner na slová v riadkoch (alebo jeden skener po slovách)
  • Mapu na evidenciu slov (kľúče) a ich frekvencií (hodnoty)

V C nemáme ani skener, ani mapy; navyše načítavanie riadkov a ich tokenizovanie môže byť náročné na pamäť: potrebujeme udržiavať celý riadok v pamäti a jeho dĺžka môže byť neurčitá.

Využime dva programy:

  • program A, ktorý rozseká riadky súboru tak, že každé slovo zapíše na samostatný riadok [vytvoríme neskôr]
  • program, ktorý načíta slová po riadkoch a zistí výskyty

Predbežná verzia

  • začnime verziou, kde načítame slovo zo štandardného vstupu a vypíšeme ho
  • využime fgets() so štandardným vstupom, ktorému zodpovedá premenná stdin
  • a puts() na načítavanie
  • vyskúšajme to spustiť buď z konzoly a zadávať vstup z klávesnice

    ./frekvencie
    
  • pozorujme prázdne riadky:

    • fgets() totiž načíta i znak konca riadka \n
    • a puts() ukončí každý reťazec na výstupe znakom konca riadka
    • vyriešiť to môžeme printf()om.
  • môžeme využiť presmerovanie súboru na štandardný vstup

    ./frekvencie < /tmp/babel.txt
    

Dátová reprezentácia

  • namiesto neexistujúcej java.util.Mapy využime pole structov.
  • struct možno chápať ako trieda bez metód, len s verejnými inštančnými premennými
  • deklarácia:

    struct polozka {
        char slovo[50];
        int frekvencia;
    };
    
  • názov dátového typu je struct polozka (nie polozka!)

  • za deklaráciou nasleduje bodkočiarka
  • premenná tohto typu je napríklad:

    struct polozka p;
    
  • k prvkom pristupujeme cez bodkovú notáciu: p.frekvencia = 1

  • zatiaľ použime neefektívnu dátovú štruktúru: pole structov pevnej dĺžky, napríklad pre 3000 (doh!) slov.
    • budeme si separátne pamätať skutočný počet prvkov v poli
    • neskôr urobíme dynamickú verziu
  • odhadnime množstvo používanej pamäte:
    • 3000 položiek
    • každá má 50 znakov (= 50 bajtov) plus 4bajty (na 32-bitovej platforme) pre int
    • dohromady cca 150 kB
  • pole deklarujme

    struct polozka polozky[3000];
    
  • logika kódu:

    • ak slovo nie je v poli, pridajme ho tam s frekvenciou 1
    • ak slovo v poli už je, zvýšme frekvenciu
  • úvaha nad optimalizáciou:

    • pole bude neustále utriedené
    • budeme v ňom binárne vyhľadávať
    • technické problémy:
      • môžeme využiť qsort() zo stdlib.h
      • a bsearch() na vyhľadanie zo stdlib..
    • riešiteľné (dokonca s podpoľami, keďže naše pole bude často riedke)
    • ale potrebujeme vedieť pointre na funkcie
  • detekcia prvku poľa nech je cez funkciu je_v_poli()

    • návratová hodnota je zdanlivo pravdivostná hodnota (0 = pravda, 1 = nepravda)
    • je lepšie vracať index alebo -1 ak sa hodnota nenájde
    • funkcia berie parametre v poradí seno, ihla
      • pozor ale, pole structov musí mať uvedenú dĺžku
    • deklarácia:

      int je_v_poli(struct polozka polozky[], int dlzka, char slovo[]) {
      
  • nezabudnime kopírovať reťazce cez strcpy()

    • overme dĺžky bufferov, aby nedošlo k pretečeniu
    • slovo i riadok majú rovnakú dĺžku, čiže je to OK
  • a porovnávať cez strcmp()
  • vyrobme funkciu pre výpis položky v tvare

    158     the
    
  • následne môžeme náš program prepojiť so štandarným nástrojom sort˛

    ./frekvencie < /tmp/babel.txt | sort -n
    

Celý zdroják

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

#define MAX_DLZKA_SLOVA 50
#define MAX_POCET_SLOV 3000

struct polozka {
        char slovo[MAX_DLZKA_SLOVA];
        int pocet;
};

int je_v_poli(struct polozka polozky[], int dlzka, char slovo[]) {
        int i;
        for(i = 0; i < dlzka; i++) {
                if( strcmp(polozky[i].slovo, slovo) == 0 ) {
                        return i;
                }
        }
        return -1;
}

void vypis_polozky(struct polozka polozky[], int dlzka) {
        int i;
        for(i = 0; i < dlzka; i++) {
                printf("%d\t%s", polozky[i].pocet, polozky[i].slovo);
        }
}

int main() {
        char riadok[MAX_DLZKA_SLOVA];

        struct polozka polozky[MAX_POCET_SLOV];

        int pocet_slov = 0;

        int index;


        while( fgets(riadok, MAX_DLZKA_SLOVA, stdin) != NULL ) {
                printf("%s", riadok);

                index = je_v_poli(polozky, pocet_slov, riadok);
                if (index != -1) {
                        /*zvys_frekvenciu_o_jedna(polozky, riadok);*/
                        polozky[index].pocet++;
                } else {
                        strcpy(polozky[pocet_slov].slovo, riadok);
                        polozky[pocet_slov].pocet = 1;
                        pocet_slov++;
                }
        }

        vypis_polozky(polozky, pocet_slov);

        return 0;
}


sort < /tmp/babel.txt | uniq -c | sort -n

Ďalšie zdroje

Pridaj komentár

Vaša e-mailová adresa nebude zverejnená. Vyžadované polia sú označené *