Проблемы с процедурой декодирования переменной длины алгоритма LZW

Question

Настройка

Скажи, что у меня есть:

• Серия чисел, полученных в результате LZW-сжатия растрового изображения:

  256 1 258 258 0 261 261 259 260 262 0 264 1 266 267 258 2 273 2 262 259 274 275 270 278 259 262 281 265 276 264 270 268 288 264 257
  

• Сжатый LZW, закодированный потоком переменной длины (включая заголовок размера кода LZW и маркеры подблока), который представляет эту же серию чисел:

  00001000 00101001 00000000 00000011 00001000 00010100 00001000 10100000 
  01100000 11000001 10000001 00000100 00001101 00000010 01000000 00011000 
  01000000 11100001 01000010 10000001 00000010 00100010 00001010 00110000 
  00111000 01010000 11100010 01000100 10000111 00010110 00000111 00011010 
  11001100 10011000 10010000 00100010 01000010 10000111 00001100 01000001 
  00100010 00001100 00001000 00000000
  

• И initial code width из 8,

Эта проблема

Я пытаюсь извлечь начальный ряд чисел (массив целых чисел) из потока байтов.

Из того, что я прочитал, процедура здесь состоит в том, чтобы взять initial code width, сканирование справа налево, чтение initial code width + 1 битов за раз, чтобы извлечь целые числа из потока байтов. Например:

iteration #1:   1001011011100/001/    yield return 4
iteration #2:   1001011011/100/001    yield return 1
iteration #3:   1001011/011/100001    yield return 6
iteration #4:   1001/011/011100001    yield return 6

Эта процедура не будет работать для итерации № 5, которая даст 1:

iteration #5:   1/001/011011100001    yield return 1 (expected 9)

Ширина кода должна была быть увеличена на единицу.

Вопрос

Как я должен знать, когда увеличить ширину кода при считывании закодированной переменной длины bytestream? У меня есть вся необходимая информация, необходимая для распаковки этого потока? Я концептуально что-то упускаю?

ОБНОВИТЬ:

После долгого разговора с серой бородой - я обнаружил, что неправильно читал двоичную строку: 00000000 00000011 00 должно быть истолковано как 256, 1, Байтстрим не читается как big-endian.

И, грубо говоря, если вы декодируете поток байтов, вы увеличиваете число считываемых битов каждый раз, когда читаете 2^N-1 кодов, где N - текущая ширина кода.

Answer 1

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

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

С примером в презентации, которую вы связали, 8 назначается, когда второй 6 передается - вам нужно переключиться на четыре бита, прежде чем читать следующий код.

(Это где пример и ваш series of numbers отличаются - ссылка представляет 4, 1, 6, 6, 2, 9.)