გარბენის სიგრძის კოდირება

Run-Length Encoding

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

ttttsssssssnwwwwQQQQoooooooo

        გარბენის სიგრძით კოდირების შემდგომ მივიღებთ:

t4s7n1w4Q4o8

        რაც გვეუბნება რომ მიმდევრობაში არის ოთხი "t" სიმბოლო, შემდეგ მოდის შვიდი "s" სიმბოლო, შემდეგ ერთი "n"  და ა.შ. საწყისი მიმდევრობა მოცემულია 28 ელემენტით, კოდირების შემდგომ ვიღებთ 12-ს(ვგულისხმობთ, რომ მაქსიმალური გარბენის სიგრძე არის 255). მონაცემების ზომა შემცირდა 2.3-ჯერ. გარბენის სიგრძის კოდირებამ შემცირების ნაცვლად შესაძლოა გაზარდოს გამომავალი მიმდევრობის სიგრძე. ყველაზე უარეს შემთხვევაში, როდესაც ყველა გარბენის სიგრძე 1-ის ტოლია და გარბენის სიგრძის მაქსიმალური ზომაა 255(ერთი ბაიტი) გამომავალი მიმდევრობის სიგრძე გაიზრდება 2-ჯერ.

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

მოვიყვანოთ პროგრამული კოდის მაგალითი, რომელიც დაწერილია C++-ზე:

#include <memory.h>

class RLE
{
public:
        RLE();
        ~RLE();

        //კოდირების მეთოდი
        bool encode( unsigned char* dataIn, unsigned int sizeIn, unsigned char*& dataOut, unsigned int& sizeOut );
        //დეკოდირების მეთოდი
        bool decode( unsigned char* dataIn, unsigned int sizeIn, unsigned char*& dataOut, unsigned int& sizeOut );
};


RLE::RLE(){}

RLE::~RLE(){}

bool RLE::encode( unsigned char* dataIn, unsigned int sizeIn, unsigned char*& dataOut, unsigned int& sizeOut )
{
        if( !dataIn || !sizeIn )
                return false;

        const unsigned char fragmentMaxLength = 0xff;

        //გამოვყოთ მეხსიერება გამომავალი მიმდევრობისთვის
        dataOut = new unsigned char[sizeIn*2*sizeof(unsigned char)];
        if( !dataOut )
                return false;

        unsigned int fragmentCounter = 0;
        unsigned char* fragmentElements = dataOut;
        unsigned char* fragmentLengthes = dataOut + sizeIn*sizeof(unsigned char);

        //ჩავამატოთ პირველი სიმბოლო
        fragmentElements[ fragmentCounter ] = dataIn[ 0 ];
        fragmentLengthes[ fragmentCounter ] = 1;

        for ( unsigned int i=1; i<sizeIn; i++ )
        {
                //თუ მიმდინარე სიმბოლო არის განსხვავებული ან ფრაგმენტის ზომამ მიაღწია მაქსიმუმს
                if( ( fragmentElements[ fragmentCounter ] != dataIn[ i ] ) || ( fragmentLengthes[ fragmentCounter ] == fragmentMaxLength ) )
                {
                        fragmentCounter++;
                        fragmentElements[ fragmentCounter ] = dataIn[ i ];
                        fragmentLengthes[ fragmentCounter ] = 1;
                }else
                {
                        fragmentLengthes[ fragmentCounter ]++;
                }
        }

        fragmentCounter++;

        //ჩავწეროთ კომპაქტურად
        memcpy( fragmentElements + fragmentCounter*sizeof(unsigned char), fragmentLengthes, fragmentCounter*sizeof(unsigned char) );
        sizeOut = fragmentCounter*sizeof(unsigned char)*2;

        return true;
}

bool RLE::decode( unsigned char* dataIn, unsigned int sizeIn, unsigned char*& dataOut, unsigned int& sizeOut )
{
        if( !dataIn )
                return false;

        unsigned int fragmentCounter = sizeIn/2;
        unsigned char* fragmentElements = dataIn;
        unsigned char* fragmentLengthes = dataIn + fragmentCounter*sizeof(unsigned char);

        //დავითვალოთ დასაბრუნებელი მიმდევრობის ზომა
        sizeOut = 0;
        for ( unsigned int i=0; i<fragmentCounter; i++ )
                sizeOut += fragmentLengthes[ i ];

        //გამოვყოთ მეხსიერება გამომავალი მიმდევრობისთვის
        dataOut = new unsigned char[ sizeOut ];
        if( !dataOut )
                return false;

        unsigned int decompressionElementCounter = 0;

        for ( unsigned int i=0; i<fragmentCounter; i++ )
        {
                memset( dataOut+decompressionElementCounter, fragmentElements[ i ], fragmentLengthes[ i ] );
                decompressionElementCounter += fragmentLengthes[ i ];
        }

        return true;
}

       მონაცემთა შეკუმშვის ეს მეთოდი ფართოდ გამოიყენება სხვადასხვა ტიპის შემკუმშველებში. ალგორითმის მუშაობის დრო წრფივია. კოდირების დროითი სირთულე არის O(n) სადაც n შემავალი სიმბოლოების რაოდენობაა. დეკოდირების დროითი სირთულე არის O(n) სადაც n შემავალი ფრაგმენტების რაოდენობაა. გარბენის სიგრძის კოდირების წინ ხშირად გამოიყენება ტრანსფორმაცია წინ გადმოტანით(MTF) რომელიც ხშირად ზრდის გარბენების რაოდენობებს და გვაძლევს სასურველ განაწილებას.