Ginagamit ang algorithm ni Huffman upang mai-compress o ma-encode ang data. Karaniwan, ang bawat character sa isang file ng teksto ay nakaimbak ng walong piraso (mga digit, alinman sa 0 o 1) na mapa sa character na iyon gamit ang isang encoding na tinatawag na ASCII. Ang isang naka-encode na file na Huffman ay sumisira sa matibay na istraktura na 8-bit upang ang mga pinaka-karaniwang ginagamit na mga character ay nakaimbak sa ilang mga piraso lamang (ang 'a' ay maaaring "10" o "1000" kaysa sa ASCII, na kung saan ay "01100001"). Ang hindi gaanong karaniwang mga character, kung gayon, ay madalas na kukuha ng higit sa 8 mga piraso ('z' ay maaaring "00100011010"), ngunit dahil bihirang maganap, ang pag-encode ni Huffman, sa kabuuan, ay lumilikha ng isang mas maliit na file kaysa sa orihinal.
Mga hakbang
Bahagi 1 ng 2: Pag-encode
Hakbang 1. Bilangin ang dalas ng bawat character sa file na mai-encode
Isama ang isang character na dummy upang markahan ang pagtatapos ng file - magiging mahalaga ito sa paglaon. Sa ngayon, tawagan itong EOF (pagtatapos ng file) at markahan ito bilang pagkakaroon ng dalas ng 1.
Halimbawa, kung nais mong i-encode ang isang text file na nagbabasa ng "ab ab cab," magkakaroon ka ng 'a' na may dalas 3, 'b' na may dalas 3, '' (puwang) na may dalas 2, 'c' na may dalas 1, at EOF na may dalas 1
Hakbang 2. Mag-imbak ng mga character bilang mga node ng puno at ilagay ang mga ito sa isang priyoridad na pila
Magtatayo ka ng isang malaking puno ng binary na may bawat character bilang isang dahon, kaya dapat mong iimbak ang mga character sa isang format tulad na maaari silang maging mga node ng puno. Ilagay ang mga node na ito sa isang priyoridad ng priyoridad sa dalas ng bawat character bilang prayoridad ng node nito.
- Ang isang binary tree ay isang format ng data kung saan ang bawat piraso ng data ay isang node na maaaring magkaroon ng hanggang isang magulang at dalawang anak. Ito ay madalas na iginuhit bilang isang sanga ng puno, kaya't ang pangalan.
- Ang isang pila ay isang maayos na pinangalanang koleksyon ng data kung saan ang unang bagay na pumapasok sa pila ay ang unang lumabas din (tulad ng paghihintay sa pila). Sa isang priyoridad na pila, ang data ay nakaimbak sa pagkakasunud-sunod ng kanilang priyoridad, upang ang unang bagay na lumabas ay ang pinaka-kagyat na bagay, ang bagay na may pinakamaliit na priyoridad, sa halip na ang unang bagay na na-enqueued.
- Sa halimbawang "ab ab cab", magiging ganito ang iyong priyoridad na pila: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Hakbang 3. Simulang buuin ang iyong puno
Alisin (o i-dequeue) ang dalawang pinaka-kagyat na bagay mula sa pangunahing pila. Lumikha ng isang bagong puno ng node upang maging magulang ng dalawang node na ito, na itinatago ang unang node bilang kaliwang anak nito at ang pangalawa bilang kanang anak. Ang priyoridad ng bagong node ay dapat na kabuuan ng mga prayoridad ng anak nito. Pagkatapos ipadala ang bagong node na ito sa linya ng priyoridad.
Ganito ang ganito ang priyoridad ng priyoridad: {'': 2, bagong node: 2, 'a': 3, 'b': 3}
Hakbang 4. Tapusin ang pagbuo ng iyong puno:
ulitin ang hakbang sa itaas hanggang sa may isang node lamang sa pila. Tandaan na bilang karagdagan sa mga node na nilikha mo para sa mga character at kanilang mga frequency, magpapaka dequeuing ka rin, magiging mga puno, at muling magpapalaki ng mga node ng magulang, mga node na sarili na nilang mga puno.
- Kapag tapos ka na, ang huling node sa pila ay ang ugat ng puno ng pag-encode, kasama ang lahat ng iba pang mga node na naka-branch dito.
- Ang mga madalas na ginagamit na character ay ang mga dahon na pinakamalapit sa tuktok ng puno, habang ang mga bihirang ginamit na character ay iposisyon sa ilalim ng puno, mas malayo sa ugat.
Hakbang 5. Lumikha ng isang mapa ng pag-encode. Maglakad sa puno upang maabot ang bawat character. Sa tuwing bibisita ka sa kaliwang anak ng isang node, iyon ay isang '0'. Sa tuwing bibisita ka sa tamang anak ng isang node, iyon ay isang '1'. Kapag nakarating ka sa isang character, itabi ang character na may pagkakasunud-sunod ng 0 at 1 na kinakailangan upang makarating doon. Ang pagkakasunud-sunod na ito ay kung ano ang nai-encode ng character tulad ng sa naka-compress na file. Itabi ang mga character at ang kanilang mga pagkakasunud-sunod sa isang mapa.
- Halimbawa, magsimula sa ugat. Bisitahin ang kaliwang anak ng ugat, at pagkatapos ay bisitahin ang kaliwang anak ng node na iyon. Dahil ang node na nandito ka ngayon ay walang mga anak, naabot mo ang isang character. Ito ay ' '. Dahil lumakad ka ng kaliwa dalawang beses upang makarating dito, ang pag-encode para sa '' ay "00".
- Para sa punong ito, magiging ganito ang mapa: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Hakbang 6. Sa output file, isama ang naka-encode na mapa bilang isang header
Papayagan nitong ma-decode ang file.
Hakbang 7. I-encode ang file
Para sa bawat character sa file na ma-encode, isulat ang pagkakasunud-sunod ng binary na naimbak mo sa mapa. Kapag natapos mo na ang pag-encode ng file, tiyaking idagdag ang EOF sa dulo.
- Para sa file na "ab ab cab", magiging ganito ang naka-encode na file: "1011001011000101011011".
- Ang mga file ay nakaimbak bilang bytes (8 bits, o 8 binary digit). Dahil ang Huffman Encoding algorithm ay hindi gumagamit ng 8-bit na format, ang mga naka-encode na file ay madalas na walang haba na mga multiply ng 8. Ang natitirang mga digit ay punan ng 0. Sa kasong ito, ang dalawang 0 ay maidaragdag sa dulo ng file, na parang ibang puwang. Maaari itong maging isang problema: paano malalaman ng decoder kung kailan titigil sa pagbabasa? Gayunpaman, dahil nagsama kami ng isang end-of-file na character, makakarating ang decoder dito at pagkatapos ay titigil, hindi papansinin ang anupaman na naidagdag pagkatapos.
Bahagi 2 ng 2: Pag-decode
Hakbang 1. Basahin sa isang naka-encode na file na Huffman
Una, basahin ang header, na dapat ang mapa ng pag-encode. Gamitin ito upang bumuo ng isang nakaka-decode na puno sa parehong paraan ng pagbuo mo ng puno na ginamit mo upang ma-encode ang file. Ang dalawang puno ay dapat magkapareho.
Hakbang 2. Basahin ang binary ng isang digit nang paisa-isa
Daanan ang puno habang binabasa mo: kung magbasa ka sa isang '0', pumunta sa kaliwang anak ng node na iyong naroon, at kung magbasa ka sa isang '1', pumunta sa tamang bata. Kapag naabot mo ang isang dahon (isang node nang walang anumang mga bata), nakarating ka sa isang character. Isulat ang character sa na-decode na file.
Dahil sa paraan ng pag-iimbak ng mga character sa puno, ang mga code para sa bawat character ay mayroong isang pag-aari ng unlapi, upang walang pag-encode ng binary na character ang maaaring mangyari sa simula ng pag-encode ng isa pang character. Ang pag-encode para sa bawat character ay ganap na natatangi. Ginagawa nitong mas madali ang pag-decode
Hakbang 3. Ulitin hanggang maabot mo ang EOF
Binabati kita! Na-decode mo ang file.
