Не большая статья доказывающая сжимаемость на "не сжимаемых данных"
http://boctopr.ru/2011/08/data-compression

оффлайн версия статьи на случай если сайт будет не доступен
http://dl.dropbox.com/u/26963803/boctopr.ru/article.ZIP

f1restarter
Если честно, статья написана несколько невнятно, понял только с 3-го раза суть алгоритма. Я так понял, что при N=8 блоки длиной 2048 бит кодируются в системе счисления, основание которой записывается числом, которое вмещается меньше, чем в 2048 бит (например в 2047 бит). А словарь для декодирования занимает 524288 бит (64 КБайт). В итоге алгоритм будет сжимать данные только там, где сумма чисел в измененной таблице распределений будет хотя бы в 2 раза меньше суммы в неизмененной таблице (экономия 1 бит на блок). И что-то мне подсказывает, что для уже сжатых данных тем же 7-zip это будет не так.

И сама статья написана с ошибками:



Полностью переписать как "Далее входящий поток кодируется в системе счисления с основанием, равным сумме чисел в измененной таблице распределений. За счет этого и происходит сжатие данных".

Еще неточность:


Кстати на видео словарь для декодирования занимает не 256 бит, которых было бы достаточно, а судя по всему это просто дамп измененной таблицы распределений.

Добавлено спустя 3 минуты 31 секунду:
Кстати, алгоритм реально будет работать на данных с высокой избыточностью. Например файл из повторяющихся одинаковых байт при N=8 он ужмет в 256 раз.

К сожалению, я больше практик, чем теоретик. Да и статьи пишу сравнительно недавно получилось немного сумбурно. Буду писать вторую статью, объясняющую некоторые неточности.
Ну первое что хочу заметить. Алгоритма два. Первый это теоретическое описание, а второй алгоритм продемонстрирован на видео. Второй алгоритм сход по идеи BTW то есть подготавливает данные для сжатия классическими алгоритмами.
А на счет систем счисление основание может быть и 2048 бит но с немного меньшей числом.
например
8 ричная система счисления.
8 комбинаций на позицию, занимают 3 бита 8*8*8=512, если перевести число 511 (с учетом нуля) в двоичную систему это будет 9 бит
6 ричная система счисления.
6 комбинаций на позицию, изначально занимают 3 бита, но если цепочка слов больше 3 то уже происходит сжатие 6*6*6=216 вариантов. Переводим число в двоичную систему будет 8 бит итого выигрыш один бит
=216 вариантов. переводим число в двоичную систему будет 8 бит итого выигрыш один бит

Добавлено спустя 5 минут 59 секунд:

истинно так, но есть комбинация, в которой алгоритм "работать" не будет вообще. Хотя цель достигнута. На неких сжатых данных достаточной длины, можно выиграть пару бить-байт. Я думаю это новый виток алгоритмов сжатия.

f1restarter Если допустить что любые данные можно сжать хотя бы на 1 бит, то в конце концов придём к тому что любые данные можно ужать всего в 1 бит
так что ищите ошибки в алгоритме

Добавлено спустя 1 минуту 26 секунд:
з.ы. информаци о том в какой системе было кодирование где-нибудь сохраняется? может это те самые "съэкономленные" биты

Ни какой ошибки здесь нет потому что это сделать не удастся, есть словарь который увеличивает выходной поток на 2^N. это по первому алгоритму, а по второму там тоже словарь есть 65536 байт целый, так что, фантастики тут нет.