2 практикалық жұмыс. 2жмыс хаффман алгоритмі
 Скачать 22.62 Kb.
|
№2жұмысХАФФМАН АЛГОРИТМІХаффман әдісі бойынша файлды қысу үшін, біріншіден, файлды толығымен оқып және әр символ қанша рет кездесетінін есептеп шығу керек. Символдардың кездесу жиілігін санағансоң, жиілігі төмендеу бойынша топтастырылады, яғни кестедегі әр символдың орнын ауыстырмай жадыда сілтеме кестесі төмендеу бойынша сортталады. Соңғы кестедегі әр сілтемені “түйін”-деп атаймыз. Мұнан былай (ағашта) осы “түйінге” көрсететін сілтемені орналастырамыз. Мысал Ұзындығы 100 байт мәтіндік файлды қарастырайық. Мәтін әртүрлі 11 символдан тұрсын. Әр символдың кездескен санын (кіріс жиілігін) есептеп келесіні алдық. 3.2-кесте
Ыңғайлық үшін символдар мен олардың кіріс жиілігін былай құрастырамыз:  Енді жиілігі ең аз екі символды аламыз: біздің мысалымызда бұл “ы” (3) және “т” (6) немесе “п”, “д” (6), соңғы үш символдардың кез келгенін алуға болады. Біз “т” символды алайық. “ы” және “т” түйіндерден жаңа түйін құрастырамыз, оның жиілігі “ы” және “т” жиіліктерінің сомасына тең.  Шеңбер ішіндегі номер – “ы” және “т” символдар жиіліктерінің сомасы. Енді қайтадан ең аз жиілікті екі символды іздейміз. “ы” және “т” символдарды алмай, олардың орнына жаңа түйінді қарастырамыз. Ең аз жиілік енді “д” мен “п” символдарда. Қайтадан түйіндердің қосылу операциясын орындаймыз.  Келесі қадамымыз – “ғ” және “і” символдарды қосу.  Енді жиілігі бірдей (= 9) “е” символы және “ы” мен “т” қосылған кездегі бірінші пайда болған жаңа түйінді аламыз.  Осылай жалғастырып, толық “ағашты” құрастырамыз, яғни бір түйінге барлығы жиналу қажет.  Ағашды құрғаннан кейін біз файлды таңбалай аламыз. Әрқашан ағаштың түбірінен (Root) бастауымыз керек. Символға таңба бергенде ағаш бойымен жоғарыға қарай жүріп, бұтақтардың барлық бұрылысын ескереміз, егер солға бұрылсақ, онда 0 таңбасын сақтаймыз және 1 таңбасын – оң бұрылысқа. “а” символ үшін таңбаны беру жолын қарастырайық: оңға 57-ге қарай жүреміз (1-ді сақтаймыз), енді сол бұрыс, сосын тағы сол бұрыс жасаймыз. “а” үшін таңба – 101. “ғ” символды қарастырсақ – оң, оң, сол, сол, яғни 1100 таңбасын аламыз. Осылай барлық символдар үшін орындаймыз: 3.3-кесте
|