Discussion :

[zeldomar]

Bonjour à tous,

J'aimerai construire une clé entière (int,long...) unique à partir de 4 int, quelqu'un aurait-il une idée d'algorithme pour arriver à cela ?

Exemple de prototype :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
int GenerateUniqueKey( int a, int b, int c, int d) ;

Merci

[ram-0000]

Tel que c'est demandé, c'est impossible.

Tes 4 paramètres sont composés de 4 int donc 128 bits (4 X 32 bits) et ta sortie (un int) fait 32 bits. Il n'est pas possible de générer une clé unique de 32 bits avec des données 128 bits, il y aura obligatoirement des collisions.

Ceci dit, tes 4 paramètres sont peut être des int mais leur domaine de variation n'est peut être pas sur 32 bits. Il va donc d'abord falloir que tu décrives un peux mieux ces paramètres et toutes les range de valeurs qu'ils peuvent prendre.

[LittleWhite]

Bonjour,

Si c'est le cas de la conversion 4 char (4 * un octet) en 1 int (1 * octets) cela a déjà était demandé (et même très récemment) sur le forum. Veuillez faire une recherce .

[Emmanuel Deloget]

Tel que c'est demandé, c'est impossible.

Tes 4 paramètres sont composés de 4 int donc 128 bits (4 X 32 bits) et ta sortie (un int) fait 32 bits. Il n'est pas possible de générer une clé unique de 32 bits avec des données 128 bits, il y aura obligatoirement des collisions.

Ceci dit, tes 4 paramètres sont peut être des int mais leur domaine de variation n'est peut être pas sur 32 bits. Il va donc d'abord falloir que tu décrives un peux mieux ces paramètres et toutes les range de valeurs qu'ils peuvent prendre.

Donc, les méthodes de compression lossless n'existent pas ?

[ram-0000]

Donc, les méthodes de compression lossless n'existent pas ?

Bien sûr que si. Mais tel que demandé et sans précision sur le domaine de variation des 4 paramètres, la compression la plus efficace est un nombre de 128 bits, c'est la concaténation des 4 paramètres.

[Emmanuel Deloget]

Bien sûr que si. Mais tel que demandé et sans précision sur le domaine de variation des 4 paramètres, la compression la plus efficace est un nombre de 128 bits, c'est la concaténation des 4 paramètres.

Voui Je suis taquin, c'est tout

La question originale impliquerait effectivement de trouver une fonction bijective de S(128bits) vers S(32bits), qui n'existe effectivement pas - vu la cardinalité des deux ensembles. On peut le démontrer par l'absurde: si une telle fonction existait, elle pourrait être utilisée pour passer de S(32) à S(8), puis de S(8) à S(2), puis de S(2) à 0 ou 1 (=S1/2). Par extension, il existerait donc une fonction bijective S(2^2^n) => S(1/2). Etant bijective, la fonction inverse permet d'obtenir n'importe quelle valeur de S(2^2^n), quelque soit n, à partir de l'ensemble S(1/2) considéré. Hors S(1/2) est un ensemble discret composé d'un unique élément, et par définition, une fonction x => f(x) associé à x une unique valeur. Donc si cette fonction existe, alors S(2^2^n), qui contient 2^2^2^n éléments, contient 1 seul élément. Les deux propositions étant en conflit, la fonction ne peut exister.

Est-ce que j'ai été clair ?

Ceci dit, il y a des algorithmes de hachage qui sont relativement performant et minimisent les risques de collision (cf. http://www.partow.net/programming/hashfunctions/). Ensuite, il y aussi des algos de compression (à base de dictionnaires, comme Huffman) qui peuvent permettre d'obtenir l'effet désiré si le domaine de variation des 4 paramètres n'est pas trop important. Si certaines propriétés sont respectées (par exemple, on a très souvent beaucoup de 0 ou de 1 à la suite), d'autres méthodes de compression peuvent être utilisées.

[ram-0000]

J'aimerai construire une clé entière (int,long...) unique à partir de 4 int

Ceci dit, il y a des algorithmes de hachage qui sont relativement performant et minimisent les risques de collision.

Au risque d'être "taquin", une collision (même si c'est un risque) implique une non-unicité de la clé.

[Médinoc]

Donc, les méthodes de compression lossless n'existent pas ?

La compression lossless à taux fixe (ici, 1/4) n'existe pas.

[Emmanuel Deloget]

La compression lossless à taux fixe (ici, 1/4) n'existe pas.

Voui, ça, je sais; je viens même de le prouver

Je réagissait à ce que je croyais avoir lu, à savoir quelque chose dans le style "pour stocker 4 entiers de 32 bits, il te faut nécessairement 128 bits". Mais je m'ai trompé d'oeil ou de cerveau.