Skip to main content

ტრანსფორმაცია წინ გადმოტანით

Move-To-Front Transform

        ტრანსფორმაციის ეს მეთოდი(MTF) თავის მხრივ არ წარმოადგენს მონაცემთა შეკუმშვის მეთოდს, თუმცა ის გამოიყენება ენტროპიული კოდირებისას როგორც წინასწარი ტრანსფორმაციის მეთოდი. მისი მიზანია შეამციროს მონაცემთა გაბნევის მაჩვენებელი რათა გაიზარდოს ენტროპიული კოდირებისას შეკუმშვის ხარისხი.
        მისი მუშაობის პრინციპი შემდეგია: ვთქვათ გვაქვს შემომავალი ელემენტების შესაძლო მნიშვნელობების სია წინასწარ განსაზღვრული, რომელშის თითოეულ სიმბოლოს გააჩნია ინდექსი. ალგორითმის მუშაობის პრინციპი შემდეგია: ვატრიალებთ ციკლს სანამ სიმბოლოების შემავალი მიმდევრობა ცარიელი არაა და ყოველ ეტაპზე ვასრულებთ შემდეგს.
  1. სიმბოლოების შემავალი მიმდევრობიდან ამოვაგდებთ პირველ ელემენტს, ვპოულობთ მისი მნიშვნელობის მქონე ელემენტს შესაძლო მნიშვნელობათა მიმდევრობაში, მის მიმდინარე ინდექსს ვწერთ გამომავალი მიმდევრობის ბოლოში.
  2. შესაძლო მნიშვნელობების სიიდან ამოვაგდებთ ნაპოვნ ელემენტს და გადავიტანთ ამავე სიის თავში.
ქვემოთ მოცემულ ცხრილში ნაჩვენებია შემავალი, გამომავალი და შესაზძლო მნიშვნელობების მიმდევრობები ალგორითმის მუშაობის პროცესში სადაც ვახდენთ "bananaaa" სიმბოლოების მიმდევრობის ტრანსფორმაციას.

შემავალიგამომავალიშესაძლო მნიშვნელობების სია
bananaaa1abcdefghijklmnopqrstuvwxyz
ananaaa1,1bacdefghijklmnopqrstuvwxyz
nanaaa1,1,13abcdefghijklmnopqrstuvwxyz
anaaa1,1,13,1nabcdefghijklmopqrstuvwxyz
naaa1,1,13,1,1anbcdefghijklmopqrstuvwxyz
aaa1,1,13,1,1,1nabcdefghijklmopqrstuvwxyz
aa1,1,13,1,1,1,0anbcdefghijklmopqrstuvwxyz
a1,1,13,1,1,1,0,0anbcdefghijklmopqrstuvwxyz
Final1,1,13,1,1,1,0,0
anbcdefghijklmopqrstuvwxyz
დეკოდირების პროცესი მუშაობს კოდირების მსგავსად, იმ განსხვავებით რომ თუ კოდირებისას ჩვენ ვეძებდით ანბანში სიმბოლოს შესაბამის ინდექსს, ახლა უნდა მოვძებნოთ ინდექსის შესაბამისი სიმბოლო.

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


#pragma once

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

  bool encode( unsigned char* DataIn, unsigned int sizeIn, unsigned char*& DataOut );
  bool decode( unsigned char* DataIn, unsigned int sizeIn, unsigned char*& DataOut );

private:
  int GetSymbolIndex( unsigned char* alphabet, unsigned char symbol );
  void MoveToFront( unsigned char* alphabet, unsigned char symbolIndex );
};




#include <memory.h>
#include "MTF.h"

bool MTF::encode( unsigned char* DataIn, unsigned int sizeIn, unsigned char*& DataOut )
{
  unsigned char alphabet[ 256 ];
  for( int i=0; i<256; i++ )
  alphabet[ i ] = i;

  DataOut = new unsigned char[ sizeIn ];
  if( !DataOut )
  return false;

  for( unsigned int i=0; i<sizeIn; i++ )
  MoveToFront( alphabet, DataOut[ i ] = GetSymbolIndex( alphabet, DataIn[ i ] ) );

  return true;
}

bool MTF::decode( unsigned char* DataIn, unsigned int sizeIn, unsigned char*& DataOut )
{
  unsigned char alphabet[ 256 ];
  for( int i=0; i<256; i++ )
     alphabet[ i ] = i;

  DataOut = new unsigned char[ sizeIn ];
  if( !DataOut )
     return false;

  for( unsigned int i=0; i<sizeIn; i++ )
  {
     DataOut[ i ] = alphabet[ DataIn[ i ] ];
     MoveToFront( alphabet, DataIn[ i ] );
  }

  return true;
}

inline int MTF::GetSymbolIndex( unsigned char* alphabet, unsigned char symbol )
{
  for( int i=0; i<256; i++ )
     if( alphabet[ i ] == symbol )
        return i;

  //ანბანი დაზიანებულია
  return -1;
}

inline void MTF::MoveToFront( unsigned char* alphabet, unsigned char symbolIndex )
{
  unsigned char c = alphabet[ symbolIndex ];
  memcpy( alphabet+1, alphabet, symbolIndex );
  alphabet[ 0 ] = c;
}

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

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 ფუნქცია გვიბრუნებს მეორე კვანძს, დანარჩენ მნიშვნელობებზე ფუნქცია გვიბრუნებს წირის სხვა წერტილებს. გამოდის რომ წირი იწყება პირველი კვანძში დამოკიდებულია საკონტროლო წერტილებზე,თუმცა არ გადის მათზე და სრულდება მეორე კვანძში. მათემატიკურად ნებისმიერ ბეზიეს წირს შეესაბამება პოლინომი რომლის ხარისხიც არის მოცემული წერტილების რაოდენობ...