Kørselslængdekodning ( eng. r un- l ength e ncoding , RLE ) eller gentagelseskodning er en datakomprimeringsalgoritme , der erstatter gentagne tegn (serier) med ét tegn og antallet af dets gentagelser. En serie er en sekvens bestående af flere identiske karakterer. Ved kodning (pakning, komprimering) erstattes en streng af identiske tegn, der udgør en serie, af en streng, der indeholder selve det gentagende tegn og antallet af dets gentagelser.
Overvej et billede, der indeholder sort tekst på en solid hvid baggrund. Når du læser pixels på et sådant billede linje for linje, vil der være en række hvide (baggrund) og sorte (bogstaver) pixels . Et bogstav Bangiver en sort pixel, og et bogstav angiver W en hvid pixel. Overvej en vilkårlig billedstreng med en længde på 51 tegn:
WWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWLad os tælle antallet af tegn:
I alt fundet 5 episoder. Lad os erstatte serien med antallet af gentagelser og selve den gentagende karakter:
9W3B24W1B14WResultatet var en sekvens på 12 tegn. Den originale sekvens bestod af 51 tegn. Dataene blev komprimeret 51/12≈4,25 gange.
Lad os tage en streng bestående af et stort antal ikke-gentagende tegn:
ABCABCABCDDDFFFFFFEfter komprimering med RLE-metoden vil en sådan linje se sådan ud:
1A1B1C1A1B1C1A1B1C3D6FDen originale streng består af 18 tegn, og den komprimerede streng består af 22. Datastørrelsen er øget med 22/18≈1,22 gange.
For at datastørrelsen ikke øges efter komprimering, opdeles alfabetet, hvori længderne af kørslerne er registreret, i to dele (normalt lige store). For eksempel kan alfabetet af heltal opdeles i to dele: positive og negative tal. Positive tal bruges til at registrere antallet af gentagelser af et tegn, og negative tal bruges til at registrere antallet af ulige tegn efter hinanden.
Lad os tælle tegnene under hensyntagen til ovenstående:
Den komprimerede streng vil blive skrevet som:
-9ABCABCABC3D6FDen originale streng består af 18 tegn, og den komprimerede streng består af 15. Datastørrelsen er faldet med 18/15=1,2 gange.
Antag, at implementeringen af RLE-metoden til at registrere længden af serien (for at tælle antallet af tegn) bruger en heltalstypevariabel med tegnet " ". I en sådan variabel kan du skrive tal fra -128 til og med 127. Hvad hvis seriens længde er 128 tegn eller mere? I dette tilfælde er serien opdelt i dele, således at længden af delen ikke overstiger 127 tegn. For eksempel vil en kørsel på 256 "A"-tegn være kodet med følgende streng (256=127+127+2): signed char
127A127A2AAt skrive RLE-algoritmen i et eller andet programmeringssprog, under hensyntagen til disse begrænsninger, er ikke-trivielt.
Selvfølgelig fungerer den kodning, der bruges til at gemme billeder, på binære data og ikke på ASCII-tegn , som i de diskuterede eksempler, men princippet forbliver det samme.
Det er klart, at en sådan kodning er effektiv for data, der indeholder et stort antal serier, for eksempel for simple grafiske billeder såsom ikoner og grafik. Denne kodning er dog ikke velegnet til jævne tonale billeder, såsom fotografier.
Almindelige formater til pakning af data med RLE inkluderer PackBits , PCX og ILBM .
Vilkårlige binære datafiler kan komprimeres ved kørselslængdekodning , fordi filformatspecifikationer ofte inkluderer gentagne bytes i datajusteringsområdet. Moderne komprimeringssystemer (såsom Deflate ) bruger dog oftere LZ77 - baserede algoritmer , som er en generalisering af kørselslængdekodningsmetoden og opererer på tegnsekvenser af formen "BWWBWWBWWBWW".
Lyddata, der har lange på hinanden følgende byte-kørsler (såsom lydeksempler af lav kvalitet ) kan komprimeres med RLE efter Delta-kodning er blevet anvendt på dem .
| Kompressionsmetoder _ | |||||||
|---|---|---|---|---|---|---|---|
| Teori |
| ||||||
| Tabsfri |
| ||||||
| Lyd |
| ||||||
| Billeder |
| ||||||
| Video |
| ||||||