|
Shennon fano kodlash tushunchasi
|
| bet | 3/5 | | Sana | 20.02.2024 | | Hajmi | 0,92 Mb. | | #159700 |
Afsuski, Shannon-Fano har doim ham eng yaxshi prefiks kodlarini bermaydi. Shu sababli, Shennon-Fano kamdan-kam hollarda ishlaydi; Huffman kodlash deyarli hisoblash jihatidan sodda va eng qisqa prognoz qilingan kod so’zi uzunligiga doimiy ravishda erishadigan prefiks kodlarini beradi. ZIP fayl formatining tarkibiy qismi bo’lgan IMPLODE siqish texnikasida Shannon-Fano kodlash yaxshi ishlashi va kichik dasturlash ehtiyojlari bilan oddiy algoritmdan foydalanish uchun mo’ljallangan bo’lsa qo’llaniladi. - Samarali kod jadvali Shannon-Fano daraxtini qurish uchun ishlatiladigan spetsifikatsiya bilan belgilanadi. Haqiqiy usul oddiy:
Shennon fano kodlash tushunchasi Har bir belgi uchun nisbiy paydo bo’lish chastotasini aniqlash uchun taqdim etilgan belgilar ro’yxatiga mos keladigan ehtimolliklar yoki chastotalar ro’yxatini tuzing. Belgilar ro’yxatini chastotaning o’sish tartibida joylashtiring, eng tez-tez uchraydigan belgilar chapda va eng kam uchraydigan belgilar o’ngda. Ro’yxatni yarmiga bo’ling, chap yarmi uchun chastotalarni o’ngdagilarga imkon qadar yaqin tuting. Ikkilik raqam 0 ro’yxatning chap qismiga, ikkilik 1 raqami esa o’ng qismiga beriladi. Natijada, birinchi qismdagi barcha belgilar kodlari 0 dan, ikkinchi qismdagi barcha belgilar kodlari esa 1 dan boshlanadi. - Guruhlarga bo’linish va kodlarga bit qo’shish orqali har bir belgi daraxtda mos kod bargiga ega bo’lguncha 3 va 4-bosqichlarni takrorlang. Bu ikki yarmining har biri uchun bajarilishi kerak.
Shennon fano algoritmning ishlashi Algoritmning bosqichlari quyida keltirilgan: Har bir belgining nisbiy paydo bo’lish chastotasini aniqlash uchun, taqdim etilgan belgilar ro’yxati uchun ehtimollar yoki chastotalar sonining mos keladigan ro’yxatini yarating. Belgilar ro’yxatini chastotaning kamayish tartibida joylashtiring, chapdan eng ko’p ishlatiladiganlaridan boshlab va eng kam ishlatiladiganlari bilan o’ngga siljiting. - Chap va o’ng bo’limlarning chastotalar soni o’rtasida iloji boricha o’xshashlik bilan ro’yxatni ikkiga bo’ling.
- Ro’yxatning chap tomoniga ajratilgan ikkilik raqam 0 va o’ngga tayinlangan ikkilik raqam 1. Birinchi bo’limdagi belgilar uchun bu barcha kodlar 0 dan boshlanadi, ikkinchi qismdagi belgilar uchun esa barcha kodlar 1 dan boshlanadi.
|
| |
