Tabella di Hash per indicizzazione dizionario - How To in C

Pubblicità
FazzoMetal

FazzoMetal

Utente Attivo
Messaggi
1,262
Reazioni
85
Punteggio
48
Salve a tutti.
Per un progetto relativo al corso di programmazione avanzata che sto seguendo in questi mesi devo sviluppare un programma che, per vari fini, deve essere in grado di scorrere molto rapidamente l'intero dizionario italiano al fine di verificare la presenza di alcune parole.
Mi viene richiesto di fare tutto ciò il più velocemente possibile, impiegando non troppa memoria, in C.
Io ho subito pensato di costruirmi un hash table in modo tale da poter utilizzare una funzione di hash per verificare, in maniera quasi immediata, la presenza o meno di una parola nel dizionario evitando di doverlo scorrere tutto.
Essendo il programma da sviluppare molto più grande e corposo di quanto descritto fin'ora, mi chiedevo se conoscete delle buone guide da seguire per implementare qualcosa del genere: essendo un problema abbastanza comune magari potrei anche trovare qualche esempio di soluzione.
Avete qualche consiglio in particolare da darmi? Credete che la strada della hash table sia quella giusta?
Grazie in anticipo
 
La hash table è una buona idea, a patto di definire un algoritmo di hashing che minimizzi le collisioni.
Per quanto riguarda la memoria, dipende da cosa intendi per "tanto" o "poco". L'intero dizionario italiano (suppongo circa 150k parole) penso occupi dai 10 ai 15MB memorizzato come sequenze di char.
Il problema viene con l'implementazione della tabella, ovviamente più spazio hai e meno collisioni si hanno: se idealmente avessi un array di chiavi senza collisioni, il tempo di accesso sarebbe unitario, e di conseguenza il lookup si approssimerebbe al tempo di hashing per generare la chiave.
Il primo punto è dunque capire quanti bucket devi avere e quale algoritmo hash utilizzare per minimizzare le collisioni e lo spazio occupato.
Il secondo punto è come gestire le collisioni. Potresti associare ad ogni bucket (chiave) una lista, quindi usi una semplicissima struttura che contenga la parola del dizionario e il puntatore all'eventuale successiva parola con stesso hash.
Intanto proverei a vedere empiricamente se algoritmi noti come MD5 e SHA1 possono essere utili, ovviamente l'hash generato va troncato a un numero di bit ragionevole.
 
Allora, riguardo la memoria preciso subito che sarebbe preferibile usarne un pò di più se questo porta a significativi vantaggi prestazionali in termini di tempi di esecuzione. Credo che allocare 15 20Mb non sia assolutamente un problema.
Riguardo eventuali collisioni derivanti dall'hashing non perfetto (che è inevitabile a quanto ne so) avevo pensato anche io alla gestione tramite liste: è più complicato rispetto altri metodi ma probabilmente è il più veloce.
Per la funzione di hash mi tornerebbe davvero utile averne una capace di generare una tabella di hash che mantenga lo stesso ordine del dizionario, in modo tale che,ad esempio, con hash(CI) si possa puntare lo spazio dove sono memorizzate tutte le parole che iniziano per "CI". Con hash di "CIA" affinare la ricerca ecc ecc. Con hash(CIAO) puntare la singola parola "CIAO".Chiedo scusa per la spiegazione un pò grezza. Secondo te è fattibile?
 
FazzoMetal ha detto:
Allora, riguardo la memoria preciso subito che sarebbe preferibile usarne un pò di più se questo porta a significativi vantaggi prestazionali in termini di tempi di esecuzione. Credo che allocare 15 20Mb non sia assolutamente un problema.
Riguardo eventuali collisioni derivanti dall'hashing non perfetto (che è inevitabile a quanto ne so) avevo pensato anche io alla gestione tramite liste: è più complicato rispetto altri metodi ma probabilmente è il più veloce.
Per la funzione di hash mi tornerebbe davvero utile averne una capace di generare una tabella di hash che mantenga lo stesso ordine del dizionario, in modo tale che,ad esempio, con hash(CI) si possa puntare lo spazio dove sono memorizzate tutte le parole che iniziano per "CI". Con hash di "CIA" affinare la ricerca ecc ecc. Con hash(CIAO) puntare la singola parola "CIAO".Chiedo scusa per la spiegazione un pò grezza. Secondo te è fattibile?
Clicca per espandere...
Fattibile, ma complica un po' le cose...
Perchè allora a te serve una struttura dati che sia anche ordinata... Una hash table non è fatta per essere ordinata, o più precisamente, non è fatta per essere ordinata sui valori ma solo sulle chiavi (gli hash dei valori).
Tra l'altro non c'è nessuna relazione tra hash di "C", hash di "CI" e hash di "CIA".
Se volessi aggiungere questa funzionalità, dovresti implementare una struttura ibrida tra hash table e linked list. Per il lookup di valori non cambierebbe nulla, per la ricerca delle parole con un certo prefisso invece si sfrutta la linked list, ma in questo caso devi scorrere sequenzialmente il dizionario. Infatti se nel dizionario italiano non ci fosse la parola "CIA", l'hash di "CIA" non avrebbe nessuna corrispondenza nella mappa.
E anche se ci fosse la parola "CI", il suo hash non è per niente detto che sia in qualche modo "vicino" a tutte le parole che iniziano per "CI", anzi molto probabilmente sarà distante, come è bene che sia per ogni buon algoritmo di hashing.
Per questo ti serve una struttura a lista, la quale però ha accesso sequenziale e quindi complessità O(N)

Alternativamente cambi totalmente struttura e usi un albero ordinato di ricerca, che avrà una complessità di lookup O(logN) e sarà ordinato.
 
1nd33d ha detto:
Fattibile, ma complica un po' le cose...
Perchè allora a te serve una struttura dati che sia anche ordinata... Una hash table non è fatta per essere ordinata, o più precisamente, non è fatta per essere ordinata sui valori ma solo sulle chiavi (gli hash dei valori).
Tra l'altro non c'è nessuna relazione tra hash di "C", hash di "CI" e hash di "CIA".
Se volessi aggiungere questa funzionalità, dovresti implementare una struttura ibrida tra hash table e linked list. Per il lookup di valori non cambierebbe nulla, per la ricerca delle parole con un certo prefisso invece si sfrutta la linked list, ma in questo caso devi scorrere sequenzialmente il dizionario. Infatti se nel dizionario italiano non ci fosse la parola "CIA", l'hash di "CIA" non avrebbe nessuna corrispondenza nella mappa.
E anche se ci fosse la parola "CI", il suo hash non è per niente detto che sia in qualche modo "vicino" a tutte le parole che iniziano per "CI", anzi molto probabilmente sarà distante, come è bene che sia per ogni buon algoritmo di hashing.
Per questo ti serve una struttura a lista, la quale però ha accesso sequenziale e quindi complessità O(N)

Alternativamente cambi totalmente struttura e usi un albero ordinato di ricerca, che avrà una complessità di lookup O(logN) e sarà ordinato.
Clicca per espandere...

Sono d'accordissimo con te quanto dici che in realtà mi servirebbe qualcosa di più di un hash table. Mi servirebbe una struttura mista in realtà. Il punto è che devo realizzare (in 1 mese di tempo residuo :/) una specie di RUZZLE solver: partendo da una matrice pseudo casuale di lettere devo trovare tutte le possibile parole al suo interno. Utilizzando una hash table pura potrei cercare velocemente una parola nel dizionario, avendo però anche a disposizione una struttura sequenziale però potrei ridurre il carico di lavoro: percorrendo un percorso sulla matrice, se mi accorgessi che la parola CI non trova corrispondenze nel dizionario, potrei allora evitare di continuare sul percorso seguito (non avrebbe senso cercare CI-XXX se CI non esistesse nel dizionario, ovviamente).
Una struttura completamente sequenziale, d'altro canto, renderebbe eccessivamente lento il software. Il punto è che non ho molta praticità nel cercare di mettere in piedi una struttura mista.
Riguardo gli alberi, purtroppo sono anche quì poco pratico (sono un elettronico in realtà) e non ho neanche idea di come si potrebbero sfruttare.

- - - Updated - - -

Praticamente mi servirebbe qualcosa che, cercato un insieme di lettere, ad esempio CIA, mi dica velocemente se nel dizionario è presente la parola CIA o se sono presenti parole che iniziano con CIA. In questo modo non solo saprei se la parola che sto analizzando esiste o meno, ma potrei anche evitare di continuare ad aggiungerle alla ricerca di una parola più lunga con la stessa radice. Mi sbaglio?
 
Se posso dire la mia non penso sia necessario indicizzare tutte le parole bensì un numero ragionevole di modo che al più la ricerca "lenta" avvenga entro un elenco limitato di parole.
Provo a fare un esempio:
- Lista di N parole ordinate.
- Indicizzo una parola ogni N\M tramite una tabella di hashing, magari.
- Quando cerco la mia parola cerco l'intervallo in cui lavorare solo con le 10ime parole.
- Al più dovrò scorrere le (N\M)-1 parole tra i miei limiti.

Non avrò una ricerca velocissima come se avessi un hash per ciascuna ma non mi vado ad "intasare" la memoria -> "impiegando non troppa memoria" cit.
Penso che sia questa la mediazione da fare tra velocità e memoria occupata.
 
Kappa27 ha detto:
Se posso dire la mia non penso sia necessario indicizzare tutte le parole bensì un numero ragionevole di modo che al più la ricerca "lenta" avvenga entro un elenco limitato di parole.
Provo a fare un esempio:
- Lista di N parole ordinate.
- Indicizzo una parola ogni N\M tramite una tabella di hashing, magari.
- Quando cerco la mia parola cerco l'intervallo in cui lavorare solo con le 10ime parole.
- Al più dovrò scorrere le (N\M)-1 parole tra i miei limiti.

Non avrò una ricerca velocissima come se avessi un hash per ciascuna ma non mi vado ad "intasare" la memoria -> "impiegando non troppa memoria" cit.
Penso che sia questa la mediazione da fare tra velocità e memoria occupata.
Clicca per espandere...

Sono felice di avere anche la tua opinione, ho scritto sul forum appositamente :)
Il tuo discorso non è certo sbagliato, in questo modo andrei ad avere una lettura comunque sia veloce senza però caricare in memoria un mega albero con sopra memorizzato, stratificato, l'intero dizionario di italiano.

Nel frattempo, comunque sia, avevo avuto un'altra idea: pensavo di lasciare il dizionario nel suo file di origine, e di leggerlo semplicemente una parola alla volta. Man mano che leggo una parola la salvo in una stringa temporanea e vado a cercarla nella scacchiera. La cerco, però, in modo intelligente. Mi spiego meglio: invece di lanciare una funzione ricorsiva in "forza bruta" andando a checkare tutte le combinazioni, potrei pensare una funzione ricorsiva intelligente. Tale funzione potrebbe controllare ad ogni step se vale la pena continuare la ricerca o no. Poniamo che stia cercando MAMMA. Se la funzione ricorsiva ha già trovato MA e, in nessuna casella adiacente all'ultima A trova un'altra M, allora è inutile continuare la ricerca che si può interrompere o come minimo indirizzare su un percorso con direzione diversa.
In questo modo dovrei risparmiare davvero tanto tempo rispetto al metodo brute force e praticamente non utilizzo memoria.
Cosa ne pensate?
 
FazzoMetal ha detto:
Sono felice di avere anche la tua opinione, ho scritto sul forum appositamente :)
Il tuo discorso non è certo sbagliato, in questo modo andrei ad avere una lettura comunque sia veloce senza però caricare in memoria un mega albero con sopra memorizzato, stratificato, l'intero dizionario di italiano.

Nel frattempo, comunque sia, avevo avuto un'altra idea: pensavo di lasciare il dizionario nel suo file di origine, e di leggerlo semplicemente una parola alla volta. Man mano che leggo una parola la salvo in una stringa temporanea e vado a cercarla nella scacchiera. La cerco, però, in modo intelligente. Mi spiego meglio: invece di lanciare una funzione ricorsiva in "forza bruta" andando a checkare tutte le combinazioni, potrei pensare una funzione ricorsiva intelligente. Tale funzione potrebbe controllare ad ogni step se vale la pena continuare la ricerca o no. Poniamo che stia cercando MAMMA. Se la funzione ricorsiva ha già trovato MA e, in nessuna casella adiacente all'ultima A trova un'altra M, allora è inutile continuare la ricerca che si può interrompere o come minimo indirizzare su un percorso con direzione diversa.
In questo modo dovrei risparmiare davvero tanto tempo rispetto al metodo brute force e praticamente non utilizzo memoria.
Cosa ne pensate?
Clicca per espandere...

Non mi sembra malvagia neanche la tua idea, mi spieghi meglio però la parte in grassetto?
La tua soluzione però non utilizza una "tabella" di hashing e sei sicuro che non vada usata? Hai avuto qualche "indizio" dal docente riguardo alla migliore strada da seguire?
 
No purtroppo il docente non ci ha detto molto.
Utilizzando la tabella di hash occuperei spazio in memoria e creerei una struttura complessa non avendo comunque a disposizione una ricerca progressiva.
Per implementare la ricerca progressiva su parole e parole con stessa radice dovrei utilizzare un albero, il che porterebbe via ancor più memoria e creerebbe una struttura dati virtuale ancor più complessa.

Io pensavo di memorizzare nella memoria del programma unicamente 1 parola alla volta del dizionario. Accedo al dizionario-->leggo la parola iesima-->salvo la parola iesima in una variabile temporanea per comodità (che utilizzerò anche per tutte le altre parole che leggerò sequenzialmente)-->avvio la ricerca intelligente in scacchiera, verificando ad ogni step che ci sia effettivamente un senso nella ricerca in corso.
 
Ma qual è il problema dell'albero? Usa un maledetto albero di ricerca k-ario e vai con Dio. Non è pesante come pensi tu. Non per dei dati così semplici - nel senso di pochi. Ciao.

- - - Updated - - -

Fra parentesi lo puoi bilanciare ed ottimizzare per la ricerca. Potresti addirittura fare una struttura n-tomica, con un albero per ogni lettera (in modo da risparmiare memoria ed essere veloce). Inoltre puoi fare accesso simultaneo tramite i threads etc etc

Gli alberi ti svoltano la vita :sisi:
 
Anche secondo me conviene usare un albero a questo punto, finchè si trattava di massimizzare le prestazioni di lookup, l'hash table era ideale.
Per aggiungere una relazione d'ordine sarebbe bastato ibridare l'albero con una lista ordinata (tra l'altro ho visto che c'è una classe delle API Java che implementa questa struttura, quindi non è una cosa così strana).
Se però vuoi anche la funzione di autocompletamento, no, conviene cambiare struttura e passare a un albero.
Una struttura che ti permette il lookup in tempo O(m) con m=numero caratteri della stringa indipendentemente dal numero di parole del dizionario è per esempio un albero Trie (trovi anche delle implementazioni nel web). L'unico dubbio è lo spazio che va ad occupare una simile struttura, considerando che deve esserci un nodo per ogni prefisso di parola (una stringa di lunghezza m richiede quindi m nodi, che possono essere condivisi con altre stringhe o no).
 
L'albero, anche se semplice, andrebbe ad occupare diversi MB di memoria: dovrei creare un albero per ogni lettera (26 alberi, dalla a alla z), ognuno avete come figli tutte le parole di 2 lettere che iniziano con la lettera radice, al livello sottostante esplodere tutte le parole di 3 lettere ecc ecc.
Posso usare solo il C e mi viene valutato sia il tempo di esecuzione che la memoria occupata: ci vorrebbe del tempo per creare e riempire l'albero e dei MB andrebbero occupati in memoria.
Facendo come ho spiegato su non userei memoria ed i tempi dovrebbero essere accettabili: anche se in modo differente, userei un algoritmo intelligente che non andrebbe brutalmente a provare tutti i percorsi.
Usando un albero il tempo sarebbe sicuramente molto più breve, ma la memoria occupata molta di più.
Leggendo questo articolo mi stavo convincendo che potessi fare a meno di qualsiasi struttura
Algoritmo del Ruzzle Solver
La tabella riassuntiva sembra appoggiare il ragionamento che stavo portando avanti.
Cosa ne dite?
 
Secondo me un approccio a programmazione dinamica è sicuramente migliore di uno a forza bruta - che se fossi un professore boccerei a prescindere.
Credo anche che tu non sappia quanto pesa un albero, che è veramente poco. Per darti una idea un albero che ho usato che aveva 25^25 nodi (leggermente di più di quello che servirebbe a te che è 24^24 in partenza, ma puoi scremare con un minimo di ottimizzazione) pesava poco più di 20mb.
Per altro se avessi studiato qualcosa di algoritmi sapresti che gli alberi sono ottimizzati ed efficienti, che puoi bilanciarli, che puoi comprimerli, che sono facili da gestire ed estremamente leggeri sia nella generazione che in memoria, al contrario dell'algoritmo che hai pensato tu, che non è stato ottimizzato dagli ultimi 70 anni di informatica teorica.
Comunque, fai come credi, anche se mi sa che una tabella hash - come il tuo algoritmo, che massimizza il numero di accessi e conversioni in memoria - è decisamente più pesante, sia dal punto di vista computazionale che dal punto di vista delle dimensioni in memoria.
 
Ultima modifica da un moderatore:
Io non capisco dove sia la pesantezza della mia soluzione: mi esprimo meglio.
Faccio all'inizio un controllo sulla scacchiera: ci sono 16 posti, nel worst case ho 16 lettere differenti-->posso già escludere 10/26 di dizionario dato che non vado neanche a cercare le parole che iniziano con lettere non contenute in scacchiera.
Per il resto scorro il dizionario (senza salvarlo da nessuna parte) e, quando sono in presenza di una parola che inizia con una delle 16 lettere presenti in tabella, chiamo la funzione ricorsiva che non sarà una brute force. Ci saranno dei controlli step to step che la renderanno enormemente più efficiente di una brute force.
Es: cerco CASA. Chiamo la funzione cerca sulla prima casella: è C? No. Bene vado avanti senza cercare alcun chè. Trovo una C in un'altra casella: ho una A in posizione adiacente? No-->non cerco neanche / Si--> mi sposto sulla casella dove c'è la A e controllo se c'è una S. Se non c'è termino la ricerca. Non andrò a fare una brute force che ogni volta calcola tutti i possibili percorsi in scacchiera.
Facendo in questo modo la memoria occupata è trascurabile rispetto ai 15MB circa che ci andrebbero per l'albero (non userei nemmeno 500KB), eviterei molte operazioni (e quindi tempo) legate alla creazione dell'alberlo ed all'allocazione della memoria ad esso destinata e farei poche ricerche, solo quelle necessarie, che dovrei fare comunque sia anche se avessi un albero.
Mi spiegheresti gentilmente perchè credi che questa soluzione (che mantiene tempi accettabili, considerando anche il tempo che ci vorrebbe a creare l'albero, e consumando quasi zero memoria) non sia competitiva?
Grazie in anticipo
 
Ultima modifica:
Pubblicità
Pubblicità
Indietro
Top