Newsgroup: it.comp.lang.c++
Titolo: [semi-OT] [ELABORAZIONE STRINGHE] interessante problema funzione di hashing

Devo gestire l'indirizzamento in una tabella hash (HT) di un insieme di
stringhe che mi sta
invogliando a progettare una funzione di hash che non commetta collisioni.
I dati sono questi:
un universo U di stringhe tutte LUNGHE uguali. Supponiamo lunghe 1024 bit
(anche se questa lunghezza
standard per tutte le stringhe potrebbe diminuire ma per adesso non
preoccupiamocene).
Queste stringhe sono SICURAMENTE TUTTE diverse tra loro poichè rappresentano
uno
stato di un automa (diciamo che ci sono 32 variabili lunghe 32 bit nel caso
dei 1024)
Ora a me ne interessa solo un sottoinsieme S di stati di U.
Supponiamo me ne interessino "solamente" 2^24 sull'universo U che |U|=2^1024
La mia tabella hash quindi dovrà indirizzare 2^24 bucket (se voglio un hash
statico
(magari con open addressing ma è da vedere)). (poi ci saranno delle liste di
puntatori ma per ora tralasciamo).
Pensando alla funzione di hash da usare mi è venuta l'idea di evitare le
collisioni dal momento che
so di avere stringhe tutte diverse tra loro.
Di solito il numero delle chiavi sulle quali viene applicata la funzione di
hash è molto più grande della
tabella stessa, ma qui no. Devo costruire una HT esattamente grande 2^24 e
so di avere tutte chiavi diverse.
Non si possono fare previsioni su come siano gli stati (cioè queste stringhe
di 1024 bit) e nemmeno fare
elaborazioni su tali stati. Se ne ottiene uno alla volta e lo si deve
mettere nella HT applicandovi la funzione di hash.
Il problema è abbastanza "combinatorico".
Forse (ma ancora devo vedere se la formalizzazione è esatta) si "riduce" a
trovare una F (iniettiva)
t.c. la seguente affermazione sia vera.(consiglio di riscriversela in
linguaggio algebrico)
    perogni (x1,x2, ... ,xn) appartenente a { {0,1}^32 }^32 esiste un unico
h appartenente {0,...,2^24} t.c. F(x1,..,xn)=h
(credo sia esatto)
rispettando e usando le ipotesi suddette.
Oppure, ancor più generica, anche formulata così:
    perogni X appartente a {0,1}^1024 esiste un unico h appartenente a
{0,...,2^24}t.c. F(X)=h
ma questa si avvicina di più alla definizione di F iniettiva.
Voi mi chiederete: "Cavolo potevi dire solo la ricerca della F?"
Bhè.... la mia è solo una riduzione generalizzata da un problema
particolare. Non è detto che sia esatto o l'unico modo, no?
Io sto pensando di cercare una F... ma working in progress... qualche idea?
Ciao!
P.S. I (Ho inserito anche qui la mia domanda poichè dovrò implementare il
tutto in C/C++)
P.S. II ovviamente non sono gradite analisi di strutture dati che facciano
riducano la "potenza" della hash table
    di qualche ordine di complessità (visto che è O(1) praticamente nulla di

 mettere nella HT applicandovi la funzione di hash.
Se non puoi ridurre euristicamente il sottoinsieme di U alla quale
appartengono gli stati che ti interessano l'unico modo di garantirti
di non avere conflitti e' usare tutta la stringa come chiave. Quindi:
o compi delle assunzioni sugli stati "interessanti" o accetti i
conflitti, e a questo punto ti conviene forse cambiare struttura dati.
Ciao,
Nicola

 Nicola
Ciao, Daniele.

Daniele capisco la tua necessita,
ma partiamo dal fatto che tu debba memorizzare tutta la tabella,
non è possibile data la dimensione, 2^1024
allora passiamo alle stringhe che ti interessano,
2^24 = 16777216 = 16 MB
sarebbe fattibile, ma non c'è alcuna necessità di funzione hash,
in questo caso è solo una perdita di tempo, tu non devi "ricercare" o
"inserire" una stringa,
devi "portarti" o "registrare" la stringa in una posizione già nota
prima che esista...ogni stringa ha già il suo spazio.
mi domando cosa farai quando gli stadi che genera questo automa
diventeranno 2^90 o 2^140,
preferisci memorizzarli e tenerti una cache di stringhe
o li scarti subito e tracci solo un contatore di scarti?
se spiegassi un po' di più questo automa potremmo ridurre la struttura
dove credi sia meglio, ma la vedo dura in partenza.
bye duido

 bye duido
Ciao!

 perchè dovrei?
In ogni caso non ha senso che tu usi una funzione valutata sull'intero
dato per individuare l'indice alla quale e' memorizzato. Tanto vale
che li memorizzi direttamente in ordine e lasci perdere la funzione
hash. Vedi tu se usare una struttura "piatta" tipo vector o una
struttura gerarchica.
Ciao,
Nicola

 trovare una F (iniettiva)
eliminare una parte dell'informazione volendo tenerla tutta?
*praticamente è impossibile.
la perdita di dati è inevitabile con l'evoluzione dell'automa
Consiglio di lasciare la voglia di progettare, la funzione hash,
che come ti ho scritto, non serve, è inutile, la "potenza" che dici è
illusoria.
se attraverso un Universo/n, sei "sempre" capace di generare un
Universo...
se attraverso una parte delle informazioni, sei "sempre" capace di
ricavarne di complete...
dovremmo parlarne più a lungo di questo ma forse il NG non è il posto
più adatto.
se fosse solo un gioco la difficolta nell'implementare una automa che
generi l'evoluzione di un oggetto è scelto e implementato dal
programmatore visto che non considera il ritorno allo stadio
originale.
bye duido

 Nicola
Ciao!

 bye duido
Ciao!

 Se devo cercare tra 10^7 stati come faccio???
Una bella ricerca dicotomica. Almeno non avrai calcolato la tua
funzione hash con 1024 bit di argomenti 10^7 volte.
Ciao,
Nicola