Техника сжатия LZW (Лемпель – Зив – Уэлч)

31.12.2019Компьютерные сети

Зачем нам нужен алгоритм сжатия?

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

Несжатые данные могут занимать много места, что не подходит для ограниченного пространства на жестком диске и скорости загрузки через Интернет.
Хотя аппаратное обеспечение становится все лучше и дешевле, алгоритмы уменьшения размера данных также способствуют развитию технологий.
Пример: одна минута несжатого HD-видео может превышать 1 ГБ. Как мы можем поместить двухчасовой фильм на диск Blu-ray объемом 25 ГБ?

Методы сжатия с потерями включают DCT (дискретное косинусное преобразование), векторное квантование и кодирование с преобразованием, в то время как методы сжатия без потерь включают RLE (кодирование длин серий), сжатие таблицы строк, LZW (Lempel Ziff Welch) и zlib. Существует несколько алгоритмов сжатия, но мы концентрируемся на LZW.

Что такое алгоритм Лемпеля – Зива – Уэлча (LZW)?

Алгоритм LZW является очень распространенным методом сжатия. Этот алгоритм обычно используется в GIF и, опционально, в PDF и TIFF. Команда Unix «сжимать», среди прочего. Это без потерь, то есть данные не теряются при сжатии. Алгоритм прост в реализации и имеет потенциал для очень высокой пропускной способности в аппаратных реализациях. Это алгоритм широко используемой утилиты сжатия файлов Unix, который используется в формате изображения GIF.

Идея опирается на повторяющиеся шаблоны для сохранения пространства данных. LZW является передовым методом сжатия данных общего назначения благодаря своей простоте и универсальности. Это основа многих утилит для ПК, которые утверждают, что «удваивают емкость вашего жесткого диска».

Как это работает?

Сжатие LZW работает путем чтения последовательности символов, группировки символов в строки и преобразования строк в коды. Поскольку коды занимают меньше места, чем строки, которые они заменяют, мы получаем сжатие. Характерные особенности LZW включают в себя:

Сжатие LZW использует таблицу кодов, с 4096 в качестве общего выбора для числа записей таблицы. Коды 0-255 в таблице кодов всегда назначаются для представления отдельных байтов из входного файла.
Когда кодирование начинается, таблица кодов содержит только первые 256 записей, а оставшаяся часть таблицы является пробелами. Сжатие достигается путем использования кодов с 256 по 4095 для представления последовательностей байтов.
Когда кодирование продолжается, LZW идентифицирует повторяющиеся последовательности в данных и добавляет их в таблицу кодов.
Декодирование достигается путем извлечения каждого кода из сжатого файла и его перевода через таблицу кодов, чтобы найти, какой символ или символы он представляет.

Пример: код ASCII. Как правило, каждый символ хранится с 8 двоичными битами, что позволяет использовать до 256 уникальных символов для данных. Этот алгоритм пытается расширить библиотеку до 9-12 бит на символ. Новые уникальные символы состоят из комбинаций символов, которые ранее встречались в строке. Он не всегда хорошо сжимается, особенно с короткими, разнообразными струнами. Но это хорошо для сжатия избыточных данных и не требует сохранения нового словаря с данными: этот метод может как сжимать, так и распаковывать данные.
Уже написана отличная статья, вы можете посмотреть более подробно здесь, а также статья Марка Нельсона заслуживает высокой оценки.

Реализация

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

LZW ENCODING

  *     PSEUDOCODE
  1     Initialize table with single character strings
  2     P = first input character
  3     WHILE not end of input stream
  4          C = next input character
  5          IF P + C is in the string table
  6            P = P + C
  7          ELSE
  8            output the code for P
  9          add P + C to the string table
  10           P = C
  11         END WHILE
  12    output code for P

Тестирование кода ниже:

Выход :

Также проверьте код , преобразованный Марк Нельсон в C ++ style.There еще одна вариация из 6 различных версий здесь . Кроме того, Rosettacode перечисляет несколько реализаций LZW на разных языках.

Сжатие с использованием LZW

Пример 1. Использование алгоритма LZW для сжатия строки: BABAABAAA
Эти шаги систематически показаны на диаграмме ниже.

LZW декомпрессия

Декомпрессор LZW создает ту же таблицу строк во время распаковки. Он начинается с первых 256 записей таблицы, инициализированных одиночными символами. Таблица строк обновляется для каждого символа во входном потоке, кроме первого. Декодирование достигается путем чтения кодов и их перевода через создаваемую таблицу кодов.

Алгоритм декомпрессии LZW

*    PSEUDOCODE
1    Initialize table with single character strings
2    OLD = first input code
3    output translation of OLD
4    WHILE not end of input stream
5        NEW = next input code
6        IF NEW is not in the string table
7               S = translation of OLD
8               S = S + C
9       ELSE
10              S = translation of NEW
11       output S
12       C = first character of S
13       OLD + C to the string table
14       OLD = NEW
15   END WHILE

Пример 2. Декомпрессия LZW: используйте LZW для декомпрессии выходной последовательности: <66> <65> <256> <257> <65> <260>
Эти шаги систематически показаны на диаграмме ниже.

В этом примере 72 бита представлены 72 битами данных. После построения разумной таблицы строк сжатие значительно улучшается.
LZW Summary: Этот алгоритм очень хорошо сжимает повторяющиеся последовательности данных. Поскольку кодовые слова имеют 12 битов, любой отдельный кодированный символ будет увеличивать размер данных, а не уменьшать его.

Код C ++ для сжатия LZW как для кодирования, так и для декодирования представлен следующим образом:

#include <bits/stdc++.h>

using namespace std;

vector<int> encoding(string s1)

{

cout << "Encoding\n";

unordered_map<string, int> table;

for (int i = 0; i <= 255; i++) {

string ch = "";

ch += char(i);

table[ch] = i;

}

string p = "", c = "";

p += s1[0];

int code = 256;

vector<int> output_code;

cout << "String\tOutput_Code\tAddition\n";

for (int i = 0; i < s1.length(); i++) {

if (i != s1.length() - 1)

c += s1[i + 1];

if (table.find(p + c) != table.end()) {

p = p + c;

}

else {

cout << p << "\t" << table[p] << "\t\t"

<< p + c << "\t" << code << endl;

output_code.push_back(table[p]);

table[p + c] = code;

code++;

p = c;

}

c = "";

}

cout << p << "\t" << table[p] << endl;

output_code.push_back(table[p]);

return output_code;

}

void decoding(vector<int> op)

{

cout << "\nDecoding\n";

unordered_map<int, string> table;

for (int i = 0; i <= 255; i++) {

string ch = "";

ch += char(i);

table[i] = ch;

}

int old = op[0], n;

string s = table[old];

string c = "";

c += s[0];

cout << s;

int count = 256;

for (int i = 0; i < op.size() - 1; i++) {

n = op[i + 1];

if (table.find(n) == table.end()) {

s = table[old];

s = s + c;

}

else {

s = table[n];

}

cout << s;

c = "";

c += s[0];

table[count] = table[old] + c;

count++;

old = n;

}

int main()

{

string s = "WYS*WYGWYS*WYSWYSG";

vector<int> output_code = encoding(s);

cout << "Output Codes are: ";

for (int i = 0; i < output_code.size(); i++) {

cout << output_code[i] << " ";

}

cout << endl;

decoding(output_code);

}

Выход:

Encoding
String    Output_Code    Addition
W    87        WY    256
Y    89        YS    257
S    83        S*    258
*    42        *W    259
WY    256        WYG    260
G    71        GW    261
WY    256        WYS    262
S*    258        S*W    263
WYS    262        WYSW    264
WYS    262        WYSG    265
G    71
Output Codes are: 87 89 83 42 256 71 256 258 262 262 71 

Decoding
WYS*WYGWYS*WYSWYSG

Преимущества LZW перед Хаффманом :

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

Ресурсы:

Эта статья предоставлена Amartya Ranjan Saikia . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Техника сжатия LZW (Лемпель – Зив – Уэлч)

0.00 (0%) 0 votes