Discussion :

[Mr_Chut]

Bonjour!

Alors voilà, je suis en train chercher un algo intelligent pour coder une chaine de caratere en un unique entier, de telle sorte que deux string differentes n'est jamais le meme code.

Par exemple "ab" ne doit pas avoir le meme code que "ba".

J'avais eu l'idée de coder de la sorte:
"abc..." = (code_ascii a)*2^0 + (code_ascii b)*2^1 + (code_ascii c)*2^2 + ....

mais le pb est que des que la chaine est trop grande, ca dépasse la capacité d'un entier, qui est limité à 31bits (en ocaml)
Existe t il un autre moyen d'associer un unique entier (pas trop grd) à une chaine?

merci d'avance!

[nicolas581]

Il faut que tu trouves une fonction injective de l'ensemble des chaînes dans l'ensemble des entiers.
- La fonction que tu proposes n'est pas une injection en effet la chaîne formée des caractères ascii "\10\10" a pour valeur 10+100 soit 110 et la chaîne réduite à "\110" a aussi comme valeur 110.
- Une fonction injective si on limite à de l'ascii sur 7bits serait x0*128^0 + x1*128^1 + x2*128^2 mais cette fonction va rapidement retournée des valeurs supérieures à 2^31
- Je ne sais pas s'il existe une fonction simple injective qui permettrait cette transformation.
- As-tu besoin d'une fonction injective ? Ton problème ressemble au choix d'une fonction de hachage idéale.
Quelques liens sur les tables de hachage :
http://ciips.ee.uwa.edu.au/~morris/Y...sh_tables.html avec une applet java pour bien comprendre.
http://fr.wikipedia.org/wiki/Table_de_hachage
http://en.wikipedia.org/wiki/Hash_table

[Médiat]

2^31 = 2 147 483 648
Si tu limites ton alphabet à 27 lettres (+ espace), donc sans prendre en compte les majuscules, les accents, la ponctuation...
27^6 = 387 420 489
27^7 = 10 460 353 203
Tu devras donc te contenter de chaînes de longueur 6.

[Yabo]

Bonjour!

Alors voilà, je suis en train chercher un algo intelligent pour coder une chaine de caratere en un unique entier, de telle sorte que deux string differentes n'est jamais le meme code.

Par exemple "ab" ne doit pas avoir le meme code que "ba".

J'avais eu l'idée de coder de la sorte:
"abc..." = (code_ascii a)*2^0 + (code_ascii b)*2^1 + (code_ascii c)*2^2 + ....

mais le pb est que des que la chaine est trop grande, ca dépasse la capacité d'un entier, qui est limité à 31bits (en ocaml)
Existe t il un autre moyen d'associer un unique entier (pas trop grd) à une chaine?

merci d'avance!

Tu as le module Int64 sous ocaml qui te fournis des entier sur 64 bits mais ca ne fait que repousser un peu le problème.

As-tu absolumeent besoin d'un entier ? Un empreinte SHA1 par exemple ne pourrait pas convenir ?

[gangsoleil]

Code :

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

1
2
3
4
 
 2^63 : 9 223 372 036 854 775 808
 
27^13 : 4 052 555 153 018 976 267

Avec int64, tu peux donc te limiter à 13 caractères au lieu de 6.
Sinon, tu vas devoir toi-même coder un type grand entier, ce qui n'est pas si complexe que ca (attention au problème de "little endian" ou "big endian" en fonction de ce que tu souhaites faire comme triatement sur ces nombres).

[sovitec]

Salut,

Il existe des choses toutes faites pour ton problème, elles s'appellent des fonctions de hash. En fait elle ne garantissent pas l'unicité du résultat, mais la probabilité que deux chaines est le même hash est tellement faible que ce n'est jamais un problème. Il existe probablement des bibliothèques OCAML pour les hash les plus populaires : MD5, SHA-1, SHA-256, TIGER, ...

[Paul Atreide]

Il faut que tu trouves une fonction injective de l'ensemble des chaînes dans l'ensemble des entiers.
- La fonction que tu proposes n'est pas une injection [...]]

Si tu ne te limites pas au niveau de la longueur de la chaîne ou de l'alphabet utilisé c'est impossible de trouver une injection. En effet, il faudrait qu'il y ait moins de chaines que de nombres. Or 2^31 n'est pas si grand que ça et du coup ça limite énormément les possibilités pour les chaînes de caractères. Par conséquent il existera forcément deux chaînes qui auront le même nombre. Comme je l'ai lu dans d'autres messages, utiliser un algo comme MD5 ou SHA1 peut être une bonne solution. Je pense qu'on doit pouvoir trouver des infos à ce sujet sur le net. A toi de jouer