Tömörítéses informatika G23c
Oldja meg a «Képformátumok» munkalapot
# Tömörítés
A tömörítés hatékonyabban próbálja megtakarítani az adatokat, így kevesebb tárhely kerül felhasználásra. Ez rendkívül fontos, különösen adatátvitelkor - pl. Film streaming vagy telefonálás -. Két alapvetően különböző típusú tömörítést különböztetünk meg:
# Veszteségmentes tömörítés
Veszteségmentes tömörítéssel az adatok teljesen rekonstruálhatók. Ez azt jelenti, hogy "olyan", mint a kódolás " egyedi és megfordítható térképezés.
Használható mindenütt, ahol nem fordulhat elő veszteség - a programok már nem futnak, ha hiányoznak a parancsok! Képek, hang és videó a gyártás és a feldolgozás során - különben a minőség minden megtakarítással (azaz kódolással) romlana. Példák flac „hangzip, rar” fájlok gif, png, raw, psd, xcf ”grafikák
# Vesztes tömörítés
Az adatok itt kerülnek mentésre. Ez lehetővé teszi a megfelelő memóriamennyiség megszerzését, de az eredeti adatokat csak részben lehet rekonstruálni. Mindenekelőtt a nem fontos adatokat próbálja kihagyni.
Használja a hordozó befejezésekor, azaz amikor már nem kell szerkeszteni. Példák mp3 „hang jpg” grafika mp4, avi, mov videó
# Grafikus
A különböző fájlformátumok minden előnyt és hátrányt kínálnak különböző tömörítésüknek köszönhetően. Az is szerepet játszik, hogy szöveget, logót, illusztrációt vagy fényképet kell-e tömöríteni.
A feladatlapon már megismerhettünk egyfajta tömörítést, nevezetesen a Run Length Encoding -t, röviden RLE-t.
Válaszolj a következő kérdésekre:
- Ahol az eljárás nagyon hatékony?
- Milyen grafikára lehetne használni?
# Huffman kódolás
1952-ben David Huffman kifejlesztett egy folyamatot, amellyel a karakterek helytakarékos módon kódolhatók. Elgondolása szerint a szövegben gyakran megjelenő karakterek rövidebb kódot kapnak, mint a szövegben ritkán megjelenő karakterek.
# Kódfa
A kódfa egy szerkezet, amelynek kiinduló csomópontja van. Innen folytathatja balra vagy jobbra lent. A 0 a kódban balra, az 1 jobbra haladást jelent. Ha egy csomópontot betűvel érünk el, akkor az egyik dekódolta a karaktert, és az elejétől kezdődik.
Huffman-fa «Annának»
- Dekódolja a következő bitsorozatot a fenti kódfával. (SP) egy szóköz.
- Most kódolja a kapott szöveget Pentacode-ban vagy ASCII-ben. Meddig fogadja a bitsorozatot?
- Találnál jobb kódot, mint a Pentacode/ASCII?
Pentacode:
12 karakter Г 5 bit = 60 bit
ASCII:
12 karakter Г 7 bit = 84 bit (eredetileg)
12 karakter Г 8 bit = 96 bit (0 bittel)
saját kód:
Csak 4 karaktert kell kódolni. Ehhez elegendő 2 bit!
| 00 | (SP) |
| 01 | A. |
| 10. | N |
| 11. | S. |
12 karakter Г 2 bit = 24 bit
# Hozzon létre egy Huffman-fát
A Huffman algoritmust a «MISSISSIPPI» szöveg kódolásának példájával kell magyarázni.
Először megszámolja, hányszor jelenik meg az egyes karakterek a szövegben, és létrehoz egy gyakorisági táblázatot.
| Frekvencia | 1 | 2 | 4 | 4 |
Most egy kódoló fa létrehozásáról van szó. A betűk frekvenciája csomópontot alkot. A frekvencia a csomóban van, az alatta lévő betű. A csomópontok növekvő gyakoriságuk szerint vannak rendezve:
Csomó a karakterek gyakoriságával
Most a két legalacsonyabb frekvenciájú csomópont új csomóponthoz kapcsolódik. Az új csomópont az eredeti csomópontok összesített gyakoriságát tartalmazza:
Kombinálja a csomópontokat 1
Ezt addig ismételjük, amíg az összes csomópont össze nem kapcsolódik. Ha két csomópont azonos frekvenciával rendelkezik, nem számít, melyiket választják:
Csomópontok egyesítése 2
Fontos, hogy a csomópontokat minden lépés után rendezni kell.
Csomópontok egyesítése 3
Amikor a fa elkészült, az összes balra mutató ágat "0" betűvel jelölik, mindazokat, amelyek jobbra mutatnak egy "1" betűvel.
Név élek
Kódolótábla készíthető úgy, hogy elolvassa a fa minden karakterének kódját:
| kód | 11. | 100 | 101 | 0 |
Hozzon létre egy Huffman-fát a következő szöveghez, és ennek megfelelően kódolja a szöveget:
Hány bitet vesz fel a szó Huffman kódolásban? Mennyit a pentacode-ban? Mennyit az ASCII-ben?
# Huffman-Baum németül
Elvileg minden kódolandó szöveghez létrejön egy Huffman-fa. Ez foglalkozik a szöveg tulajdonságával és biztosítja, hogy a gyakran előforduló karakterekhez rövid kódot rendeljenek. A fát azonban a kódolt adatokkal együtt el kell menteni - a dekódoláshoz használják.
Ha megnézzük a német nyelvű betűk gyakoriságát, ezeket az adatokat felhasználhatjuk egy Huffman-fa létrehozására, amely alkalmas lenne a hosszabb német szövegekre.
Hufmann-fa a német nyelvű karakterek gyakoriságához
Tudna válaszolni a következő kérdésekre:
- Miért játszik szerepet a nyelv?
- Miért nincs hely a Huffmannál a következő mondathoz?