Flyt-til-front

Move -to-front ( MTF ) er en  transformation til kodning af data (normalt en strøm af bytes ), designet til at forbedre ydeevnen af ​​entropi-kodning . Hvis det implementeres godt , er det hurtigt nok til at blive inkluderet som et ekstra trin i datakomprimeringsalgoritmer . Den kan også bruges sammen med BWT, Burrows-Wheeler transformationen .

Algoritme

Den grundlæggende idé bag transformationen er at erstatte hvert inputtegn med dets nummer i en speciel stak af nyligt brugte tegn. Sekvenser af identiske tegn vil for eksempel blive erstattet (startende fra det andet tegn) med en sekvens af nuller. Hvis tegnet ikke har optrådt i indtastningssekvensen i lang tid, vil det blive erstattet af et større tal. Transformationen erstatter sekvensen af ​​inputtegn med en sekvens af heltal, hvis der var mange lokale korrelationer i inputdataene, så vil små blandt disse tal, der er bedre komprimerbare ved entropikodning end de originale data, råde.

Algoritmen blev først beskrevet i [1]. Oprindeligt blev algoritmen kaldt "en stak bøger" ("bogstak"). Historien om udviklingen af ​​algoritmen er beskrevet i [2].

Bruges ofte ved konvertering af bytes. Til at begynde med skrives hver mulig byteværdi til listen, i en celle med et tal svarende til byteværdien, dvs. (0, 1, 2, 3, ..., 255). Denne liste ændres under databehandlingen. Det første tegn, der behandles, erstattes af sig selv, hvorefter det element, der svarer til det pågældende tegn, flyttes til listens hoved (forskydning af elementer fra 0 til deres position med 1 til højre). Efterfølgende tegn kodes af nummeret på det element, der indeholder deres værdi. Efter at hvert tegn er kodet, forfremmes disse elementer også til toppen af ​​listen.

Eksempel

Overvej driften af ​​algoritmen på alfabetet af engelske bogstaver (vi nummererer dem fra nul). Lad os tage ordet

b - er skrevet i element nummer 1. Efter at have flyttet b til toppen af ​​listen , bliver b nul, og a bliver 1 .

Det vil blive konverteret til

Algoritmer, der bruger MTF

• bzip2

Litteratur

1. Ryabko, B. Ya. Datakomprimering ved hjælp af en "bogstak" , Problems of Information Transmission, 1980, v. 16:(4), s. 265-269.
2. Ryabko, B. Ya.; Horspool, R. Nigel; Cormack, Gordon V. Kommentarer til: "A locally adaptive data compression scheme" af JL Bentley, DD Sleator, RE Tarjan og VK Wei. Comm. ACM 30 (1987), nr. 9, 792-794.