algorithme de conversion

Version imprimable

09/08/2004, 02h24
Noteirak

algorithme de conversion
Bonjour !
Je suis face à un problème assez épineux qui demande un algorithme pour être régler, mais malheureusement je n'ai pas encore assez de compétences pour montrer ce genre d'algorithme (ou pas assez de logique, la suite vous le dira :P).

J'aimerai monter un alogorithme de conversion capable de transformer n'importe quel chaine de caractère d'une longeur de 16 octets (répondant au standart ASCII) pouvant avoir n'importe quel caractère ASCII, en une chaine de maximum 24 caractères ne contenant que [0-9,a-f].
L'ordre, l'emplacement, ou n'importe quoi d'autre des différents elléments devra permetre de retrouver la chaine originel.
Code:

1 2 3 Ex : ChaineDe16Elemen -> af5cd129e3ac59be[...] --> Cette chaine devra permetre via un algorithme de retrouver la chaine originelle (ChaineDe16Elemen)
Moins il y a des caractères pour la seconde chaine, mieux c'est !
Si il existe un algorithme de cryptographie me permetant la meme chose, je suis prenneur !
Si vous avez des suggestions ou des idées pour programmer ce genre d'algorithme, votre aide est la bienvenue ! Merci d'avance.
09/08/2004, 05h28
Luc Hermitte

Ca rentre pas.
ASCII -> 7 bits par caractères.
16 * 7 = 112 bits
112 / 4 -> 28 quartets (nombre sur 4 bits -> de 0 à 15 (15 == f en hexa) pour stocker ta chaine.

28 > 24 => bug dans les énoncés.

Ou alors il faut une compression qui assure qu'il y aura toujours une réduction. Je ne suis pas un pro du domaine, mais je pense que ce n'est pas possible (avoir une correspondance exacte sur 127^16 valeurs dinstinctes possibles qui tienne toujours en 24 quartets). Quelque soit l'ago de compression, je pense que l'on pourra toujours trouver une chaine contre-exemple qui dépasse.

Quant au cryptage, en général on augmente par rapport à la taille de la chaine originale.
09/08/2004, 06h18
Médiat

>>Luc, je confirme tout le début de ta démonstration, mais

Citation:

Envoyé par Luc Hermitte

Ou alors il faut une compression qui assure qu'il y aura toujours une réduction.

Quelque soit la compression il y a quand même 128^16 (5*10^33) chaînes possibles au départ et 16^24 (8*10^28) à l'arrivée, donc pas d'injection possible (donc il n'y a pas toujours réduction (sinon tous les fichiers pourraient se comprimer en un seul caractère :lol: ))!
09/08/2004, 07h13
Luc Hermitte

A défaut de relacher la contrainte sur le 24, il faudrait éliminer des caractères. p.ex. le code ASCII 0 sert à définir une fin de chaine (si mes souvenirs sont bons).
En l'éliminant, la taille de l'ensemble de départ se reduit à \sigma_0^{15} 127^i , soit \frac^{127^16-1}_{127-1}.

C'est toujours trop gros mais ça donne l'idée -- virer les 32 premiers caractères est toujours insuffisant. Une fois cet ensemble réduit, il est très facile de l'ordonner. Le résultat à générer correspondrait à la position (en hexa) de l'élément de départ dans son ensemble trié.
09/08/2004, 07h27
Médiat

64^16 = 16^24, donc il faut réduire l'alphabet de départ à 64 signes !
09/08/2004, 10h05
gangsoleil

Citation:

Envoyé par pgibone

64^16 = 16^24, donc il faut réduire l'alphabet de départ à 64 signes !

26 minuscules + 26 majuscules + 10 chiffres = 62 caracteres... reste pas beucoup de place !
09/08/2004, 10h09
Noteirak

Les lettres peuvent servir à plus que bettement dire la position d'une autre !
Ex : si a en première position, ac b en second, 3 en troisième, etc...
ou bien utiliser le code hexa de ces valeurs ou le code binaire pour programmer des instructions.
Je pense sérieusement qu'il y a moyen de cette facon, mais dite moi ce que vous en pensez.

J'aimerai que les lettres soient des instructions ! Et si besoin est avec un tableau de départ ou quelque chose... vous voyez ce que je veux dire ?
09/08/2004, 10h32
Médiat

Citation:

Envoyé par Noteirak

vous voyez ce que je veux dire ?

Euhh Non

Ta question de départ est :

Citation:

transformer n'importe quel chaine de caractère d'une longeur de 16 octets (répondant au standart ASCII) pouvant avoir n'importe quel caractère ASCII, en une chaine de maximum 24 caractères ne contenant que [0-9,a-f].
L'ordre, l'emplacement, ou n'importe quoi d'autre des différents elléments devra permetre de retrouver la chaine originel.

Si cela n'a pas changé, il n'y a qu'une réponse : impossible ! Il te faut une injection et ce n'est pas possible si l'ensemble de départ est plus grand que l'ensemble d'arrivée.
09/08/2004, 10h59
Noteirak

c'est n'es pas un algo en soit, enfin si mais non :)

Je veux considérer la chaine [0-9,a-f] comme un script si vous voulez, un code source pour permetre d'exécuter des instructions pour retrouver la chaine original !
09/08/2004, 12h09
Nemerle

Précise, car j'ai l'impression qu'un script ne change rien au problème.

A moins d'utiliser tes 24 octets pour faire une machine de turing...