Datakomprimering

Från Wikipedia, den fria encyklopedin
Hoppa till navigation Hoppa till sökning

Datakomprimeringen (troligen lånöversatt och germaniserad från engelska ' datakomprimering ' ) - även (ytterligare germaniserad) känd som datakomprimering [1] - är en process där mängden digital data komprimeras eller reduceras . Detta minskar lagringsutrymmet som krävs och den tid det tar att överföra data. Inom kommunikationsteknik är komprimering av meddelanden från en källa av en avsändare känd som källkodning . [2] [3]

Vid komprimering av data försöker man alltid ta bort överflödig information. För detta ändamål omvandlas data till en representation med vilken all - eller åtminstone det mesta av informationen kan presenteras i en kortare form. Denna process utförs av en kodare och processen är känd som komprimering eller komprimering . Det omvända är känt som dekomprimering eller dekomprimering .

Man talar om förlustfri komprimering, förlustfri kodning eller redundansminskning när exakt originaldata kan återställas från de komprimerade data. Detta är till exempel nödvändigt vid komprimering av körbara programfiler .

Med förlustfri komprimering eller irrelevansminskning kan originaldata vanligtvis inte längre exakt återvinnas från de komprimerade data, det vill säga en del av informationen går förlorad; algoritmerna försöker utelämna endast "oviktig" information så långt som möjligt. Sådana metoder används ofta för bild- eller videokomprimering och ljuddatakomprimering .

Rent generellt

Datakomprimering sker i de flesta långdistansöverföringar av digital data idag. Det hjälper till att spara resurser vid överföring eller lagring av data genom att omvandla den till en form som - beroende på applikationen - är så minimal som möjligt. Endast data som är redundanta i någon form kan komprimeras utan förlust . Om det inte finns någon redundans - till exempel vid helt slumpmässiga data - är förlustfri komprimering i princip omöjlig på grund av Kolmogorov -komplexiteten . Dovecote -principen förbjuder också att filer komprimeras utan förlust. Å andra sidan är förlustfri komprimering alltid möjlig: En algoritm ordnar data enligt hur viktiga de är och kasserar sedan de "oviktiga". I listan över hur viktiga vilka komponenter är kan fler och fler kasseras genom att flytta "behållströskeln" i enlighet därmed.

När det gäller datakomprimering krävs beräkningsinsatser på både avsändaren och mottagarens sida för att komprimera eller återställa data. Beräkningsinsatsen är dock mycket olika för olika komprimeringsmetoder. Deflate och LZO , till exempel, är mycket snabba i komprimering och dekomprimering, medan LZMA till exempel uppnår särskilt omfattande komprimering - och därmed minsta möjliga mängd data - med stor ansträngning, medan komprimerad data kan konverteras tillbaka till sin ursprungliga form väldigt snabbt. Beroende på tillämpningsområdet tvingar detta till ett annat val av komprimeringsmetod. Komprimeringsmetoder är därför antingen optimerade för dataflöde , energikrav eller datareduktion, och syftet med komprimering är därför inte alltid så kompakt som möjligt. Skillnaden blir tydlig i dessa exempel:

  • Om video- eller ljudinspelningar sänds live måste komprimering och återställning utföras så snabbt som möjligt. Förlust av kvalitet är motiverat om den maximala (möjliga) överföringshastigheten följs. Detta gäller till exempel telefonsamtal, där samtalspartnern ofta fortfarande kan förstås även om ljudkvaliteten är dålig.
  • Om en enda fil laddas ner av otaliga användare är en långsam men mycket kraftfull komprimeringsalgoritm värd. Den minskade bandbredden under överföringen gör enkelt upp den tid som krävs för komprimering.
  • Vid säkerhetskopiering och arkivering av data måste en algoritm användas som också kan användas inom en avlägsen framtid. I det här fallet är det bara populära, beprövade algoritmer som ifrågasätts, som ibland inte har de bästa komprimeringsfrekvenserna.
  • Datatypen är också relevant för valet av komprimeringsmetod. Till exempel har de två komprimeringsprogrammen gzip och bzip2 som användsUnix-liknande operativsystem egenskaperna att gzip endast komprimerar block på 32 000 byte, medan bzip2 har en blockstorlek på 900 000 byte. Redundanta data komprimeras endast inom dessa block.

Ibland omvandlas data till en annan representation före komprimering. Detta gör det möjligt för vissa metoder att senare komprimera data mer effektivt. Detta förbehandlingssteg kallas förkodning . Ett exempel på detta är Burrows-Wheeler-transformationen och Move to front i bzip2 . [4]

Datakomprimering överlappar delvis med informationsteori och artificiell intelligens , och inom området förlust av datakomprimering även med perceptuell psykologi (se nedan). Informationsteorin påverkas eftersom filstorleken för en datamängd som är så komprimerad som möjligt direkt indikerar informationsinnehållet i denna datamängd.

Om en komprimeringsalgoritm kan lära sig under vilka teckensträngen "ABC" följs av en "D" behöver "D" inte sparas i den komprimerade filen - när den ursprungliga filen återställs vet algoritmen var ett "D" är "ska infogas. Även om en sådan komprimeringsalgoritm ännu inte har tagits i bruk, är olika komprimeringsmetoder som använder artificiella neurala nätverk och maskininlärning under utveckling. [5]

Gränser för komprimerbarhet

Förlorad kompression

Som beskrivits ovan är förlustfri komprimering alltid möjlig - tröskeln för vad som anses vara "redundant" kan ökas tills endast 1 bit återstår. Gränserna är flytande och bestäms av applikationen: Till exempel "Huset är stort" kan komprimeras till "Huset är stort"; om läsaren vill veta "vilka fastigheter har huset?" går det inte längre att skilja om det är "grått", "grönt" eller "stort". Om läsaren vill veta "sa något om ett hus?", Kan detta fortfarande besvaras jakande.

Vid förlust av bildkomprimering förloras / blir detaljerna alltmer suddiga, och till sist "suddas" allt ut till en yta med en enhetlig färg; en ljudinspelning blir vanligtvis tråkig och otydlig, efter största möjliga komprimering skulle den bara ha en enkel sinuston med de flesta algoritmer.

Förlustfri komprimering

Vid förlustfri komprimering gäller mycket snävare gränser, eftersom det måste säkerställas att den komprimerade filen kan omvandlas tillbaka till den ursprungliga filen.

Kolmogorow -komplexiteten behandlar minsta möjliga "manual" som är nödvändig för att återställa originaldata från komprimerade data. Till exempel kan talet "100000000000000000000000000000000000" komprimeras mycket enkelt: "Skriv 1 och sedan 35 nollor", vilket är en komprimering från 36 till 29 tecken. Vilket antal siffror som helst efter decimalpunkten för cirkelnumret Pi kan också komprimeras med dess beräkningsregel - varigenom komprimeringsalgoritmen då måste erkänna att det är talet Pi. Det bör noteras att med komprimerade filer måste återställningsalgoritmen också läggas till i filstorleken, eftersom alla komprimerade filer utan en sådan algoritm är värdelösa. Ovanstående nummer kan också komprimeras med "10 ^ 35" eller "1e35", i vilket fall läsaren måste vara medveten om återställningsmetoden, nämligen effektnotationen . Men om en teckensträng inte har någon igenkännbar struktur / särdrag är komprimering inte möjlig - instruktionerna bör innehålla oförändrade originaldata.

En annan anledning till att vissa data är inkomprimerbara är den så kallade duvcote-principen : Om det finns färre häckningsplatser för duvor än det finns duvor i duvcotan , måste två eller flera duvor oundvikligen dela en häckningsplats. En av 2 n möjliga bitar av information kan lagras på ett n-bitars lagringsutrymme, och följaktligen kan bara en av hälften så mycket information som möjligt lagras på ett lagringsutrymme som är en bit mindre: 16 bitar → 2 16 = 65536 möjligt information, 15 bitar → 2 15 = 32768 möjlig information. Om vi ​​antar att varje möjlig fil skulle kunna reduceras med en bit, skulle detta, enligt duvhalsprincipen, innebära att varje lagringsutrymme måste innehålla två olika komprimerade filer samtidigt. Eftersom det måste finnas en reversibel, otvetydig tilldelning mellan komprimerade och okomprimerade filer i förlustfri komprimering, är detta förbjudet.

Om dovecote -principen inte gällde, och om det fanns en algoritm som kunde komprimera vilken fil som helst med minst en bit, kunde denna tillämpas rekursivt på den komprimerade filen - all information kunde reduceras till 0 bitar. I praktiken kan data som redan har komprimeras bara komprimeras igen om en inte 100% effektiv algoritm användes i föregående körning, som ännu inte helt har tagit bort redundansen (t.ex. visas en mycket stor fil full av nollor två gånger med gzip komprimerad).

Slutsatsen från dessa två fakta är att rent slumpmässig data (troligtvis) är okomprimerbar (eftersom den mestadels är ostrukturerad) och att mycket, men inte alla, data kan komprimeras. Två priser, $ 100 för framgångsrik komprimering av en miljon slumpmässiga siffror [6] [7] och $ 5000 för framgångsrik komprimering av en fil av vilken längd som helst som prissponsorn Mike Goldman skapat, [8] har inte betalats ut hittills.

Förlustfri komprimering

Med förlustfri komprimering kan originaldata exakt återställas från komprimerade data. Ingen information går förlorad i processen. I huvudsak använder förlustfria komprimeringsmetoder redundans av data, som också kallas redundansreduktion .

Den teoretiska grunden är informationsteori (relaterad till algoritmisk informationsteori ). På grund av informationsinnehållet anger det ett minsta antal bitar som krävs för att koda en symbol. Förlustlösa komprimeringsmetoder försöker koda meddelanden på ett sådant sätt att de närmar sig deras entropinära som möjligt.

text

Texter, förutsatt att de består av bokstäver eller lagras som teckensträngar , och därmed inte som en bild ( rastergrafik , vanligtvis en bildfil efter att en bok har skannats ), tar relativt lite lagringsutrymme . Detta kan reduceras till 20% till 10% av det utrymme som ursprungligen krävdes av en metod för förlustfri komprimering.

Exempel:

 Källtext: ÄN EN SMÅ BIDRAG ÄR EN BIDRAG
Kodad text: OCKSÅ EN LITEN BIDRAG ÄR / 2/4

Här insåg man att orden EIN och CONTRIBUTION visas två gånger, vilket indikerar att dessa motsvarar de som var tidigare. Vid närmare granskning kan EIN i SMALL då också kodas i enlighet därmed.

Ordboksmetod

Tokenbaserad komprimering är relaterad. Ofta återkommande sökord ersätts av förkortningar, tokens .

 Källtext: Skriv ut "Hej"; Skriv ut "här"
Kodningstext: 3F "Hej"; 3F "Här"

För tilldelning av tokens till de faktiska orden måste antingen en extern ordbok vara tillgänglig eller så måste den vara synlig / inkluderad i den komprimerade filen.

Körningslängdskodning (RLE)

Med RLE, tysk körningslängdskodning , sparas identiska textkomponenter som visas efter varandra bara en gång - med antalet repetitioner. Här upprepas "10 grader" tre gånger:

 Källtext: De senaste dagarna var temperaturen 10 grader, 10 grader, 10 grader och sedan 14 grader.
Kodad text: De senaste dagarna var temperaturen / 3/10 grader, / och sedan 14 grader.

Burrows-Wheeler-transformationen är en reversibel operation som omvandlar en given text på ett sådant sätt att samma bokstäver visas efter varandra så ofta som möjligt. Data kan sedan komprimeras med RLE.

Entropikodning

Förfarande för så kallad entropikodning :

Den välkända Morse-koden fungerar på en liknande princip och fungerar som ett bra exempel: Frekventa bokstäver på engelska (t.ex. E = . ) Sparas som korta koder, sällan som långa koder (t.ex. Q = _ _. _ ).

Som ett exempel, en källtext med en längd av 66 tecken (datamängd 462 bitar med 7 bitar per tecken, se ASCII ):

 OM FLYGA BAKOM FLYG, FLYG FLY FLYG EFTER.

En mycket enkel, men inte särskilt effektiv entropikodning består av att sortera alla delar av ett meddelande (se tabell; "_" står för mellanslag) efter deras frekvens och numrera dem med binära nummer:

Textdel ... ... ersätts med ...
_ATT FLYGA 1
OM_ 10
_TILL. 11
BAKOM 100
, 101

Texten komprimerad med denna ordbok är

 10100 1 1 1 101 1 1 1 11

och kräver 50 bitar i binär kodning, eftersom resultatet innehåller tre olika tecken (0, 1 och separatorn “”), dvs 2 bitar per tecken. Separatorerna är nödvändiga här eftersom den här koden inte är prefixfri . Den prefixfria Huffman-koden, det vill säga följande ordlista,

Textdel ... ... ersätts med ...
_ATT FLYGA 1
OM_ 011
_TILL. 010
BAKOM 001
, 000

är mer effektivt, eftersom det leder direkt till ett binärt resultat med en längd på 18 bitar:

 011001111000111010

I båda fallen måste dock ordlistan också sparas i den komprimerade filen - annars kan inte källtexten rekonstrueras.

Program filer

När det gäller programfiler är det kritiskt att de är i sitt ursprungliga tillstånd igen efter att de har dekomprimerats. Annars skulle ett felfritt eller korrekt utförande vara osannolikt. Komprimerade programfiler är vanligtvis själva körbara filer. De består av en rutin som dekomprimerar programkoden och sedan kör den. Som ett resultat är komprimeringen av programmet helt 'transparent' för användaren (han märker det inte).

Applikationsexempel är UPX och Upack .

Förlorad kompression

Vid förlustfri komprimering tas irrelevant information bort, vilket också kallas irrelevansreduktion . En del av informationen från originaldata går förlorad, så att originalet inte längre kan rekonstrueras från de komprimerade data.

Det behövs en modell som avgör vilken del av informationen som är tillgänglig för mottagaren. Förlorad komprimering används mest för bild-, video- och ljudöverföring. Mänsklig uppfattning används som modell där. Ett populärt exempel är MP3 -ljudformatet, som tar bort frekvensmönster som människor inte kan höra eller höra dåligt.

Den teoretiska grunden är hastighetsförvrängningsteorin . Den beskriver den minsta dataöverföringshastighet som krävs för att överföra information med en viss kvalitet.

Bilder, videor och ljudinspelningar

För högkomprimerade bilder i JPEG -format framträder 8 × 8 pixelrutor som komprimeringsartefakter . Över originalstorleken, under ett förstorat avsnitt
Jämförelse av komprimeringsartefakter i JPEG -format med det förlustfria PNG -formatet

Ljud, bild och film är användningsområden för komprimering utan förlust. Annars skulle de ofta enorma mängderna data vara mycket svåra att hantera. Registreringsenheterna begränsar redan datavolymen. Minskningen av lagrade data baseras på människors fysiologiska uppfattningsegenskaper . Komprimeringen av algoritmer använder vanligtvis konvertering av signalkurvor från avsökningssignaler till en frekvensrepresentation.

I mänsklig akustisk uppfattning uppfattas inte längre frekvenser över cirka 20 kHz och kan redan sänkas i inspelningssystemet. Befintliga, tysta sekundära toner i en ljudblandning är också svåra att uppfatta om mycket höga toner inträffar exakt samtidigt, så att de ohörbara frekvenskomponenterna kan tas bort av datakomprimeringssystemet (se psykoakustik ) utan att detta uppfattas som irriterande av lyssnaren skulle. När digitaliserade akustiska händelser (musik, tal, ljud) reduceras till värden på cirka 192 kbit / s (som med många nedladdningar från Internet) kan människor hitta små eller inga kvalitetsskillnader jämfört med okomprimerat källmaterial (t.ex. en CD ).

I mänsklig optisk uppfattning är färger mindre upplösta än förändringar i ljusstyrka, från vilka YUV-422-reduktionen, som redan är känd i analog färg-tv , härleds. Kanter, å andra sidan, är mer signifikanta och det finns en biologisk kontrastförbättring ( Mach -ränder ). Med måttlig lågpassfiltrering för färgreduktion, till exempel med JPEG- algoritmen baserad på DCT-transformation eller den nyare JPEG2000- algoritmen baserad på wavelet-transformation , kan datamängden vanligtvis reduceras till 10% eller mindre av den ursprungliga datamängden utan betydande kvalitetsminskningar.

Rörliga bilder (filmer) består av successiva individuella bilder. Det första tillvägagångssättet var att komprimera varje bild individuellt med hjälp av JPeg -algoritmen. Det resulterande formatet är Motion JPEG (motsvarar MPEG-1 om det bara innehåller I-ramar). De mycket högre komprimeringshastigheterna nuförtiden kan endast uppnås om likheten hos närliggande bilder (ramar) beaktas under kodningen. För att göra detta bryts bilden upp i mindre rutor (typiska storlekar ligger mellan 4 × 4 och 16 × 16 pixlar) och liknande rutor söks i bilder som redan har överförts och använts som mall. Besparingen beror på att istället för hela bildinnehållet måste endast skillnaderna mellan rutorna, som är liknande i sig, överföras. Dessutom används ändringarna från den föregående till den aktuella bilden för att härleda i vilken riktning bildinnehållet har förskjutits och hur långt; endast en förskjutningsvektor lagras sedan för motsvarande område.

Komprimeringsartefakter

Komprimeringsartefakter är signalstörningar som orsakas av komprimering utan förlust.

Ansökan inom kommunikationsteknik

Användning av käll- , kanal- och linjekodning för att överföra en signal

Vid överföring av data reduceras ofta mängden data som ska överföras genom komprimering. I ett sådant fall talar man om källkodning . [2] [3] Källkodningen används ofta tillsammans med kanalkodning och linjekodning , men bör inte förväxlas med dessa: Medan källkodning minskar överflödig (redundant) information från en datakälla, har kanalkodning som uppgift att överföra överföring eller för att kunna känna igen och korrigera minnesfel under dataöverföringen. Linjekodningen, å andra sidan, gör en spektral anpassning av signalen till kraven för överföringskanalen.

Tidstabell för komprimeringsalgoritmerna

Den hundraåriga stenografin kan ses som datakomprimering, vilket ger handskriften högsta möjliga datahastighet

1833–1865 Utveckling av morsekoden, som översätter frekventa bokstäver till korta tecken och sällsynta bokstäver till längre, vilket föreslår idén om entropikodning

1883 David Forsyth , schackspelare och journalist, publicerar en metod med vilken schackfigurernas position registreras på ett platsbesparande sätt med löpningskodning → Forsyth-Edwards-notation

1949 Informationsteori , Claude Shannon

1949 Shannon-Fano-kodning

1952 Huffman -kodning , statisk

1964 Begreppet Kolmogorov -komplexitet

1975 Heltalskodningsschema, Elias

1977 Lempel-Ziv-metod LZ77

1978 Lempel-Ziv-förfarande LZ78

1979 områdeskodning (en implementering av aritmetisk kodning )

1982Lempel-Ziv-Storer-Szymanski (LZSS)

1984 Lempel-Ziv-Welch algoritm (LZW)

1985 Apostolico, Fraenkel, Fibonacci kodning

1986 Gå framåt , (Bentley et al., Ryabko)

1991 Reduced Offset Lempel Ziv (ROLZ, även LZRW4, Lempel Ziv Ross Williams)

1994 Burrows-Wheeler transformation ( bzip2 )

1995 zlib , gratis standardbibliotek för Deflate

1996 Lempel-Ziv-Oberhumer algoritm (LZO), mycket snabb komprimering

1997 Sequitur

1998 Lempel-Ziv-Markow-algoritmen (LZMA)

2006 Hutter Prize för bästa datakomprimering

2009 PAQ , högsta kompressionshastighet på bekostnad av mycket långa drifttider; Användning av ett neuralt nätverk (nu ZPAQ )

2011 Snabb , snabb kodare från Google

2011 LZ4 , mycket snabb pulsgivare

2013 zopfli , förbättrad tömningsgivare

2015 Brotli , stark kompression

Välkända metoder för källkodning

förlorande båda möjliga förlust mindre
AAC ( MPEG )
Aiff
ALS ( MPEG )
Apple Lossless
ATRAC
DjVu
Dolby Digital
DTS
FLAC
Monkey's audio
G.729
GIF
HuffYUV
JPEG
JPEG 2000
LA
MJPEG
MP2 ( MPEG )
MP3 ( MPEG )
MPEG-1
MPEG-2
MPEG-4 (se H.264 , Xvid , DivX )
Musepaket
PGF
PNG
TGA
TIFF
Vorbis ( Ogg )
WavPack
WebP
WMA
WMV
bilder Audio Video

Dataöverföring

  • MNP-1 till MNP-10 (Microcom Networking Protocol)
Felkorrigering och datakomprimeringsprotokoll från Microcom Inc. för modem , en mångårig standard. Har förbättrats med:
  • V.42bis - datakomprimeringsprotokoll för ITU -T

biologi

Sensoriska uppfattningar filtreras, vilket också är en typ av komprimering, närmare bestämt en förlustig komprimering, eftersom endast aktuell information uppfattas. Saknade föremål byts omedvetet ut vid behov. Till exempel kan mänskliga ögon bara se tydligt i ett litet område ( fovea centralis ); utanför detta smala synfält ersätts saknad information omedvetet av mönster. Det mänskliga ögat kan också uppfatta skillnader i ljusstyrka mycket bättre än skillnader i färgton - YCbCr -färgmodellen som används i JPEG -bilder använder detta faktum och sparar färgvärdet med mycket mindre precision.

Även vid lyssning ersätts svaga eller saknade signaler omedvetet, vilket algoritmer som MPEG ( MP3 ) eller Vorbis använder sig av.

Se även

webb-länkar

Wikibooks: Bok om datakomprimering - lärande och läromedel
Wiktionary: datakomprimering - förklaringar av betydelser, ordets ursprung, synonymer, översättningar

Individuella bevis

  1. datakomprimering - Duden , Bibliographisches Institut ; 2016
  2. a b Stefan Brunthaler: Källa och linjekodning. (PDF; 528 kB) I: TH Wildau . 2018, åtkomst den 12 augusti 2018 (föreläsningskommunikationsteknik i telematik SS2018 ).
  3. a b Peter Maluck, Jürg Scheidegger: Source Coding - Guided Discovery Learning. (PDF; 776 kB) I: SwissEduc . 24 augusti 2009, tillgänglig 12 augusti 2018 ( Communication Technology Seminar).
  4. a b Tilo Strutz: Bilddatakomprimering - grunder, kodning, vågor, JPEG, MPEG, H.264, HEVC . Springer Vieweg , Wiesbaden 2017, ISBN 978-3-8348-1427-2 , s.   421
  5. ^ Matthew V. Mahoney: Snabb textkomprimering med neurala nätverk . I: AAAI (red.): Proceedings of the Thirteenth International Florida Artificial Intelligence Research Society Conference . 2000, ISBN 1-57735-113-4 , sid.   5 .
  6. Mark Nelson: The Million Random Digit Challenge Revisited. 20 juni 2006, åtkomst 12 augusti 2018 .
  7. ^ Mark Nelson: Den bestående utmaningen att komprimera slumpmässiga data. DrDobbs.com , 6 november 2012, öppnade 12 augusti 2018 .
  8. Patrick Craig:The $5000 Compression Challenge. Abgerufen am 12. August 2018 (englisch).