Теория сжатия без потерь, основана ли степень сжатия на размере шаблона и времени повторения?

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

Правильно ли я предполагаю, что степень сжатия зависит от шаблонов?

  1. Размер
  2. Раз повторяется

Например, двоичные данные:

10 10 10 10 10 10 10 10 узор (10) размер 2, узор (10) повторяется 8

1001 1001 1001 1001 узор (1001) размер 4, узор (1001) повторный 4

0000000 11111111 шаблон (0) размер 1, шаблон (0) повторяется 8; выкройка (1) размер 1, выкройка (1) повторная 8; Или 0000000 11111111 шаблон (0000000) размер 8, шаблон (0000000) повторяется 8; выкройка (11111111) размер 8, выкройка (11111111) повторяется 1;

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

Заранее спасибо.


compression binary-data lzw huffman-code lossless
person chineerat    schedule 08.10.2012    source источник
comment
Ваши первые два примера должны сжиматься одинаково, если алгоритм умен. (Они эквивалентны — первый можно также рассматривать как шаблон размера 4, повторяющийся 4 раза.) В более общем смысле любой шаблон длиной N, который повторяется M раз, можно рассматривать как шаблон, состоящий из N*C. длины и повторяется M/C раз для некоторой константы C.   -  person cdhowie    schedule 09.10.2012
comment
Алгоритмы сжатия очень разные. Алгоритмов в стиле LZ должны быть десятки. Почему ты спрашиваешь?   -  person usr    schedule 09.10.2012
comment
Всем привет! Спасибо за ваши ответы. Причина, по которой я спросил, заключается в том, что у меня есть идея применить слой алгоритма перед сжатием без потерь. Это всего лишь концепция, еще предстоит провести тщательное тестирование, не говоря уже о прототипе. Мне было любопытно, какие входные данные для LZW и алгоритма Хаффмана без потерь обеспечивают максимальное сжатие. У меня есть блок-схема того, как я хотел бы применить алгоритм и его ограничения ниже: i46.tinypic.com/351vmll.png Ваше честное мнение? Не стесняйтесь протыкать дыры   -  person chineerat    schedule 15.10.2012

Ответы (1)


arrow_upward
2
arrow_downward

Это все последовательности, которые вряд ли можно увидеть в дикой природе. В чем суть вопроса?

Обычные компрессоры ориентированы на байты. Таким образом, любой шаблон, который приводит к простому повторению одного и того же байта, даст самую высокую степень сжатия. Например. 1032:1 в пределе для выкачки. Другие простые повторения коротких шаблонов получат очень высокие коэффициенты сжатия. Например. снова 1032:1 для выкачки шаблонов из двух или трех повторяющихся байтов.

Ограничение на сжатие в этих абсурдно экстремальных случаях зависит от формата сжатия, а не от данных.

person Mark Adler    schedule 09.10.2012
comment
Всем привет! Спасибо за ваши ответы. Причина, по которой я спросил, заключается в том, что у меня есть идея применить слой алгоритма перед сжатием без потерь. Это всего лишь концепция, еще предстоит провести тщательное тестирование, не говоря уже о прототипе. Мне было любопытно, какие входные данные для LZW и алгоритма Хаффмана без потерь обеспечивают максимальное сжатие. У меня есть блок-схема того, как я хотел бы применить алгоритм и его ограничения ниже: i46.tinypic.com/ 351vmll.png Ваше честное мнение? Смело делайте дырки. - person chineerat; 14.10.2012
comment
Вам нужно провести небольшое исследование. LZW устарел, а кодирование Хаффмана является лишь частью других схем моделирования избыточности. Прочтите о LZ77, преобразовании Берроуза-Уилера, прогнозировании путем частичного совпадения и арифметическом кодировании. Вы также можете взглянуть на XML-WRT, текстовый препроцессор, применяемый для улучшения последующего сжатия без потерь. - person Mark Adler; 14.10.2012