Работают ли алгоритмы сжатия без потерь на битовом уровне?

Question

Скажем, например, что у меня есть файл, и я хочу создать алгоритм сжатия в C, если мой алгоритм получит битовое представление этого файла, поработайте над ним и напишите новый файл, который будет знать только мой алгоритм.распаковать?

Answer 1

Интуиция простого сжатия файлов

Рассмотрим отображение M: K -> V .

Требования для такого сопоставления состоят в том, чтолюбая входная строка k может быть специально сопоставлена ​​с некоторой, возможно, более короткой строкой M (k) = v .

Пример

Ваш входной файл

aaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbcccccaaaaaaaaaa

Алгоритм сжатия должен найти какое-то отображение M , которое обеспечит хорошее сжатие, не занимая слишком много времени длясделай это.В этом случае, интуитивно, вы можете использовать:

M(aaaaaaaaaa) = a
M(bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) = b
M(ccccc) = c

И сжатый файл становится

abca

Вы можете распаковать файл, выполнив то же самое в обратном порядке.

(обратите внимание, что отображение нужно каким-то образом хранить рядом с сжатым файлом, чтобы вы могли распаковать его позже)

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