Huffman alqoritmi məlumatları sıxışdırmaq və ya kodlaşdırmaq üçün istifadə olunur. Normalda, mətn sənədindəki hər bir simvol, ASCII adlanan bir kodlaşdırma istifadə edərək həmin xarakterə uyğun gələn səkkiz bit (rəqəmlər, 0 və ya 1) şəklində saxlanılır. Huffman kodlu bir fayl, sərt 8 bit quruluşunu parçalayır, beləliklə ən çox istifadə olunan simvollar bir neçə bitdə saxlanılır ('a' "01100001" olan ASCII deyil, "10" və ya "1000" ola bilər).). Ən az yayılmış simvollar, çox vaxt 8 bitdən çox ('z' "00100011010" ola bilər), lakin çox nadir hallarda baş verdikləri üçün, Huffman kodlaması, ümumiyyətlə, orijinaldan daha kiçik bir fayl yaradır.
Addımlar
2 -nin 1 -ci hissəsi: Kodlaşdırma
Addım 1. Kodlaşdırılacaq fayldakı hər bir xarakterin tezliyini sayın
Faylın sonunu qeyd etmək üçün kukla bir xarakter əlavə edin - bu daha sonra əhəmiyyətli olacaq. Hələlik buna EOF (faylın sonu) deyin və 1 tezliyinə malik olaraq qeyd edin.
Məsələn, "ab ab cab" oxunan bir mətn faylını kodlaşdırmaq istəyirsinizsə, 3 tezliyi ilə 'a', 3 tezliyi ilə 'b', 2 tezliyi ilə '(boşluq), 1 tezliyi ilə' c 'olardı. və EOF 1 tezliyi ilə
Addım 2. Simvolları ağac qovşaqları kimi saxlayın və onları prioritet növbəyə qoyun
Yarpaq kimi hər bir xarakteri olan böyük bir ikili ağac quracaqsınız, buna görə də simvolları ağacın qovşaqlarına çevrilə biləcək formatda saxlamalısınız. Bu qovşaqları, hər bir xarakterin tezliyi düyünün prioriteti olaraq prioritet sıraya yerləşdirin.
- İkili ağac, hər bir məlumat parçasının bir ana və iki uşağa qədər ola biləcək bir qovşaq olduğu bir məlumat formatıdır. Çox vaxt budaqlanan bir ağac olaraq çəkilir, buna görə də adı.
- Növbə, növbəyə girməli olan ilk şeyin də çıxmaq üçün ilk şey olduğu (adda gözləmə kimi) düzgün adlandırılmış məlumat toplusudur. Prioritet növbədə, məlumatlar prioritet sırasına görə saxlanılır, beləliklə çıxan ilk şey ən vacib şeydir, ilk növbədə deyil, ən kiçik prioritetli şeydir.
- "Ab ab kabin" nümunəsində, prioritet növbəniz belə görünür: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Addım 3. Ağacınızı qurmağa başlayın
Prioritet növbədən ən təcili iki şeyi çıxarın (və ya ləğv edin). Birinci düyünü sol uşağı, ikincisini isə sağ uşağı olaraq saxlayaraq, bu iki qovşağın valideyni olmaq üçün yeni bir ağac qovşağı yaradın. Yeni düyünün prioriteti uşağının prioritetlərinin cəmi olmalıdır. Sonra bu yeni qovluğu prioritet növbəyə qoyun.
Prioritet növbəsi indi belə görünür: {'': 2, yeni qovşaq: 2, 'a': 3, 'b': 3}
Addım 4. Ağacınızı qurmağı bitirin:
növbədə yalnız bir düyün olana qədər yuxarıdakı addımı təkrarlayın. Diqqət yetirin ki, personajlar və onların tezlikləri üçün yaratdığınız qovşaqlara əlavə olaraq, ağacdan çıxarılaraq, özləri artıq ağac olan düyünləri yenidən sıradan çıxaracaqsınız.
- İşiniz bitdikdə, növbədəki son qovşaq, kodlaşdırma ağacının kökü olacaq və bütün digər qovşaqlar ondan ayrılır.
- Ən çox istifadə olunan simvollar ağacın üst hissəsinə ən yaxın olan yarpaqlar olarkən, nadir hallarda istifadə edilən simvollar ağacın dibində, kökdən daha uzaqda yerləşəcəkdir.
Addım 5. Bir kodlaşdırma xəritəsi yaradın. Hər bir xarakterə çatmaq üçün ağacdan keçin. Hər dəfə bir düyünün sol uşağını ziyarət etdiyiniz zaman bu '0' olur. Hər dəfə bir düyünün sağ uşağını ziyarət etdiyiniz zaman bu '1' dir. Bir xarakterə çatanda, xarakteri ora çatmaq üçün lazım olan 0s və 1s ardıcıllığı ilə saxlayın. Bu ardıcıllıq, xarakterin sıxılmış faylda olduğu kimi kodlaşdırılacağı şeydir. Xəritədə personajları və onların ardıcıllığını saxlayın.
- Məsələn, kökündən başlayın. Kökün sol uşağını ziyarət edin və sonra həmin düyünün sol uşağını ziyarət edin. Hazırda olduğunuz qovşaqda heç bir uşaq olmadığı üçün bir xarakterə çatmısınız. Bu '' dir. Bura gəlmək üçün iki dəfə sola getdiyiniz üçün '' kodlaması "00" dur.
- Bu ağac üçün xəritə belə görünəcək: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Addım 6. Çıxış faylına kodlaşdırma xəritəsini başlıq olaraq daxil edin
Bu, faylın deşifr edilməsinə imkan verəcəkdir.
Addım 7. Faylı kodlaşdırın
Faylın kodlanacağı hər bir xarakter üçün xəritədə saxladığınız ikili ardıcıllığı yazın. Dosyanı kodlamağı bitirdikdən sonra EOF -u sonuna əlavə etdiyinizə əmin olun.
- "Ab ab cab" faylı üçün kodlanmış fayl belə görünür: "1011001011000101011011".
- Fayllar bayt olaraq saxlanılır (8 bit və ya 8 ikili rəqəm). Huffman Encoding alqoritmi 8-bit formatını istifadə etmədiyi üçün kodlaşdırılmış fayllar çox vaxt 8-dən çox olan uzunluqlara malik olmayacaq. Qalan rəqəmlər 0s ilə doldurulacaq. Bu vəziyyətdə, faylın sonunda başqa bir yerə bənzəyən iki 0 işarəsi əlavə olunacaq. Bu bir problem ola bilər: dekoder oxumağı nə vaxt dayandıracağını haradan bilir? Ancaq bir fayl sonu xarakteri daxil etdiyimiz üçün dekoder buna çatacaq və sonra əlavə olunan başqa bir şeyi görməməzlikdən gələcək.
2 -dən 2 -ci hissə: Kod çözmə
Addım 1. Huffman kodlu bir faylda oxuyun
Əvvəlcə kodlaşdırma xəritəsi olmalı olan başlığı oxuyun. Dosyanı kodlaşdırmaq üçün istifadə etdiyiniz ağacı necə qurdunuzsa, dekodlaşdırma ağacı qurmaq üçün bundan istifadə edin. İki ağac eyni olmalıdır.
Addım 2. Bir dəfədə ikili rəqəmlə oxuyun
Oxuyarkən ağacı gəzin: '0' ilə oxusanız, olduğunuz nöqtənin sol uşağına, '1' də oxuyursanız sağ uşağa gedin. Bir yarpağa çatanda (heç bir uşağı olmayan bir qovşaq), bir xarakterə gəldiniz. Şifrəni açılmış fayla yazın.
Simvolların ağacda saxlanılma üsulu səbəbindən hər bir xarakter üçün kodlar bir prefiks xüsusiyyətinə malikdir, belə ki, heç bir simvolun ikili kodlaşdırması başqa bir simvolun kodlaşdırılmasının əvvəlində baş verə bilməz. Hər bir xarakter üçün kodlaşdırma tamamilə unikaldır. Bu, deşifr etməyi çox asanlaşdırır
Addım 3. EOF -a çatana qədər təkrarlayın
Təbrik edirik! Faylın kodunu açmısınız.
