Réduire une chaîne binaire fixe de 1 bit ?

Bonjour,

Est-ce qu'il vous serez possible de m'indiquer si il est possible de réduire une chaîne binaire quelconque de longueur fixe (disons 120 chiffres binaires) de juste 1 chiffre (ou bit) par compression ? N'hésitez pas à proposer la solution complète.

Avec comme postula qu'aucune perte d'informations n'est admise et que les solutions pour chaque combinaisons binaires doivent être uniques et trouvées, sauf pour les cas particuliers (ils doivent être rares) ; les cas particuliers seraient inscrits dans un index externe. L'index externe contient le numéro de séquence (à quel moment agir) et la valeur de la chaîne binaire de cette séquence (l'index peut aussi servir d'index ...).

Si il y a 120 puissance de 2 ... pour le nombre de combinaisons possibles, l'algorithme doit être bien conçu ; toutes les astuces et connaissances mathématiques et ou algorithmiques doivent être utilisées ! Ça ne devrait pas être une liste avec 120 puissance de 2 règles mais un algorithme capable de traiter toutes les combinaisons sans être obligé d'écrire chaque règles = optimisation au maximum possible.

J'ai déjà réfléchit au fait que si la chaîne binaire quelconque de longueur fixe (disons 120 chiffres binaires) contient par exemple plus de 1 que de 0, alors une partie des bits va servir à indiquer que c'est les 0 que l'on traites pour obtenir une réduction (en longueur de la chaîne) de 1 chiffre (ou bit) et inversement quand il y a plus de 0 que de 1.

Le but est de n'avoir besoin que d'un minimum de traitement à effectuer afin de pouvoir toujours réduire la chaîne binaire quelconque de longueur fixe (disons 120 chiffres binaires) de 1 chiffre (ou bit) et jamais plus de 1 chiffre (ou bit) même si c'est possible.

La longueur de la chaîne binaire doit être la plus petite possible ; environ 120 chiffres binaires (ou bits) et ce sont les solutions de compressions mises au points minutieusement qui doivent déterminer au final sa longueur à 1 ou 2 chiffres binaires (ou bits) près. En ajoutant 1 chiffre binaire (ou 1 bit) l'on double le nombre de combinaison à traiter, à contrario si la chaîne binaire quelconque de longueur fixe (disons 120 chiffres binaires) n'est pas assez longue, alors l'on ne peut pas traiter toutes les combinaisons, même si il y en a peu ; il y aura trop de cas particulier et la compression est caduque ; le dosage doit donc être précis.


Avec comme postula, qu'il faut obtenir une réduction/compression de 1 chiffre/bit de la chaîne binaire (quelconque) d'une longueur fixe de disons 120 chiffres binaires, vous pouvez comprendre que la longueur de la chaîne binaire est effectivement réduite de 1 chiffre en compressant 1 bit dans la chaîne binaire en la transformant ; mais en fait, la chaîne prélève le bit à l'extérieur ou plutôt à coté et à contrario le restitue quand l'on décompresse les données ; exemple :

La chaîne binaire ou plutôt le masque de sélection binaire, (disons toujours d'une longueur fixe de 120 chiffres binaires), peut être plaqué, par exemple, sur la fin d'un fichier informatique moins 1 bit, par exemple avec le fichier toto.vhd 300 Go.

Si la fin du fichier est disons sur la droite, on laisse 1 bit libre sur la droite et le masque de 120 chiffres binaires est à gauche du bit ; si il n'y a pas ou plus de bit sur la gauche pour que la chaîne garde sa longueur fixe, alors il n'y a rien à traiter et la chaîne à toujours sa longueur (et il n'y a pas ou plus de bit dit libre à droite).

Si il y a des bits à traiter, successivement on va incorporer et compresser le bit à droite du masque dans la chaîne de traitement représenté par le masque en transformant entièrement la chaîne binaire (qui est aussi le masque) pour obtenir une compression et sans perte d'informations (si c'est un cas problématique : code spécial et index). Après le traitement, si il y a encore des bits à traiter à gauche, on déplace le masque de 1 bit vers la gauche et il va y avoir 1 bit de libre à droite à traiter ; et ainsi de suite.


La chaîne binaire après un premier traitement, est à la fois un masque de sélection et une chaîne binaire crée avec un algorithme de compression (algorithme à justement mettre au point).


Pour lire ou décompresser les données l'on fait l'inverse.


(toto.vhd 300 Go ferait 120 bits compressé ; un index peut discriminer 2 mêmes codes)


Par exemple, il va être plutôt très simple de coder les séquences répétitives :

010101010
=> bit 1 (50/50 1 et 0) traité + répète lire 2 chiffres séquence 01
ou
00010001000100010...
=> bit 1 traité (moins de 1) + tous les 4 bits = 1 (impair/coupure fix auto fin de chaîne)
ou
0000000000000000...
=> bit 1 (50/50 1 et 0) traité + répète lire 4 chiffres séquence 1100

Il faut peut-être tester une règle pour chaque combinaisons et une interface pourrait facilitée les tests. Chacune des règles doit tenir comptes des autres. Le codage doit être une sorte d'arborescence = par exemple l'on doit trouver toujours la même séquence de départ qui serait le codage (multi-niveau) de savoir si il y a plus de 1 ou de 0, ensuite traité et codé en conséquence. Info quand il est indiqué codage "multi-niveau" ; exemple avec 4 bits, on a 16 combinaisons et on peut arbitrairement donner une double signification à une même valeur : par exemple de 1à4 on précise que l'on traitre les bits à 1 et un autre code est attribué et par exemple de 5à8 on précise encore que l'on traite les bits à 1 mais l'autre code est différent. Le code zéro peut servir de by pass pour un autre jeu de code à un autre emplacement ... par exemple. Une interface double emploie utilisation/test pourrait facilitée les tests ou l'optimisation.


Avec ce système à mettre au point et grâce à un index, à la fois qui sert à stocker les cas particuliers et qui sert aussi d'index, il est possible de traiter n'importe quelle quantité de données et l'on peut accéder directement à certaines zones grâce à l'index. L'index peut lui-même être compressé ... un index plus petit peut servir de bootstrap ; l'algorithme doit tenir le moins de place possible et il doit pouvoir traiter toutes informations nativement (il ne serait pas compressé) ; peut-être qu'une partie peut être compressée, un bootstrap de préparation serait nécessaire. En fait, à l'utilisation (décompression), soit il y a beaucoup de mémoire (rapide) et on ouvre tout (on décompresse tout) ou alors on lis les données séquentiellement (pas d'accès direct) en mémoire (rapide) à chaque fois qu'une info est demandée ; l'index peut pointer vers le début de certaines zones (pas n'importe où).

merci, n'hésitez pas à proposer une interface graphique (ça avance mieux comme ça) reprenant (en plusieurs versions successives 00.00.01_2011-02-22_AlphaInterface 00.01.00_2011-02-22_BetaInterface 01.00.00_2011-02-22_Algo+-OK <= 3 notations de base) tout ce que vous trouvez par vous-même ou qui est proposé par autrui (demandez aux gens ce que visuellement dans l'interface vous pouvez améliorer = texte, icônes, logo, menus) ; le plus dur à incorporer et à mettre au point, ce sont les règles algorithmiques pour chaque combinaisons = ça doit couvrir toutes les combinaisons (120 puissance de 2 si la chaîne de longueur fixe est longue disons de 120 chiffres binaires) et avec le moins possible de cas particuliers (la combinaison traitée normalement bloquerait trop d'autres combinaisons traitées ou dépasse la capacité de traitement = pas assez de bits, par exemple).