Discussion :

[Benoit_T]

Bonjour,


Je cherche à résoudre le problème suivant, il peut paraître surprenant mais je ne peux le contourner d'aucune manière.

Je dispose de n fichiers, n<2048 dont le nom est limité à 12 caractères quelconques.

Je cherche à générer pour chacun de ces fichiers un identifiant unique, entier numérique, contenu sur 16 bits.

En fait le problème revient à déterminer pour l'ensemble des n nom de fichier, une fonction de hachage me donnant un identifiant unique et différent pour chaque nom de fichier.

f(fichier_1) = n1, f(fichier_2) = n2 ..., f(fichier_nb_fichiers) = n_nb_fichiers...

avec pour tout i, j, i différent de j, f(fichier_i) != f(fichier_j)

Intuitivement je dirais que c'est possible. Avez-vous une approche à me suggérer car je seche sur ce problème et mes recherches n'ont pas aboutie.

Je pourais y aller en force brute et tester des hachages paramétrés jusqu'à ne plus avoir de collision mais ça n'est guère esthétique...

Cordialement,

[pseudocode]

On appelle cela une fonction de hash parfaite (http://en.wikipedia.org/wiki/Perfect_hashing), c'est à dire sans collisions.

Sur la page de wikipedia, tu as une liste de logiciels qui génèrent des fonctions de hash parfaites pour un ensemble donné.

[Mac LAK]

Un bête et méchant CRC16 du nom ne pourrait-il pas résoudre ton problème ?

Après, tu auras forcément des collisions : même en se limitant à 26 lettres (et donc sans les chiffres), ton espace de noms est de cardinalité 26^12, soit 95.428.956.661.682.176 noms possibles... Tu as donc forcément une surjection stricte entre tes noms et ton identifiant 16 bits !!!

Certes, on peut associer sans problèmes chaque nom de fichier à un identifiant unique, de par l'hypothèse n<2048 que tu poses. D'un point de vue strict, j'aurais tendance à lister les fichiers et à leur coller un numéro incrémental à chacun, chaque numéro correspondant à l'entrée d'un vecteur de noms, ce qui permet d'avoir une LUT immédiate entre ce numéro "haché" et le nom du fichier. Dans l'autre sens, c'est plus complexe, mais un bon petit vecteur trié et une recherche dichotomique devrait te permettre de limiter la casse.

Bien sûr, si ta liste de fichiers est figée, c'est plutôt facile de trouver une fonction de hachage qui corresponde. Si la liste évolue dans le temps, c'est mal barré.