🗊Презентация Алгоритм LZW

Алгоритм lzw Виконали студенти групи І-34 Віятик Христина Шимків Назар

Опис процесу Процес стиснення виглядає наступним чином. Послідовно зчитуються символи вхідного потоку і відбувається перевірка, чи існує в створеній таблиці рядків такий рядок. Якщо такий рядок існує, зчитується наступний символ, а якщо рядок не існує, в потік заноситься код для попередньої знайденої рядка, рядок заноситься в таблицю, а пошук починається знову.

псевдокод алгоритму Ініціалізація словника усіма можливими односимвольними фразами. Ініціалізація вхідної фрази ω першим символом повідомлення. Зчитати наступний символ K з кодованого повідомлення. Якщо кінець повідомлення, то видати код для ω, інакше: Якщо фраза ω (K) вже є в словнику, привласнити вхідний фразі значення ω (K) і перейти до Кроку 2, інакше видати код ω, додати ω (K) в словник, привласнити вхідний фразі значення K і перейти до Кроку 2. кінець

LZ78 орієнтується на дані, які тільки будуть отримані (LZ78 не використовує ковзне вікно, він зберігає словник з вже переглянутих фраз). Алгоритм зчитує символи повідомлення доти, поки що накопичується подстрока входить цілком в одну з фраз словника. Як тільки цей рядок перестане відповідати хоча б одній фразі словника, алгоритм генерує код, що складається з індексу рядка в словнику, яка до останнього введеного символу містила вхідну рядок, і символу, що порушив збіг. Потім в словник додається введена подстрока. Якщо словник вже заповнений, то з нього попередньо видаляють менш всіх використовувану в порівняннях фразу. Якщо наприкінці алгоритму ми не знаходимо символ, який порушив збіги, то тоді ми видаємо код у вигляді (індекс рядка в словнику без останнього символу, останній символ). LZ78 орієнтується на дані, які тільки будуть отримані (LZ78 не використовує ковзне вікно, він зберігає словник з вже переглянутих фраз). Алгоритм зчитує символи повідомлення доти, поки що накопичується подстрока входить цілком в одну з фраз словника. Як тільки цей рядок перестане відповідати хоча б одній фразі словника, алгоритм генерує код, що складається з індексу рядка в словнику, яка до останнього введеного символу містила вхідну рядок, і символу, що порушив збіг. Потім в словник додається введена подстрока. Якщо словник вже заповнений, то з нього попередньо видаляють менш всіх використовувану в порівняннях фразу. Якщо наприкінці алгоритму ми не знаходимо символ, який порушив збіги, то тоді ми видаємо код у вигляді (індекс рядка в словнику без останнього символу, останній символ).

декодування Особливість LZW полягає в тому, що для декомпресії нам не треба зберігати таблицю рядків у файл для розпакування. Алгоритм побудований таким чином, що ми в змозі відновити таблицю рядків, користуючись тільки потоком кодів. Тепер уявімо, що ми отримали закодоване повідомлення, наведене вище, і нам потрібно його декодувати. Перш за все, нам потрібно знати початковий словник, а наступні записи словника ми можемо реконструювати вже на ходу, оскільки вони є просто конкатенацією попередніх записів.