Szöveges kódolási projekt - PDF ingyenes letöltés
1 ISN képzés a terminál tanárai számára Denis Bouhineau, Éric Gaussier, Alexandre Termier, Cyril Labbé, Philippe Bizard, Anne Rasse, Jean-Marc Vincent UFR IM 2 AG Képzés terminál tanároknak I. szint 1/34
2 1. terv 2. cél 3. téma 3. algoritmus 4. megvalósítás 5 Futtatási hossz kódolás 6 Megvalósítás 2/34
3 Projektcélok 1 A fák algoritmusának és tervezésének, prioritási sorainak, rekurziós iterációinak elemzése 2 C nyelvű kódírás, amely megerősíti ennek a nyelvnek a gyakorlatát, fájlok, együtt fejlesztés 3 Validálás minden szakaszban bonyolultsági elemzés, teljesítményértékelés (kísérletezés) Mini -projekt felépítése: csapatmunka: teljes munkaidős párok (több mint egy hét) autonómia Értékelés: védekezés/szoftver bemutatás Eljárás: bemutató: 15 perc kérdések: 15 perc Célkitűzések: bemutatni, hogy milyen munkák készítik elő a tesztjátékokat a beszéd előadásának menete 3/34
4 Szervezési tervezés: szervezés: TD 8: 30-tól 9: 30-ig, gépterem, majd hétfő: kezdet [TD szoba] kedd: projekt architektúra [gépterem] szerda: bitenkénti bemenetek/kimenetek [TD szoba] csütörtök: fejlesztés [gépterem] péntek: validálás, költségelemzés, bemutató [TD szoba] Felügyelet: Denis Bouhineau, Éric Gaussier, Alexandre Termier, Cyril Labbé, Philippe Bizard, Anne Rasse, Jean-Marc Vincent Weboldal: 4/34
5 Projekt témája: veszteségmentes tömörítés A menüben: Huffman algoritmusa bináris fájlok olvasásának/írásának fájlok tömörítéséhez/dekompressziójához való kódolásához és dekódolásához menet közben Run Length Encoding algoritmus alapvető verzióváltozatai (előzmények, escape szekvencia, PackBits) Kísérletezés különféle adatformátumokkal: szövegek, programok (forrás és bináris), képek stb. 5/34
6 Emlékeztető: A bemenő ábécét kódoló Huffman (karakterek, pixelek stb.) Ábécét (biteket) egy Huffman-kód: az A minden eleméhez hozzárendel egy szekvenciát: A kódoló dekódolás A jellemzői: változó hosszúságú kód (= morzekód; Ascii kód) Előtag tulajdonság: kódolás (a 1) = w 1, kódolás (a 2) = w 2 w 1 és w 2 nem egymás előtagjai (hatékony dekódolási algoritmus) 6/34
7 A Huffman-kódolás alkalmazása Kódoljon egy bináris fájlban egy A-elemet: hozzárendel egy rövid kódot a kezdeti szekvencia leggyakoribb tömörítéséhez Megjegyzések: a kódot az eredeti szövegnek megfelelően kell felépíteni. kódolás előtt: Statikus Huffman kódolás közben: Dinamikus Huffman A dekódolás során ismerni kell. (azonosokra továbbítva vagy újraszámítva) 7/34
8 Huffman fa Huffman kód ábrázolása = Huffman fa levelek halmaza = A bal gyermek hozzáférésének elemei = 0; hozzáférés a jobb gyermekhez = 1 kód (a) = az útvonal címkéinek σ szekvenciája: gyökér σ a 0 1 E A B D C F kód (e) = 1; kód (a) = 001; kód (c) = 0110; stb. az előtag tulajdonságot tiszteletben tartják! 8/34
9 Kódolási algoritmus Adott Huffman-fát: S = a 1. egy R 0 1 EABDCF 1 kódoló tábla C felépítése a Huffman-fa első mélységi átvizsgálása az σ gyök σ szekvencia aktuális csomópontjának memorizálásával az egyes levelekhez a: C [a] = σ Rq: rekurzív vagy iteratív algo (explicit verem) 2 S átjárása és R előállítása C 9/34 használatával
10 Dekódoló algoritmus adott Huffman-fát: RS = a 1. a Huffman-fa 0 1 EABDCF 1 bejárása az R mentén (0: bal gyermek; 1: jobb gyermek) 2 minden levélnél elérte: a-nak S-be írása visszatér a a Huffman-fa gyökere/34
11 Huffman-fát építeni? Attól függ, hogy az A S elemei milyen gyakorisággal fordulnak elő: nagy frekvencia = a gyökhöz közeli elemek. Frekvenciatábla megszerzése: Freq [ai] = fi (fi = ai frekvenciája S-ben, valós 0 és 1 között) Statikus megközelítés: 1 Freq felépítése S első útjával (fi = ai/S előfordulásának száma) 2 Huffman fa felépítése (Freq használatával) 11/34
12 Informális algoritmus a fa felépítéséhez F prioritási várólistát (Fap) használunk, ebből: az elemek a fa csomópontjai, a prioritások valósak (nagy értékű, nagy prioritású) Algo: 1 szúrja be az elemeket (ai, Freq [ai]) az F 2 fedéllel, feltéve, hogy az F legalább 2 elemet tartalmaz, két elemet (n 1, f 1) és (n 2, f 2) vegyen ki az F betét minimális tömegéből (n, f 1 + f 2) F-be, ahol n egy új csomópont a bal gyermekeknek n 1 és a jobb gyerekeknek n 2 3, az F fennmaradó eleme a Huffman-fa gyökere 12/34
13 Adatszerkezetek A készlet: kibővített Ascii-kód karakterei (0 és 255 között). Táblázat frekvenciája: 0 és 255 közötti indexelésű valós számok táblázata: Huffman-fa: vagy cellák láncolása mutatókkal, vagy táblázat (256 lap 511 csomópont) Fap F: párok (fa csomópont, valós) Szekvencia: 0 és 1 karakterek sora 13/34
14 Globális architektúra Összekapcsolt programok összessége: D dekódolás S Frekvencia számítás Frekvencia felépítés Tengely tengely R Kommunikációs kódolás lehetséges fájlokkal vagy csövekkel (csövekkel)/34