Программисты — удалённая работа в Москве

Системное программирование. Разработка с нуля. Кодирование длин серий (run-length encoding, RLE) — алгоритм сжатия данных, заменяющий повторяющиеся символы на один символ и число его повторов. Рассмотрим произвольную строку символов: AAAAABBBCCCCCCCCCAAAABAAAAAAAA. Посчитаем количество символов: 5 символов «A» 3 символа «B» 9 символов «C» 4 символа «A» 1 символ «B» 8 символов «A» Итого найдено 6 серий. Заменим серии на число повторов и сам повторяющийся символ: 5A3B9C4A1B8A. Получилась последовательность из 12 символов. Исходная последовательность состояла из 30 символов. Данные были сжаты в 30/12?2.5 раза. Возьмём строку, состоящую из большого количества неповторяющихся символов: ABCABCABCDDDEEEEEE. После сжатия методом RLE такая строка будет выглядеть так: 1A1B1C1A1B1C1A1B1C3D6E Исходная строка состоит из 18 символов, а сжатая — из 22. Размер данных увеличился в 22/18?1.22 раза. Увеличение размера после сжатия произошло из-за того, что есть 9 символов подряд, которые были только по 1 разу. Можно было бы компактнее записать, что следующие 9 символов встречаются по одному разу, а далее 3 раза D, 6 раз E. Чтобы в дальнейшем различать, что означает записанное число, договоримся, что положительные числа будем использовать для записи количества повторов одного символа, а отрицательные — для записи количества неодинаковых символов, следующих друг за другом. Тогда сжатая строка запишется в виде: -9ABCABCABC3D6E. Исходная строка состоит из 18 символов, а сжатая — из 15. Размер данных уменьшился в 18/15=1.2 раза. Но тогда нужно хранить отдельно знак -. Нужно сделать так, чтобы количество символов, встречающихся по одному разу, и количество повторяющихся символов можно было бы записать одним символом (байтом). Для записи длин серий (для подсчёта количества символов) используем переменную целочисленного типа со знаком signed char. В такую переменную можно записать числа от -128 до 127 включительно. Учтем, что нет необходимости записывать, что какой-то символ повторился 0 раз. Если длина серии будет отрицательное число, то его модуль будет означать сколько символов далее в последовательности встречаются по одному разу. А если длина серии является неотрицательным числом Х, то оно означает, что следующий символ встретился в последовательности X+2 раз. Тогда сжатая строка запишется в виде -9ABCABCABC1D4E и будет занимать 14 байт (представление в памяти в 16-ричном виде: F7 41 42 43 41 42 43 41 42 43 01 44 04 45). Как же быть, если длина серии равна 130 символам и более? В этом случае серию разделяют на части так, чтобы длина части не превышала 129 символов. Например, серия, состоящая из 200 символов «A», будет закодирована следующей строкой: 7F 41 45 41. Пояснение: 200 = 129 + 71, 129 - 2 = 127 в 16-ричном виде 7F, 71 - 2 = 69 в 16-ричном виде 45. Как быть, если неповторяющихся символов более 128? В этом случае серию разделяют на части так, чтобы длина части не превышала 128 символов. Необходимо написать программу, которая выполняет RLE: кодирование и декодирование. Выполняемое действие, имена входного и выходного файлов задаются в командной строке. Например, для кодирования файла input.txt и записи ответа в файл output.rle: ./rle -e input.txt output.rle Для декодирования файла input.rle и записи ответа в файл decoded: ./rle -d input.rle decoded Требования Программа не должна использовать контейнеры STL (std::vector, std::string и т. д.).