Körningslängdskodning - Run-length encoding

Inte att förväxla med körlängd begränsad .

Run-length encoding ( RLE ) är en form av förlustfri datakomprimering där datakörningar (sekvenser där samma datavärde förekommer i många på varandra följande dataelement) lagras som ett enda datavärde och -räkning, snarare än som den ursprungliga körningen . Detta är mest effektivt på data som innehåller många sådana körningar, till exempel enkla grafiska bilder som ikoner, linjeritningar, Conways Game of Life och animationer. För filer som inte har många körningar kan RLE öka filstorleken.

RLE kan också användas för att referera till ett tidigt grafikfilformat som stöds av CompuServe för att komprimera svartvita bilder, men ersattes i stor utsträckning av deras senare Graphics Interchange Format (GIF). RLE hänvisar också till ett lite använt bildformat i Windows 3.x , med tillägget rle, som är en körningslängdskodad bitmapp, som används för att komprimera startskärmen för Windows 3.x.

Exempel

Tänk på en skärm som innehåller vanlig svart text på en solid vit bakgrund, över hypotetisk skanningslinje, den kan återges enligt följande:

12W1B12W3B24W1B14W2W

Detta kan tolkas som en sekvens av tolv Ws, ett B, tolv Ws, tre Bs, etc., och representerar de ursprungliga 67 tecknen på bara 18. Medan det faktiska formatet som används för lagring av bilder i allmänhet är binärt snarare än ASCII -tecken så här förblir principen densamma. Även binära datafiler kan komprimeras med denna metod; filformatspecifikationer dikterar ofta upprepade byte i filer som stoppningsutrymme. Men nyare komprimeringsmetoder som DEFLATE använder ofta LZ77 -baserade algoritmer, en generalisering av körningslängdskodning som kan dra fördel av körningar av teckensträngar (t.ex. BWWBWWBWWBWW).

Körningslängdskodning kan uttryckas på flera sätt för att rymma dataegenskaper samt ytterligare komprimeringsalgoritmer. Till exempel kodar en populär metod körlängder för körningar med endast två eller flera tecken, med hjälp av en "Escape" -symbol för att identifiera körningar, eller använder själva tecknet som Escape, så att varje tecken visas två gånger anger det en körning. I det föregående exemplet skulle detta ge följande:

WW12BWW12BB3WW24BWW14

Detta skulle tolkas som en körning på tolv W, en B, en körning på tolv Ws, en körning på tre B, etc. I data där körningar är mindre frekventa kan detta avsevärt förbättra komprimeringshastigheten.

En annan fråga är tillämpningen av ytterligare komprimeringsalgoritmer. Även med körningarna extraherade kan frekvenserna för olika tecken vara stora, vilket möjliggör ytterligare komprimering; om körningslängderna skrivs i filen på de platser där körningarna inträffade, avbryter förekomsten av dessa nummer det normala flödet och gör det svårare att komprimera. För att övervinna detta separerar vissa run-length encoders data- och escape-symbolerna från körlängderna, så att de två kan hanteras oberoende. För exempeldata skulle detta resultera i två utgångar, strängen " WWBWWBBWWBWW" och siffrorna ( 12,12,3,24,14).

Historia och applikationer

Run-length encoding (RLE) -scheman användes vid överföring av analoga tv-signaler redan 1967. År 1983 patenterades run-length encoding av Hitachi . RLE är särskilt väl lämpad för paletten baserade bitmappsbilder som datorikoner , och var en populär bildkomprimeringsmetod på tidiga onlinetjänster såsom CompuServe före tillkomsten av mer sofistikerade format som GIF . Det fungerar inte bra på bilder med kontinuerlig ton, till exempel fotografier, även om JPEG använder det på de koefficienter som återstår efter omvandling och kvantisering av bildblock.

Vanliga format för kodad data med körlängd inkluderar Truevision TGA , PackBits , PCX och ILBM . Den Internationella teleunionen beskriver också en standard för att koda följdlängd-färg för telefaxmaskiner, så kallade T.45. Standarden, som kombineras med andra tekniker till modifierad Huffman -kodning , är relativt effektiv eftersom de flesta faxade dokument i allmänhet är vita utrymmen, med enstaka avbrott i svart.

Se även

Referenser

externa länkar