Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

LZW

Это весьма популярный вариант алгоритма LZ78, который был разработан Терри Уэлчем (Terry Welch) в 1984 ([Welch 84] и [Phillips 92]). Его главной особенностью является удаление второго поля из метки. Метка LZW состоит только из указателя на место в словаре. Для лучшего понимания алгоритма LZW мы временно забудем, что словарь является деревом и будем предполагать, что словарь - это просто массив, состоящий из строк разной длины. Метод LZW начинается инициализацией словаря всеми символами исходного алфавита. В общем случае 8-битного алфавита, первые 256 записей (отдельные символы с номерами от 0 до 255) заносятся в словарь до поступления сжимаемых данных. Поскольку словарь уже частично заполнен, первые поступившие символы всегда будут обнаружены в словаре, поэтому метка может состоять всего лишь из указателя, и нет надобности дополнительно хранить код символа, как в алгоритмах LZ77 и LZ78.

(Алгоритм LZW запатентован и для его использования необходима лицензия. Издание патентов для программного обеспечения обсуждается в [Salomon 00].)

Метод LZW накапливает поступающие на вход символы в строке I. После каждого нового символа, добавленного в строку I, кодер ищет I в словаре. Если строка обнаружена, то процесс удлинения I продолжается. В некоторый момент добавление нового символа х приводит к необнаружению строки 1х (символ х был добавлен к I). Тогда кодер (1) записывает в выходной файл указатель в словаре на строку I, (2) сохраняет строку 1х (которая теперь будет называться фразой) в словаре на следующей допустимой позиции и (3) инициализирует (присваивает) строке I новое значение х. Чтобы проиллюстрировать процесс кодирования, мы еще раз воспользуемся последовательностью «sir_sid_eastman_easily_teases_sea_sick_seals». Получаем следующие шаги.


В

Новая



В

Новая


I

словаре?

запись

Выход

I

словаре?

запись

Выход

S

да



У

да



si

нет

256-si

115 (s)

У-

нет

274-у.

121 (у)

i

да



_

да



ir

нет

257-ir

105 (i)

_t

нет

275-_t

32(_)

г

да



t

да



r_

нет

258-r_

114 (r)

te

нет

276-te

116 (t)

_

да



e

да



-S

нет

259-_s

32(.)

ea

да



s

да



eas

нет

277-eas

263 (ea)

si

да



s

да



sid

нет

260-sid

256 (si)

se

нет

278-se

115 (s)

d

да



e

да



d_

нет

261-d_

100 (d)

es

нет

279-es

101 (e)

_

да



s

да



_e

нет

262-_e

32(.)

s_

нет

280-s_

115 (s)

e

да



_

да



ea

нет

263-ea

101 (e)

_s

да



a

да



_se

нет

281se

259 (_s)

as

нет

264-as

97(a)

e

да



s

да



ea

да



St

нет

265-st

115 (s)

ea.

нет

282-ea_

263 (ea)

t

да



_

да



tm

нет

266-tm

116 (t)

_s

да



m

да



_si

нет

283-_si

259 (_s)

ma

нет

267-ma

109 (m)

i

да



a

да



ic

нет

284-ic

105 (i)

an

нет

268-an

97(a)

с

да



n

да



ck

нет

285-ck

99(c)

n_

нет

269-n_

110 (n)

к

да



_

да



k_

нет

286-k_

107 (k)

_e

да



_

да



_ea

нет

270-_ea

262 (_e)

_s

да



a

да



_se

да



as

да



_sea

нет

287-_sea

281 (_se)

asi

нет

271-asi

264 (as)

a

да



i

да



al

нет

288-al

97(a)

il

нет

272-il

105 (i)

1

да



1

да



Is

нет

289-ls

108 (1)

iy

нет

273-ly

108 (1)

s s,eof

да нет


115 (s)

Табл. 2.6. Кодирование строки «sir_sid_eastman_...

0. Инициализируем словарь записями от 0 до 255 всеми 8-битовыми символами.

1. Первый входной символ s обнаруживается в словаре под номером 115 (это его код ASCII). Следующий входной символ i, но строки si нет в словаре. Кодер делает следующее: (1) он выдает на выход ссылку 115, (2) сохраняет si в следующей доступной позиции словаря (запись номер 256) и (3) инициализирует I строкой i.

2. На вход поступает символ г, но строки ir нет в словаре. Кодер (1) записывает на выход 105 (ASCII код i), (2) сохраняет в словаре ir (запись 257) и (3) инициализирует I строкой г.

0

NULL

110

п

262

_e

276

te

1

S0H



263

ea

277

eas



115

s

264

as

278

se

32

SP

116

t

265

St

279

es





266

tm

280

s_

97

а

121

У

267

ma

281

_se

98

Ъ



268

an

282

ea.

99

с

255

255

269

n_

283

_si

100

d

256

si

270

_ea

284

ic

101

е

257

ir

271

asi

285

ck



258

r_

272

il

286

k_

107

к

259

_s

273

iy

287

_sea

108

1

260

sid

274

У-

288

al

109

m

261

d_

275

_t

289

Is

Табл. 2.7. Словарь LZW.

Табл. 2.6 суммирует все шаги процесса. В табл. 2.7 приведены некоторые исходные записи из словаря LZW плюс записи, добавленные в процессе кодирования данной строки. Полный выходной файл имеет следующий вид (входят только числа, но не символы в скобках):

115 (s), 105 (i), 114 (г), 32 (_), 256 (si), 100 (d), 32 (_), 101 (е), 97 (а), 115 (s), 116 (t), 109 (m), 97 (a), 110 (n), 262 (_e), 264 (as), 105 (i), 108 (1), 121 (y), 32 (_), 116 (t), 263 (ea), 115 (s), 101 (e), 115 (s), 259 (_s), 263 (ea), 259 (_s), 105 (i), 99 (c), 107 (k), 280 (_se), 97 (a), 108 (1), 115 (s), eof.

На рис. 2.8 приведена запись этого алгоритма на псевдокоде. Через Л обозначается пустая строка, а через <<а,Ь>> - конкатенация (соединение) двух строк а и Ь.

Инструкция алгоритма «добавить <<di,ch>> в словарь» будет обсуждаться особо. Ясно, что на практике словарь может переполниться, поэтому эта инструкция должна также содержать тест на переполнение словаря и некоторые действия при обнаружении переполнения.

Поскольку первые 256 записей занесены в словарь в самом начале, указатели на словарь должны быть длиннее 8 бит. В простейшей реализации указатели занимают 16 бит, что допускает 64К записей в словаре (64К = 216 = 65536). Такой словарь, конечно, быстро переполнится. Такая же проблема возникает при реализации алгоритма LZ78, и любое решение, допустимое для LZ78, годится и для LZW. Другое интересное свойство этого алгоритма заключается в том, что строки в словаре становятся длиннее на один символ на каждом шаге. Это означает, что требуется много времени для появления длинных строк в словаре, а значит и эффект сжатия будет проявляться медленно. Можно сказать, что LZW медленно приспосабливается к входным данным.

for i:=0 to 255 do

добавить i как 1-символьную строку в словарь; добавить Л в словарь; di:=словарный индекс Л; repeat read(ch);

if <<di,ch>> есть в словаре then

di:=словарныи индекс <<di,ch>>; else

output(di);

добавить <<di,ch>> в словарь; di:^словарный индекс ch; endif; until конец входного файла;

Рис. 2.8. Алгоритм LZW.

Пример: Применим алгоритм LZW для кодирования строки символов «alf _eats_alf alf а». Последовательность шагов отображена в табл. 2.9. Кодер выдает на выход файл:

97 (а), 108 (1), 102 (f), 32 (_), 101 (е), 97 (а), 116 (t), 115 (s), 32 (_), 256 (al), 102 (f), 265 (alf), 97 (a),

а в словаре появляются следующие новые записи:

(256: al), (257: If), (258: f_), (259: _е), (260: еа), (261: at), (262: ts),

(263: s_), (264: _a), (265: alf), (266: fa), (267: alfa).

Пример: Проанализируем сжатие строки «аааа. . .» алгоритмом LZW. Кодер заносит первую «а» в I, ищет и находит а в словаре. Добавляет в I следующую а, находит, что строки 1х (=аа) нет в словаре. Тогда он добавляет запись 256: аа в словарь и выводит метку 97 (а) в выходной файл. Переменная I инициализируется второй «а», вводится третья «а», 1х вновь равна аа, которая теперь имеется в словаре. I становится аа, появляется четвертая «а». Строка 1х равна ааа, которых нет в словаре. Словарь пополняется этой строкой, а на выход идет метка 256 (аа). I инициализируется третьей «а», и т.д. и т.п. Дальнейший процесс вполне ясен.

В результате строки а, аа, ааа, аааа. . . добавляются в словарь в позиции 256, 257, 258, ..., а на выход подается последовательность

97 (а), 256 (аа), 257 (ааа), 258 (аааа), ....

Значит, выходной файл состоит из указателей на все более и более длинные последовательности символов а, и А; указателей обозначают строку, длина которой равна 1 + 2 + • • • + к — (к + к2)/2.


В

Новая



В

Новая


I

словаре ?

запись

Выход

I

словаре?

запись

Выход

а

да



s_

нет

263-s_

115 (s)

al

нет

256-а1

97(a)

_

да



1

да



_a

нет

264-_а

32(.)

If

нет

257-lf

108 (1)

a

да



f

да



al

да



f.

нет

258-f_

102 (f)

alf

нет

265-alf

256 (al)

_

да



f

да



_e

нет

259-_е

32 (w)

fa

нет

266-fa

102 (f)

e

да



a

да



ea

нет

260-еа

101 (е)

al

да



a

да



alf

да



at

нет

261-at

97(a)

alfa

нет

267-alfa

265 (alf)

t

да



a

да



ts

нет

262-ts

116 (t)

a,eof

нет


97(a)

s

да







Табл. 2.9. Кодирование LZW для «alf _eats_alf alf a»

Предположим, что входной файл состоит из 1 миллиона символов а. Мы можем найти длину сжатого файла, решив квадратное уравнение + к2)/2 = 1000000 относительно неизвестной к. Решение будет к « 1414. Выходит, что файл длиной 8 миллионов бит будет сжат в 1414 указателей длины не менее 9 бит (а на самом деле^ 16 бит). Фактор сжатия или 8М/( 1414 х 9) « 628.6 или 8МД1414 х 16) « 353.6.

Результат потрясающий, но такие файлы попадаются весьма редко (заметим, что этот конкретный файл можно сжать, просто записав в выходной файл «1000000 а» без использования LZW).