Теория на компресията

Теория на компресията

Продължителност на курса

40 часа

Анотация

Компресията на данни е област от Теорията на информацията – наука, водеща началото си от работата на Клод Шенън “Математическа теория на комуникацията”. Курсът изследва най-прилаганите математични методи за компресиране на данни, като дава възможност на курсистите да се запознаят с теоретическите и практически постановки от теорията на компресията и теорията на информацията. Разглеждат се механизмите, използвани от известни архиватори (като PKZIP и ARC), както и методите за компресия на изображения, използвани в различни формати (TIFF, GIF , JPEG). Разглеждат се различни компресиращи модели, използвани за пренос на данни (MNP), както и модели за компресия на звук (в частност формат MP3). Курсът е и с практическа насоченост, като дава достатъчна подготовка за написването на собствена архивираща програма.

Необходими предварителни познания

Предполага се, че учащите имат основни знания по програмиране.

Съдържание

1. Общи положения в теорията на компресията и теория на информацията. Измерване на компресия, ентропия и информационен излишък. Видове компресия.

2. Кодиране на последователности – класически вариант и подобрения. Редукция на нулите. Отрицателни броячи и групиране.

3. Кодиране с битови карти. Полубайтово пакетиране. Кодиране на Чен-Хо.

4. Алгоритми за компресия на текст: двуатомно кодиране, MacWrite, MTF.

5. Относително кодиране. Математическо очакване – кодиране с линейно предсказване.

6. Статистическо моделиране: моделиране в краен контекст, адаптивно моделиране, модели от по-висок ред.

7. Минимум излишък. Метод на Шенън-Фано. Цен на код. Оптимален подбуквен код. Хъфманово кодиране.

8. Адаптивни модели. Адаптивно хъфманово кодиране.

9. Аритметично кодиране. Модели на Марков.

10. Компресия с речници. Статични и адаптивни речници. Метод на Зив-Лемпел. LZ77, LZ78.

11. Компресия с плъзгащ се прозорец.

12. Компресия на изображения без загуба на информация. Компресия на изображения със загуба на информация. Изрязване, квантифициране и уейвлети.

13. Компресия на звук. Процес на кодиране в MP3. Маскиране на звуци.

Теория на компресията
Продължителност на курса	40 часа
Анотация
Компресията на данни е област от Теорията на информацията – наука, водеща началото си от работата на Клод Шенън “Математическа теория на комуникацията”. Курсът изследва най-прилаганите математични методи за компресиране на данни, като дава възможност на курсистите да се запознаят с теоретическите и практически постановки от теорията на компресията и теорията на информацията. Разглеждат се механизмите, използвани от известни архиватори (като PKZIP и ARC), както и методите за компресия на изображения, използвани в различни формати (TIFF, GIF , JPEG). Разглеждат се различни компресиращи модели, използвани за пренос на данни (MNP), както и модели за компресия на звук (в частност формат MP3). Курсът е и с практическа насоченост, като дава достатъчна подготовка за написването на собствена архивираща програма.
Необходими предварителни познания
*Предполага се, че учащите имат основни знания по програмиране.*
Съдържание
1. Общи положения в теорията на компресията и теория на информацията. Измерване на компресия, ентропия и информационен излишък. Видове компресия. 2. Кодиране на последователности – класически вариант и подобрения. Редукция на нулите. Отрицателни броячи и групиране. *3. Кодиране с битови карти. Полубайтово пакетиране. Кодиране на Чен-Хо.* *4. Алгоритми за компресия на текст: двуатомно кодиране, MacWrite, MTF.* *5. Относително кодиране. Математическо очакване – кодиране с линейно предсказване.* 6. Статистическо моделиране: моделиране в краен контекст, адаптивно моделиране, модели от по-висок ред. *7. Минимум излишък. Метод на Шенън-Фано. Цен на код. Оптимален подбуквен код. Хъфманово кодиране.* *8. Адаптивни модели. Адаптивно хъфманово кодиране.* *9. Аритметично кодиране. Модели на Марков.* *10. Компресия с речници. Статични и адаптивни речници. Метод на Зив-Лемпел. LZ77, LZ78.* *11. Компресия с плъзгащ се прозорец.* 12. Компресия на изображения без загуба на информация. Компресия на изображения със загуба на информация. Изрязване, квантифициране и уейвлети. *13. Компресия на звук. Процес на кодиране в MP3. Маскиране на звуци.*