Sto provando a scrivere una tabella di hash (perfetta) per comprimere la mappatura da unicode codepoint names to their codepoint number (mappando la seconda colonna alla prima colonna). Come puoi vedere, i possibili input sono molto limitati, infatti ci sono esattamente 38 caratteri nell'alfabeto: AB...YZ, 0...9, - e spazio. Inoltre, c'è un sacco di (stringa) ripetizione, DIGIT ZERO, DIGIT ONE, ..., LATIN CAPITAL LETTER A, LATIN CAPITAL LETTER B eccFunzione di hash efficiente per stringhe alfanumeriche a bassa entropia
La tabella hash perfetta viene calcolata scegliendo un seme S, e poi cercando di costruire una tabella di hash perfetta semina (in qualche modo) l'hasher di S. Se non è possibile creare una tabella, riprova con un nuovo seme. Avere un sacco di collisioni richiede generalmente più tentativi perché è più difficile per l'algoritmo fare tutto in ordine.
Il risultato di questo è il mio dominio di input ha bassa entropia, e la creazione della tabella richiede un sacco di tentativi con semplici funzioni di hash come DJB2; le migliori hash come FNV funzionano abbastanza bene, ma funzioni più complicate e più lente come SipHash sembrano richiedere in media ancora meno tentativi.
Poiché questo è completamente statico e precompilato, non mi preoccupo troppo della qualità per la qualità (vale a dire la sicurezza e la distribuzione probabilistica per input arbitrari in fase di esecuzione non contano), ma le funzioni di qualità superiore riducono il tempo di precomputazione richiesto per un dato livello di compressione, al contrario, mi consente di ottenere una maggiore compressione in un determinato periodo di tempo.
Domanda: ci sono efficienti funzioni di hash pubblicate ottimizzate per l'input con vincoli di dominio come questo? Cioè, ci sono funzioni hash che sfruttano la struttura extra per fare meno operazioni, ma ottenere comunque un risultato ragionevole?
Ho cercato cose come "funzione hash alfanumerico", ma i risultati non sono correlati (in genere si tratta solo di generare una stringa alfanumerica come output di una funzione hash); anche qualche indicazione sul gergo corretto per cercare documenti sarebbe utile.
(Questa domanda è motivata con l'essere un po 'interessante da risolvere, non è effettivamente necessario.)
Vuoi un hash perfetto per 27268 articoli? Sembra difficile per me. Perché non usare solo un hash * standard * e gestire le collisioni? (e forse usa un fattore di riempimento basso) – wildplasser
@wildplasser funziona bene, ci vuole solo un po 'di tempo per generare. Per esempio. [questo array] (https://github.com/huonw/unicode_names/blob/1f331f78201b914604346e1d6fc3e9b3b2eda772/src/generated_phf.rs # L771) è l'hashtable stesso: usa l'hash della stringa di input come indice in quella tabella (e poi verifica che sia corretto). Il punto di questa domanda è sfruttare la struttura dell'input per essere più veloce, facendo meno lavoro possibile. Inoltre, questo è per la compressione, quindi un fattore a basso carico non è buono. – huon
@wildplasser Infine, nota che attualmente sto usando una funzione di hash standard (in realtà ne menziono tre nella domanda). – huon