Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Méthode de compression universelle
Bonsoir,
Soit A un matrice carré de 3 dimension avec comme élément des entiers entre 0 et 14.
1.En enregistre dans la memoire toutes les possibilités de A.
Soit F un fichier binaire tout fichier binaire est décomposer des matrices A
Soit F=AA...Ab memoire grande
A sera remplacer par l'adresse de A dans fichier binaire
F=adresseA...adresseA b memoire petite
Et On boucle
Est ce que c'est correct.
Ça dépend : tu veux faire quoi ? En tentant de raccrocher ça à ton titre (ça parle de compression, mais ce que tu proposes là n'a rien d'universel…), oui, tu arriveras à encoder tes matrices et à effectuer l'opération inverse.Envoyé par fanmanga
Maintenant, je ne suis pas sûr que tu arriveras à compresser beaucoup de choses : compare la taille d'un identifiant avec celle d'un encodage optimal direct de la matrice (neuf fois quatre bits, plutôt que trente-deux ou soixante-quatre en utilisant des int). Pour vraiment compresser, la notion de probabilité est essentielle : les matrices les plus fréquentes sont codées avec très peu de bits. Par exemple, regarde http://tcharles.developpez.com/Huffman/, c'est à la base de pas mal de stratégies de compression efficaces.
Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.
Créer des applications graphiques en Python avec PyQt5
Créer des applications avec Qt 5.
Pas de question d'ordre technique par MP !
Bonjour
Rappel: la compression absolue n'existe pas.
Si c'est ça que tu entends par "compression universelle", tu vas être déçue. Il ne peut pas exister de méthode compressant n'importe quoi en quelque chose de plus petit. Pire: sur la moitié des matrices tu ne gagnes qu'1 bit, sur le quart 2 bit ... sur 1/256ème 8 bits.
Ça, je comprends. Ça veut dire que tu vas poster ton problème encore, encore et encore jusqu'à ce que developpez.net/forums sature.Et On boucle
Cette réponse vous apporte quelque chose ? Cliquez suren bas à droite du message.
Voila je donne un exemple.
Je prend un matrice de dimension 10 avec comme valeur entre 0 et 14 j'enregistre tout les possibilités de A sur la mémoire.
Soit notre fichier B=23567754224522..0=AAA...0
Je le divise en matrice de dimension 10 .
Et je blaye mon fichier matrice par matrice
Quand je trouve A je le remplace par l'adresse de A dans la memoire qui es aussi un chiffre.
Donc j'obtiens un nouveau fichier binaire C=adresse A adresse A... avec moin de memoire.
Avec adresse A est un chiffre.
Je refait la meme opération j'obtien un nouveau fichier avec moin de memoire ainsi de suite.
Ça m'a l'air tordu, ton truc. Non, en fait, il manque une question. Donc j'en invente une et j'y réponds.
Supposons que cette procédure permette de compresser, même itérée à l'infini. Tu ne pourras jamais descendre en dessous d'une limite théorique donnée par le théorème de Shannon (codage de source), c'est-à-dire l'entropie de ce que tu compresses (et hop, des probas).
D'ailleurs, est-ce que cette procédure permet de compresser ? Pour des matrices 10 * 10, en utilisant un total de quinze valeurs différentes possibles encodées sur quatre bits en entrée (donc une valeur inutilisée sur les seize), c'est pas impossible. Combien y a-t-il de telles matrices ?, c'est-à-dire qu'il faut
bits pour leur attribuer un nombre à chacune, avec un dictionnaire de taille
bits, de l'ordre de
Gio (chaque mot correspond à une matrice complète dans l'espace de départ, chacun des cent éléments étant alors codé sur quatre bits ; les numéros sont donnés par la position dans le fichier). En construisant le dictionnaire intelligemment, il doit être possible de s'en sortir sans le calculer au complet et le transmettre. En appliquant cette procédure une fois, on passe donc de
bits pour une matrice à
, c'est-à-dire un taux de compression de l'ordre de nonante-huit pour cent, une jolie manière de dire trois fois rien. Et si on applique la même procédure une nouvelle fois ? Il reste quand même le même nombre d'items à représenter : il te faudra encore et toujours tes
Hop, la limite de Shannon en plein dans la tronche ? Effectivement si toutes les matrices sont équiprobables, pas du tout sinon.
Courrier tapé, non relu.
Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.
Créer des applications graphiques en Python avec PyQt5
Créer des applications avec Qt 5.
Pas de question d'ordre technique par MP !
Est ce cette méthode marche....
Non, il lui manque des pattes. Pose une vraie question, suffisamment précise. Veux-tu savoir s'il est possible de décompresser ? Oui. Veux-tu savoir si cette compression est efficace ? Non. Veux-tu savoir si l'implémentation est efficace en mémoire ? Ça dépend de la manière de faire, une manière naïve sera strictement impraticable, même sur un énorme supercalculateur. Ou bien il fallait comprendre encore autre chose ?
Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.
Créer des applications graphiques en Python avec PyQt5
Créer des applications avec Qt 5.
Pas de question d'ordre technique par MP !
Pourquoi cette compression est pas efficace?
Je t'invite à relire cette discussion et à poser des questions précises sur les points qui ne te sont pas clairs, toutes les explications s'y trouvent.
Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.
Créer des applications graphiques en Python avec PyQt5
Créer des applications avec Qt 5.
Pas de question d'ordre technique par MP !
Pourquoi le nombre de l'adresse et plus grand que le nombre de matrice A=1234..0 dimension 10.
Plus notre adresse est uselle plus en gagne des case mémoire.
Exemple je remplace A matrice nombre par l'adresse nombre 1 j'obtien un nouveau fichier un nombre entier reduit ainsi de suite
L'explication de dourouc05 est pourtant claire....
En reprenant ses hypothèses (car tu ne donnes quasiment aucune info, heureusement qu'on possède tous une boule de cristal en bois...) : des matrices 10x10 contenant des mots sur 4 bits.
Lors du premier passage, la taille va diminuer d'environ 2.25%. Pour les passages suivants, la compression sera tellement infime qu'on pourra la considérer comme inexistante.
Un index représentant une matrice est écrit sur 391 bits. Donc après le premier passage de compression, le fichier est une suite de 391 bits. On reprend le fichier et on considère que c'est une suite de matrices de 400 bits.
Le point bloquant va venir du contenu du dictionnaire : il ne contient pas toutes les combinaisons possibles puisque les valeurs contenus dans la matrice sont comprises entre 0 et 14 (manque 15). Donc la première compression a généré des sous-suites impossibles à compresser une nouvelle fois. Ces sous-suites sont "contaminées" et ne bougeront plus.
Intéressons-nous aux sous-séquences compressibles. Leurs nombre, leurs longueurs ? Statistiquement, on pourrais imaginer 14/16ème du fichier dans le meilleur des cas. On applique une nouvelle compression qui diminue ce 14/16ème de 2.25%. La contamination s'étend encore plus dans les sous-séquences puisque l'entropie augmente.
A partir de la troisième compression, la taille du fichier compressé ne changera plus.
N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java
Que la force de la puissance soit avec le courage de ta sagesse.
Et si je choisis un matrice(100 valeur) de dimension 10 donc 100 octet dans la memoire ,avec des valeurs comprise entre 0 et 15
Puis des pointeurs (index)simple qui sont coder par 3 octet exemple d'un pointeur simple b=14 10 14 pourquoi le pointeur doit obligement etre s'ecrire sur 391 bit.
Je prend mon matrice A avec 100 valeur 100 octet et je le remplace par b avec 3 octet.
Mon fichier F=AAA..A avec taille grande
Mon nouveaux fichier F=bbbb.b avec taille réduit.
Avec les b je peux constuire un nouvau matrice A .
Pourquoi la 2 compression sera infime.
Ca aussi, dourouc05 l'a très bien expliquer. Alors je vais simplement reformuler.
Dans ton dictionnaire, tu dois avoir toutes les combinaisons possibles des matrices 10x10 avec des valeurs entre 0 et 14.
Ton dictionnaire aura une taille de : 15^100. Ce nombre écrit en binaire demande 391 bits pour s'écrire.
Mais je te vois venir : les deux premiers index peuvent s'écrire sur un seul bit (zéro pour le premier et un pour le second) ! Et bien oui.... mais non. comment feras-tu la différence entre un index sur 1 bit suivi d'un index sur 6 bits par rapport à un seul index codé sur 7 bits ?
Avant d'aller plus loin, va lire tout ce que tu peux trouver sur la limite de Shannon et l'entropie de Shannon. Lorsque tu auras une idée un plus précise concernant les théorèmes associés, nous pourrons fermer cette discussion.
Bonne lecture !
N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java
Que la force de la puissance soit avec le courage de ta sagesse.
Et si j'utilise cette méthode soit Z un fichier binaire composé des matrices A=22719735 (taille grande avec 8 case de mémoire pour coder le 2 2 7 ..et 5)avec comme éléments entre 0 et 15
je prend se nombre A et je fait conversion en hexadécimal 15AACF7 (taille petite 7 case de mémoire pour coder le 1 5 ...et 7).
En change le base en peux réduire notre fichier Z(taille grand)=Z'(taille petite avec moins case mémoire).
que pensez vous.
Peu importe la base, la quantité d'information restera de 391 bits. Évidemment, si tu veux vraiment avoir une chance de compresser, il ne faut pas utiliser les caractères ASCII "0" et "1", mais bien des bits (voir, par exemple, Wikipedia : https://en.wikipedia.org/wiki/Bit_manipulation). Là, tu utiliseras exactement la base qui correspond à la taille des mots que tu choisis, aucune perte possible (sauf qu'un système de fichiers n'alloue pas des blocs pour des fichiers au bit près, de même pour les réseaux qui comptent la taille des paquets en octets, mais tu ne pourras rien y faire).
Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.
Créer des applications graphiques en Python avec PyQt5
Créer des applications avec Qt 5.
Pas de question d'ordre technique par MP !
Tu confonds stockage d'une donnée et représentation d'une donnée. Ton idée sur le changement de base concerne uniquement la représentation d'une donnée mais la quantité d'information à stocker reste la même.
Ta matrice A=22719735 sera écrite sur 391 bits et vaudra "0000 0000 ... 0000 0001 0101 1010 1010 1100 1111 0111". 391 bits, c'est le stockage minimum nécessaire pour différencier les index.
Quelque soit la base choisie pour représenter cette valeur, il te faudra toujours 391 bits pour représenter ton index, soit environ 49 octets, et ça que tu la représentes en base décimale, hexadécimale, octale ou autre...
PS : Flodelarab avait raison sur la boucle...
N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java
Que la force de la puissance soit avec le courage de ta sagesse.
Et si je procède ainsi soit A un bout de code écrit sur A=[10 11 1 9 14 5 9 15 14 10] sur 5 octet.
En calcule le Z=10*2^9+11*2^8+ 1*2^7+ 9*2^6 +14*2^5+5*2^4+9*2^3+15*2^2+ 14*2^1 +10*2^0
puis le E=10*16^9+11*16^8+ 1*16^7+ 9*16^6 +14*16^5+5*16^4+9*16^3 +15*16^2+ 14*16^1 +10*16^0 qui es a un format unique si on a E en peut déduire A.
Le B=E/Z=78697139 sa donne toujours un entier .
Si en connais le B en peux déduire le E et le Z car il s'écrive sur le même forme donc en peux déduire le A si en connais le B.
Si en code le B sa donne 4 octet donc une octet gagné.
Que pensez vous?
Bonjour à toi.
Tu viens de réinventer le principe de la compression RLE : on identifie des séquences identiques de bits et on les remplace par des substitutions plus courtes. Par exemple 111010 par 10.
Sauf que bien sûr cela ne permet pas une compression infinie. En effet réfléchis à la façon dont tu vas devoir encoder ton flux de sortie : comment savoir si 10 signifie 111010 ou bien littéralement 10 ?
Tu as deux façons de résoudre cette ambiguïté.
a) La première consiste à identifier "toutes les séquences possibles de bits" et à créer pour chacune une séquence de substitution. Mais dans certains cas la substitution sera plus lourde que la séquence de départ parce que tu auras déjà utilisé toutes les courtes séquences ! Si tu as N séquences au départ, tu dois avoir N séquences à l'arrivée, de plus en plus longues. Et puis il te faudrait ajouter une table des correspondances.
b) Tu ajoutes des informations à ton flux pour distinguer les substitutions des séquences d'origine, littérales. C'est l'approche de RLE.
Dans tous les cas ta compression sera limitée par le degré d'entropie (de désordre) du flux source. Pour faire simple la seule et unique façon de compresser consiste à identifier les redondances (répétitions) dans le flux et à les exploiter. Mais si le flux est complètement aléatoire alors aucune compression n'est possible et tout algorithme produira un flux alourdi. C'est ce qui explique que tu ne peux pas infiniment recompresser le flux compressé: la nature de la compression élève l'entropie et produit donc un flux peu compressible. Très rapidement recompresser alourdira ton flux.
Troll en vue ! Ne le nourrissez pas !
N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java
Que la force de la puissance soit avec le courage de ta sagesse.
Lu'!
Je te répondre la même chose que sur un certain autre site :
fanmangaextrazlove a écrit:
L'erreur c'est qu'il n'y a pas de démonstration, tu te bases sur un exemple, pas sur un cas général. Tu veux faire une démonstration :Mais dit moi y t'il une erreur dans la démonstration.
- Soit f la fonction de (0,1)^n vers (0,1)^32 avec n arbitrairement grand et f^-1 son inversion définies par : <écrire ta définition de f et f^-1 ici>,
- Montrons que pour tout n de N et tout z de Z encodable dans (0,1)^n : f^-1( f (z) ) = z .
Et là tu écris la preuve et tu vas vite comprendre que tu n'y arriveras pas. Même mieux essaie juste avec une fonction de (0,1)^(n+1) vers (0,1)^n.
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager