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

• podobnú funkcionalitu možno dosiahnuť cez

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

• Najdlhšie slová v slovenčine, Jazyková poradňa SME.

• Najdlhšie slovenské slovo: výsledky pátrania, blog Jána Babaríka
• The Longest Word in English, takes 35 hours to pronounce
• Typické dlhé slovo: Supercalifragilisticexpialidocious