Az adatok tömörítése a Huffman -kódolás segítségével: 10 lépés

Tartalomjegyzék:

Az adatok tömörítése a Huffman -kódolás segítségével: 10 lépés
Az adatok tömörítése a Huffman -kódolás segítségével: 10 lépés

Videó: Az adatok tömörítése a Huffman -kódolás segítségével: 10 lépés

Videó: Az adatok tömörítése a Huffman -kódolás segítségével: 10 lépés
Videó: Unf*ck a forgatókönyved 5 perc alatt | Valóságos írási tanácsok 2024, Március
Anonim

Huffman algoritmusát használják az adatok tömörítésére vagy kódolására. Általában a szövegfájl minden karaktere nyolc bitben (0 vagy 1 számjegy) van tárolva, amely az adott karakterhez társul az ASCII nevű kódolás segítségével. Egy Huffman-kódolású fájl lebontja a merev 8 bites struktúrát, így a leggyakrabban használt karaktereket csak néhány bitben tárolják (az "a" lehet "10" vagy "1000", nem pedig ASCII, azaz "01100001"). A legkevésbé gyakori karakterek tehát gyakran sokkal többet foglalnak 8 bitnél (a „z” lehet „00100011010”), de mivel ilyen ritkán fordulnak elő, a Huffman -kódolás összességében sokkal kisebb fájlt hoz létre, mint az eredeti.

Lépések

Rész 1 /2: Kódolás

Tömörítse az adatokat a Huffman kódolás használatával 1. lépés
Tömörítse az adatokat a Huffman kódolás használatával 1. lépés

1. lépés: Számolja meg a kódolni kívánt fájl minden karakterének gyakoriságát

A fájl végének jelöléséhez adjon meg egy álkaraktert - ez később fontos lesz. Egyelőre nevezzük EOF -nek (fájl vége), és jelöljük meg 1 -es gyakorisággal.

Például, ha az "ab ab cab" szövegű szövegfájlt kívánja kódolni, akkor az "a" a 3. frekvenciával, a "b" a 3. gyakorisággal, a '' (szóköz) a 2. gyakorisággal, a "c" az 1. gyakorisággal és EOF 1 -es frekvenciával

Tömörítse az adatokat a Huffman kódolás használatával 2. lépés
Tömörítse az adatokat a Huffman kódolás használatával 2. lépés

Lépés 2. Tárolja a karaktereket facsomópontként, és helyezze őket prioritási sorba

Egy nagy bináris fát fog építeni, ahol minden karakter levél lesz, ezért a karaktereket olyan formátumban kell tárolni, hogy azok a fa csomópontjaivá válhassanak. Helyezze ezeket a csomópontokat egy prioritási sorba, ahol minden karakter frekvenciája a csomópont prioritása.

  • A bináris fa egy adatformátum, ahol minden adat egy csomópont, amelynek legfeljebb egy szülője és két gyermeke lehet. Gyakran elágazó fának rajzolják, innen a név.
  • A várólista egy találóan megnevezett adatgyűjtemény, ahol az első dolog, ami a sorba kerül, szintén az első, ami kijön (például a sorban állás). Egy prioritási sorban az adatokat prioritási sorrendjük szerint tárolják, így az első dolog, ami a legsürgetőbb, a legkisebb prioritású, nem az első sorba kerül.
  • Az "ab ab cab" példában a prioritási sor így nézne ki: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Tömörítse az adatokat a Huffman kódolás használatával 3. lépés
Tömörítse az adatokat a Huffman kódolás használatával 3. lépés

3. lépés. Kezdje el a fa építését

Távolítsa el (vagy sorolja le) a két legsürgetőbb dolgot az elsőbbségi sorból. Hozzon létre egy új facsomópontot, amely e két csomópont szülője lesz, az első csomópontot bal oldali gyermekként, a másodikat pedig jobb gyermekként tárolja. Az új csomópont prioritásának az utód prioritásainak összegének kell lennie. Ezután sorolja be ezt az új csomópontot a prioritási sorba.

A prioritási sor most így néz ki: {'': 2, new node: 2, 'a': 3, 'b': 3}

Tömörítse az adatokat a Huffman kódolás használatával 4. lépés
Tömörítse az adatokat a Huffman kódolás használatával 4. lépés

4. lépés: Fejezze be a fa építését:

ismételje meg a fenti lépést, amíg csak egy csomópont nem lesz a sorban. Ne feledje, hogy a karaktereken és azok gyakoriságán létrehozott csomópontokon kívül dequing is lesz, fává változik, és újraszekvenálja a szülőcsomópontokat, amelyek maguk is fák.

  • Ha befejezte, a sor utolsó csomópontja lesz a kódolófa gyökere, és az összes többi csomópont elágazik tőle.
  • A leggyakrabban használt karakterek a fa tetejéhez legközelebb eső levelek lesznek, míg a ritkán használt karakterek a fa alján, a gyökértől távolabb helyezkednek el.
Tömörítse az adatokat a Huffman kódolás használatával 5. lépés
Tömörítse az adatokat a Huffman kódolás használatával 5. lépés

5. lépés: Hozzon létre kódolási térképet. Sétáljon át a fán, hogy elérje az egyes karaktereket. Minden alkalommal, amikor meglátogat egy csomópont bal oldali gyermekét, ez egy „0”. Minden alkalommal, amikor meglátogatja a csomópont megfelelő gyermekét, ez az „1”. Amikor eljut egy karakterhez, tárolja a karaktert a 0 -as és 1 -es sorozattal, amelyre szükség volt az eléréshez. Ez a sorrend a karakter kódolása, mint a tömörített fájlban. Tárolja a karaktereket és azok sorozatát a térképen.

  • Kezdje például a gyökérrel. Látogassa meg a gyökér bal gyermekét, majd látogassa meg a csomópont bal gyermekét. Mivel a csomópontnak, ahol most van, nincs gyermeke, elért egy karaktert. Ez ' '. Mivel kétszer ment balra, hogy ideérjen, a '' kódolása "00".
  • Ennél a fánál a térkép így fog kinézni: {'': "00", 'a': "10", "b": "11", "c": "010", EOF: "011"}.
Tömörítse az adatokat a Huffman kódolás használatával 6. lépés
Tömörítse az adatokat a Huffman kódolás használatával 6. lépés

6. lépés. A kimeneti fájlban fejlécként adja meg a kódolási térképet

Ez lehetővé teszi a fájl dekódolását.

Tömörítse az adatokat a Huffman kódolás használatával 7. lépés
Tömörítse az adatokat a Huffman kódolás használatával 7. lépés

7. lépés. Kódolja a fájlt

A kódolni kívánt fájl minden karakteréhez írja be a térképen tárolt bináris szekvenciát. Miután befejezte a fájl kódolását, feltétlenül adja hozzá az EOF -et a végéhez.

  • Az "ab ab cab" fájl esetében a kódolt fájl így fog kinézni: "1011001011000101011011".
  • A fájlokat bájtokban tárolják (8 bit vagy 8 bináris számjegy). Mivel a Huffman kódolási algoritmus nem használja a 8 bites formátumot, a kódolt fájlok sokszor nem 8-szorosak. A fennmaradó számjegyeket 0-val kell kitölteni. Ebben az esetben két 0 -t adunk a fájl végéhez, ami úgy néz ki, mint egy másik szóköz. Ez problémát jelenthet: honnan tudja a dekódoló, mikor kell abbahagyni az olvasást? Mivel azonban egy fájlvégi karaktert vettünk fel, a dekódoló erre jut, majd leáll, figyelmen kívül hagyva minden mást, amit később hozzáadtak.

2/2. Rész: Dekódolás

Tömörítse az adatokat a Huffman kódolás használatával 8. lépés
Tömörítse az adatokat a Huffman kódolás használatával 8. lépés

1. lépés Olvassa el egy Huffman-kódolású fájlban

Először olvassa el a fejlécet, amelynek a kódolási térképnek kell lennie. Használja ezt a dekódolófa felépítéséhez, ugyanúgy, ahogy a fájlt kódolta. A két fának azonosnak kell lennie.

Tömörítse az adatokat a Huffman kódolás használatával 9. lépés
Tömörítse az adatokat a Huffman kódolás használatával 9. lépés

Lépés 2. Olvassa el a bináris számjegyeket egyenként

Menjen végig a fán olvasás közben: ha „0” -val olvassa, menjen a csomópont bal gyermekéhez, ahol éppen van, és ha „1” -ben olvassa, akkor a jobb gyermekhez. Amikor eléri a levelet (egy csomópontot gyermek nélkül), egy karakterhez érkezett. Írja be a karaktert a dekódolt fájlba.

Mivel a karakterek a fában tárolódnak, az egyes karakterek kódjai előtaggal rendelkeznek, így egyetlen karakter bináris kódolása sem fordulhat elő egy másik karakter kódolásának kezdetén. Az egyes karakterek kódolása teljesen egyedi. Ez jelentősen megkönnyíti a dekódolást

Tömörítse az adatokat a Huffman -kódolás segítségével 10. lépés
Tömörítse az adatokat a Huffman -kódolás segítségével 10. lépés

3. lépés. Ismételje addig, amíg el nem éri az EOF -et

Gratulálunk! Dekódolta a fájlt.

Ajánlott: