ჰაფმენის კოდირება

Huffman Coding

        ჰაფმენის მეთოდი განეკუთვნება უდანაკარგო მონაცემთა შეკუმშვის ჯგუფს ( ის ასევე განეკუთვნება ენტროპიული კოდერების ჯგუფსაც ). მეთოდი იყენებს მეხსიერებაში მონაცემთა განაწილების სტატისტიკურ მაჩვენებლებს. მოვიყვანოთ მაგალითი: ვთქვათ მოცემული გვაქვს ტექსტი, რომელიც არის შენახული ტრადიციული მეთოდით(მაგალითად ASCII კოდებით), თითოეული სიმბოლო ჩაწერილია ერთ ბაიტში(რვა ბიტში). ამ შემთხვევაში ჩვენ მეხსიერებაში ვმოძრაობთ თანაბარი სიგრძის ნახტომებით და ამოგვაქვს მეხსიერებიდან შესაბამისი სიმბოლო ერთი ოპერაციით. მონაცემების შენახვის ასეთი მიდგომა ხშირ შემთხვევაში იწვევს მეხსიერების გაფლანგვას. ჩვენ შეგვიძლია დავაკვირდეთ ტექსტს და დავადგინოთ რომელი სიმბოლო გვხვდება უფრო ხშირად და რომელი ნაკლებად. მაშინ შევძლებთ რომ იმ სიმბოლოებს რომელიც ხშირად გვხვდება გამოვუყოთ უფრო მცირე ზომის ბიტების მიმდევრობა და რომელიც იშვიათად გვხვდება იმათ უფრო დიდი. კოდირების ამ ჯგუფს რომელიც თანაბარი ზომის ელემენყებისტან შემდგარ მიმდევრობას უსაბამებს, ცვლადი ზომის ელემენტების მიმდევრობას უწორებენ ცვლადი სიგრძით კოდირებას. ჰაფმენის მეთოდი გვეხმარება სწორედ ყოველი სიმბოლოსთვის ცვლადი სიგრძის ბიტური მიმდევრობების დადგენაში. ამ შემთხვევეში უკვე მეხსიერებიდან სიმბოლოს ამოღება ერთი ოპერაციით ვერ ხერხდება. ჩვენთვის ცნობილი არაა სიმბოლო, შესაბამისად არაა ცნობილი მისი სიგრძეც ამის გამო ჩვენ გვიწევს ბიტების მიმდევრობის განხილვა სათითაოდ. უნდა ავიღოთ პირველი ბიტი და მოვძებნოთ ჩვენს ანბანში შეესაბამება თუ არა ამ ერთ ბიტიან მიმდევრობას რაიმე სიმბოლო, თუ ვერ მოიძებნა შემდეგ უნდა დავამატოთ შემდეგი ბიტი და ვნახოთ ამ ორ ბიტიან მიმდევრობას შეესაბამება თუ არა სიმბოლო და ასე მანამ, სანამ არ ვიპოვით შესაბამისი მიმდევრობის მქონე სიმბოლოს და შემდეგ გადავალთ შემდეგი სიმბოლოს ამოცნობაზე. აქედან გამომდინარე ჩვენ ვერ ამოვიცნობთ i-ურ სიმბოლოს მანამ სანამ არ გვექნება ამოცნობილი ყველა სიმბოლო 0-დან i-მდე, რადგან ჩვენ ვერ ვიპოვით i-ური სიმბოლოს დასაწყისს ბიტების მიმდევრობაში. ასევე უნდა აღინიშნოს ის ფაქტი რომ არცერთი სიმბოლოს შესაბამისი ბიტური მიმდევრობა არ უნდა იყოს სხვა მიმდევრობის პრეფიქსი. აქვე განვმართოთ რას ვუწოდებთ პრეფიქსს. ბიტური მიმდევრობა A არის ბიტური მიმდევრობა B-ს  პრეფიქსი თუ B მიმდევრობა მიიღება A მიმდევრობის ბოლოში ბიტების დამატებით. ყველა ამ პირობის გათვალისწინებით ჩვენ შევძლებთ მოცემული ანბანის ორგანიზებას ორობითი ხის სახით. როგორც უკვე ვთქვით ჩვენი ამოცანაა შევადგინოთ ახალი ანბანი, ბაიტის ყველა შესაძლო მნიშვნელობას შევუსაბამოთ ბიტების გარკვეული უნიკალური მიმდევრობა. ალგორითმის მუშაობის პირველ ეტაპზე ხდება მოცემული საწყისი ბაიტების მიმდევრობის ანალიზი და ბაიტის(სიმბოლოს) ყველა მნიშვნელობისათვის სიხშირეების დადგენა, რომელიც შეგვიძლია წარმოვადგინოთ ცხრილის სახით სადაც ბაიტის თითოეულ მნიშვნელობას შეესაბამება გარკვეული სიხშირის მახასიათებელი (ის შეიძლება ასევე შევინახოთ ფარდობითი სიხშირის სახით თუმცა ამას რპინციპული მნიშვნელობა არ გააჩნია)
        ჰაფმენის მეთოდის საშუალებით ჩვენ ვახდენთ ორობითი ხის აგებას, რომლის ყოველი ფოთოლი შეიცავს ელემენტის საწყის მნიშვნელობას, ხოლო გზა ფოთლიდან ხის ძირამდე გვაძლევს მის ცვლადი სიგრძის ორობით კოდს. ინფორმაციის შენახვა ხის სახით გვეხმარება ლოგარითმულ დროში მივწვდეთ კოდირებული სიმბოლოს რეალურ მნიშვნელობას. ორობითი ხე არაბალანსირებულია.

სურათზე მოცემულია ჰაფმენის ორობითი ხე(სურათი აღებულია ვიკიპედიიდან), რომლის ფოთლებშიც შენახულია ელემენტები და მათი სიხშირეები.

        განვიხილოთ ჰაფმენის ორობითი ხის აგების მეთოდი. პირველ ეტაპზე შემოსული სიმბოლოები უნდა დავალაგოთ სიხშირის მაჩვენებლის მიხედვით(კლებადობით).
ავიღოთ ყველაზე დაბალი ალბათობის მქონე ორი სიმბოლო, შევქმნათ მათი მშობელი შიდა კვანძი მათი სიხშირეების ჯამით, ჩავამატოთ შვილი კვანძების მაგივრად და გადავალაგოთ სია ისე რომ ისევ კლებადობით იყოს დალაგებული. ეს პროცესი უნდა გავიმეოროთ სანამ ერთი კვანძი(ხის ფესვი) არ დაგვრჩება სიაში.

სურათზე ნაჩვენებია 4 სიმბოლო თავისი სიხშირეებით და ხის აგების პროცესი  ჰაფმენის მეთოდით.

პროგრამული იმპლემენტაცია

        პროგრამული კოდი დაწერილია C++-ზე:

#include <malloc.h>
#include <memory.h>
#include <search.h>
#include <string.h>

#pragma pack(push,1)

class HuffmanNode8
{
public:
        HuffmanNode8()
        {
                nFrequency = 0;
                byAscii = 0;
                dwCode = 0;
                nCodeLength = 0;
                pParent = pLeft = pRight = 0;
        }

        unsigned int nFrequency;
        unsigned char byAscii;
        unsigned int dwCode;
        unsigned short nCodeLength;
        HuffmanNode8 *pParent, *pLeft, *pRight;
};

#pragma pack(pop)


class Huffman
{
public:
        Huffman(){}
        ~Huffman(){}

        bool Compress( unsigned char* pSrc, int nSrcLen, unsigned char*& pDes, int& nDesLen );
        bool Decompress( unsigned char* pSrc, int nSrcLen, unsigned char*& pDes, int& nDesLen );
private:
        //ადარებს 2 ელემენტს სიხშირეების მიხედვით
        static int __cdecl frequencyCompare( const void* elem1, const void* elem2 );
        //ადარებს 2 ელემენტს მნიშვნელობების მიხედვით
        static int __cdecl CompareSymbol8( const void* elem1, const void* elem2 );
        HuffmanNode8* PopNode( HuffmanNode8* pNodes[], int nIndex, bool bRight );
        void SetNodeCode( HuffmanNode8* pNode );
        //აგებს ჰაფმენის ხეს
        int GetHuffmanTree( HuffmanNode8 nodes[], bool bSetCodes = true );
};




int __cdecl Huffman::frequencyCompare( const void* elem1, const void* elem2 )
{
        HuffmanNode8* pNodes[2] = { (HuffmanNode8*)elem1, (HuffmanNode8*)elem2 };

        if( pNodes[0]->nFrequency == pNodes[1]->nFrequency )
                return 0;

        return ( pNodes[0]->nFrequency < pNodes[1]->nFrequency )? 1 : -1;
}

int __cdecl Huffman::CompareSymbol8(const void* elem1, const void* elem2 )
{
        return ( ( (HuffmanNode8*)elem1 )->byAscii > ( (HuffmanNode8*)elem2 )->byAscii )? 1 : -1;
}

HuffmanNode8* Huffman::PopNode( HuffmanNode8* pNodes[], int nIndex, bool bit )
{
        HuffmanNode8* pNode = pNodes[ nIndex ];
        pNode->dwCode = bit;
        pNode->nCodeLength = 1;
        return pNode;
}

void Huffman::SetNodeCode( HuffmanNode8* pNode )
{
        HuffmanNode8* pParent = pNode->pParent;

        while( pParent && pParent->nCodeLength )
        {
                pNode->dwCode <<= 1;
                pNode->dwCode |= pParent->dwCode;
                pNode->nCodeLength++;
                pParent = pParent->pParent;
        }
}

int Huffman::GetHuffmanTree( HuffmanNode8 nodes[], bool bSetCodes )
{
        HuffmanNode8* pNodes[ 256 ], *pNode;

        //დავამატოთ შემოსული სიმბოლოები ჰაფმენის მიმდევრობაში
        int nNodeCount=0, nCount=0;
        for( nCount = 0; nCount < 256 && nodes[ nCount ].nFrequency; nCount++ )
                pNodes[ nNodeCount++ ] = &nodes[ nCount ];

        int nParentNode = nNodeCount, nBackNode = nNodeCount - 1;

        while( nBackNode > 0 )
        {
                //მშობელი კვანძი
                pNode = &nodes[ nParentNode++ ];

                //ამოვაგდოთ პირველი შვილი
                pNode->pLeft = PopNode(pNodes, nBackNode--, false);

                //ამოვაგდოთ მეორე შვილი
                pNode->pRight = PopNode(pNodes, nBackNode--, true);

                // adjust parent of the two poped nodes
                pNode->pLeft->pParent = pNode->pRight->pParent = pNode;

                // adjust parent frequency
                pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency;

                // insert parent node depending on its frequency
                int i = 0;
                for( i = nBackNode; i >= 0; i-- )
                        if( pNodes[ i ]->nFrequency >= pNode->nFrequency )
                                break;

                memmove( pNodes+i+2, pNodes+i+1, (nBackNode-i)*sizeof(int) );
                pNodes[i+1] = pNode;
                nBackNode++;
        }

        //ხის ფოთლებს ჩავუწეროთ კოდები
        if( bSetCodes )
                for( nCount = 0; nCount < nNodeCount; nCount++ )
                        SetNodeCode( &nodes[ nCount ] );

        return nNodeCount;
}



bool Huffman::Compress( unsigned char* pSrc, int nSrcLen, unsigned char*& pDes, int &nDesLen )
{
        HuffmanNode8 nodes[ 511 ];

        //შევავსოთ ცხრილში მნიშვნელობები
        int nCount = 0;
        for( nCount = 0; nCount < 256; nCount++ )
                nodes[nCount].byAscii = (unsigned char)nCount;

        //დავითთვალოთ თითოეული მნიშვნელობის მოსვლის სიხშირეები
        nCount = 0;
        for( nCount = 0; nCount < nSrcLen; nCount++ )
                nodes[ pSrc[ nCount ] ].nFrequency++;

        //დავალაგოთ ჰაფმენის ცხრილი სიხშირეების კლების მიხედვით
        qsort( nodes, 256, sizeof(HuffmanNode8), Huffman::frequencyCompare );

        //ავაგოთ ჰაფმენის ხე ცხრილის მიხედვით
        int nNodeCount = GetHuffmanTree( nodes );

        int nNodeSize = sizeof(unsigned int) + sizeof(unsigned char);
        nDesLen = nSrcLen + nNodeCount*nNodeSize;

        //გამოვყოთ გამომავალი მეხსიერება pDes = (unsigned char*)malloc( nDesLen );
        unsigned char* pDesPtr = pDes;
        memset( pDesPtr, 0, nDesLen );

        //შევინახოთ საწყისი მონაცემების ზომა გამომავალი მონაცემების პირველ 4 ბაიტში
        ((unsigned int*)pDesPtr)[0] = (unsigned int)nSrcLen;
        pDesPtr += sizeof(unsigned int);

        //შევინახოთ ჰაფმენის ხის ფოთლების რაოდენობა
        pDesPtr[0] = (unsigned char)(nNodeCount-1);
        pDesPtr += sizeof(unsigned char);

        //ჩავწეროთ ჰაფმენის ხის ფოთლები
        for( nCount = 0; nCount < nNodeCount; nCount++ )
        {
                //კვანძები მასივში დალაგებულია სიხშირეების კლებით
                memcpy( pDesPtr, &nodes[ nCount ], nNodeSize );
                pDesPtr += nNodeSize;
        }

        //დავალაგოთ კვანძები მნიშვნელობების ზრდის მიხედვით
        //რათა შევძლოთ ინდექსით მიმართვა მასივში
        qsort(nodes, 256, sizeof(HuffmanNode8), Huffman::CompareSymbol8);


        //ჩავწეროთ შემოსული სიმბოლოების მიმდევრობა ახალი კოდებით
        unsigned int nDesIndex = 0;
        for( nCount = 0; nCount < nSrcLen; nCount++ )
        {
                *(unsigned int*)(pDesPtr+(nDesIndex>>3)) |= nodes[pSrc[nCount]].dwCode << (nDesIndex&7);
                nDesIndex += nodes[ pSrc[ nCount ] ].nCodeLength;
        }

        //დავითვალოთ შეკუმშული ინფორმაციის ზომა
        nDesLen = ( pDesPtr - pDes ) + ( nDesIndex + 7 )/8;

        //მეხსიერების რეალოკაცია მოვახდინოთ რეალურ ზომაზე
        pDes = (unsigned char*)realloc( pDes, nDesLen );

        return true;
}


bool Huffman::Decompress( unsigned char* pSrc, int nSrcLen, unsigned char* &pDes, int &nDesLen)
{
        //წავიკითხოთ მონაცემების სიგრძე რომელიც შენახულია მონაცემების დასწყისში
        nDesLen = *(unsigned int*)pSrc;

        //გამოვყოთ მეხსიერება გამომავალი მონაცემებისათვის
        pDes = (unsigned char*)malloc( nDesLen+1 );

        //სიგრძის შემდგომ მოდის კვანძების რაოდენობა
        int nNodeCount = *( pSrc + sizeof(unsigned int) ) + 1;

        //ინიციალიზაცია გავუკეთოთ ჰაფმენის ელემნტებს
        HuffmanNode8 nodes[511], *pNode;
        int nNodeSize = sizeof(unsigned int) + sizeof(unsigned char), nSrcIndex = nNodeSize;
        for( int nCount = 0; nCount < nNodeCount; nCount++ )
        {
                memcpy( &nodes[nCount], pSrc+nSrcIndex, nNodeSize );
                nSrcIndex += nNodeSize;
        }

        //ავაგოთ ჰაფმენის ხე
        GetHuffmanTree( nodes, false );

        //მოვძებნოთ ხის ძირი
        HuffmanNode8 *pRoot = &nodes[0];
        while( pRoot->pParent )
                pRoot = pRoot->pParent;

        int nDesIndex = 0;
        unsigned int nCode;

        //გარდავქმნათ ბაიტების ზომა ბიტების ზომაში
        nSrcIndex <<= 3;

        while( nDesIndex < nDesLen )
        {
                //წავიკითხოთ ბიტების მიმდევრობა (მხოლოდ პირველი 4 ბაიტი)
                nCode = ( *(unsigned int*)( pSrc + ( nSrcIndex >> 3 ) ) ) >> ( nSrcIndex&7 );

                //დავიწყოთ ძებნა ხეში ძირიდან და საკითხულ 4 ბაიტის თავში ვნახოთ
                //ჰაფმენის ორობითი კოდი
                pNode = pRoot;

                //ჩავიდეთ შვილებში სანამ მას ყავს მარცხენა შვილი
                //თუ კვანძს ყავს მარცხენა შვილი, მას ეყოლება მარჯვენაც
                while( pNode->pLeft )
                {
                        //თუ პირველი ბიტი არის 1 ჩავდივართ მარჯვენა შვილში, თუ 0 მარცხენაში
                        pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
                        //ვშლით პირველ ბიტს
                        nCode >>= 1;
                        //წაკითხული ბიტების მთვლელს ვზრდით 1-ით
                        nSrcIndex++;
                }
                //ნაპოვნი კვანძიდან(ფოთლიდან) წავიკითხოთ რეალური მნიშვნელობა
                //და გავზარდოთ ჩაწერილი ბაიტების მთვლელი
                pDes[ nDesIndex++ ] = pNode->byAscii;
        }

        return true;
}

        ჰაფმენის კოდირების მეთოდი ძალიან ფართოდ გამოიყენება როგორც ვიდეო, ასევე აუდიო კოდეკებში. მონაცემთა შეკუმშვის გარეშე უბრალოდ შეუძლებელი იქნებო ამხელა მოცულობის მონაცემების შენახვა.