Користувач:Illuminatus94/пісочниця
Стиснення без втрат - клас алгоритмів стиснення даних, що дозволяє ідеально відновлювати (з точністю до біта) вихідні дані зі стислих даних. Стиснення без втрат використовується в тих випадках, коли важливо, щоб оригінал і декомпресованна інформація були однаковими або де відхилення від вихідних даних є неприйнятним. Типовими прикладами є виконувані файли, текстові документи та сирцевий код.
Алгоритм RLE[ред. | ред. код]
RLE - від англійського Run Length Encoding. Цей алгоритм працює з серіями даних(послідовностями), в яких один символ зустрічається кілька разів. Кодування полягає в заміні великих послідовностей повторюваних даних в один елемент цих даних та кількість його повторів
.
Приклад використання[ред. | ред. код]
Для прикладу уявимо зображення, що містить чорний текст на білому фоні. Текст містить велику кількість серій білих пікселів в порожніх місцях та багато коротких серій чорних пікселів у тексті. Нехай для приклад наведено довільний рядок зображення в чорно-білому варіанті. B уособлює чорний піксель, а W білий:
“WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW”
При застосуванні простого кодування довжини серій до рядка, ми отримаємо наступне:
“12W1B12W3B24W1B14W”
Останній запис інтерпретується як «дванадцять W», «одна B», «дванадцять W», «три B» і т. д. Таким чином, код представляє вихідні 67 символів у вигляді всього лише 18.
Приклад коду кодування та декодування алгоритмом RLE[ред. | ред. код]
public static string Encode(string s)
{
StringBuilder sb = new StringBuilder();
int count = 1;
char current =s[0];
for(int i = 1; i < s.Length;i++)
{
if (current == s[i])
{
count++;
}
else
{
sb.AppendFormat("{0}{1}", count, current);
count = 1;
current = s[i];
}
}
sb.AppendFormat("{0}{1}", count, current);
return sb.ToString();
}
public static string Decode(string s)
{
string a = "";
int count = 0;
StringBuilder sb = new StringBuilder();
char current = char.MinValue;
for(int i = 0; i < s.Length; i++)
{
current = s[i];
if (char.IsDigit(current))
a += current;
else
{
count = int.Parse(a);
a = "";
for (int j = 0; j < count; j++)
sb.Append(current);
}
}
return sb.ToString();
}
Переваги та недоліки[ред. | ред. код]
Цей алгоритм дуже простий у реалізації і не вимагає багато ресурсів CPU. Стиснення RLE ефективний тільки з файлами, які містять багато повторюваних даних. Зображення, які містять великі білі або чорні області добре підходять для цього використання цього алгоритму. Кольорові зображення, також можуть дати хороший коефіцієнт стиснення.
Де застосовується алгоритм RLE[ред. | ред. код]
Стиснення RLE може бути використане в наступних форматах:
Алгоритм ЛЕМПЕЛЯ — ЗІВА — ВЕЛЧА (LZW)[ред. | ред. код]
LZW названий на честь Авраама Лемпеля(англ. Abraham Lempel), Якоба Зіва(англ. Jacob Ziv) і Террі Уелча(англ. Terry Welch), учених, які розробили цей алгоритм стиснення. Це алгоритм стиснення без втрат "на основі словника". Алгоритми, засновані на словнику сканують файли на послідовності даних, які зустрічаються більше ніж один раз. Ці послідовності, потім зберігаються в словнику в межах стислого файлу, з посиланнями скрізь де були знайденні повтори даних. Лемпель та Зів опублікував серію статей, що описують різні алгоритми стиснення. Їхній перший алгоритм був опублікований в 1977 році, звідси і його назва: LZ77. Цей алгоритм стиснення зберігає свій словник в самих даних.
Принцип роботи[ред. | ред. код]
Даний алгоритм при стисненні даних (кодуванні джерела) динамічно створює таблицю перетворення рядків: певним послідовностям символів ставляться у відповідність групи бітів фіксованої довжини (зазвичай 12-бітні). Таблиця ініціюється всіма 1-символьними рядками. По мірі кодування алгоритм переглядає текст символ за символом і зберігає кожен новий унікальний 2-символьний рядок в таблицю у вигляді пари код/символ, де код посилається на відповідний перший символ. Після того, як новий 2-символьний рядок збережений в таблиці, на вихід передається код першого символу. Коли на вході читається черговий символ, для нього по таблиці знаходиться рядок, що вже зустрічався, максимальної довжини, після чого в таблиці зберігається код цього рядка з наступним символом на вході; на вихід видається код цього рядка, а наступний символ використовується у якості початку наступного рядка.
Алгоритму декодування на вході потрібен лише закодований текст, оскільки він може відтворювати відповідну таблицю перетворень безпосередньо по закодованому тексту.
Алгоритм[ред. | ред. код]
- Ініціалізація словника всіма можливими односимвольними фразами. Ініціалізація вхідної фрази ω першим символом повідомлення.
- Знайти в словнику рядок ω найбільшої довжини, який збігається з останніми прийнятими символами.
- Зчитати черговий символ K з кодованого повідомлення.
- Якщо КІНЕЦЬ_ПОВІДОМЛЕННЯ, то видати код для ω, інакше - крок 5.
- Якщо фраза ωK вже є в словнику, присвоїти вхідній фразі ω значення ωK і перейти до Кроку 3, інакше видати код ω, додати ωK в словник, присвоїти вхідній фразі ω значення K і перейти до Кроку 3.
- Кінець. [1].
Приклад коду кодування та декодування алгоритмом LZW[ред. | ред. код]
public static List<int> Compress(string uncompressed)
{
// build the dictionary
Dictionary<string, int> dictionary = new Dictionary<string, int>();
for (int i = 0; i < 256; i++)
dictionary.Add(((char)i).ToString(), i);
string w = string.Empty;
List<int> compressed = new List<int>();
foreach (char c in uncompressed)
{
string wc = w + c;
if (dictionary.ContainsKey(wc))
{
w = wc;
}
else
{
// write w to output
compressed.Add(dictionary[w]);
// wc is a new sequence; add it to the dictionary
dictionary.Add(wc, dictionary.Count);
w = c.ToString();
}
}
// write remaining output if necessary
if (!string.IsNullOrEmpty(w))
compressed.Add(dictionary[w]);
return compressed;
}
public static string Decompress(List<int> compressed)
{
// build the dictionary
Dictionary<int, string> dictionary = new Dictionary<int, string>();
for (int i = 0; i < 256; i++)
dictionary.Add(i, ((char)i).ToString());
string w = dictionary[compressed[0]];
compressed.RemoveAt(0);
StringBuilder decompressed = new StringBuilder(w);
foreach (int k in compressed)
{
string entry = null;
if (dictionary.ContainsKey(k))
entry = dictionary[k];
else if (k == dictionary.Count)
entry = w + w[0];
decompressed.Append(entry);
// new sequence; add it to the dictionary
dictionary.Add(dictionary.Count, w + entry[0]);
w = entry;
}
return decompressed.ToString();
}
Переваги та недоліки[ред. | ред. код]
- LZW стиснення працює найкраще для файлів, що містять багато повторюваних даних. Це часто трапляється з текстовими і монохромними зображеннями.Файли, стислі, та які не мають повторюваної інформації навпаки можуть ставати більшого розміру!
- LZW стиснення є швидким.
- LZW є досить старим методом стиснення. Сучасні комп’ютерні системи мають потужність використовувати більш ефективні алгоритми.
- Для використання LZW алгоритму у свої додаткам повинно бути оплачене роялті.
Де застосовується алгоритм LZW?[ред. | ред. код]
Стиснення алгоритмом може бути використане у різних форматах:
- TIF файли
- GIF файли
- PDF файли - в останні додатків LZW був замінений на більш ефективний алгоритм Flate.
Алгоритм ХАФФМАНА[ред. | ред. код]
Також відомий як кодування Хаффмана, алгоритм для стиснення без втрат файлів на основі частоти появи символу у файлі, який стискається. Алгоритм Хаффмана заснований на статистичному кодуванні.
Ідея алгоритму[ред. | ред. код]
Знаючи ймовірності символів у повідомленні, існує можливість описати процедуру побудови кодів змінної довжини, що складаються з цілої кількості бітів. Символам які мають більшу ймовірністю ставляться більш короткі коди у відповідність. Коди Хаффмана мають властивість префіксності (жодне кодове слово не є префіксом іншого), це дозволяє їх точно декодувати.
Принцип роботи[ред. | ред. код]
Практичний приклад покаже принцип роботи: Припустимо, ви хочете стиснути наступну порцію даних:
ACDABA
Є 6 символів, вони займають 6 байт або 48 біт. З кодування Хаффмана, у файлі шукаються символи які найчастіше з’являються (в даному випадку символ 'А' -3 рази), а потім будується дерево, яке замінює символи короткими бітовими послідовностями. В даному випадку алгоритм буде використовувати наступну таблицю: A = 0, B = 10, C = 110, D = 111. Якщо ці кодові слова використовуються для стиснення файлу, стислі дані виглядають так:
01101110100
Це означає, що 11 біт використовуються замість 48, ступінь стиснення від 4 до 1 для даного файлу.
Кодування Хаффмана можна додатково оптимізувати двома різними способами:
- Адаптивне кодування Хаффмана динамічно змінює кодові слова відповідно до зміни ймовірностей символів.
- Розширене стиснення Хаффмана може кодувати групи символів, а не окремі символи.
Посилання[ред. | ред. код]
- Алгоритм Лемпеля — Зіва — Велча (укр.)
- Методы сжатия даннях / В. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. – М.: ДИАЛОГ – МИФИ, 2002. – 384 с.
- Зив Дж. Алгоритм универсального сжатия дан- ных / Дж. Зив // Проблемы передачи информации. – 1996. – № 2. – С. 47-55.
- Вільна енциклопедія«Вікіпедія»[Електронний ресурс].–Режим доступу: https://uk.wikipedia.org/wiki/RLE - RLE.
- Вільна енциклопедія«Вікіпедія»[Електронний ресурс].–Режим доступу: https://uk.wikipedia.org/wiki/Алгоритм_Лемпеля_—_Зіва_—_Велча - Алгори́тм Ле́мпеля — Зіва — Ве́лча.
- Вільна енциклопедія«Вікіпедія»[Електронний ресурс].–Режим доступу: https://uk.wikipedia.org/wiki/ Код_Хаффмана - Код_Хаффмана.
- Стрюк А.Ю. Цветовые модели в системах сжатия видеоинформации / А.Ю. Стрюк, К.О. Бохан // Радио- электроника и информатика. – 2002. – № 1. – С. 23-25.
- Гриньов Д.В. Цветоразностная модель представления цвета в задачах сжатия изображений / Д.В. Гринь- ов // Системи обробки інформації: зб. наук. пр. – Х.: ХУ ПС, 2009. – Вип. 6 (80). – С. 30-34.
- ↑ Стиснення зображень