Новинки:

Сайт подключен к Orphus. Если вы заметили опечатку, выделите слово и нажмите Ctrl+Enter. Спасибо!

Ответы на упражнения:


Ответы на упражнения к главе 3, "Словарные методы сжатия данных"

Упражнение: Предложите несколько более эффективных способов кодирования результатов работы LZ77, чем использование простых кодов фиксированной длины.

Можно указать два основных пути повышения эффективности кодирования:

  1. Использование предопределенных кодов переменной длины. Для кодирования длин совпадений и смещений часто используют универсальные коды целых чисел, например γ-коды Элиаса. Эффективность такого кодирования обеспечивается тем, что частоты длин совпадений и смещений в целом убывают с ростом значения числа, поэтому чаще всего используемые длины и смещения обычно будут получать коды меньшей длины. Часто имеет смысл изменять естественное отображение числа в код: например, если известно, что длина совпадения 2 используется в среднем реже длины совпадения 3, то длине 3 следует ставить в соответствие более короткий код, чем длине 2. Можно упорядочить длины совпадения в порядке убывания частоты использования при сжатии тестовых данных и кодировать не величину длины, а соответствующую позицию в ряду отсортированных чисел.
  2. Статистическое кодирование с помощью методов Хаффмана, Шеннона-Фано или арифметического кодирования. При этом кодирование может выполняться как исходя из безусловных частот элементов, так и условных. В последнем случае частота обычно обуславливается значением нескольких предыдущих элементов. При обработке смещений целесообразно кодировать на основе статистики только старшие биты чисел, поскольку, с одной стороны, вследствие большого количества возможных величин смещений статистика для отдельного значения накапливается медленно, с другой стороны, это позволяет избежать трудностей поддержания большого алфавита элементов, для которых подсчитывается статистика. Пример разбиения величин смещений на группы для организации кодирования такого рода приведен в табл. 3.7.

Упражнение: Из-за наличия порога THRESHOLD часть допустимых значений длины реально не используется, поэтому размер буфера BUF_SIZE может быть увеличен при неизменном LEN_LN. Проделайте соответствующие модификации фрагментов программ кодирования и декодирования.

Изменения выделены жирным шрифтом.

Кодирование:

const int
  THRESHOLD = 2,
  OFFS_LN = 14,
  LEN_LN = 4;
const int
  WIN_SIZE = (1 << OFFS_LN),
  BUF_SIZE = (1 << LEN_LN) – 1 + THRESHOLD;
inline int MOD (int i) { return i & (WIN_SIZE-1); };

...
//собственно алгоритм сжатия
int buf_sz = BUF_SIZE;
/* инициализация: заполнение буфера, поиск совпадения
для первого шага
*/
...
while ( buf_sz ) {
  if ( match_len > BUF_SIZE) match_len = BUF_SIZE;
  if ( match_len < THRESHOLD ) {
    CompressedFile.WriteBit (0);
    CompressedFile.WriteBits (window [pos], 8);
    match_len = 1;
  }else{
    CompressedFile.WriteBit (1);
    CompressedFile.WriteBits (match_offs, OFFS_LN);
    CompressedFile.WriteBits (match_len-THRESHOLD, LEN_LN);
  }
  for (int i = 0; i < match_len; i++) {
    DeletePhrase ( MOD (pos+buf_sz) );
    if ( (c = DataFile.ReadSymbol ()) == EOF)
      buf_sz--;
    else
      window [MOD (pos+buf_sz)] = c;
    pos = MOD (pos+1); // сдвиг окна на 1 символ
    if (buf_sz)
      AddPhrase (pos, &match_offs, &match_len)
    ;
  }
}
CompressedFile.WriteBit (1);
CompressedFile.WriteBits (0, OFFS_LN);

Декодирование:

for (;;) {
  if ( !CompressedFile.ReadBit () ){
    c = CompressedFile.ReadBits (8);
    DataFile.WriteSymbol (c);
    window [pos] = c;
    pos = MOD (pos+1);
  }else{
    match_pos = CompressedFile.ReadBits (OFFS_LN);
    if (!match_pos)
      break;
    match_len = CompressedFile.ReadBits (LEN_LN)+THRESHOLD;
    for (int i = 0; i < match_len; i++) {
      c = window [MOD (match_pos+i)];
      DataFile.WriteSymbol (c);
      window [pos] = c;
      pos = MOD (pos+1);
    }
  }
}

 

Упражнение: Объясните, почему размеры полей, хранящих величины HLIT, HDIST и HCLEN, именно таковы, как это указано в табл. 3.10.

Размеры полей определяются диапазонами возможных значений числа литералов/длин совпадений, смещений и кодов длин кодов соответственно с учетом вычитаемых констант. Вообще, введение данных полей не было обязательным и ставило целью небольшое улучшение сжатия за счет уменьшения числа определяемых кодов. Величины констант объясняются следующим образом. Из HLIT вычитается 257, поскольку, с одной стороны, частота появления того или иного из 256 литералов обычно не зависит от величины литерала, и нет оснований надеяться, что литералы с большим значением не будут использоваться в сжимаемом блоке, и, с другой стороны, 257-ой по счету символ со значением 256 указывает на завершение блока и поэтому всегда используется. Вычитание из HDIST единицы предполагает, что должен иметься хотя бы один код смещения. Это условие исторически сложилось при развитии Deflate. Тем не менее, можно указать в таблице описания кодов смещений, что единственный код базы смещения имеет нулевую длину. Вычитание из HCLEN четверки позволяет записать количество кодов длин кодов посредством 4-битового слова, поскольку алфавит кодов длин кодов CWL может включать до 19 символов. При этом накладывается ограничение на минимальное количество описываемых кодов длин кодов — 4, поэтому коды 16, 17, 18, 0, располагающиеся в начале алфавита CWL, всегда определяются.

 

Упражнение: Объясните, почему использование ленивого сравнения при сжатии не требует внесения изменений в алгоритм декодера.

Ленивое сравнение представляет собой вариант стратегии разбора, ничем принципиально не отличающийся от “жадного” разбора. И в том, и в другом случае указатели всегда соответствуют полностью известной декодеру фразе. Декодирование указателей и литералов также всегда будет правильным инвариантно стратегии разбора, поскольку для декодера коды длин совпадений, смещений и литералов не зависят от частоты и последовательности появления соответствующих элементов. Декодер считывает уже готовые таблицы кодов. Таким образом, независимость алгоритма разжатия от деталей алгоритма разбора входной последовательности на фразы словаря и литералы определяется общей особенностью словарных схем типа LZ77 и блочно-адаптивным кодированием указателей и литералов.

 

Упражнение: Придумайте алгоритм кодирования найденной последовательности фраз и литералов.

Возможный алгоритм:

// меняем направление связей списка, с тем чтобы головным
// элементом стал path[0]
i = MAX_T;
int  next_i = path[i].prev_t,
next_prev = path[next_i].prev_t;
while (i) {
  path[next_i].prev_t = i;
  i = next_i;
  next_i = next_prev;
  next_prev = path[next_i].prev_t;
}
path[MAX_T].prev_t = 0;

//
кодируем последовательность фраз и литералов
do {
  if ((path[i].prev_t – i) == 1){
    //кодируем литерал в позиции i
    encode_symbol (i);
    ...
  }else{
    //кодируем строку, начинающуюся с позиции i, как
    // фразу со смещением
path[i].offs и
    // длиной path[i].prev_t – i
    encode_phrase (i, path[i].offs, path[i].prev_t – i);
    ...
  }
  i = path[i].prev_t;
} while (i);

 

Упражнение: Напишите упрощенный алгоритм декодирования.

Вариант решения:

metasymbol = decode_symbol (&symbol_type);
if (symbol_type == LITERAL){
  window [t+1] = metasymbol;
  ...
}else{
  offset_base = metasymbol >> 3;
  match_len = (metasymbol & 7) + 2;
  if (match_len == 9)
    match_length += decode_length_footer ()
  ;
  offset_footer = decode_offset_footer ();
  ...
}


наверх

Ответы на упражнения к главе 4, "Методы контекстного моделирования"

Упражнение: Предложите способы увеличения средней скорости вычисления оценок для методов контекстного моделирования со смешиванием, как полным, так и частичным.

[незавершенный ответ]

Сортировка счетчиков: в порядке убывания частоты; с учетом новизны, т.е. последние встреченные в контексте символы смещаются в начало списка (массива) счетчиков.
Предварительное суммирование счетчиков и организация многовходовой таблицы кумулятивных частот нередко обеспечивает значительное повышение скорости поиска. См. описание соответствующей структуры данных у Фенвика.
Продолжение следует...

Упражнение: Выполните действия, описанные в примере 2, используя ОВУ по методу C. Если текущий символ ‘б’, то точность его предсказания улучшится, останется неизменной или ухудшится?

В соответствии с табл. 4.4:

,

поэтому при вычислении каждой оценки к общему числу просмотров контекста C следует прибавлять количество разных символов в контексте S, а не 1, как в методе A. Процесс вычисления оценки вероятности символа‘б’ можно описать в сравнении для методов A и C при помощи следующей таблицы:

Метод

Последовательность оценок для КМ каждого порядка от 3 до –1

Общая оценка вероятности q(s)

Представление требует битов

3

2

1

0

–1

 

“ббв”

“бв”

“в”

“”

     

A

-

-

-

2.6

C

-

-

-

4

Обратите внимание, что в методе C формирование кодового пространства символа ухода производится без учета исключения, поэтому для контекста “в” оценка ‘б’ равна именно , а не .

Таким образом, использование ОВУ по методу C приводит к ухудшению предсказания символа ‘б’ в указанной ситуации. Это, тем не менее, никоим образом не свидетельствует о преимуществе метода A над C. Действительно, если текущим символом является ‘г’, то он точнее предсказывается методом C, поскольку при этом оценка его вероятности выше:

.

Метод C обычно позволяет точнее предсказывать уход из “молодых” контекстных моделей.

Упражнение: Добавление адаптивного метода ОВУ требует изменения действий по кодированию знака конца файла. Предложите вариант такой модификации.

Возможен такой вариант:

void encode (void){
...
// закодируем знак конца файла символом ухода с КМ(0)
  int esc;
  ContextModel *CM = &cm[context[0]];
  calc_SEE (CM, &esc);
  AC.encode (CM->TotFr, esc, CM->TotFr+esc);
  CM = &cm[256];
  calc_SEE (CM, &esc);
  AC.encode (CM->TotFr, esc, CM->TotFr+esc);
  AC.FinishEncode();  
}

Кодирование знака конца файла можно осуществлять более элегантным способом, не выделяя данное действие как особый случай. Для необходимо либо явно ввести символ конца файла в алфавит, присвоив ему код 256, либо перейти от табличного хранения счетчиков символов контекста к списковому. В последнем случае функция encode может приобрести следующий вид:

void encode (void){

  int  c,
       success;
  init_model ();
  AC.StartEncode (CompressedFile.GetFile());
  do{
    c = DataFile.ReadSymbol();
    // текст функции без изменения
    ...
  }while (c != EOF);
  AC.FinishEncode();
  done_model ();
}

 

Упражнение: Объясните смысл слагаемого Fo–k,o в выражении (4.2).

Fo–k,o — это сумма всех “чистых” частот символов, т.е. это слагаемое равно сумме количеств реальных появлений символов в контекстах порядков o–k+1 … o без учета унаследованных частот и частот символа ухода. Можно сказать, что Fo–k,o характеризует собственную информационную значимость контекстов порядков o–k+1 … o — чем оно больше, тем весомее оценки, вычисляемые для данных контекстов. Коррекция знаменателя правой дроби в формуле (4.2) на величину Fo–k,o позволяет учесть то, что Fo–k,o символов, не равных si, были закодированы в контекстах порядка o–k+1 … o. Информация об этом отсутствует в родительской КМ (o–k).

Упражнение: Сравните DAFC с алгоритмом работы компрессора Dummy. Если пренебречь RLE, то какие изменения следует внести в Dummy, чтобы получить реализацию DAFC?

Введем константы и переменные:

const int N = 31; // число КМ(1)
const int M = 50; // порог частоты встречаемости символа
int   cnt[256],   // частоты встречаемости символов
      con_num;    // количество КМ(1)

Изменим реализацию функции update_model:

void update_model (int c){
  while (SP) {
    SP--;
    if ((stack[SP]->TotFr + stack[SP]->esc) >= MAX_TotFr)
      rescale (stack[SP])
    ;
    // увеличение счетчика ухода не производится,
    // счетчик символа ухода всегда равен 1
    stack[SP]->count[c] += 1;
    stack[SP]->TotFr += 1;
  }
  if ((++cnt[c] == M) && (con_num < N)) {
    cm[c].esc = 1;
    con_num++;
  }
}

Модифицируем также функции encode_sym и decode_sym:

int encode_sym (ContextModel *CM, int c){
  if (CM->esc) stack [SP++].cm = CM;
  ...
}

int decode_sym (ContextModel *CM, int *c){
  if (!CM->esc) return 0;
  ...
}

Упражнение: Сожмите строку с самого начала, найдите действительные значения fr(1) и fr(3), используемые при кодировании 'о' и 'л' в примере.

Для определенности будем считать, что алфавит строки равен {‘м’, ‘о’, ‘л’, ‘ч’, ‘н’, ‘е’, ‘_’, ‘к’}, и он определяет первоначальное ранжирование; начальные значения fr(i) примем за 1.

Процесс обработки опишем с помощью нижеприведенной таблицы.

Шаг

Контекст

Символ

Счетчики символов в КМ и ранги

Ранг i и частота его использования

     

м

о

л

ч

н

е

_

к

i

fr(i)

1

-

м

0

0

0

0

0

0

0

0

1

1

     

1

2

3

4

5

6

7

8

   

2

м

о

0

0

0

0

0

0

0

0

2

1

     

1

2

3

4

5

6

7

8

   

3

о

л

0

0

0

0

0

0

0

0

3

1

     

1

2

3

4

5

6

7

8

   

4

л

о

0

0

0

0

0

0

0

0

2

2

     

1

2

3

4

5

6

7

8

   

5

о

ч

0

0

1

0

0

0

0

0

4

1

     

2

3

1

4

5

6

7

8

   

6

ч

н

0

0

0

0

0

0

0

0

5

1

     

1

2

3

4

5

6

7

8

   

7

н

о

0

0

0

0

0

0

0

0

2

3

     

1

2

3

4

5

6

7

8

   

8

о

е

0

0

1

1

0

0

0

0

6

1

     

3

4

2

1

5

6

7

8

   

9

е

_

0

0

0

0

0

0

0

0

7

1

     

1

2

3

4

5

6

7

8

   

10

_

м

0

0

0

0

0

0

0

0

1

2

     

1

2

3

4

5

6

7

8

   

11

м

о

0

1

0

0

0

0

0

0

1

3

     

2

1

3

4

5

6

7

8

   

12

о

л

0

0

1

1

0

1

_

к

3

2

     

4

5

3

2

6

1

7

8

   

 

наверх

Ответы на упражнения к главе 7, "Предварительная обработка данных"

Упражнение: Каким образом будет передан байт, равный самому флагу исключения?

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

//EXCLUSION_FLAG — флаг исключения
...
c = DataFile.ReadSymbol();
if (c == EXCLUSION_FLAG){
  c = PreprocFile.ReadSymbol();
  // копировать символ в выходной файл без преобразования
  DataFile.WriteSymbol(c);
}else{
  // обработка символа;
  // если требуется, то возможно обратное преобразование
  ...
}

Упражнение: Почему необходимо делать модификацию в том случае, когда предыдущий символ является пробелом?

Иначе преобразование может быть необратимым. Действительно, декодер не имеет информации, чтобы отличить добавленный в результате преобразования пробел от имевшегося изначально. Пример необратимого преобразования:

“очевидно,” --> “очевидно_,” ,

“очевидно_,” --> “очевидно_,” .

 

    наверх