Strutturazione di dati: i file

Nei paragrafi precedenti abbiamo discusso le modalità di rappresentazione di singole informazioni (caratteri, numeri, immagini, suoni). Nella realtà, sarà in generale necessario rappresentare informazioni più complesse che in un certo senso possono essere viste come composte a partire da tali informazioni elementari. Consideriamo un semplice esempio che verrà usato come guida in questo paragrafo. Si consideri una banca e si vogliano mantenere all'interno di un elaboratore tutte le informazioni riguardanti i clienti. Ad esempio, per ogni cliente si vogliano ricordare:

• cognome;

• nome;

• indirizzo;

• numero di conto;

• disponibilità sul conto;

(ovviamente si potrebbero mantenere anche altri tipi di informazioni).

I dati riguardanti un cliente devono essere raggruppati; i dati riguardanti clienti diversi essere mantenuti separati tra di loro e, globalmente, le informazioni devono essere organizzate (strutturate) in modo tale che il loro reperimento ed uso risulti semplice (ciò significa, ad esempio, che i dati riguardanti un cliente devono essere recuperati in blocco). Per tale ragione è opportuno introdurre dei meccanismi per strutturare i dati, costruendo strutture composte di codifica delle informazioni. In particolare, nell'esempio tutte le informazioni riguardanti un cliente possono essere viste dal punto di vista logico come un blocco unico (una unica informazione complessa), memorizzato indipendentemente dagli altri e le cui componenti possono, quando servono, essere analizzate indipendentemente.

Il concetto di file (archivio) è stato introdotto proprio per tale obiettivo. Intuitivamente, un file è un meccanismo di strutturazione di informazioni che permette di aggregare singole informazioni (informazioni elementari) in strutture più complesse. Più precisamente, un file può essere definito introducendo i seguenti concetti:

• Un capo è un insieme di byte che codifica una singola informazione; tipicamente si può avere:

  • una informazione numerica (un numero intero o decimale - capo numerico): il campo sarà l'insieme di byte per la codifica (binaria o floating-point) del numero stesso;

  • una informazione alfabetica o alfanumerica (campo alfabetico o alfanumerico): il capo sarà una sequenza di byte che codificano i caratteri della stringa alfabetica (o alfanumerica). Ad esempio, un capo alfabetico può contenere il nome di una persona ossia la sequanza di caratteri che costituiscono il nome della persona;

  • una immagine o un suono.

• Un record è un insieme di campi che sono logicamente correlati tra di loro ossia, in altri termini, che costituiscono nel loro insieme una informazione complessa. Nell'esempio della banca discusso in precedenza, li informazioni riguardanti un singolo cliente possono essere viste come un record i cui campi sono:

  • un campo alfabetico per il nome;

  • un campo alfabetico per il cognome;

  • un campo alfanumerico per l'indirizzo;

  • un campo numerico per il numero del conto;

  • un campo numerico per la disponibilità sul conto;

• Un file è una sequenza di record. Ad esempio, le informazioni riguardanti la banca possono essere viste come un file con un record per ogni cliente e tale per cui ogni record è suddiviso in campi che contengono le singole informazioni come discusso in precedenza.

Il file è l'entità fondamentale di organizzazione logica delle informazioni in un sistema di elaborazione; in particolare, un file può essere visto come un blocco di informazioni che ha un ben preciso significato logico per l'utente (più avanti vedremo le tecniche utilizzate per memorizzare i file all'interno della memoria di un elaboratore).

La definizione di file data in precedenza è la più generale possibile; in realtà si possono distinguere due diversi tipi di file:

• file strutturati, che sono effettivamente sequenze di record (e quindi di campi) come nel caso dell'esempio concernente la banca discusso in precedenza;

• file di testo, in cui l'informazione è semplicemente una sequenza di caratteri (byte) che costituiscono un testo (ad esempio una lettera o un capitolo); in tal caso si può pensare che il record coincida con il singolo carattere e non sia quindi ulteriormente suddiviso in campi.

Nel seguito concentreremo l'attenzione sul primo tipo di file analizzando in particolare gli aspetti concernenti l'organizzazione logica delle informazioni; l'organizzazione fisica verrà trattata in seguito.

Un primo aspetto rilevante riguardante l'organizzazione logica dei file è la lunghezza dei record. Vi sono due possibilità:

• file con record a lunghezza costante;

• file con record a lunghezza variabile;

Nel primo caso tutti i record sono formati dallo stesso numero di byte; ad esempio tutti i record hanno lo stesso insieme di campi e ogni campo ha una lunghezza prefissata (è formato da un numero prefissato di byte), indipendentemente dalla lunghezza dell'informazione che contiene. Nel secondo caso la dimensione dei campi può variare, ad esempio in funzione della lunghezza dell'informazione in essa contenuta.

Consideriamo un file con record a lunghezza costante. Possiamo rappresentare graficamente tale file come una tabella le cui righe corrispondono ai record e sono suddivise in colonne corrispondenti ai campi. Ad esempio, il file corrispondente alla banca può essere rappresentato come mostrato nella figura sotto.

Figura 1 - File con record a dimensione costante

Nella definizione di tale file deve essere precisato il numero di byte destinato ad ognuno dei campi. Ad esempio, per il file in figura sopra potremmo decidere che i due campi numerici sono formati da 4 byte, i campi alfanumerici per il nome e il cognome sono formati da 15 byte e il campo alfanumerico per l'indirizzo è formato da 30 byte. Tale divisione deve essere sufficientemente grande da contenere la più lunga informazione che potrà dover essere memorizzata nel campo (per cui abbiamo supposto, ad esempio, che non vi siano nomi con più di 15 caratteri). E' chiaro, tuttavia, che tale valore massimo è difficile da stabilire a priori (si pensi al campo per l'indirizzo di un cliente della banca). Inoltre nella gran parte dei casi l'informazione che deve essere inserita all'interno di un campo occupa meno spazio di quello destinato (si pensi, ad esempio, al nome "Ada" per cui 12 byte - ossia una percentuale del 80% - del campo risultano inutilizzati). Questo è lo svantaggio principale della scelta di avere i record a dimensioni costanti: parte dello spazio risulta sprecato; vedremo tuttavia nel seguito alcuni importanti vantaggi dei file con record a dimensione costante.

L'alternativa al prefissare la dimensione dei campi è quella di avere campi a dimensione variabile in funzione dello spazio richiesto dalle informazioni che devono essere contenute nel campo. Ad esempio, è sufficiente un campo con 3 byte per il nome "Ada" mentre sarà necessario utilizzare un campo con 12 byte per il nome "Massimiliano". Si avranno quindi, record a dimensione variabile, come mostrato nella figura sotto.

Figura 2 - File con record a dimensione variabile

Il secondo aspetto che è fondamentale discutere riguardo ai file è il problema del reperimento delle informazioni. Le informazioni vengono infatti memorizzate per essere poi utilizzate (e modificate) per cui è fondamentale avere dei metodi per accedere alle informazioni. Si pensi al file banca: durante le operazioni si vorrà accedere al campo contenente la disponibilità su un conto per leggere o modificarne il valore.

Per discutere i meccanismi di accesso è fondamentale fare una precisazione che riguarda, almeno in parte, la memorizzazione fisica dei file. Sebbene abbiamo usato una struttura a tabella per descrivere logicamente le informazioni contenute in un file (figura 1 e 2), è importante notare che un file è una struttura lineare: una sequenza di record, ossia una sequenza di campi e quindi una sequenza di byte. In altri termini la struttura è la seguente:

questo è anche il modo in cui un file viene memorizzato fisicamente in memoria. Nel caso in cui i campi e quindi i record abbiamo dimensione variabile è necessario introdurre nella sequenza di byte che costituiscono un file di caratteri speciali per separare le informazioni. In particolare, sarà necessario introdurre un carattere speciale per separare i record tra di loro (useremo il carattere "&") e un carattere speciale per separare un campo dall'altro, all'interno di un record (useremo il carattere "#"). Ad esempio, nel caso del file della banca (figura 2) la sequenza di byte effettivamente memorizzata sarà:

...&1146561#5135250#Massimiliano#Rossi#Via Milano 15&271564#23147432#Cristina#Bianchi#Corso Venezia 1&.....

Si noti che tali separatori non sono necessari nel caso di file con campi (e quindi record) a dimensioni costanti in quanto in tale caso si possono separare i campi in base al numero di byte che costituiscono ogni campo. L'accesso alle informazioni all'interno di un file deve quindi essere effettuato su una struttura lineare. In particolare, possiamo supporre che il problema sia quello di reperire un record (o un campo). Vi sono tre fondamentali metodi di accesso ai file che verranno analizzati nei prossimi paragrafi: accesso sequenziale, diretto, con chiave.

File ad accesso sequenziale

L'accesso sequenziale ai file è quello più semplice ed è possibile qualunque sia il tipo di file. Supponiamo di dover cercare un record: la ricerca avviene sempre dall'inizio del file e leggendo man mano tutti i record fino a quando non si arriva a quello desiderato. Ad esempio, supponiamo di voler leggere il record riguardante il cliente "Bianchi" e quindi la sua disponibilità. Partiremo allora dall'inizio del file leggendo tutte le informazioni nei campi e passando da un record all'altro fino a che il campo con il cognome (il quarto nell'esempio di figura 2) non è quello desiderato. Ciò significa quindi, che si devono leggere tutti i record passando da uno al successivo fino ad arrivare a quello cercato.

Dovrebbe essere chiaro che tale metodo di accesso non è efficiente in quanto comporta che ogni volta la ricerca venga effettuata a partire dall'inizio del file e leggendo tutte le informazioni. L'unico vantaggio di tale metodo di accesso è che esso può essere utilizzato per qualunque tipo di file in quanto non richiede che il file abbia una struttura logica particolare (quindi può essere utilizzato tanto in file con record a dimensione costante quanto in file con record a dimensione variabile).

File ad accesso diretto

L'inefficienza dell'accesso sequenziale è legata al fatto che si devono leggere tutti i record dall'inizio fino a che non si arriva a quello desiderato.

L'ideale, dal punto di vista della velocità di accesso, sarebbe di poter accedere direttamente al record (campo) desiderato senza dover considerare quelli precedenti. Per poter fare ciò è necessario sapere esattamente in quale punto del file inizia il record cui si è interessati.

Il punto di inizio di un record (o di un campo) all'interno di un file prende il nome di "indirizzo" del record (campo). Se l'indirizzo dell'informazione desiderata è noto allora è possibile posizionarsi direttamente in tale punto ed accedere all'informazione in modo diretto (ossia senza considerare le altre informazioni). Si noti che in tal caso il tempo necessario per accedere ad una informazione non dipende dal punto in cui l'informazione si trova (posizione nella sequenza). Disporre degli indirizzi per poi accedere alle informazioni richiede, tuttavia, altre strutture informative in cui tali indirizzi vengono memorizzati. Analizzeremo più precisamente tale problema nel prossimo paragrafo.

Nel caso in cui i record del file abbiano lunghezza uguale allora è possibile stabilire quale sia il punto di inizio di ogni record anche senza sapere direttamente gli indirizzi. Supponiamo, ad esempio, che la lunghezza di ogni record sia di 50 byte, allora si avrà che i record iniziano rispettivamente ai byte 0, 50, 100, 150 .... del file. Se si conosce la posizione di un record all'interno della sequenza, all'ora è facile calcolare l'indirizzo del record stesso ed è quindi possibile accedere direttamente e recuperare il record stesso senza bisogno di scorrere quelli precedenti. Se si deve leggere il terzo record è infatti sufficiente posizionarsi al centesimo byte all'interno del file e il record occuperà i 50 byte successivi. Più in generale, per recuperare il record in n-esima posizione ci si dovrà posizionare al byte 50*(n-1). La modalità di accesso basata su tale tecnica di indirizzamento prende il nome di "accesso diretto". La possibilità di effettuare accesso diretto (che è molto più veloce ed efficiente di quello sequenziale) è il maggior vantaggio derivante dall'uso di file con record a dimensione fissa. Nel caso di file con record a lunghezza variabile, invece non è possibile calcolare l'indirizzo di un record dalla sua posizione e, pertanto l'accesso diretto non è possibile (a meno che non si disponga direttamente degli indirizzi, come vedremo nel prossimo paragrafo).

Si ha quindi che i file con record a dimensione costante hanno accesso più veloce ma portano a uno spreco di spazio mentre i file con record a dimensione variabile richiedono solamente lo spazio necessario ma non consentono accesso diretto. Tali vantaggi/svantaggi devono essere pesati nella scelta della migliore rappresentazione date le esigenze che si hanno nella utilizzazione dei file (ad esempio, tenendo conto di quanto spazio di memoria è disponibile o se si ha bisogno di reperire le informazioni in modo veloce). Si noti, comunque, che, come vedremo in seguito, si deve tener conto di quale sia il supporto di memoria su cui il file verrà memorizzato in quanto solo alcuni supporti consentono l'accesso diretto alle informazioni in esse memorizzate (il disco, detto hard disk, permette l'accesso diretto mentre il nastro permette solo l'accesso sequenziale).

File ad accesso con chiave

Si è visto che la possibilità di effettuare l'accesso ai record in modo veloce è legata alla conoscenza degli indirizzi dei record del file. Si può pensare, allora, di mantenere le informazioni di tali indirizzi al di fuori del file (ossia di ricordarsi in quale punto inizia ogni record) in modo tale che poi l'accesso possa essere effettuato in modo veloce. Per poter fare questo è necessario avere un modo per identificare univocamente i record (con un nome, in un certo senso) ricordandosi l'indirizzo di inizio di ognuno di essi. Questa è l'idea del metodo di accesso con chiave. Più precisamente, tale metodo di accesso può essere schematizzato come segue:

• In primo luogo si deve individuare un campo presente in tutti i record da utilizzare come riferimento unico ai record. Tale campo (che prende il nome di "campo chiave") deve avere la proprietà che il suo valore sia diverso in ognuno dei record (ossia non vi devono essere due record in cui il tale campo assume lo stesso valore). In questo modo il campo chiave permette di individuare univocamente ogni record del file (ossia di dare un nome unico ad ogni record).

• Si costruisce quindi un nuovo file (che prende il nome di "file delle chiavi" - o "tabella delle chiavi") che ha record (a dimensione costante) che contengono due campi (due informazioni):

  • un campo per contenere una chiave;

  • un campo per contenere un indirizzo all'interno del file

  L'idea è che tale file contiene un elemento per ogni record del file delle informazioni e che tale elemento contiene il valore del campo chiave del record e l'indirizzo del record.

Consideriamo l'esempio della banca. In tale file si può utilizzare come chiave il campo numero di conto in quanto tale campo è l'unico per cui i valori sono diversi in ogni record (questo non è il caso, in generale, per campi quali il nome, il cognome o l'indirizzo di un cliente). Nell'esempio si organizzerà quindi la tabella delle chiavi come un record che contiene:

• una chiave, ossia il numero di un conto;

• l'indirizzo nel file in cui inizia il record per tale conto.

Ossia graficamente:

(nel file delle informazioni accanto ad ogni record è scritto, per semplicità di interpretazione, l'indirizzo di inizio del record stesso). In questo modo se si deve accedere al record del conto numero 271564, si può:

• accedere alla tabella delle chiavi, cercare la chiave 271564 e leggere l'indirizzo del record corrispondente nel file delle informazioni;

• accedere in modo diretto al record, dato il suo indirizzo;

In altri termini, è possibile accedere direttamente ad un record dato il valore del campo chiave. Si ha quindi una velocità di accesso simile all'accesso diretto (si vedano più avanti i commenti su come realizzare l'accesso veloce alla tabella delle chiavi). Lo svantaggio è quello di dover mantenere altra informazione: la tabella delle chiavi. Si ha quindi una perdita di spazio rispetto al caso dei file con record a dimensione variabile (ed è quindi opportuno scegliere chiavi che non occupino troppo spazio).

Due osservazioni sono importanti in conclusione. Si noti, in primo luogo, che l'accesso con chiave può essere visto come la combinazione di due accessi diretti: uno alla tabella delle chiavi che ha record a dimensione costante (se vedano, tuttavia, i commenti del prossimo paragrafo) e uno al file delle informazioni dato l'indirizzo recuperato nella tabella delle chiavi. In secondo luogo, si vuole enfatizzare l'importanza di scegliere come chiave un campo i cui valori siano diversi all'interno di record diversi del file. Se così non fosse si potrebbero avere ambiguità. Supponiamo, ad esempio, di scegliere come chiave per il file della banca il campo "cognome" del cliente; se vi sono due persone con lo stesso cognome (come nell'esempio in figura 2) allora si avrebbe un'ambiguità nel reperimento degli indirizzi: data la chiave "Rossi" non sarebbe possibile determinare in modo univoca a quale record accedere.

Strategie di ricerca

L'accesso diretto ai record di un file è il più efficiente tra quelli discussi fino ad ora. Tuttavia, esso richiede che sia noto l'indirizzo (o la posizione relativa) del record da cercare all'interno del file. Se tale indirizzo non è disponibile l'accesso diretto non può essere effettuato. Consideriamo il caso della tabella delle chiavi: si può accedere direttamente ad una chiave (e quindi all'indirizzo del record da cercare nel file delle informazioni) solo se ne conosce la posizione all'interno della tabella. Se si conosce solo il valore della chiave (ad esempio, si sa solo che si vuole accedere al record del conto 271564) allora si deve effettuare una ricerca all'interno della tabella delle chiavi. E' importante, allora, definire delle strategie affinché tale ricerca possa essere fatta in modo efficiente.

Un modo semplice per fare la ricerca è quello sequenziale; si tratta cioè di fare un accesso sequenziale al file "tabella delle chiavi" fino a quando non si trova il record con la chiave desiderata. In questo modo, però, si perdono tutti i vantaggi dell'accesso con chiave e si ritorna ai tempi dell'accesso sequenziale. Per effettuare l'accesso in modo efficiente è necessario dare una organizzazione logica alla tabella delle chiavi.

Un primo punto è quello di mantenere le chiavi ordinate rispetto ai valori delle chiavi stesse. Se le chiavi sono ordinate, infatti la ricerca può essere effettuata in modo più efficiente usando una tecnica nota come "ricerca binaria", che vedremo tra un attimo. Se la tabella delle chiavi non è mantenuta ordinata, allora essa perderà tutti i vantaggi in quanto sarà necessario, in generale, cercare le chiavi in modo sequenziale.

Data una tabella delle chiavi ordinata (per valori crescenti o decrescenti delle chiavi) è possibile cercare efficientemente una chiave e quindi l'indirizzo del record che essa denota. Si supponga di cercare la chiave "k" e che la tabella delle chiavi contenga N elementi; si procede nel modo seguente (ricerca binaria in un insieme ordinato):

si va in primo luogo a considerare il record che si trova a metà della tabella (ossia che si trova in posizione N/2; sia k' la chiave che si trova in tale posizione

• se k' = k allora abbiamo finito e abbiamo trovato l'elemento desiderato;

• se k<k' allora l'elemento cercato è nella prima metà della tabella delle chiavi; si può allora proseguire la ricerca considerando solo gli elementi dall'inizio a N/2 -1;

• se k>k' allora l'elemento cercato è nella seconda metà della tabella delle chiavi; si può allora proseguire la ricerca considerando solo gli elementi da N/2 + 1 fino alla fine.

In questo modo la ricerca può essere effettuata in modo molto veloce (richiede, in media, un numero di passi logaritmico in N).

Un modo ancora più veloce per effettuare la ricerca di un elemento in una tabella è quello che prevede l'uso di "funzioni di hash". Si supponga di avere una tabella delle chiavi con N elementi. L'idea è che gli elementi vengano inseriti all'interno della tabella secondo una particolare strategia. Si suppone di avere a disposizione una funzione chiamata "hash" che applicata ad una chiave "k" restituisce un valore compreso tra 0 e N-1. Se

$$hash(k) = a$$

allora la regola da seguire è che l'elemento con chiave "k" deve essere inserito nella a-esima posizione della tabella (o nella prima posizione libera successiva alla a-esima se questa è già occupata). In questo modo ogni volta che si deve cercare un elemento nella tabella, dato il valore "k" della chiave, si può procedere nel modo seguente: valutando la funzione hash si trova la posizione in cui l'elemento dovrà trovarsi (oppure si dovrà cercare negli elementi successivi). La funzione dovrà essere fatta in modo tale che i suoi valori siano sparsi uniformemente, in modo tale la probabilità che la funzione assuma lo stesso valore per due chiavi diverse sia bassa e in modo che la sua valutazione possa essere fatta velocemente. Una funzione usata solitamente nel caso di chiavi a valori numerici è il resto della divisione intera della chiave per N. In questo modo si ha che anche se non si conosce la posizione di una chiave nella tabella ma solo il suo valore, il tempo di accesso è simile a quello dell'accesso diretto.