codage des caractères

Version imprimable

06/04/2016, 11h03
mido1951

codage des caractères

Bonjour,

Je veux savoir comment coder des caractères en 2 bit.
je veux gagner de la mémoire et j'ai 4 caractère à coder donc comment coder ces 4 caractères en binaire?
Merci
06/04/2016, 11h10
ternel
En manipulant les bits d'une variable de type char.
les opérateurs dédiés sont:
- & et | pour faire les AND et OR bit par bit: ainsi, 17 & 0001b = 0001b car 17 = 10001b)
- << et >> pour décaler les bits d'un nombre:par exemple, 1<<2 devient 4 (car 1= 0001b et 0100b=4)
- éventuellement, ~ pour l'inverse binaire
06/04/2016, 11h16
mido1951

merci pour ta réponse mais je n'ai pas compris. :(
est-ce que je peux avoir un exemple?
Merci et désolé. J'ai jamais utilisé ce genre de codage.
06/04/2016, 11h21
CodeurPlusPlus

Bonjour,

une vidéo qui parle des "champs de bits". Les manipulations permettant d'accéder séparément à n'importe quel bit y sont expliquées :

https://www.youtube.com/watch?v=hz-ON1osZJE

Mais ce n'est pas niveau bébé...
06/04/2016, 11h25
mido1951

j'ai dit que j'ai 4 caractères et je veux coder ces caractères en 2 bits et non pas sur 8bit (le cas d'un caractère) pour gagner en mémoire.
Je veux avoir un exemple de code en C pour un codage de caractère en 2 bits.
merci

En fait, il y a une bonne raison pour laquelle tu ne l'a jamais fait: c'est rarement utile.

Qu'essaie-tu de faire avec ca?
char est la taille la plus petite pour une variable.
Tu peux essayer de stocker deux valeurs en même temps dans un char, si tu parviens à trouver un moyen de les séparer.
Le problème, c'est que du coup, chaque utilisation de la variable est plus lente, car tu ne peux manipuler que des chars (la faute au processeur :D)

La difficulté, ce n'est pas de stocker des choses ne différant que sur 2 bits, mais de stocker 2 choses distinctes (voire 4, dans ton cas) dans une seule variable.
les bits fields peuvent clairement servir:
Code:

1 2 3 4 5 6 struc quad_value { unsigned char a:2; unsigned char b:2; unsigned char c:2; unsigned char d:2; };
un peu de documentation: http://en.cppreference.com/w/c/language/bit_field

Cela dit, voici un exemple pour les manipulations par bits:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 typedef unsigned char meteo_t; meteo_t const masque_temperature=0x01;//premier bit meteo_t const temperature_froid = 0x00; meteo_t const temperature_chaud = 0x01; meteo_t const masque_vent=0x06;//deuxième et troisième bits meteo_t const vent_aucun = 0<<1; meteo_t const vent_faible = 1<<1; meteo_t const vent_moyen = 2<<1; meteo_t const vent_fort = 3<<1; void f() { meteo_t meteo = temperature_froid | vent_fort; //le | crée une valeur dont chaque bit est actif si le bit correspondant est actif dans au moins un opérande. if ((meteo & masque_temperature == temperature_froid)) { printf("froid"); } else { printf("chaud"); } switch (meteo & masque_vent) { case vent_aucun: printf("pas de vent"); break; case vent_faible: printf("peu de vent"); break; case vent_moyen: printf("venteux"); break; case vent_fort: printf("vent violent, soyez prudent."); break; } }
J'imagine bien que tu manipule quatre constantes du type A, T, C et G, représentable par les entiers 0,1,2,3.

06/04/2016, 11h41
Daïmanu

Bonjour.

Simple question, quels caractères tu veux encoder ?
Sur 2 bits, il n'y a que 4 combinaisons de bits possibles, 00, 01, 10 et 11, et donc 4 éléments encodables.

Tu dois savoir qu'en C, on ne peut pas avoir de variable de taille inférieurs à un char, qui a une taille de 1 byte (8 bits sur la majorité des systèmes).
Si tu veux utiliser 2 bits, tu dois "découper" des chars avec des champs de bits comme l'a dit CodeurPlusPlus, et utiliser les opérateurs présentés par leternel.

Mais sache que, à moins que tu as un besoin absolu et critique d'économiser la mémoire, on préfère éviter ce genre de technique car ça demande beaucoup de code pour au final un gain faible.
06/04/2016, 11h45
mido1951

Citation:

Envoyé par leternel

En fait, il y a une bonne raison pour laquelle tu ne l'a jamais fait: c'est rarement utile.

Qu'essaie-tu de faire avec ca?
char est la taille la plus petite pour une variable.
Tu peux essayer de stocker deux valeurs en même temps dans un char, si tu parviens à trouver un moyen de les séparer.[/CODE]

J'imagine bien que tu manipule quatre constantes du type A, T, C et G, représentable par les entiers 0,1,2,3.

oui mes caractères sont A, T, C et G.
en fait, j'ai de longues sequences et si je code chaque caractère sur 8bit ça prend bcp de mémoire donc je dois minimiser la taille de ces caractères pour qu'ils ne prennent pas bcp de mémoire (8 bit). 2 bit est suffisant.
et je n'ai jamais fait ce genre de manipulation en C. c'est pour ça je veux de l'aide sur la manipulation de ce genre variable.
parce que je ne peux pas definir une sequence de chaine de caratères char*.
Alors comment definir une sequence de chaine de caractere avec les caracteres qui prennes 2 bit seulement en mémoire??
Merci

Citation:

Envoyé par Daïmanu

Simple question, quels caractères tu veux encoder ?

A, C, G et T.
06/04/2016, 12h03
ternel

Entre temps, j'ai modifié mon message précédent, pour rajouter une précision sur les bitfields.

Tu peux faire une séquence de quad_value.
Si tu connais à l'avance la taille de chaque séquence, ou au minimum une taille maximale, et tu peux utiliser un tableau "dynamique" de quad_value (c'est à dire un pointeur et un malloc(N*sizeof(quad_value))).

Sinon, il te faut passer par une liste chainée, et tu perds tout le gain envisagé, un pointeur coutant au moins 32 bits.
Tu peux mitiger cela avec une liste de petits tableaux (par exemple une 32-sizeof(pointeur)).
06/04/2016, 13h20
mido1951
d'accord donc je dois juste declarer le quad_value puis je fais une allocation d'une chaine de caractère de quad_value et j'utilise la chaine comme d'habitude?

Declaration:
Code:

1 2 3 4 5 6 7 8 struc quad_value { unsigned char a:2; unsigned char b:2; unsigned char c:2; unsigned char d:2; }; quad_value* chaine= malloc(N*sizeof(quad_value))); //pour la declaration de chaine
c'est ça?
Merci

Bof c'est plus simple de faire comme cela, define ou function au choix:

Il faut utiliser des unsigned char :mrgreen:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#define GET_CHAR(VAL) \
    ((VAL == 0x00)? 'A': ((VAL == 0x01)? 'C': ((VAL == 0x10)? 'G': 'T' /*0x11*/)))
 
#define GET_VALUE(CHAR) \
    ((CHAR == 'A')? 0x00: ((CHAR == 'C')? 0x01: ((CHAR == 'G')? 0x10: 0x11 /*'T'*/)))
 
#define GET_FIRST(VAL, CHAR) \
   CHAR = GET_CHAR((VAL & 0x03));
 
#define GET_SECOND(VAL, CHAR) \
   CHAR = GET_CHAR(((VAL & 0X0C) >> 2));
 
#define GET_THIRD(VAL, CHAR) \
   CHAR = GET_CHAR(((VAL & 0X30) >> 4));
 
#define GET_FOURTH(VAL, CHAR) \
   CHAR = GET_CHAR(((VAL & 0XC0) >> 6));
 
#define SET_FIRST(VAL, CHAR) \
   VAL &= 0XFC; \
   VAL += GET_VALUE(CHAR);
 
#define SET_SECOND(VAL, CHAR) \
   VAL &= 0XF3; \
   VAL += (GET_VALUE(CHAR) << 2);
 
#define SET_THIRD(VAL, CHAR) \
   VAL &= 0XCF; \
   VAL += (GET_VALUE(CHAR) << 4);
 
#define SET_FOURTH(VAL, CHAR) \
   VAL &= 0X3F; \
   VAL += (GET_VALUE(CHAR) << 6);

06/04/2016, 13h55
picodev

Bonjour,

Citation:

Envoyé par mido1951

oui mes caractères sont A, T, C et G.
en fait, j'ai de longues sequences et si je code chaque caractère sur 8bit ça prend bcp de mémoire donc je dois minimiser la taille de ces caractères pour qu'ils ne prennent pas bcp de mémoire (8 bit). 2 bit est suffisant.

Quel est l'ordre de grandeur de ces séquences ? Quel est l'ordre de grandeur du nombre de séquences ?

Comme le dit Leternel, le gain de place peut ne pas être significatif par rapport aux pertes de performances dues aux manipulations.

Citation:

Envoyé par mido1951

d'accord donc je dois juste declarer le quad_value puis je fais une allocation d'une chaine de caractère de quad_value et j'utilise la chaine comme d'habitude?
Merci

Non tu ne pourras pas utiliser une chaîne de quad comme un char *. Il va falloir écrire toues les fonctions de manipulations et d'accès.
06/04/2016, 14h00
ternel

On a oublié de rappeler la base des problèmes d'optimisation:

On n'optimise pas un code non fonctionnel.
On n'optimise pas avant d'avoir mesuré ce qui en a besoin.

Ecris du code fonctionnel, termine l'algorithme, et après seulement viendront les considérations d'optimisation.
06/04/2016, 14h02
mido1951

Citation:

Envoyé par picodev

Bonjour,

Quel est l'ordre de grandeur de ces séquences ? Quel est l'ordre de grandeur du nombre de séquences ?

Comme le dit Leternel, le gain de place peut ne pas être significatif par rapport aux pertes de performances dues aux manipulations.

Non tu ne pourras pas utiliser une chaîne de quad comme un char *. Il va falloir écrire toues les fonctions de manipulations et d'accès.

j'ai environ 100.000 sequences avec la plus grande sequence est de 60.000 et une longueure moyenne de 6000.
06/04/2016, 14h12
picodev

Citation:

Envoyé par mido1951

j'ai environ 100.000 sequences avec la plus grande sequence est de 60.000 et une longueure moyenne de 6000.

Donc en gros 600Mo en moyenne avec un grand maximum à 6Go. Pas la peine de se prendre la tête sur la place je pense. Il vaut mieux penser à bien gérer quelles séquences sont en mémoires à un moment donné. Enfin tout dépend de ce que tu fais avec.

Comme te le conseille à juste titre Leternel, fait déjà un programme qui fonctionne. Ensuite un profiler te montreras où il est judicieux d'essayer d'optimiser le code.
06/04/2016, 14h20
ternel
100k * 60k = 6 Go
soit environ 6 giga-octets, avec des caractères normaux.
Il y a des chances que ton PC dispose de plus de RAM que cela. Surtout qu'il s'agit probablement de faire tourner ton programme sur une machine de calcul disposant de plus de RAM qu'un simple poste de travail.

Poses-toi l'autre question: As-tu réellement besoin d'avoir toutes les séquences en mémoire simultanément?
En général, non, seulement de deux ou trois.

En effet, la quasi-totalité des algorithmes sont de la forme:
```
soit un Bidule de référence
pour chaque Bidule d'un ensemble donné,
    utiliser le Bidule courant avec le Bidule de référence
retourner le résultat
```
Et pour cela, il n'est pas nécessaire de charger tout l'ensemble intégralement en mémoire, mais simplement d'entrelacer la lecture du fichier contenant les séquences et le calcul.

L'algo devient:
```
soit un Bidule de référence
pour chaque ligne du fichier,
    convertir la ligne en un Bidule
    utiliser ce Bidule avec le Bidule de référence
retourner le résultat
```