Алгоритм LZW — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример)
Строка 92: Строка 92:
 
|-
 
|-
 
|}
 
|}
 +
 +
=== Кодирование ===
 +
Без использования алгоритма LZW, при передаче сообщения как оно есть — 25 символов по 5 бит на каждый — оно займёт 125 бит. Сравним это с тем, что получается при использовании LZW:
 +
 +
{| class="wikitable" border =1, style="text-align: center; margin-left: auto; margin-right: auto;"
 +
|- bgcolor =#EEEEEE
 +
! scope="col" width="6em" rowspan="2" | Текущий символ
 +
! scope="col" width="4em" rowspan="2" | Следующий символ
 +
! colspan="2" | Вывод
 +
! scope="col" width="7em" rowspan="2" colspan="2" | Extended Dictionary
 +
! rowspan="2" | Comments
 +
|- bgcolor =#EEEEEE
 +
!  Код  || Биты
 +
|-
 +
| style="text-align: center;" | NULL
 +
| style="text-align: center;" | T || ||
 +
| style="border-right: none;" |
 +
| style="border-left: none;" | ||
 +
|-
 +
| style="text-align: center;" | T
 +
| style="text-align: center;" | O
 +
| 20 || 10100
 +
| style="border-right: none;" | 27:
 +
| style="border-left: none;" | TO
 +
| style="text-align: left;" | 27 = first available code after 0 through 26
 +
|-
 +
| style="text-align: center;" | O
 +
| style="text-align: center;" | B
 +
| 15 || 01111
 +
| style="border-right: none;" | 28:
 +
| style="border-left: none;" | OB ||
 +
|-
 +
| style="text-align: center;" | B
 +
| style="text-align: center;" | E
 +
| 2 || 00010
 +
| style="border-right: none;" | 29:
 +
| style="border-left: none;" | BE ||
 +
|-
 +
| style="text-align: center;" | E
 +
| style="text-align: center;" | O
 +
| 5 || 00101
 +
| style="border-right: none;" | 30:
 +
| style="border-left: none;" | EO ||
 +
|-
 +
| style="text-align: center;" | O
 +
| style="text-align: center;" | R
 +
| 15 || 01111
 +
| style="border-right: none;" | 31:
 +
| style="border-left: none;" | OR ||
 +
|-
 +
| style="text-align: center;" | R
 +
| style="text-align: center;" | N
 +
| 18 || 10010
 +
| style="border-right: none;" | 32:
 +
| style="border-left: none;" | RN
 +
| style="text-align: left;" | 32 requires 6 bits, so for next output use 6 bits
 +
|-
 +
| style="text-align: center;" | N
 +
| style="text-align: center;" | O
 +
| 14 || 001110
 +
| style="border-right: none;" | 33:
 +
| style="border-left: none;" | NO ||
 +
|-
 +
| style="text-align: center;" | O
 +
| style="text-align: center;" | T
 +
| 15 || 001111
 +
| style="border-right: none;" | 34:
 +
| style="border-left: none;" | OT ||
 +
|-
 +
| style="text-align: center;" | T
 +
| style="text-align: center;" | T
 +
| 20 || 010100
 +
| style="border-right: none;" | 35:
 +
| style="border-left: none;" | TT ||
 +
|-
 +
| style="text-align: center;" | TO
 +
| style="text-align: center;" | B
 +
| 27 || 011011
 +
| style="border-right: none;" | 36:
 +
| style="border-left: none;" | TOB ||
 +
|-
 +
| style="text-align: center;" | BE
 +
| style="text-align: center;" | O
 +
| 29 || 011101
 +
| style="border-right: none;" | 37:
 +
| style="border-left: none;" | BEO ||
 +
|-
 +
| style="text-align: center;" | OR
 +
| style="text-align: center;" | T
 +
| 31 || 011111
 +
| style="border-right: none;" | 38:
 +
| style="border-left: none;" | ORT ||
 +
|-
 +
| style="text-align: center;" | TOB
 +
| style="text-align: center;" | E
 +
| 36 || 100100
 +
| style="border-right: none;" | 39:
 +
| style="border-left: none;" | TOBE ||
 +
|-
 +
| style="text-align: center;" | EO
 +
| style="text-align: center;" | R
 +
| 30 || 011110
 +
| style="border-right: none;" | 40:
 +
| style="border-left: none;" | EOR ||
 +
|-
 +
| style="text-align: center;" | RN
 +
| style="text-align: center;" | O
 +
| 32 || 100000
 +
| style="border-right: none;" | 41:
 +
| style="border-left: none;" | RNO ||
 +
|-
 +
| style="text-align: center;" | OT
 +
| style="text-align: center;" | #
 +
| 34 || 100010
 +
| style="border-right: none;" |
 +
| style="border-left: none;" |
 +
| style="text-align: left;" | # stops the algorithm; send the cur seq
 +
|-
 +
| || || 0 || 000000
 +
| style="border-right: none;" |
 +
| style="border-left: none;" |
 +
| style="text-align: left;" | and the stop code
 +
|-
 +
|}
 +
 +
 +
Таким образом, используя LZW мы сократили сообщение на 29 бит из 125 — это почти 22 %. Если сообщение будет длиннее, то элементы словаря будут представлять всё более и более длинные части текста, благодаря чему повторяющиеся слова будут представлены очень компактно.

Версия 18:35, 21 октября 2010

Алгори́тм Ле́мпеля — Зи́ва — Ве́лча (Lempel-Ziv-Welch, LZW) — это универсальный алгоритм сжатия данных без потерь, созданный Абрахамом Лемпелем(Abraham Lempel), Якобом Зивом (Jacob Ziv) и Терри Велчем (Terry Welch). Он был опубликован Велчем в 1984 году, в качестве улучшенной реализации алгоритма LZ78, опубликованного Лемпелем и Зивом в 1978 году. Алгоритм разработан так, чтобы его можно было быстро реализовать, но он не обязательно оптимален, поскольку он не проводит никакого анализа входных данных.

Применение

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

Алгоритм был реализован в программе compress, которая стала более или менее стандартной утилитой Unix-систем приблизительно в 1986 году. Несколько других популярных утилит-архиваторов также используют этот метод или близкие к нему.

В 1987 году алгоритм стал частью стандарта на формат изображений GIF. Он также может (опционально) использоваться в формате TIFF.

В настоящее время, алгоритм содержится в стандарте PDF.

Описание

Данный алгоритм при сжатии (кодировании) динамически создаёт таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные). Таблица инициализируется всеми 1-символьными строками (в случае 8-битных символов — это 256 записей). По мере кодирования, алгоритм просматривает текст символ за символом, и сохраняет каждую новую, уникальную 2-символьную строку в таблицу в виде пары код/символ, где код ссылается на соответствующий первый символ. После того как новая 2-символьная строка сохранена в таблице, на выход передаётся код первого символа. Когда на входе читается очередной символ, для него по таблице находится уже встречавшаяся строка максимальной длины, после чего в таблице сохраняется код этой строки со следующим символом на входе; на выход выдаётся код этой строки, а следующий символ используется в качестве начала следующей строки.

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

Алгоритм

  1. Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы ω первым символом сообщения.
  2. Считать очередной символ K из кодируемого сообщения.
  3. Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для ω, иначе
  4. Если фраза ωK уже есть в словаре, присвоить входной фразе значение ωK и перейти к Шагу 2, иначе выдать код ω, добавить ωK в словарь, присвоить входной фразе значение K и перейти к Шагу 2.

Конец

Пример

Данный пример показывает алгоритм LZW в действии, показывая состояние выходных данных и словаря на каждой стадии, как при кодировании, так и при раскодировании сообщения. С тем чтобы сделать изложение проще, мы ограничимся простым алфавитом — только заглавные буквы, без знаков препинания и пробелов. Сообщение, которое нужно сжать, выглядит следующим образом:

TOBEORNOTTOBEORTOBEORNOT#

Маркер # используется для обозначения конца сообщения. Тем самым, в нашем алфавите 27 символов (26 заглавных букв от A до Z и #). Компьютер представляет это в виде групп бит, для представления каждого символа алфавита нам достаточно группы из 5 бит на символ. По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы. 5-битные группы дают 25 = 32 возможных комбинации бит, поэтому, когда в словаре появится 33-е слово, алгоритм должен перейти к 6-битным группам. Заметим, что, поскольку используется группа из всех нолей 00000, то 33-я группа имеет код 32. Начальный словарь будет содержать:

Символ Битовый код Номер
# 00000 0
A 00001 1
B 00010 2
C 00011 3
D 00100 4
E 00101 5
F 00110 6
G 00111 7
H 01000 8
I 01001 9
J 01010 10
K 01011 11
L 01100 12
M 01101 13
N 01110 14
O 01111 15
P 10000 16
Q 10001 17
R 10010 18
S 10011 19
T 10100 20
U 10101 21
V 10110 22
W 10111 23
X 11000 24
Y 11001 25
Z 11010 26

Кодирование

Без использования алгоритма LZW, при передаче сообщения как оно есть — 25 символов по 5 бит на каждый — оно займёт 125 бит. Сравним это с тем, что получается при использовании LZW:

Текущий символ Следующий символ Вывод Extended Dictionary Comments
Код Биты
NULL T
T O 20 10100 27: TO 27 = first available code after 0 through 26
O B 15 01111 28: OB
B E 2 00010 29: BE
E O 5 00101 30: EO
O R 15 01111 31: OR
R N 18 10010 32: RN 32 requires 6 bits, so for next output use 6 bits
N O 14 001110 33: NO
O T 15 001111 34: OT
T T 20 010100 35: TT
TO B 27 011011 36: TOB
BE O 29 011101 37: BEO
OR T 31 011111 38: ORT
TOB E 36 100100 39: TOBE
EO R 30 011110 40: EOR
RN O 32 100000 41: RNO
OT # 34 100010 # stops the algorithm; send the cur seq
0 000000 and the stop code


Таким образом, используя LZW мы сократили сообщение на 29 бит из 125 — это почти 22 %. Если сообщение будет длиннее, то элементы словаря будут представлять всё более и более длинные части текста, благодаря чему повторяющиеся слова будут представлены очень компактно.