Программа сжатия в C

То, что вы пытаетесь сделать, называется кодированием длины выполнения.

Я думаю, что подсчет общих символов и, в частности, любого конкретного символа (например, точек, запятых, пробелов) является ненужным отвлечением, если ваша цель состоит в том, чтобы просто сжать строку по длине. Так что давайте пока проигнорируем это.

Вот как вы можете легко выполнить кодирование длины цикла строки 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. Продолжайте увеличивать счетчик до тех пор, пока массив имеет одинаковую последовательность символов, как только последовательность символов прерывается, установите счетчик как число сжатия для вашего последнего символа и установите счетчик на 0, чтобы добавить его снова для следующей последовательности. Чтобы проверить последовательность, вы просто помещаете переменную char, которая хранит значение последнего элемента массива и сравнивает его со следующим элементом массива в следующем цикле, чтобы увидеть, не прерывается ли последовательность.

Это алгоритм O (n), и его следует использовать.

Мне кажется, у вас смешались две проблемы.

Первый, как указал @Darren, называется Кодирование длины выполнения. : найдите последовательность идентичных байтов и замените их одним байтом, за которым следует количество повторений. Второй, насколько я могу судить, заключается в том, чтобы подсчитать, сколько некоторых «специальных» символов встречается в строке.

Полное кодирование

Я собираюсь дать реализацию RLE, отличную от реализации @Darren. Как и его решение, мое не касается частей = «специального символа» задания. я собираюсь начать с

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_run и 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' и len == 5, он добавляет C5 к выходному буферу.

С этой функцией есть одна довольно серьезная проблема. Рассмотрим, что происходит со строкой "ABCDE": каждая буква имеет число повторений, равное единице, поэтому строка кодируется как "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, также обрабатывает попадание в конец строки, т. е. c равно 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, если вы используете глобальный массив, хотя, опять же, вы бы не сделали этого в реальной реализации.

Вот решение, которое я разработал для этого задания. Эта функция использовалась для сжатия строки. Надеюсь, это поможет, если у кого-то все еще есть проблема.

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


           }

Может быть, слишком долго, но легко понять, я думаю.

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