Förlustfri kompression

Förlustfri datakomprimering är en  klass av datakomprimeringsalgoritmer (video, ljud, grafik, dokument presenterade i digital form, program i programmeringsspråk och maskinkoder och många andra typer av data), när man använder vilka kodade data kan rekonstrueras entydigt till närmaste bit , pixel , voxel , etc. I det här fallet återställs originaldata helt från det komprimerade tillståndet. Denna typ av komprimering skiljer sig fundamentalt från datakomprimering med förlust . För varje typ av digital information finns det som regel optimala förlustfria komprimeringsalgoritmer.

Förlustfri datakomprimering används i många applikationer. Till exempel används den i alla filarkiverare . Det används också som en komponent vid förlustkompression.

Förlustfri komprimering används när identiteten av den komprimerade data till originalet är viktig. Ett vanligt exempel är körbara filer och källkod. Vissa grafiska filformat (som PNG ) använder endast förlustfri komprimering, medan andra ( TIFF , FLIF eller GIF ) kan använda både förlustfri och förlustfri komprimering.

Kompression och kombinatorik

Teoremet är lätt att bevisa.

För alla N > 0 finns det ingen förlustfri komprimeringsalgoritm som:

  1. En fil som inte är längre än N byte behåller antingen samma längd eller minskar den.
  2. Minskar en fil med längd högst N med minst en byte.

Bevis. Utan förlust av generalitet kan vi anta att filen A med längden exakt N har minskat . Låt oss beteckna alfabetet som . Låt oss överväga en uppsättning . I denna uppsättning källfiler finns det inte fler än . Därför är dekompressionsfunktionen tvetydig , en motsägelse. Teoremet har bevisats.

Denna sats kastar dock inte det minsta en skugga över förlustfri kompression. Faktum är att vilken komprimeringsalgoritm som helst kan modifieras så att den ökar storleken med högst 1 bit: om algoritmen har minskat filen skriver vi "1", sedan den komprimerade sekvensen, om den har ökat, skriver vi " 0", sedan den ursprungliga.

Så inkompressibla fragment kommer inte att leda till okontrollerad "bloat" av arkivet. "Verkliga" filer med längden N är mycket mindre än (de säger att data har låg informationsentropi ) - till exempel är det osannolikt att bokstavskombinationen "blyg" kommer att förekomma i en meningsfull text, och i digitaliserat ljud kan nivån inte hoppa från 0 till 100 %. På grund av specialiseringen av algoritmer för en viss typ av data (text, grafik, ljud etc.) är det dessutom möjligt att uppnå en hög grad av komprimering: till exempel komprimerar universella algoritmer som används i arkivering ljud med ca. tredje (1,5 gånger), medan FLAC  är 2,5 gånger. De flesta specialiserade algoritmer är till liten användning för "främmande" typer av filer: till exempel är ljuddata dåligt komprimerade av en algoritm som är utformad för texter.

Förlustfri komprimeringsmetod

I allmänna termer är innebörden av förlustfri komprimering följande: något mönster finns i originaldata och, med hänsyn till detta mönster, genereras en andra sekvens som fullständigt beskriver den ursprungliga. Till exempel, för att koda binära sekvenser med många nollor och få ettor, kan vi använda följande substitution:

00 → 0 01 → 10 10 → 110 11 → 111

I det här fallet sexton bitar

00 01 00 00 11 10 00 00

kommer att konverteras till tretton bitar

0 10 0 0 111 110 0 0

En sådan substitution är en prefixkod , det vill säga den har följande funktion: om vi skriver en komprimerad sträng utan mellanslag kan vi fortfarande lägga mellanslag i den - och därför återställa den ursprungliga sekvensen. Den mest kända prefixkoden är Huffman-koden .

De flesta förlustfria komprimeringsalgoritmer fungerar i två steg: den första genererar en statistisk modell för inkommande data, den andra bitmappar den inkommande datan och använder modellen för att producera "sannolikhet" (det vill säga ofta förekommande) data, som används oftare än "osannolika" data. .

Statistiska algoritmmodeller för text (eller textbaserade binära data som körbara filer) inkluderar:

Kodningsalgoritmer genom generering av bitsekvenser:

Förlustfria komprimeringsmetoder

Se hela listan i Kategori:Datakomprimering

Multipurpose

Ljudkomprimering

Grafikkomprimering

Videokomprimering

Textkomprimering

Exempel på algoritmer

Exempel på format och deras implementeringar

Se även

Anteckningar

  1. ↑ TIFF v6-specifikation (nedlänk) . Datum för åtkomst: 18 december 2010. Arkiverad från originalet den 3 juli 2012. 

Länkar

 Kompressionsmetoder _
Teori
Information
Enheter
Förlust mindre
Entropikompression
Ordboksmetoder
Övrig
Audio
Teori
Metoder
Övrig
Bilder
Villkor
Metoder
Övrig
Video
Villkor
Metoder
Övrig