Version imprimable
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 :
Merci ;)Code:
2
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.
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 :).
Donc, les méthodes de compression lossless n'existent pas ? :)Citation:
Envoyé par ram-0000
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.Citation:
Envoyé par Emmanuel Deloget
Voui :) Je suis taquin, c'est tout :)Citation:
Envoyé par ram-0000
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.
Citation:
Envoyé par zeldomar
Au risque d'être "taquin", une collision (même si c'est un risque) implique une non-unicité de la clé.Citation:
Envoyé par Emmanuel Deloget
Roooh !Citation:
Envoyé par ram-0000
Mais ça suffit la taquinseté !
:)
La compression lossless à taux fixe (ici, 1/4) n'existe pas.Citation:
Envoyé par Emmanuel Deloget
Voui, ça, je sais; je viens même de le prouver :)Citation:
Envoyé par Médinoc
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.