Classe Dizionario

posted by Viralex | 03-Oct-2007 1:06

Ho inserito la classe dizionario nella sezione downloads.
Questa classe fa parte del progetto Leda, il gioco del paroliere.
Anche Leda si trova nella sezione downloads, è stato sviluppato con le librerie grafiche allegro e contiene un ottimo esempio di backtracking su tabella.

La struttura della classe dizionario è una combinazione tra un Hash e una serie di alberi binari di ricerca.
La funzione hash genera tutti gli indirizzi di un array di 26^3 elementi (17753), corrispondenti a tutte le possibili combinazioni di tre lettere.
Ogni cella di questo array è un puntatore alla radice di un albero binario di ricerca che contiene tutte le parole che hanno il prefisso indicato dalla posizione dell'array. Ovviamente per risparmiare memoria le parole negli alberi sono state private del prefisso poichè lo sappiamo ricostruire a seconda dell' indice in cui ci troviamo.
Ad esempio la cella 0 contiene tutte le parola che iniziano per 'aaa' la cella 1 'aab' e così via.

Quando inseriamo o cerchiamo un elemento c'è un accesso diretto O(1) allo spazio delle soluzioni che hanno un certo prefisso. Successivamente si ha un tempo di ricerca ed inserimento logaritmico rispeto al numero di elementi O(log n)
Non ho implementato la funzione che cancella un elemento perchè non era necessaria per il progetto che dovevo svolgere. E' presente il distruttore che elimina tutta la struttura.

Il Leda carica in pochi secondi un dizionario di 600'000 parole in circa 26MB di memoria ram. La ricerca è istantanea.

Potete usare/modificare la classe a vostro piacimento, basta che citiate nel programma.

Altre possibili implementazioni sono: l'utilizzo di opportuni alberi generici (figlio-fratello). se si applica direttamente occupa moltissima memoria. forse è meglio farlo per sillabe o gruppi di lettere.
Un'altra idea che ho avuto è quella di generare un grafo che contenga tutti e soli i percorsi di ogni parola.

commentate e/o ite la vostra se avete esperienza in questo campo.

Viralex