Funzioni Hash e motori di ricerca

gik25

Funzioni Hash e motori di ricerca

Dunque, molti di voi sanno che se devo "giocare" con un database di grosse dimensioni un primo passo per ridurlo è quello di sostituire le parole con dei numeri.

Es. cane -> 1

Questo può essere fatto con una ricerca su DB, ma richiede un accesso al DB per ciascuna parola (accesso all'hard disk in molti casi, il che significa un rallentamento notevole)

Oppure si può usare una funzione hash ottenendo di rappresentare ogni parola con poche lettere.

Tuttavia mi sono reso conto che c'è una terza possibilità: sfruttare i 64 bit dei processori moderni per creare un hash binario a 64 bit che sia gestito come un unico numero.
Quante sono le parole italiane? Beh, 64 bit permettono di salvare 2^64 parole. Ovvero 18. 446.744.073. 709.551.616 = 18 miliardi di miliardi di combinaizioni. Fate conto che basterebbero processori a 32 bit ;).

Proseguendo col ragionamento mi sono domandato cosa fare con gli altri 32 bit e mi sono venute in mente almeno due possibilità:

salvare più parole in un solo campo a 64 bit
costruire una hash reversibile

La seconda cosa, qualora risultasse fattibile, significherebbe una tecnica di compressione eccezionalmente veloce, adatta alla ricerca full text, e permetterebbe di salvare un db in meno spazio.

es. HashReverse(1 5 6 7 9 15) -> il mio cane va al mare.

Per chi non ha capito il vantaggio mettiamola cosi:
"parola1" occupa 7 byte memorizzata come stringa (ogni byte = 8 bit => 56 bit). Ci sono tot mila parole (es. 100000), considerandone 10 volte tante la stessa informazione può essere memorizzata con Log(1000000)/Log(2) bit = 20 bit. Se si utilizza il codice di Huffman probabilmente si può ridurre ancora, e se lo si applica a più parole si comprime ancora di più. Il vantaggio oltre al risparmio di spazio e l'aumento di velocità potrebbe derivare dalle possibilità di ricerca full text (2 - 3 lettere), facilità di creazione di indici, creazione di DB per il confronto tra parole...