Компютърни науки за компресия G23c
Решете работния лист «Формати на изображения»
# Компресия
При компресиране се прави опит да се съхраняват данни по-ефективно, така че да се използва по-малко място за съхранение. Особено при прехвърляне на данни - напр. Поточно предаване на филм или телефония - това е изключително важно. Разграничаваме два фундаментално различни вида компресия:
# Компресия без загуби
При компресия без загуби данните могат да бъдат напълно реконструирани. Т.е. подобно на кодирането - това е a уникално и обратимо картографиране.
Може да се използва навсякъде, където не може да възникне загуба - програма вече не се изпълнява, ако липсват команди! Изображения, аудио и видео по време на производството и редактирането - в противен случай качеството ще намалява с всяко запазване (т.е. кодиране). Примери flac - звук zip, rar - файлове gif, png, raw, psd, xcf - графики
# Компресия със загуба
При запазване данните се премахват тук. Това позволява да се получи съответно голямо количество памет, но оригиналните данни могат да бъдат възстановени само частично. Преди всичко се опитва да остави не важни данни.
Използва се при завършване на носител, т.е. когато вече не е за редактиране Примери mp3 - звук jpg - графика mp4, avi, mov - видео
# Графика
Различните файлови формати предлагат всички предимства и недостатъци благодарение на различното им компресиране. Също така играе роля дали текстът, логото, илюстрацията или снимката трябва да бъдат компресирани.
В листа с упражненията вече опознахме тип компресия, а именно кодиране на дължина на изпълнение или накратко RLE.
Отговори на следните въпроси:
- Когато процедурата е много ефективна?
- За какъв вид графика може да се използва?
# Huffman кодиране
През 1952 г. Дейвид Хъфман разработва процес, чрез който символите могат да бъдат кодирани по начин, спестяващ място. Неговата идея е, че символите, които се появяват често в текста, получават по-кратък код от символите, които рядко се появяват в текста.
# Кодово дърво
Кодовото дърво е структура с начален възел. Оттук можете да продължите вляво или отдолу вдясно. 0 в кода означава да отидете наляво, а 1 означава да отидете надясно. Когато се стигне до възел с буква, човек е декодирал символ и започва отново от началото.
Huffman дърво за «Anna»
- Декодирайте следната последователност от битове с горното кодово дърво. (SP) означава интервал.
- Сега кодирайте получения текст или в Pentacode, или в ASCII. Колко дълго се получава битовата последователност?
- Можете ли да намерите по-добър код от Pentacode/ASCII?
Пентакод:
12 знака Г 5 бита = 60 бита
ASCII:
12 знака Г 7 бита = 84 бита (първоначално)
12 знака Г 8 бита = 96 бита (с 0 бита)
собствен код:
Трябва да е възможно да се кодират само 4 знака. 2 бита са достатъчни за това!
| 00 | (SP) |
| 01 | А. |
| 10 | н |
| 11. | С. |
12 знака Г 2 бита = 24 бита
# Създайте дърво на Хафман
Алгоритъмът на Хафман трябва да бъде обяснен с примера за кодиране на текста «MISSISSIPPI».
Първо преброявате колко често всеки знак се появява в текста и създавате честотна таблица.
| Честота | 1 | 2 | 4-ти | 4-ти |
Сега става въпрос за създаване на кодиращо дърво. Честотите на буквите образуват възел. Честотата е във възела, буквата под него. Възлите са сортирани според нарастващата им честота:
Възел с честота на знаците
Сега двата възела с най-ниски честоти са прикрепени към нов възел. Новият възел съдържа натрупаната честота на оригиналните възли:
Комбинирайте възли 1
Това се повтаря, докато всички възли се свържат заедно. Ако два възела имат еднаква честота, няма значение кой е избран:
Обединяване на възли 2
Важно е възлите да се пресортират след всяка стъпка.
Обединяване на възли 3
Когато дървото приключи, всички клонове, които сочат наляво, са маркирани с «0», всички, които сочат надясно, с «1».
Имена на краищата
Таблица за кодиране вече може да бъде направена чрез четене на кода за всеки символ от дървото:
| код | 11. | 100 | 101 | 0 |
Създайте дърво на Huffman за следния текст и съответно кодирайте текста:
Колко бита заема думата в кодирането на Huffman? Колко в пентакод? Колко в ASCII?
# Huffman-Baum за немски
По принцип се създава дърво на Хафман за всеки текст, който трябва да бъде кодиран. Това се занимава със свойствата на текста и гарантира, че на често срещащите се символи се присвоява кратък код. Дървото трябва да бъде запазено заедно с кодираните данни - то се използва за декодиране.
Ако погледнете честотата на буквите в немския език, ние можем да използваме тези данни, за да създадем дърво на Хафман, което би било подходящо за по-дълги немски текстове.
Дърво на Хуфман за честотата на знаците в немския език
Можете ли да отговорите на следните въпроси:
- Защо езикът играе роля?
- Защо в следващото изречение няма място за съхранение с Huffman?