c - C中的压缩程序

Question

我想压缩一系列字符。例如，如果我输入

输入：FFFFFBBBBBBBCCBBBAABBGGGGGSSS（27 x 8 位 = 216 位）输出：F5B7C2B3A2B2G5S3（14 x 8 位 = 112 位）

到目前为止，这就是我所拥有的，我可以计算数组中的字符数。但最重要的任务是按相同的顺序计算它们。我似乎无法弄清楚 :( 几周前我就开始关注 C 语言，我对数组、指针、ASCII 值有所了解，但无论如何似乎无法按顺序计算这些字符。我尝试了什么都有。这种方法不好，但它是我最接近它的方法。

#include <stdio.h>
#include <conio.h>

int main()
{

 int charcnt=0,dotcnt=0,commacnt=0,blankcnt=0,i, countA, countB;
 char str[125];



 printf("*****String Manipulations*****\n\n");
 printf("Enter a string\n\n");

 scanf("%[^'\n']s",str);


 printf("\n\nEntered String is \" %s \" \n",str);


 for(i=0;str[i]!='\0';i++)
 {

 // COUNTING EXCEPTION CHARS                         
 if(str[i]==' ')
    blankcnt++;

 if(str[i]=='.')
    dotcnt++;

 if(str[i]==',')
    commacnt++;

 if (str[i]=='A' || str[i]=='a')

  countA++;

      if (str[i]=='B' || str[i]=='b')

  countA++;

 }

 //PRINT RESULT OF COUNT
 charcnt=i;
 printf("\n\nTotal Characters : %d",charcnt);
 printf("\nTotal Blanks     : %d",blankcnt);
 printf("\nTotal Full stops : %d",dotcnt);
 printf("\nTotal Commas     : %d\n\n",commacnt);
 printf("A%d\n", countA);

 }

Answer 1

您正在尝试做的是称为Run-Length Encoding。

如果您的目标是简单地运行长度压缩字符串，我认为对所有字符的计数，特别是对任何特定字符（例如点、逗号、空格）的计数是不必要的干扰。所以让我们暂时忽略它。

以下是您可以轻松地对 ASCII 字符串进行游程编码的方法。即原始字符串将被压缩字符串覆盖。这可能是也可能不是您想要的，但它节省了另一个缓冲区的分配并且易于编码。

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;
}

如果需要计算或排除任何特殊字符，您可以在while循环中轻松完成。

添加此项以允许从命令行进行测试。使用原始字符串作为单个参数运行。

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

您对输出的要求没有完全指定，所以我的假设是：

1. 优化假设：长度为 1 的运行未压缩。这在解压缩时很容易检测到，并确保压缩字符串永远不会比原始字符串长。例如"ABBCDEF"压缩到"AB2CDEF"（而不是"A1B2C1D1E1F1"）

2. 简化假设：超过 9 个字符的运行将被压缩成几部分。这确保了游程长度始终可以用单个 ASCII 数字表示。ie"AAAAAAAAAAAABBBB"压缩到"A9A3B4" 如果你需要输出为"A12B4"，这并不难。删除run_len == 9比较并展开下面的代码run_len > 1以iota用于字符串渲染。

Answer 2

设置一个计数器。在 for 循环中扫描数组。只要数组具有相同的字符序列，就继续增加计数，一旦字符序列中断，将计数设置为最后一个字符的压缩数，并将计数设置为 0 以再次将其添加到下一个序列。要检查序列，您只需放置一个 char 变量，该变量保留最后一个数组项的值，并将其与下一个循环中的下一个数组项进行比较，以查看序列是否中断。

这是一个 O(n) 算法，应该使用。

Answer 3

在我看来，您将两个问题混合在一起。

正如@Darren 所指出的，第一个称为运行长度编码：查找一系列相同的字节，并将它们替换为单个字节，然后是重复计数。第二个，据我所知，是计算字符串中出现了多少“特殊”字符。

游程编码

我将给出与@Darren 不同的 RLE 实现。像他的解决方案一样，我的不处理作业的“特殊字符”部分=。我要开始

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';
}

这是游程编码的框架：遍历输入查找运行，然后将这些运行发送到输出中，并进行适当编码。这个循环由三个步骤组成：

1. 该find_run函数将查找从输入中的当前位置开始的最长允许运行，由 指向in。它返回该运行的长度，该长度始终大于零。
2. 同样，emit_run获取一个字符和一个重复计数，并在输出缓冲区中生成正确的编码。它返回要在输出缓冲区中使用的下一个位置。
3. 发出运行后，我们将指针按字节推进输入缓冲区len并重复循环。

循环完成后，我们将一个 NUL 字节附加到输出缓冲区，以便它形成一个有效的字符串。在任何类型的真正压缩器中，最后一步都不会完成，输入和输出缓冲区都将具有与之相关的大小。

剩下的唯一部分是实际实现find_runand emit_run。让我们开始吧，emit_run因为它有点简单：

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

这需要一个输出缓冲区out、一个字符c和相关的重复计数len。例如，给定c == 'A'and len == 5，它会附加C5到输出缓冲区。

这个函数有一个相当严重的问题。考虑一下字符串会发生什么"ABCDE"：每个字母的重复计数为 1，因此字符串被编码为"A1B1C1D1E1"，几乎没有被压缩。有多种方法可以解决这个问题，其中一些在这个问题的答案中进行了讨论，所有这些方法都可以通过对emit_run.

这给我们留下了首先找到运行的问题。

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;
}

该函数有一个开始扫描的位置in，并返回输入的第一个字符重复的次数。

1. 将缓冲区的第一个字符复制到 中run_char，并初始化run_len为零。
2. 查看c输入中的每个字符，并确定运行是否结束。如果c不等于run_char，或者运行已达到其最大长度，则运行结束。请注意，检查c不等于run_char也处理命中字符串的末尾，即cis NUL。
3. 如果运行已结束，则离开循环并返回运行长度。
4. 如果运行尚未结束，则在输入中向前移动一个字符，并增加运行长度。

所有这些部分共同实现了一个简单版本的游程编码。下面是一个小程序的骨架来测试一下。

#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);
}

我试图设置这个特定的实现以最大限度地提高算法的清晰度，但@Darren 的版本更接近您在生产代码中看到的，因为整个实现都在一个函数中。他选择就地编码当然是有效的，尽管我认为就地和单独的输出缓冲区版本都很常见。如果您是 C 新手，尤其是指针，前者更难理解。此外，在任何生产版本中，输入和输出缓冲区都将给出明确的长度，并且会有额外的代码来检查输出缓冲区的溢出，这两个我在这里都忽略了。

字符计数

关于字符计数，不要尝试为每个单独的特殊字符保留一个魔术变量。相反，我建议使用 256 元素数组来累积所有字符的计数，然后再打印出您想要的条目。

如果您使用全局数组，这是一个相当容易的修改find_run，尽管在实际实现中您不会这样做。

Answer 4

这是我为此分配制定的解决方案 - 此函数用于压缩字符串。如果仍有问题，希望对您有所帮助。

    #include <stdio.h>

extern compression_function(char arr[1000])

{
   char current_char;
   int count, i,j=0,t=0,G=0,H=0, char_size=0;
   int original_length=0,com_number_length=0,compressed_length=0;
   int index=0;

    FILE* outputfile;
    FILE* processing;

   outputfile= fopen("C:\\Users\\Desktop\\output.txt","w");
   processing= fopen("C:\\Users\\Desktop\\processing.txt","w");

   if(outputfile == '\0' )
{ 
                printf("Cannot Write To File!\n");

                }        


current_char = arr[0]; 
count = 1; 
i = 0; 

printf("\n\nOUTPUT: ");
//USING A WHILE LOOP
while (arr[i] != '\0') 
{ 
//'i' WILL BE INCREMENTED TO CHECK ALL THE CHAR IN THE ARRAY      

i++;

// CHECK IF THE CURENT CHAR IS THE SAME AS THE LAST ONE        
if( arr[i] == current_char )
{
count++; 
}

//ELSE IF NO MORE CHAR IS SIMILAR, IT WILL PRINT THE COUNT RESULT RIGHT AWAY    
else
{
if(count==1)
{ 
//sprintf(output_array,"%c", current_char);             
printf("%c", current_char);
fprintf(outputfile,"%c", current_char);
fprintf(processing,"%c", current_char);

G++;
}

if(count>=2)
{        
       printf("%c%d", current_char, count);
       fprintf(outputfile,"%c%d", current_char,count);
       fprintf(processing,"%c", current_char );
       }

if (count>9)
{
           j++;
           }
           if (count>99)
{
           t++;
           }

//REST ALL COUNT FOR THE SECOND DIFFRENT CHAR IN ARRAY

   current_char = arr[i]; 
   count = 1;
   char_size++;


//BREAK THE LOOP WHEN CHAR IN ARRAY IS NULL       
   if( current_char == '\0' )
   {

           break;

           }   
    } 
    }

 original_length = strlen(arr);
 com_number_length=(char_size+j+t-G);
 compressed_length=(char_size+char_size+j+t-G);

 fclose(outputfile);
 fclose(processing);

 //CALLING FUNCTION-SIZE-CALCULATOR
size_calculator(original_length,char_size,com_number_length,compressed_length);


           }

Answer 5

我认为可能太长但很容易理解。

#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;
}