Ответы:
Подобная задача встречается при кодировании аналогового сигнала в виде 0 и 1 в компьютерных сетях. Почитайте про скремблирование.
Для произвольного файла невозможно гарантировать увеличение размера менее, чем на 25%.
Это будет очевидно, если рассмотреть файл, состоящий из одних 1.
Я бы сделал так: Для каждой группы из двух бит, ввел бы первый начальный флаговый бит, который бы означал например если "1" - то следующие два бита остаются как есть, если "0" - то следующие два бита, содержали/содержат "11" (то есть, то что нужно выкинуть или вернуть, при обратном процессе). Т.к. в байте таких групп 4, мы увеличиваем число бит на 4, то есть в два раза :) Боюсь, уложиться именно в 25% максимум - просто невозможно. Теперь, мы работаем с файлом как с обычным набором данных, помятуя о том, что каждый третий бит (и первый, в первом блоке) - у нас лишние, и нужны для кодирования
Пока ехал домой, понял, что мой предыдущий пост содержал ошибку.
решение по крайней мере лучшее, чем увеличение файла в 2 раза, это ставить нули межу не всеми битами:)
например разбиваем последовательность по 7 бит
если встречается 11, то вставляем нули, а перед блоком записываем 1, иначе оставляем как есть, а перед блоком записываем 0.
учитываем это при обработке.
полагаю есть какая-то оптимальная длина блока.
можно закодировать способ обработки блока 2-мя битам, варьируя длинной блока, или способом расстановки нулей (например ставить через один), или на что хватит фантазии.
Пусть длина исходного файла 2m (в битах; 2m потому, что она чётная). Мы хотим получить файл длины 2n
согласен с господами ub и gaosipov. а для реализуемости идеи с преобразованием входного потока из четверичной системы в троичную можно разбить входной поток на блоки четверичных цифр максимально приемлемого размера и конвертировать блоками. для решения проблемы с нулями в конце входного потока можно в начало выходного потока дописывать их число в той же троичной системе, тогда однозначность отображения входных потоков на выходные будет обеспечена.
Если мы разобъём на блоки, то время ухудшится: будет O(n^2) вместо O(n log n) (это потому, что время деления у нас теперь будет равно не логарифму, а количеству блоков, которое есть O(n)), зато бедт маленькая константа при n^2 (чем боле блок - ткм меньше) и в памяти можно будет хранить не всё, а только блок.
Допустим, мы придумали алгоритм, как превратить файл длины 2n
в "хороший файл длины 125/100 от 2n, то есть длины 5n/2,
с возможностью последующего восстановления.
сколько всего возможных файлов длины не больше 2n:
16 лет назад