Новая тема: алгоритмы сжатия данных
типа LZW, LZ77 и т.п.
1. Алгоритм LZW, один из первых алгоритмов
этого типа
Идея таких алгоритмов -- кодировать повторяющиеся
длинные фрагменты текста одним кодом.
Словарь для повторяющихся сегментов сообщения
создается "на лету" при кодировке сообщения и
зависит только от сообщения. Сообщение в LZW
строится из фрагментов, уже занесенных в словарь.
Закодированное сообщение состоит из индексов
этих фрагментов в словаре.
Алгоритм LZW используется в
1) формате *.gif кодировки изображений, использующих
палитру (без потери инормации);
2) в текстах формата *.pdf (это программы на языке
PostScript, сжатые с помощью алгоритма LZW);
3) в изображениях формата *.tiff и др.
Для произвольных текстов степень сжатия примерно
в 2 раза.
Для начала рассмотрим классический (самый первый)
алгоритм LZW без последующих улучшений.
Мы трактуем сообщение как последовательность
байтов (байт -- 8 битов или целое число в диапазоне
0..255). Память современного компьютера -- массив байтов,
файл -- последовательность байтов, поэтому естественно
кодировать именно последовательность байтов.
В алгоритме LZW мы поддерживаем словарь, содержащий
конечные последовательности байтов ("слов").
Каждый фрагмент (pattern) имеет индекс в словаре,
и при кодировании мы выдаем последовательность
этих индексов. При этом в словарь в процессе
кодирования/декодирования постоянно добавляются новые
фрагменты, длина которых увеличивается.
В классическом алгоритме словарь имеет размер,
не больший чем 2^12 = 4096 элементов. Индексы
фрагментов в словаре кодируются 12-ю битами.
Начинаем со словаря, который содержит все байты,
т.е. 256 элементов.
0 [0]
1 [1]
...
10 [10] \n
...
32 [32] ' ' space
...
48 [48] '0'
...
57 [57] '9'
...
65 [65] 'A'
...
90 [90] 'Z'
...
255 [255]
Начальный размер словаря 256 фрагментов.
Алгоритм кодирования.
1. Инициализируем словарь (добавляем в него
256 однобайтовых последовательностей).
2. Пока мы не в конце входного потока, подолжаем
читать символы из него. Иначе завершаем алгоритм.
Из входного потока читаем символы, пока
прочитанное слово всё еще содержится в словаре.
Как только при добавлении очередного байта из
входного потока слово уже не содержится в словаре,
либо дошли до конца потока, останавливаемся.
Получаем фрагмент
[prefix, byte]
или
[prefix], если дошли до конца потока.
Например, abacd все еще содержится в словаре,
но abacde уже нет.
[abacd, e] prefix = "abacd", byte = "e"
3. В конец словаря заносим фрагмент [prefix, byte]
([abacde] в нашем примере), в выходной
поток выдаем индекс префикса (индекс
фрагмента "abacd" в нашем примере).
4. Продолжаем читать входной поток с байта,
следующего за префиксом (в нашем примере
с байте "e". Переходим к пункту 2.
Применим алгоритм на примере входной последовательности
BABAABAAA
на самом деле это последовательность байтов
[66, 65, 66, 65, 65, 66, 65, 65, 65]
__
BABAABAAA
^
Читаем BA, prefix = B, byte = A
Добавляем в словарь (256, BA)
Выдаем 66 (код фрагмента B)
__
BABAABAAA
^
Читаем AB, prefix A, byte B
Добавляем в словарь (257, AB)
Выдаем 65 (код фрагмента A)
___
BABAABAAA
^
Читаем BAA, prefix BA, byte A
Добавляем в словарь (258, BAA)
Выдаем 256 (код фрагмента BA)
___
BABAABAAA
^
Читаем ABA, prefix AB, byte A
Добавляем в словарь (259, ABA)
Выдаем 257 (код фрагмента A)
__
BABAABAAA
^
Читаем AA, prefix A, byte A
Добавляем в словарь (260, AA)
Выдаем 65 (код фрагмента A)
__
BABAABAAA
^
Читаем AA, prefix AA, конец потока
В словарь ничего не добавляется
Выдаем 260 (код фрагмента AA)
В результате получаем
[66, 65, 256, 257, 65, 260]
Длина исходной последовательности 9 символов =
= 9*8 = 72 бита
Длина выходной последовательности 6 индексов =
= 6*12 = 72 бита
В современной версии алгоритма индексы элементов
словаря, которые выдаются в выходную последовательность,
записываются переменным числом битов.
Начинаем с 9 битов, когда размер словаря < 512
и для записи индексов достаточно 9 битов.
Когда размер словаря превышает 511, увеличиваем
число битов на запись индекса в выходном потоке
до 10, с 1024 до 11, и с 2048 до 12 битов.
Ограничение на размер словаря -- обычно 4096
элементов, т.е. как только словарь жостигнет размера
4096 = 2^12, мы перестаем добавлять элементы в словарь.
Если используется переменное число бит на индекс,
то размер закодированного сообщения будет равен
длине выходной последовательности * 9 =
= 6*9 = 54 бита = 7 байтов.
Длина исходной последовательности = 9 байтов.
Давайте напишем на Питоне алгоритм кодировки для
LZW-метода.
def encodeLZW(x):
y = []
dictionary = dict()
for c in range(256):
dictionary[bytes((c,))] = c
l = len(x)
prefix = bytes((x[0],))
pos = 1
codeWord = 256
while pos < l:
c = x[pos]; pos += 1
if prefix + bytes((c,)) in dictionary:
prefix = prefix + bytes((c,))
else:
y.append(dictionary[prefix])
dictionary[prefix + bytes((c,))] = codeWord
codeWord += 1
prefix = bytes((c,))
y.append(dictionary[prefix])
return y
Алгоритм декодирования, идея
Алгоритм декодирования по мере обработки
индексов закодированного сообщения строит словарь,
аналогичный словарю, который строит алгоритм
кодирования при создании закодированного
сообщения. Это должен быть такой же словарь,
но отстающий на один шаг -- при декодировании
словарь декодировщика имеет на 1 элемент
меньше, чем словарь кодировщика. Это следует
учитывать при написании программы декодирования по
LZW-алгоритму.
Алгоритм декодирования
На входе имеем последовательность индексов
элементов словаря.
1. Инициализируем словарь (добавляем в него
256 однобайтовых последовательностей).
previous_string = ""
2. Пока мы не в конце входного потока, продолжаем
читать символы из него. Иначе завершаем алгоритм.
Из входного поток читаем индекс idx.
Если idx < размер словаря,
| то выдаем dictionary[idx];
| В словарь добавляем
| previous_string + dictionary[idx][0]
| (к предыдущей строке добавляем
| первую букву только что выданной строки,
| и эту строку добавляем в словарь)
| previous_string = dictionary[idx]
иначе |
| s = previous_string + previous_string[0]
| (к предыдущей строке добавляем
| первую букву предыдущей строки)
| В словарь добавляем s.
| (полученную строку добавляем в словарь)
| previous_string = s
конец если
переходим к пункту 2
Рассмотрим наш пример:
закодированная последовательность
y = [66, 65, 256, 257, 65, 260]
1. Инициализируем словарь.
0 [0]
...
65 [A]
66 [B]
...
255 [255]
CodeWord = 256
Предыдущая строка = ""
[66, 65, 256, 257, 65, 260]
^
Читаем индекс 66. Он в нашем словаре, значит,
выдаем B. В словарь ничего не добавляем
Предыдущая строка = "B"
[66, 65, 256, 257, 65, 260]
^
Читаем индекс 65. Он в нашем словаре, значит,
выдаем "A". В словарь добавляем
Предыдущая строка + первая буква("A")
256 BA
Предыдущая строка = "A"
[66, 65, 256, 257, 65, 260]
^
Читаем индекс 256. Он в нашем словаре, значит,
выдаем "BA". В словарь добавляем
Предыдущая строка + первая буква("BA")
257 AB
Предыдущая строка = "BA"
[66, 65, 256, 257, 65, 260]
^
Читаем индекс 257. Он в нашем словаре, значит,
выдаем "AB". В словарь добавляем
Предыдущая строка + первая буква("AB")
258 BAA
Предыдущая строка = "AB"
[66, 65, 256, 257, 65, 260]
^
Читаем индекс 65. Он в нашем словаре, значит,
выдаем "A". В словарь добавляем
Предыдущая строка + первая буква("A")
259 ABA
Предыдущая строка = "A"
[66, 65, 256, 257, 65, 260]
^
Читаем индекс 260. Он НЕ в нашем словаре, значит,
s = Предыдущая строка +
первая буква(Предыдущая строка)
выдаем s, т.е. "AA"
В словарь добавляем s
260 AA
Предыдущая строка = "AA"
Прочли все индексы -- алгоритм заканчивается.
Выдано BABAABAAA -- совпадает
с исходной последовательностью.
Приведем запись алгоритма декодирования в методе
LZW на Python3:
def decodeLZW(y):
x = bytearray()
dictionary = dict()
for byte in range(256):
dictionary[byte] = bytes((byte,))
l = len(y)
previousCodeWord = y[0]
x += dictionary[previousCodeWord]
c = dictionary[previousCodeWord][0]
pos = 1
codeWord = 256
while pos < l:
currentCodeWord = y[pos]; pos += 1
if currentCodeWord in dictionary:
s = dictionary[currentCodeWord]
else:
s = dictionary[previousCodeWord] + bytes((c,))
# Output s
x += s
c = s[0]
dictionary[codeWord] = (
dictionary[previousCodeWord] + bytes((c,))
)
previousCodeWord = currentCodeWord
codeWord += 1
return x
Примеры использования приведенных алгоритмов
LZW кодирования и раскодирования на Python3
Рассмотрим сначала пример, который мы кодировали
и раскодировали вручную. Входная строка
BABAABAAA
>>> s = "BABAABAAA"
>>> x = bytes(s, "ascii")
>>> x
b'BABAABAAA'
>>> y = encodeLZW(x)
>>> y
[66, 65, 256, 257, 65, 260]
>>> xx = decodeLZW(y)
>>> xx
bytearray(b'BABAABAAA')
>>> x == xx
True
Мы видим, что алгоритмы работают корректно, и
результаты совпадают с теми, что мы вычислили
раньше вручную. И еще один пример: на входе --
английская скороговорка
The rain in Spain always stays in the plain.
Вот что выдают алгоритмы кодирования и декодирования:
>>> s = "The rain in Spain always stays in the plain."
>>> x = bytes(s, "ascii")
>>> x
b'The rain in Spain always stays in the plain.'
>>> y = encodeLZW(x)
>>> y
[84, 104, 101, 32, 114, 97, 105, 110, 32, 262, 32, 83,
112, 261, 263, 97, 108, 119, 97, 121, 115, 32, 115,
116, 274, 276, 265, 116, 257, 32, 112, 108, 269, 46]
>>> xx = decodeLZW(y)
>>> xx
bytearray(b'The rain in Spain always stays in the plain.')
>>> x == xx
True
>>> len(x)
44
>>> len(y)
34
Сокращение при сжатии с последовательности байтов
длины 44 до длины 34, элементы выходной
последовательности занимают 9 бит. В битах сокращение
с 44*8 = 352 бит до 34*9 = 306 бит.