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

Move-To-Front Transform

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

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

1. სიმბოლოების შემავალი მიმდევრობიდან ამოვაგდებთ პირველ ელემენტს, ვპოულობთ მისი მნიშვნელობის მქონე ელემენტს შესაძლო მნიშვნელობათა მიმდევრობაში, მის მიმდინარე ინდექსს ვწერთ გამომავალი მიმდევრობის ბოლოში.
2. შესაძლო მნიშვნელობების სიიდან ამოვაგდებთ ნაპოვნ ელემენტს და გადავიტანთ ამავე სიის თავში.

ქვემოთ მოცემულ ცხრილში ნაჩვენებია შემავალი, გამომავალი და შესაზძლო მნიშვნელობების მიმდევრობები ალგორითმის მუშაობის პროცესში სადაც ვახდენთ "bananaaa" სიმბოლოების მიმდევრობის ტრანსფორმაციას.

შემავალი	გამომავალი	შესაძლო მნიშვნელობების სია
bananaaa	1	abcdefghijklmnopqrstuvwxyz
ananaaa	1,1	bacdefghijklmnopqrstuvwxyz
nanaaa	1,1,13	abcdefghijklmnopqrstuvwxyz
anaaa	1,1,13,1	nabcdefghijklmopqrstuvwxyz
naaa	1,1,13,1,1	anbcdefghijklmopqrstuvwxyz
aaa	1,1,13,1,1,1	nabcdefghijklmopqrstuvwxyz
aa	1,1,13,1,1,1,0	anbcdefghijklmopqrstuvwxyz
a	1,1,13,1,1,1,0,0	anbcdefghijklmopqrstuvwxyz
Final	1,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;
}

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