Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


2.4. 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 продолжается. В некоторый момент добавление нового символа х приводит к необнаружению строки Iх (символ х был добавлен к I). Тогда кодер (1) записывает в выходной файл указатель в словаре на строку I, (2) сохраняет строку Iх (которая теперь будет называться фразой) в словаре на следующей допустимой позиции и (3) инициализирует (присваивает) строке I новое значение х. Чтобы проиллюстрировать процесс кодирования, мы еще раз воспользуемся последовательностью «sir_sid_eastman_easily_teases_sea_sick_seals». Получаем следующие шаги.

I

В

словаре?

Новая запись

Выход

I

В

словаре?

Новая запись

Выход

s

да

 

 

y

да

 

 

si

нет

256-si

115 (s)

y_

нет

274-у_

121 (у)

i

да

 

 

_

да

 

 

ir

нет

257-ir

105 (i)

_t

нет

275-_t

32 (_)

r

да

 

 

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

нет

281-_se

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)

аn

нет

268-an

97 (a)

с

да

 

 

n

да

 

 

ck

нет

285-ck

99 (c)

n_

нет

269-n_

110 (n)

k

да

 

 

_

да

 

 

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)

l

да

 

 

l

да

 

 

ls

нет

289-ls

108 (l)

ly

нет

273-ly

108 (l)

s

 

да

 

115 (s)

 

 

 

 

s ,eof

нет

 

 

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

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

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

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

0

NULL

110

n

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

b

 

 

268

аn

282

ea_

99

с

255

255

269

n_

283

_si

100

d

256

si

270

_ea

28-1

ic

101

е

257

ir

271

asi

285

ck

 

258

r_

272

il

286

k_

107

k

259

_s

273

ly

287

_sea

108

l

260

sid

274

y_

288

al

109

m

261

d_

275

_t

289

ls

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

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

115 (s), 105 (i), 114 (r), 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 приведена запись этого алгоритма на псевдокоде. Через  обозначается пустая строка, а через  - конкатенация (соединение) двух строк  и .

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

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

095.jpg

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

Пример: Применим алгоритм LZW для кодирования строки символов «alf_eats_alfalf а». Последовательность шагов отображена в табл. 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: lf), (258: f_), (259: _е), (260: ea), (261: at), (262: ts), (263: s_), (264: _a), (265: alf), (266: fa), (267: alfa).

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

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

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

Значит, выходной файл состоит из указателей на все более и более длинные последовательности символов а, и к указателей обозначают строку, длина которой равна .

I

В

словаре ?

Новая запись

Выход

I

В

словаре?

Новая запись

Выход

а

да

 

 

s_

нет

263-s_

115 (s)

al

нет

256-а1

97 (а)

_

да

 

 

1

да

 

 

нет

264-_а

32 (_)

lf

нет

257-lf

108 (1)

а

да

 

 

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 (а)

alfa

нет

267-alfa

265 (alf)

t

да

 

 

a

да

 

 

ts

нет

262-ts

116 (t)

a,eof

нет

 

97 (a)

s

да

 

 

 

 

 

 

Табл. 2.9. Кодирование LZVV для «alf_eats_alfalfa»

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

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

 



<< ПредыдущаяОглавлениеСледующая >>