Körlängdskodning ( eng. r un- l ength e ncoding , RLE ) eller repetitionskodning är en datakomprimeringsalgoritm som ersätter upprepade tecken (serier) med ett tecken och antalet repetitioner. En serie är en sekvens som består av flera identiska karaktärer. Vid kodning (packning, komprimering) ersätts en sträng med identiska tecken som utgör en serie med en sträng som innehåller själva det upprepande tecknet och antalet repetitioner.
Överväg en bild som innehåller svart text på en solid vit bakgrund. När du läser pixlarna i en sådan bild rad för rad kommer det att finnas en serie vita (bakgrund) och svarta (bokstäver) pixlar . En bokstav Bbetecknar en svart pixel och en bokstav betecknar W en vit pixel. Tänk på en godtycklig bildsträng med en längd på 51 tecken:
WWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWLåt oss räkna antalet tecken:
Totalt hittade 5 avsnitt. Låt oss byta ut serien med antalet repetitioner och själva den upprepande karaktären:
9W3B24W1B14WResultatet blev en sekvens på 12 tecken. Den ursprungliga sekvensen bestod av 51 tecken. Data komprimerades 51/12≈4,25 gånger.
Låt oss ta en sträng som består av ett stort antal icke-repeterande tecken:
ABCABCABCDDDFFFFFFEfter komprimering med RLE-metoden kommer en sådan linje att se ut så här:
1A1B1C1A1B1C1A1B1C3D6FDen ursprungliga strängen består av 18 tecken och den komprimerade strängen består av 22. Datastorleken har ökat med 22/18≈1,22 gånger.
För att datastorleken inte ska öka efter komprimering delas alfabetet där längderna på körningarna registreras i två delar (vanligtvis lika). Till exempel kan alfabetet av heltal delas upp i två delar: positiva och negativa tal. Positiva siffror används för att registrera antalet repetitioner av ett tecken, och negativa siffror används för att registrera antalet ojämna tecken som följer efter varandra.
Låt oss räkna tecknen, med hänsyn till ovanstående:
Den komprimerade strängen kommer att skrivas som:
-9ABCABCABC3D6FDen ursprungliga strängen består av 18 tecken och den komprimerade strängen består av 15. Datastorleken har minskat med 18/15=1,2 gånger.
Antag att implementeringen av RLE-metoden för att registrera längden på serien (för att räkna antalet tecken) använder en heltalsvariabel med tecknet " ". I en sådan variabel kan du skriva tal från -128 till och med 127. Vad händer om seriens längd är 128 tecken eller mer? I det här fallet är serien uppdelad i delar så att längden på delen inte överstiger 127 tecken. Till exempel skulle en körning av 256 "A"-tecken kodas med följande sträng (256=127+127+2): signed char
127A127A2AAtt skriva RLE-algoritmen på något programmeringsspråk, med hänsyn till dessa begränsningar, är inte trivialt.
Naturligtvis fungerar kodningen som används för att lagra bilder på binär data och inte på ASCII-tecken , som i exemplen som diskuteras, men principen förblir densamma.
Uppenbarligen är sådan kodning effektiv för data som innehåller ett stort antal serier, till exempel för enkla grafiska bilder såsom ikoner och grafik. Denna kodning är dock inte väl lämpad för jämna tonbilder som fotografier.
Vanliga format för packning av data med RLE inkluderar PackBits , PCX och ILBM .
Godtyckliga binära datafiler kan komprimeras genom körlängdskodning , eftersom filformatspecifikationer ofta inkluderar upprepade bytes i datajusteringsområdet. Moderna komprimeringssystem (som Deflate ) använder dock oftare LZ77 - baserade algoritmer , som är en generalisering av run-length-kodningsmetoden och fungerar på teckensekvenser av formen "BWWBWWBWWBWW".
Ljuddata som har långa på varandra följande bytekörningar (såsom ljudsampel av låg kvalitet ) kan komprimeras med RLE efter att Delta-kodning har tillämpats på den .
| Kompressionsmetoder _ | |||||||
|---|---|---|---|---|---|---|---|
| Teori |
| ||||||
| Förlust mindre |
| ||||||
| Audio |
| ||||||
| Bilder |
| ||||||
| Video |
| ||||||