Huffman-kódok: példák alkalmazása

Abban a pillanatban, kevesen gondolunk arra, hogyan működik a fájl tömörítés. Összehasonlítva az előző használata a személyi számítógép sokkal könnyebb lett. És szinte minden ember dolgozik a fájlrendszer fájljait. De kevesen gondolnak, hogyan működnek és milyen alapon file tömörítés. A legelső változata ennek a folyamatnak volt a Huffman-kód, és ezeket használják ma a különböző népszerű archivers. Sok felhasználó nem is gondolnak, hogy milyen egyszerű fájl tömörítési zajlik, és működik a rendszer. Ebben a cikkben megnézzük, hogy a kompresszió, ami árnyalja felgyorsítható és leegyszerűsítheti a kódolás, valamint, hogy mi az elvet a fa kódolás.

History algoritmus

A legelső algoritmus hatékony kódolás az elektronikus információs vált kód Huffman javasolt már a közepén a huszadik század, mégpedig 1952-ben. Ez volt az, aki abban a pillanatban az alapelem a legtöbb létrehozott programok tömöríteni az információkat. Abban a pillanatban, az egyik legnépszerűbb források felhasználásával ezt a kódot az archívum ZIP, ARJ, RAR és még sokan mások. Továbbá, a Huffman algoritmus használható tömöríteni JPEG-képek és egyéb grafikus objektumokat. Nos, minden faxot is a modern kódolás, feltalálta 1952-ben. Annak ellenére, hogy létrehozása óta a kód volt annyi ideje, hogy ez a nap is használják a különböző új membránok és a berendezés a régi és modern típusú.

Az elv hatékony kódolás

Az alapot a Huffman algoritmus tartalmaz egy rendszert, amely lehetővé teszi, hogy cserélje ki a leghitelesebb, a leggyakrabban előforduló szimbólumok kódolt bináris rendszer. És azok, akik kevésbé gyakori, helyettesíteni hosszabb kódokat. Long Huffman-kód csak akkor kerül sor, miután a rendszer minden legkisebb értékek. Ez a technika lehetővé teszi, hogy minimálisra csökkentsék a hossza a kódot minden jel az eredeti üzenet egészét. A lényeg az, hogy az elején a kódolási valószínűségét a betűk kell már ismert. Ez belőlük lesz kész, és az utolsó üzenet. Ezen adatok alapján, hogy végzett az építőiparban a Huffman-kód fát, alapján megrendezésre kerülő leveleket kódoló eljárás az archívumban.

Huffman kód, például

Annak illusztrálására, az algoritmus, fontolja meg egy grafikus változata építése kódfában. Ahhoz, hogy ezt a módszert használja, hogy hatékony legyen, szükséges tisztázni a meghatározás bizonyos értékek szükségesek a koncepció a folyamatot. A készlet a több csomópont és ívek, amelyek irányított csomópontok közötti, úgynevezett gráf. A fa maga egy gráf egy sor speciális tulajdonságai:

• minden egyes csomópont tartalmazhat nem több, mint az egyik ívek;
• egyik csomópont legyen a gyökér a fa, azaz, hogy ne legyen része az ív egyáltalán
• ha a szár kezdődik mozog az íveket, a folyamat lehetővé teszi, hogy teljesen kapcsolatba a csomópontokat.

Van is egy ilyen dolog, része a Huffman-kód a levél a fa. Ez egy csomópont, ahonnan nem megy minden arc. Ha két csomópontot köti össze egy ív, az egyik ezek közül a szülő a másik gyerek, attól függően, hogy melyik csomópont az ív kialszik, és mi szerepel. Ha két csomópont azonos szülőcsomópont, hívják őket testvér oldalakon. Ha a levelek, levelek a csomópontok több ívek, akkor az úgynevezett bináris fa. Csak így a Huffman fa. A különlegessége az építési egységek az, hogy a súlya minden szülő összegével egyenlő a súlyok minden gyermek csomópont.

Egy algoritmust építése a fa Huffman

Az építőiparban a Huffman-kód bemenet a betűk az ábécé. Generált területek jegyzékét, amelyek mentesek a jövőben kódfában. A tömeg minden csomópont a listában meg kell egyeznie, mint a valószínűségét a betűk üzenete ennek megfelelő csomóponthoz. Ebben az esetben az, aki a súlya a legkisebb közül választjuk több a szabad helyek a jövő fa. Ebben az esetben, ha a minimális arány figyelhető meg, több helyszínen, akkor szabadon választhat az pár. Aztán jön létre a szülő csomópont, amelynek meg kell mérjük, mint az összeg a súlyok a csomópontpárt. Ezt követően, a szülők küldeni a listát a szabad WC-k, és a gyerekek eltávolítjuk. Ebben ív megfelelő mutatók, egyesek és nullák. Ez a folyamat ismétlődik, mint szükséges ahhoz, hogy csak egyetlen csomópontot. Ezután kiírja a bináris számjegy, fentről lefelé.

Hatékonyságának javítása tömörítés

Annak érdekében, hogy növeljék a tömörítési hatékonyságot, szükséges során fa épület kódot kell használni az összes adatot a valószínűségét a betűk egy adott fájl mellé egy fa, és nem teszi lehetővé az a tény, hogy ezek elszórtan számos szöveges dokumentumokat. Ha az előre séta ezt a fájlt, akkor azonnal kiszámítja a statisztikát, hogy gyakran vannak betűk, a létesítmény figyelemmel a tömörítés.

Felgyorsítása a sűrítési folyamat

Ahhoz, hogy gyorsítsák fel az algoritmus, a meghatározása a leveleket kell végezni, nem a előfordulási valószínűsége egy adott levelet, és a gyakorisága előfordulása. Az algoritmus könnyebbé válik, és velük együtt dolgozni sokkal gyorsabb. ez is elkerülhető kapcsolatos műveleteket a lebegőpontos osztás. Ezen kívül dolgozik ebben az üzemmódban a dinamikus Huffman-kódot, vagy inkább maga az algoritmus nem vonatkozik az esetleges változtatásokat. Ez elsősorban annak köszönhető, hogy az a tény, hogy a valószínűségek egyenesen arányos a frekvenciával. Érdemes odafigyelni arra, hogy a végső tömege a fájlt, vagy az úgynevezett gyökér csomópont összegével egyenlő a karakterek száma a kezelendő tárgyat.

következtetés

Huffman-kód - egyszerű és régóta fennálló algoritmus, amely még ma is sokan használják, jól ismert programok és a vállalatok. Az egyszerűség és a világosság a hatékony eredmény eléréséhez tömöríteni fájlok bármilyen mennyiség és jelentősen csökkenti a lemezterület tárolására. Más szóval, a Huffman algoritmus - már régóta vizsgálják, és a munka diagram, amely sürgős nem csökken ezen a napon. És azzal a képességgel, hogy csökkentse a fájlok méretét, átadják a hálózaton vagy más módon sokkal egyszerűbb, gyors és kényelmes. Munka az algoritmus, akkor tömöríteni minden olyan információt, teljesen veszélytelen szerkezetét és minőségét, de a maximális hatás súlyának csökkentését fájlt. Más szóval, a kódoló a Huffman-kód volt, és továbbra is a legnépszerűbb és a megfelelő módszer a tömörítés a fájl méretét.