liblzg

liblzg
Stabil frisättning	1.0.10 / 29 november 2018 ; för 4 år sedan
Förvar	github .com /mbitsnbites /liblzg ;
Skrivet i	C , Pascal , Lua , Assembly language , JavaScript
Operativ system	Cross-plattform
Typ	Datakomprimering
Licens	zlib licens
Hemsida	liblzg .bitsnbites .eu

liblzg är ett komprimeringsbibliotek för att utföra förlustfri datakomprimering . Den implementerar en algoritm som är en variant av LZ77- algoritmen, kallad LZG-algoritmen, med huvudfokus på att tillhandahålla en mycket enkel och snabb avkodningsmetod. En av nyckelfunktionerna i algoritmen är att den inte kräver något minne under dekompression. Programvarubiblioteket är fri programvara, distribuerad under zlib-licensen .

Algoritm

Om en dubblettserie av bytes (en upprepad sträng) upptäcks i den okomprimerade dataströmmen, infogas en bakåtreferens, som istället länkar till den tidigare platsen för den identiska strängen. En kodad matchning med en tidigare sträng består av en längd (3–128 byte) och ett avstånd (1–526 341 byte). Komprimeringsnivån kan styras genom att ange det maximala avståndet för vilket duplicerade strängar kommer att sökas (detta är storleken på det skjutbara fönstret ).

Dataformat

Dataformatet består av en rubrik, följt av den komprimerade datan. Rubriken innehåller en identifierare och hushållsinformation, såsom komprimerade och dekomprimerade datastorlekar och en 32-bitars kontrollsumma (en variant av Fletchers kontrollsumma ).

Den komprimerade datan börjar med fyra byte, som identifierar fyra unika 8-bitars markörsymboler ( m1 , m2 , m3 och m4 ). Dessa används för att separera bokstavliga databytes från olika former av längd-avståndsparkodningar .

Varje symbol som inte är en markörbyte anses vara en bokstavlig byte och kommer att kopieras som den är till den dekomprimerade databufferten. Emellertid, om avkodaren stöter på någon av de fyra markörbyten, kommer den att avkoda ett längd-avståndspar som används som en tillbakareferens till tidigare dekomprimerade data.

Markörbyten tolkas enligt följande (% anger ett binärt tal):

Allmän kopia (m1)

m1 representerar den mest allmänna formen av en kopieringsoperation, och den upptar fyra byte i den komprimerade dataströmmen:

m1	%ooolllll	%mmmmmmmm	%nnnnnnnn

...där längd= DEKODELENGTH(%lllll+2) och offset= %ooommmmmmmnnnnnnnn + 2056 .

Medium kopia (m2)

m2 är en kortare form av en kopieringsoperation, som upptar tre byte i den komprimerade dataströmmen:

m2	%ooolllll	%mmmmmmmm

...där längd= DEKODELENGTH(%lllll+2) och offset= %ooommmmmmmmm + 8 .

Kort kopia (m3)

m3 kräver bara två byte och används för korta längder, nära markören:

m3	%lloooooo

...där längd= %ll+3 och offset= %oooooo + 8 .

Nästan kopia (m4)

m4 kräver bara två byte och används för närliggande kopior (inklusive RLE , när offset är 1):

m4	%ooolllll

...där längd= DEKODELENGTH(%lllll+2) och offset= %ooo + 1 .

Bokstavlig kopia

Som ett specialfall, om någon av markörsymbolerna följs av en nollbyte (0), skrivs själva markörsymbolen till den dekomprimerade bufferten.

Icke-linjär längdkodning

Funktionen DECODELENGTH implementerar en icke-linjär mappning av ett tal i intervallet 3-33 till ett tal i intervallet 3-128, enligt följande tabell:

Längdparameter, L (3-33)	Avkodad längd (3-128)
33	128
32	72
31	48
30	35
<30	L

Datatillväxt i värsta fall

Eftersom markörsymbolerna väljs som de fyra minst vanliga symbolerna i den okomprimerade dataströmmen (med en sannolikhet på högst ${\tfrac {1}{256}}$ vardera), och en enda förekomst av en markör symbolen kräver två byte för att koda, den komprimerade datan kan växa med högst ${\tfrac {4}{256}}$ < 1,6 % jämfört med den dekomprimerade datan (i värsta fall).

Liblzg-biblioteket kompenserar för detta genom att använda ett vanligt 1:1 kopieringsläge om kodaren identifierar att den komprimerade datan kommer att vara större än den ursprungliga okomprimerade datan. Därför är den maximala datatillväxten i praktiken 0 % (plus storleken på datahuvudet, som är 16 byte).

Genomföranden

Både komprimerings- och dekompressionsalgoritmerna är implementerade i ett bibliotek med öppen källkod, skrivet i programmeringsspråket C. Det finns också flera alternativa implementeringar av dekompressionsalgoritmen tillgängliga (till exempel i JavaScript och 8-bitars assemblerspråk ).

Se även

externa länkar

liblzg hemsida