Mutare-în față

Move -to-front ( MTF ) este o  transformare pentru codificarea datelor (de obicei un flux de octeți ) concepută pentru a îmbunătăți performanța codificării entropiei . Dacă este implementat bine, este suficient de rapid pentru a fi inclus ca pas suplimentar în algoritmii de comprimare a datelor . Poate fi folosit și împreună cu BWT, transformarea Burrows-Wheeler .

Algoritm

Ideea de bază din spatele transformării este înlocuirea fiecărui caracter de intrare cu numărul său într-o stivă specială de caractere utilizate recent. Secvențele de caractere identice, de exemplu, vor fi înlocuite (începând cu al doilea caracter) cu o secvență de zerouri. Dacă caracterul nu a apărut în secvența de introducere de mult timp, acesta va fi înlocuit cu un număr mai mare. Transformarea înlocuiește secvența de caractere de intrare cu o secvență de numere întregi, dacă au existat multe corelații locale în datele de intrare, atunci între aceste numere vor prevala cele mai mici, mai bine compresibile prin codificare entropică decât datele originale.

Algoritmul a fost descris pentru prima dată în [1]. Inițial, algoritmul a fost numit „o stivă de cărți” („stiva de cărți”). Istoria dezvoltării algoritmului este descrisă în [2].

Folosit adesea la conversia octeților. Inițial, fiecare valoare posibilă de octet este scrisă în listă, într-o celulă cu un număr egal cu valoarea octetului, adică. (0, 1, 2, 3, ..., 255). Această listă se modifică în timpul procesării datelor. Primul caracter procesat este înlocuit cu el însuși, după care elementul corespunzător acelui caracter este mutat în capul listei (deplasând elementele de la 0 la poziția lor cu 1 la dreapta). Caracterele ulterioare sunt codificate după numărul elementului care conține valoarea lor. După ce fiecare caracter este codificat, aceste elemente sunt, de asemenea, promovate la capul listei.

Exemplu

Luați în considerare funcționarea algoritmului pe alfabetul literelor engleze (le numerotăm de la zero). Să luăm cuvântul

b - este scris în elementul numărul 1. După mutarea b în capul listei , b va deveni zero, iar a va deveni primul

Acesta va fi convertit în

Algoritmi care folosesc MTF

• bzip2

Literatură

1. Ryabko, B. Ya. Comprimarea datelor prin intermediul unei „stive de cărți” , Probleme de transmitere a informațiilor, 1980, v. 16:(4), pp. 265–269.
2. Ryabko, B. Ya.; Horspool, R. Nigel; Cormack, Gordon V. Comentarii la: „A locally adaptive data compression scheme” de JL Bentley, DD Sleator, RE Tarjan și VK Wei. Comm. ACM 30 (1987), nr. 9, 792-794.