Fonction qui propage l'entrée

14

Je voudrais savoir s'il existe une fonction des nombres à n bits aux nombres à n bits qui présente les caractéristiques suivantes:f

  • f doit être bijectif
  • Les deux et devrait être assez rapide calculableff1
  • f doit renvoyer un nombre qui n'a pas de corrélation significative avec son entrée.

La justification est la suivante:

Je veux écrire un programme qui fonctionne sur des données. Certaines informations des données sont stockées dans une arborescence de recherche binaire où la clé de recherche est un symbole d'un alphabet. Avec le temps, j'ajoute d'autres symboles à l'alphabet. Les nouveaux symboles obtiennent simplement le prochain numéro gratuit disponible. Par conséquent, l'arborescence aura toujours un petit biais vers des touches plus petites, ce qui provoque un rééquilibrage plus important que je ne le pense.

Mon idée est de réduire les nombres de symboles avec telle sorte qu'ils soient largement répartis sur toute la plage de . Étant donné que les numéros de symbole n'ont d'importance que lors de l'entrée et de la sortie, ce qui ne se produit qu'une seule fois, l'application d'une telle fonction ne devrait pas être trop coûteuse.[ 0 , 2 64 - 1 ]f[0,2641]

J'ai pensé à une itération du générateur de nombres aléatoires Xorshift, mais je ne connais pas vraiment un moyen de l'annuler, bien que cela devrait théoriquement être possible.

Quelqu'un connaît-il une telle fonction?
Est-ce une bonne idée?

FUZxxl
la source
1
Je ne suis pas un expert, mais vous pouvez peut-être utiliser une permutation pseudo-aléatoire (voir par exemple le chiffrement Feistel )
Vor
Si vous calculez essentiellement une fonction de hachage, pourquoi ne pas utiliser le hachage?
vonbrand
@vonbrand Hashing n'est pas réversible. Voir exigence numéro 2.
FUZxxl
Pourquoi doit-il être réversible? Quel est le problème avec le rendre réversible par recherche?
vonbrand
1
Vous pouvez stocker (f (x), x) sous forme de clés.
adrianN

Réponses:

6

Vous pouvez utiliser le hachage de Fibonacci , à savoir

.hF(k)=k512k512

Pour vous obtenez n nombres distincts par paires (environ) répartis uniformément dans [ 0 , 1 ] . En mettant à l'échelle [ 1 .. M ] et en arrondissant (vers le bas), vous obtenez des nombres répartis uniformément dans cet intervalle.k=1,,nn[0,1][1..M]

Par exemple, ce sont mis à l'échelle [ 0..10000 ] (séquence d'origine gauche, trié à droite):hF(1),,hF(200)[0..10000]

entrez la description de l'image ici

Ceci est un exemple de ce que Knuth appelle le hachage multiplicatif . Pour la taille du mot de l'ordinateur, un certain entier relativement premier à w et M le nombre d'adresses nécessaires, nous utilisonswAwM

h(k)=M((kAw)mod1)

comme fonction de hachage. Ce qui précède suit avec (assurez-vous de pouvoir le calculer avec une précision suffisante). Bien que cela fonctionne également avec tout autre nombre irrationnel en plus deϕ-1, c'est l'un des deux seuls nombres qui conduisent aux nombres "les plus uniformément répartis".A/w=ϕ1=512ϕ1

Pour en savoir plus, consultez L'art de la programmation informatique , volume 3 de Donald Knuth (chapitre 6.4 à partir de la page 513 de la deuxième édition). En particulier, vous découvrirez pourquoi les nombres résultants sont distincts par paires (au moins si ) et comment calculer la fonction inverse si vous utilisez A et w naturels au lieu de ϕ - 1 .nMAwϕ1

Raphael
la source
1
Comment calculer efficacement ? f1
frafl
1
@frafl J'espère que ma modification répond quelque peu à votre préoccupation. Il est clair, cependant, que ces techniques de hachage ne sont pas spécialement conçues pour être efficacement inversibles.
Raphael
Oui, je vais le voter, mais je ne le recommanderais pas comme réponse acceptée.
frafl
1

Pour les entrées bits, cette fonction fonctionne:k

hash(n)=(nmod2k2)2k2+ndiv2k2

Ceci est réversible, en ce que , et a des paires non séquentielles { n , m } , n < m , où h a s h ( m ) < h a s h ( n ) . Attention, la sortie et l'entrée peuvent être corrélées, surtout si votre entrée est en { 1 , , 2 khash(hash(n))=n{n,m},n<mhash(m)<hash(n).{1,,2k21}

Réf: Fonction de hachage réversible

Reza
la source
Cela semble simple et agréable. Je vais tester celui-là.
FUZxxl
1
1ρ
c'est assez clair! pour 64 bits (0x00000000FFFFFFFF) et vous devez décaler (<<) 32 bits. Cette fonction est simple, pratique et assez rapide en pratique.
Reza
1
x{1,,2321}232x