Flytta-till-front

Move -to-front ( MTF ) är en  transformation för kodning av data (vanligtvis en ström av byte ) utformad för att förbättra prestandan för entropikodning . Om den implementeras väl är den tillräckligt snabb för att inkluderas som ett extra steg i datakomprimeringsalgoritmer . Den kan också användas tillsammans med BWT, Burrows-Wheeler-transformen .

Algoritm

Grundidén bakom omvandlingen är att ersätta varje inmatat tecken med dess nummer i en speciell stapel med nyligen använda tecken. Sekvenser av identiska tecken, till exempel, kommer att ersättas (med början från det andra tecknet) med en sekvens av nollor. Om tecknet inte har förekommit i inmatningssekvensen på länge kommer det att ersättas med ett större nummer. Transformationen ersätter sekvensen av indatatecken med en sekvens av heltal, om det fanns många lokala korrelationer i indata, så kommer små, bland dessa siffror, bättre komprimerbara genom entropikodning än originaldata att råda.

Algoritmen beskrevs först i [1]. Ursprungligen kallades algoritmen "en stack of books" ("book stack"). Historien om utvecklingen av algoritmen beskrivs i [2].

Används ofta vid konvertering av byte. Initialt skrivs varje möjligt bytevärde till listan, i en cell med ett nummer lika med bytevärdet, dvs. (0, 1, 2, 3, ..., 255). Denna lista ändras under databehandlingen. Det första tecknet som bearbetas ersätts av sig självt, varefter elementet som motsvarar det tecknet flyttas till listans huvud (skiftar element från 0 till sin position med 1 åt höger). Efterföljande tecken kodas av numret på elementet som innehåller deras värde. Efter att varje tecken har kodats flyttas även dessa element upp till listans huvud.

Exempel

Tänk på hur algoritmen fungerar på alfabetet av engelska bokstäver (vi numrerar dem från noll). Låt oss ta ordet

b - skrivs i element nummer 1. Efter att ha flyttat b till toppen av listan kommer b att bli noll och a blir 1:a

Det kommer att konverteras till

Algoritmer som använder MTF

• bzip2

Litteratur

1. Ryabko, B. Ya. Datakomprimering med hjälp av en "bokstack" , Problems of Information Transmission, 1980, v. 16:(4), sid. 265–269.
2. Ryabko, B. Ya.; Horspool, R. Nigel; Cormack, Gordon V. Kommentarer till: "A locally adaptive data compression scheme" av JL Bentley, DD Sleator, RE Tarjan och VK Wei. Comm. ACM 30 (1987), nr. 9, 792-794.