Programme de Compression en C

Ce que vous essayez de faire est appelée Run-Length Encoding.

Je pense que le comptage de l'ensemble des personnages et, plus précisément, de quelque caractère particulier (par exemple, des points, des virgules, des espaces) est une distraction inutile si votre objectif est simplement de longueur compresser la chaîne. Donc, nous allons ignorer pour l'instant.

Voici comment vous pouvez le faire facilement en run-length encoding (encodage d'une chaîne de caractères ASCII en place. c'est à dire la chaîne d'origine sera remplacée par le comprimé de la chaîne. Cela peut ou peut ne pas être ce que vous voulez, mais il économise de l'attribution d'un autre tampon et est facile à coder.

char *compress(char *str) {
    char *start = str;
    char *c_first = str;
    char *c_last = str;
    char *c_write = str;
    int run_len = 0;
    while (*str) {
        ++c_last;
        ++run_len;
        if (!(*c_last) || *c_last != *c_first || run_len == 9) { 
            //end of run
            *(c_write++) = *c_first;
            if (run_len > 1)
                *(c_write++) = '0' + run_len;
            //start next run
            run_len = 0; 
            c_first = c_last;
        }
        ++str;
    }
    *c_write = 0;
    return start;
}

Si le nombre ou l'exclusion de tous les caractères spéciaux le long de la route est nécessaire, vous pouvez le faire facilement dans la while boucle.

Ajouter ce pour permettre de tester à partir de la ligne de commande. Exécuter avec votre chaîne d'origine comme le seul argument.

int main(int argc, char **argv) {
    if (argc != 2)
        return 1;
    printf("%s\n", compress(argv[1]));
    return 0;
}

À vos exigences pour la sortie ne sont pas complètement spécifié, si mes hypothèses sont les suivantes:

1. Optimisation de l'hypothèse: Pistes de longueur 1 ne sont pas compressés. C'est facile à détecter lors de la décompression et assure la compression de la chaîne n'est jamais plus long que l'original. par exemple, "ABBCDEF" comprime "AB2CDEF" (au lieu de "A1B2C1D1E1F1")

2. Hypothèse simplificatrice: Pistes de plus de 9 caractères seront compressés en plusieurs morceaux. Cela garantit une longueur de course peut toujours être exprimé en une seule ASCII des chiffres. c'est à dire "AAAAAAAAAAAABBBB" comprime "A9A3B4" Si vous avez besoin de la sortie de la "A12B4", il n'est pas difficile. Supprimer la run_len == 9 de comparaison et d'étendre le code sous run_len > 1 à utiliser iota pour la chaîne de rendu.

OriginalL'auteur Darren Stone

Il me semble que vous avez deux problèmes mélangés.

La première, comme cela a été souligné par @Darren, est appelé Run-Length Encoding: look pour une séquence d'octets identiques, et de les remplacer par un seul octet suivi par un nombre de répétitions. La seconde, aussi loin que je peux dire, est de compter combien de certains des caractères "spéciaux" se produisent dans la chaîne.

Run-Length Encoding

Je vais vous donner une mise en œuvre différente de RLE que @Darren. Comme sa solution, mine de ne pas traiter avec le "caractère spécial" pièces= de la cession. Je vais commencer avec

void
rll_encode(char *in, char *out)
{
    while (*in != '
void
rll_encode(char *in, char *out)
{
while (*in != '\0') {
int len = find_run(in);
out = emit_run(out, *in, len);
in = in + len;  //advance the input
}
*out = '\0';
}
') {
        int len = find_run(in);
        out = emit_run(out, *in, len);
        in = in + len;  //advance the input
    }
    *out = '
void
rll_encode(char *in, char *out)
{
while (*in != '\0') {
int len = find_run(in);
out = emit_run(out, *in, len);
in = in + len;  //advance the input
}
*out = '\0';
}
';
}

C'est le squelette de run-length encoding: se déplacer dans l'entrée de trouver des pistes, puis émet ceux exécuter dans la sortie, correctement encodés. Cette boucle est constituée de trois étapes:

1. La find_run fonction est d'aller le chercher le plus long autorisé exécuter en commençant à l'emplacement actuel de l'entrée, pointé par in. Il retourne la longueur de la course, qui sera toujours plus grande que zéro.
2. De même, emit_run prend un caractère et une répétition de compter, et génère le bon encodage dans la mémoire tampon de sortie. Il retourne le prochain emplacement à utiliser dans le tampon de sortie.
3. Après émettant de la course, on avance le pointeur dans la mémoire tampon d'entrée par len octets et répéter la boucle.

Après la boucle est terminée, on ajoute un octet NUL sur le tampon de sortie de sorte qu'il forme une chaîne valide. Dans un vrai compresseur de toute sorte, cette dernière étape ne serait pas fait, et l'entrée et la sortie des tampons seraient tous les deux ont des tailles qui leur sont associés.

La seule bits de gauche sont pour la mise en œuvre find_run et emit_run. Commençons par emit_run que c'est un peu plus simple:

char *
emit_run(char *out, char c, int len)
{
    *out++ = c;
    *out++ = '0' + len;
    return out;
}

Cela prend un tampon de sortie out, un personnage c, et c'est assocated nombre de répétitions len. Compte tenu, par exemple, c == 'A' et len == 5, il ajoute C5 de la mémoire tampon de sortie.

Il y a un assez grave problème avec cette fonction. Examinons ce qui se passe à la chaîne "ABCDE": chaque lettre a un compteur de répétition de l'un, et la chaîne est codé comme "A1B1C1D1E1", ce qui est très peu compressé. Il existe plusieurs approches à ce problème, certains sont discutés dans les réponses à cette question, et tout ce qui peut être mis en œuvre par de petits changements à emit_run.

Ce qui nous laisse avec le problème de trouver les pistes en premier lieu.

int
find_run(char *in)
{
    char run_char = *in;
    int run_len = 0;
    for (;;) {
        char c = *in;
        bool run_ended = 
            c != *run_char || //catches '
int
find_run(char *in)
{
char run_char = *in;
int run_len = 0;
for (;;) {
char c = *in;
bool run_ended = 
c != *run_char || //catches '\0', too
run_len == MAX_RUN;
if (run_ended)
break;
run_len++;
in++;
}
return run_len;
}
', too
            run_len == MAX_RUN;
        if (run_ended)
            break;
        run_len++;
        in++;
    }
    return run_len;
}

Cette fonction est donné un endroit pour commencer la numérisation, in, et renvoie combien de fois le premier caractère de l'entrée se répète.

1. Copie le premier caractère de la zone tampon dans run_char, et initialiser run_len à zéro.
2. Regarder chaque personnage c dans l'entrée, et de décider si la course a pris fin ou non. La course se termine si un c n'est pas égal à run_char, ou si l'exécution a atteint sa longueur maximale. Notez que la vérification de c pas égal à run_char gère également frapper la fin de la chaîne, c'est à dire, c est NUL.
3. Si la course est terminée, sortir de la boucle et le retour de la longueur du cycle.
4. Si la course n'est pas terminée, aller de l'avant dans la saisie d'un caractère, et l'incrément de la longueur du cycle.

Toutes ces pièces ensemble, de mettre en œuvre une version simple de run-length encoding. Ce qui suit est un squelette d'un petit programme de test.

#include <stdio.h>
#include <stdbool.h>
#define MAX_RUN 9

/* insert emit_run from above */
/* insert find_run from above */
/* insert rll_encode from above */

int main(int argc, char **argv)
{
    char out[1024];
    rll_encode(argv[1], out);
    printf("%s\n", out);
}

J'ai essayé de mettre en place cette mise en oeuvre particulière afin de maximiser la clarté de l'algorithme, mais @Darren version est plus proche de ce que vous pouvez voir dans le code de production dans l'ensemble de la mise en œuvre est en une seule fonction. Son choix pour encoder en place est certainement valable, bien que je pense que les deux en place et de séparer en sortie de la mémoire tampon versions sont communs. Les premiers sont un peu plus difficile à comprendre si vous êtes nouveau à C, et en particulier des pointeurs. Aussi, dans toutes les versions de production, à la fois l'entrée et la sortie des tampons serait donné de manière explicite les longueurs, et il y aurait un code supplémentaire de vérifier pour le débordement de la mémoire tampon de sortie, les deux dont j'ai ignoré ici.

Caractère De Comptage

Concernant le caractère de comptage, n'essayez pas de garder une magie variable séparée pour chaque caractère spécial. Au lieu de cela, je suggère à l'aide d'un 256-élément de tableau d'accumuler des comtes de tous de caractères, puis plus tard d'imprimer seulement les entrées que vous voulez.

C'est assez facile de modification de find_run si vous utilisez un réseau mondial, mais encore une fois, vous ne voudriez pas le faire de cette façon dans une véritable mise en œuvre.

OriginalL'auteur Dale Hagglund

Peut-être trop long mais facile à comprendre je pense.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* compress(char* str) {
int i;
int z = 0;
int k = 1;
int size_str = strlen(str);
char *compress_str = malloc(size_str + 1);
if (size_str < 2) {
return str;
}
for (i = 0; i < size_str; i++) {
if (i == 0) {
compress_str[z] = str[i];
} else {
if (str[i] == str[i-1]) {
compress_str[z] = str[i];
if ( k >= 9 && k < 99) {
k++;
compress_str[z + 1] = (k / 10) + 48;
compress_str[z + 2] =  (k % 10) + 48;
} else if (k >= 99) {
k++;
compress_str[z + 1] = (k / 100) + 48;
compress_str[z + 2] =  ((k / 10) % 10) + 48;
compress_str[z + 3] =  (k % 10) + 48;
} else {
k++;
compress_str[z + 1] = k + 48;
}
} else {
if (k >= 10 && k < 100) {
z = z + 3;
k = 1;
compress_str[z] = str[i];
} else if  (k >= 100) {
z = z + 4;
k = 1;
compress_str[z] = str[i];
} else if (k > 1 && k <= 9) {
z = z + 2;
k = 1;
compress_str[z] = str[i];
} else if (k == 1){
z++;
compress_str[z] = str[i];
}
}
}
}
return compress_str;
}
int main() {
char* res;
char* str;
str = (char *)malloc(10240 * sizeof(char));
scanf("\n%[^\n]", str);
res = compress(str);
printf("%s\n", res);
return 0;
}

OriginalL'auteur vmule