Компресија компјутерски науки G23c
Решете го работниот лист «Формати на слики»
# Компресија
Компресијата се обидува да заштеди податоци поефикасно за да се користи помалку простор за складирање. Ова е исклучително важно, особено кога пренесувате податоци - на пр., Стриминг на филм или телефонирање -. Разликуваме два фундаментално различни типа на компресија:
# Компресија без загуби
Со компресија без загуби, податоците можат целосно да се реконструираат. Ова значи дека „е„ како кодирање “ уникатно и реверзибилно пресликување.
Може да се користи каде и да нема загуба - програма веќе не работи ако недостасуваат команди! Слики, аудио и видео за време на производството и уредувањето - во спротивно квалитетот би се намалил со секоја заштеда (т.е. кодирање). Примери флеш-звук, рар-датотеки gif, png, raw, psd, xcf графика
# Загубена компресија
Податоците се отстрануваат тука при зачувување. Ова овозможува да се добие соодветно голема количина меморија, но оригиналните податоци можат да бидат само делумно реконструирани. Пред сè, се обидува да остави неважни податоци.
Користете кога завршувате медиуми, т.е. кога веќе не треба да се уредува Примери mp3 или „звук jpg“ од графика mp4, avi, mov и „видео
# Графички
Различните формати на датотеки ги нудат сите предности и недостатоци благодарение на нивната различна компресија. Исто така, игра улога дали текстот, логото, илустрацијата или фотографијата треба да се компресираат.
На листот за вежби веќе запознавме еден вид компресија, имено кодирање со должина или скратено RLE.
Одговори ги следниве прашања:
- Каде што постапката е многу ефикасна?
- За каква графика може да се користи?
# Кодирање на Хафман
Во 1952 година Дејвид Хафман разви процес со кој ликовите можат да се кодираат на начин на заштеда на простор. Неговата идеја е ликовите што често се појавуваат во текстот даваат пократок код отколку ликовите што ретко се појавуваат во текстот.
# Дрво со кодови
Дрво со кодови е структура со почетен јазол. Од тука можете или да продолжите лево или долу десно. 0 во кодот значи одење лево, 1 значи одење десно. Кога се стигнува до јазол со буква, некој декодирал карактер и еден започнува одново од почеток.
Дрво Хафман за «Ана»
- Декодирајте ја следната низа на битови со горното дрво со кодови. (SP) се залага за празно место.
- Сега кодирајте го примениот текст или во Пентакод или во ASCII. Колку долго е примена низата на битови?
- Можете ли да најдете подобар код од Pentacode/ASCII?
Пентакод:
12 карактери Г 5 бита = 60 бита
ASCII:
12 карактери Г 7 бита = 84 бита (првично)
12 карактери Г 8 бита = 96 бита (со 0 бита)
сопствен код:
Мора да биде можно да се кодираат само 4 карактери. 2 бита се доволни за ова!
| 00 | (СП) |
| 01 | А. |
| 10 | Н. |
| 11 | С. |
12 карактери Г 2 бита = 24 бита
# Создадете дрво Хафман
Алгоритмот Хафман треба да се објасни со примерот на кодирање на текстот «MISSISSIPPI».
Прво сметате колку пати се појавува секој знак во текстот и креирате табела за фреквенција.
| Фреквенција | 1 | 2 | 4-ти | 4-ти |
Сега станува збор за создавање дрво за кодирање. Фреквенциите на буквите секоја формираат јазол. Фреквенцијата е во јазолот, буквата под него. Јазлите се подредени според нивната зголемена фреквенција:
Јазол со фреквенција на знаци
Сега двата јазли со најниски фреквенции се прикачени на нов јазол. Новиот јазол ја содржи акумулираната фреквенција на оригиналните јазли:
Комбинирајте ги јазлите 1
Ова се повторува сè додека сите јазли не се поврзат заедно. Ако два јазли имаат иста фреквенција, не е важно кој е избран:
Спојување на јазли 2
Важно е јазлите повторно да се сортираат по секој чекор.
Спојување на јазли 3
Кога дрвото ќе заврши, сите гранки што покажуваат лево се обележани со «0В», сите оние што покажуваат надесно со «1В».
Имиња на рабовите
Сега може да се креира табела за кодирање со читање на кодот за секој карактер од дрвото:
| код | 11 | 100 | 101 | 0 |
Направете дрво Хафман за следниот текст и соодветно кодирајте го текстот:
Колку битови зафаќа зборот во кодирањето на Хафман? Колку во пентакод? Колку во ASCII?
# Хафман-Баум за германски
Во принцип, се создава дрво Хафман за секој текст да биде кодиран. Ова се занимава со својствата на текстот и гарантира дека на знаците што често се појавуваат им се доделува краток код. Дрвото треба да се зачува заедно со шифрираните податоци - се користи за декодирање.
Ако ја погледнете фреквенцијата на буквите на германски јазик, можеме да ги искористиме овие податоци за да создадеме дрво Хафман, што би било погодно за подолги германски текстови.
Дрво Хафман за фреквенцијата на знаците на германски јазик
Можете ли да одговорите на следниве прашања:
- Зошто јазикот игра улога?
- Зошто со Хафман нема простор за складирање за следната реченица?