Загальні теоретичні відомості. Алгоритм реалізації методу

↑

▷ Содержание

⇐ ПредыдущаяСтр 6 из 8Следующая ⇒

2. Загальні теоретичні відомості

Даний алгоритм при стисненні (кодуванні) динамічно створює таблицю перетворення рядків: певним послідовностям символів (словам) ставляться у відповідність групи бітів фіксованої довжини.

Спочатку таблиця ініціюється всіма 1-символьними рядками (у випадку 8-бітних символів – це 256 записів).

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

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

3. Алгоритм реалізації методу

1. Створення словника всіма можливими односимвольними фразами.

2. Ініціалізація вхідної фрази А першим символом повідомлення.

3. Пошук у словнику рядок А найбільшої довжини, яка співпадає з останніми прийнятими символами.

4. Зчитати черговий символ В з кодованого повідомлення.

5. Якщо КІНЕЦЬ_ПОВІДОМЛЕННЯ, то видати код для А, інакше - крок 5.

6. Якщо фраза АВ вже є в словнику, присвоїти вхідній фразі А значення АВ і перейти до кроку 3, інакше - видати код А, додати АВ в словник, присвоїти вхідній фразі А значення В і перейти до кроку 3.

7. Кінець.

Познавательные статьи:



Формы дистанционного обучения

Передача мяча двумя руками снизу

Значение правильной осанки для жизнедеятельности человека

Основные ошибки при выполнении передач мяча на месте