Algoritm BSTW
Algoritmen BSTW är en datakomprimeringsalgoritm , uppkallad efter dess designers Bentley, Sleator , Tarjan och Wei 1986. BSTW är en ordboksbaserad algoritm som använder en flytta-till-front-transform för att hålla nyligen sedda ordboksposter längst fram i ordboken. Ordboksreferenser kodas sedan med någon av ett antal kodningsmetoder, vanligtvis Elias deltakodning eller Elias gammakodning .
Denna algoritm publicerades i följande artikel: "A Locally Adaptive Data Compression Scheme", Communications of the ACM, 1986, volym 29 nummer 4, s. 320–330.
En relaterad idé publicerades i Ryabko, B. Ya. "Datakomprimering med hjälp av en bokstapel", Problems of Information Transmission, 1980, v. 16: (4), s. 265–269.
Det ursprungliga namnet på denna kod är "book stack". Historien om upptäckten av bokstapeln (eller flytta-till-front )-koden kan hittas här: 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.
externa länkar