Skip to main content

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

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) რომელიც ხშირად ზრდის გარბენების რაოდენობებს და გვაძლევს სასურველ განაწილებას.





Comments

Popular posts from this blog

რუსული რულეტკის მეთოდი

Russian Roulette Technique რუსული რულეტკის მეთოდი არის ფართოდ გავრცელებული ტექნიკა მონტე-კარლოს ინტეგრირების პროცესის შესაწყვეტად(სახელწოდება მოდის ცნობილი რუსული თამაშიდან). იმის მაგივრად, რომ პროცესი შევწყვითოთ ხისტად, მაგალითად შერჩევების რაოდენობის რაიმე მაქსიმალურ რაოდენობაზე, რუსული რულექტკის მეთოდი გვეხმარება ინტეგრირების პროცესის მიუკერძოვებლად შეწყვეტაში. მთავარი იდეა რუსული რულეტკის მეთოდისა არის ის, რომ რუსული რულეტკა წყვეტს მონტე კარლოს მეთოდს რაიმე არანულოვანი p ალბათობით(ალბათობა შეიზლება შეირჩეს ერთხელ ან მონტე კარლოს მეთოდის ყოველ ბიჯზე სათითაოდ რაიმე მნიშვნელოვნობით) ან აგრძელებს მას და შემდგომი პროცესიდან მიღებულ შედეგს ამრავლებს 1/p - ზე. რადგან რუსული რულეტკის მეთოდი პროცესის შეწყვეტას ახდენს რაიმე არანულოვანი p ალბათობით ყოველთვის რჩება იმის შანსი, რომ პროცესი გაგრძელდეს რაც იმას ნიშნავს, რომ მონტე კარლოს ინტეგრირების პროცესისათვის ნებისმიერი სიღრმე მიღწევადი ხდება. სწორედ ამიტომ ხისტი შეზღუდვით მიღებული მიკერძოება( სისტემატიური შეცდომა ) ქრება რუსული რ...

ფერების RGB მოდელი

RGB Color Model         ფერების RGB მოდელი წარმოადგენს ისეთ მოდელს რომელშიც სამი ძრირითადი ფერის წითელი, მწვანე და ლურჯის საშუალებით მიიღება ფერების ფართო სპექტრი. მისი დასახელებაც მოდის სწორედ ძირითადი ფერების ინგლისური სახელწოდების ინიციალებიდან(Red, Green, Blue).         ფერთა სპექტრის ამდაგვარი წარმოდგენა დაკავშირებულია იმასთან, რომ გამოსახულების გამოტანის მოწყობილობებში რომელიც გააჩნიათ კომპიუტერებს, ტელევიზორებს ფერის მიღება ფიზიკურად ხდება სწორედ ამ სამი ძირითადი ფერის შეზავებით. დღესდღეობით ყველაზე გავრცელებული არის 24 ბიტიანი RGB მოდელი, სადაც თითოეულ კომპონენტს ეთმობა ერთი ბაიტი და შესაბამისად შეუძლია მიიღოს ნებისმიერი მნიშვნელობა [0, 255] დიაპაზონში, რაც საბოლოოდ გვაძლევს 16777216 განსხვავებულ ფერს.

ბეზიეს წირი

Bezier Curve         ბეზიეს წირები ფართოდ გამოიყენება კომპიუტერული მეცნიერების სხვადასხვა მიმართულებებში  CAD  სისტემებში, კომპიუტერულ გრაფიკაში და ა.შ. ისისნი პოპულარობით სარგებლობენ მისი სიმარტივის, ინტუიტიურობის და მოსახერხებულობის გამო.         მათემატიკურად ბეზიეს წირი არის ფუნქცია რომელსაც გადაეცემა ერთი პარამეტრი t(0-დან 1-მდე) და ის გვიბრუნებს წერტილს წირზე. ფუნქციის მნიშვნელობა დამოკიდებულია შემავალ t პარამეტრზე და n ცალ წერტილზე, რომლიდანაც პირველ და ბოლო წერტილს ვუწოდებთ კვანძებს(knots), ხოლო დანარჩენებს საკონტროლო წერტილებს(Control points). როდესაც t=0 ფუნქცია გვიბრუნებს პირველ კვანძს, როდესაც t=1 ფუნქცია გვიბრუნებს მეორე კვანძს, დანარჩენ მნიშვნელობებზე ფუნქცია გვიბრუნებს წირის სხვა წერტილებს. გამოდის რომ წირი იწყება პირველი კვანძში დამოკიდებულია საკონტროლო წერტილებზე,თუმცა არ გადის მათზე და სრულდება მეორე კვანძში. მათემატიკურად ნებისმიერ ბეზიეს წირს შეესაბამება პოლინომი რომლის ხარისხიც არის მოცემული წერტილების რაოდენობ...