C中的压缩程序

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

输入:FFFFFBBBBBBBCCBBBAABBGGGGGSSS(27 x 8位= 216位)输出:F5B7C2B3A2B2G5S3(14 x 8位= 112位)

到目前为止,这就是我所拥有的,我可以计算数组中的字符数。 但最重要的任务是以相同的顺序计算它们。 我似乎无法弄明白:(仅仅几个星期前我已经盯着做C,我对数据,指针,ASCII值有所了解但无论如何似乎无法按顺序计算这些字符。我试过一个所有的一切。这种方法并不好,但它最接近它。

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

你要做的是称为运行长度编码 。

我认为如果你的目标是简单地对字符串进行行程长度压缩,那么对整个字符,特别是任何特定字符(例如点,逗号,空格)的计数是不必要的分心。 所以现在让我们忽略它。

以下是您可以轻松地对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数字表示。 即"AAAAAAAAAAAABBBB"压缩为"A9A3B4"如果您需要输出为"A12B4" ,则不难。 删除run_len == 9比较并展开run_len > 1下的代码以使用iota进行字符串渲染。

设置一个计数器。 在for循环中扫描数组。 只要数组具有相同的字符序列,就保持递增计数,一旦字符序列中断,将计数设置为最后一个字符的压缩数,并将count设置为0,以便为下一个序列再次添加它。 要检查序列,您可以简单地放置一个char变量,该变量保存最后一个数组项的值,并将其与下一个循环中的下一个数组项进行比较,以查看序列是否中断。

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

听起来像你有两个混合在一起的问题。

第一个,正如@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_runemit_run 。 让我们从emit_run开始,因为它有点简单:

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

这将输出缓冲区out ,字符c和它的关联重复计数len 。 例如,给定c == 'A'len == 5 ,它将C5附加到输出缓冲区。

这个function有一个相当严重的问题。 考虑字符串"ABCDE"会发生什么:每个字母的重复次数为1,因此字符串编码为"A1B1C1D1E1" ,几乎不会被压缩。 这个问题有多种方法,其中一些方法在这个问题的答案中讨论过,所有这些方法都可以通过对emit_run的小改动来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; } 

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

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

所有这些部分一起实现了一个简单版本的游程编码。 以下是测试它的小程序的框架。

 #include  #include  #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一个相当容易的修改,尽管你不会在真正的实现中这样做。

这是我为此任务设计的解决方案 – 此函数用于对字符串进行压缩。 如果仍有问题,希望它有所帮助。

  #include  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+tG); compressed_length=(char_size+char_size+j+tG); fclose(outputfile); fclose(processing); //CALLING FUNCTION-SIZE-CALCULATOR size_calculator(original_length,char_size,com_number_length,compressed_length); } 

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

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