Datacompressie
Hallo, Linux Nijmegen!
We gaan...
boodschappen doen! 
1 sinaasappel
        
1 sinaasappel
1 sinaasappel
        
1 sinaasappel
1 sinaasappel
1 sinaasappel
        
1 sinaasappel
1 sinaasappel
1 sinaasappel
1 sinaasappel
        
1 sinaasappel
1 sinaasappel
1 sinaasappel
1 sinaasappel
1 sinaasappel
        
1 sinaasappel
1 sinaasappel
1 sinaasappel
1 sinaasappel
1 sinaasappel
1 sinaasappel
Dat kan efficiënter!
6× 1 sinaasappel
Questions! 
       ingepakt - uitgepakt
100 × ––––––––––––––––––––––
            uitgepakt
        
1 sinaasappel
1 sinaasappel
1 sinaasappel
1 sinaasappel
1 sinaasappel
1 sinaasappel
78 karakters 
6× 1 sinaasappel
16 karakters 
        16 karakters - 78 karakters
100 × ––––––––––––––––––––––––––––––
               78 karakters
80% afgevallen
Joris Zwart logo
🛎️

Minder data met behoud van informatie.

mindmap
  root((Datacompressie))
    (Redundantie)
      [Perceptueel]
      [Statistisch]
      [Structureel]
    (Entropie)
    (Lossless)
      [Run-Length Encoding]
      [Lempel–Ziv familie]
        [Sliding window]
        [Woordenboek]
      [Huffman]
        [Frequenties]
        [Prefixvrije codes]
    (Lossy)
      [Perceptuele modellen]
        [Auditief]
        [Visueel]
      [Transforms]
        [DCT]
          [Frequentiedomein]
        [Wavelets]
      [Kwantisatie]
        [Afronden]
        [Bitreductie]
    (Video & Audio)
      [Temporele redundantie]
        [I/P/B-frames]
        [Motion vectors]
      [Audio]
        [Psycho-akoestiek]
        [Bitrate-allocatie]
    (Trade‑offs)
      [Compressieratio]
      [CPU]
      [RAM]
      [Latency]
    (Moderne ontwikkelingen)
      [Edge-compressie]
Lossless vs. lossy

Verliesvrij / verliesrijk

JPEG 100%

JPEG 95%

JPEG 80%

JPEG 50%

JPEG 25%

JPEG 10%

JPEG 5%

JPEG 1%

JPEG trade-off
Quality Size
100% 198,9 kB
95% 37,9 kB
80% 16,7 kB
50% 10,5 kB
25% 6,2 kB
10% 4,4 kB
5% 4,0 kB
1% 3,9 kB
PNG dan?
Vandaag

Lossless - verliesvrij

mindmap
  root((Datacompressie))
    (Redundantie)
      [Statistisch]
      [Structureel]
    (Entropie)
    (Lossless)
      [Run-Length Encoding]
      [Lempel–Ziv familie]
        [Sliding window]
        [Woordenboek]
      [Huffman]
        [Frequenties]
        [Prefixvrije codes]
    (Lossy)
    (Trade‑offs)
      [Compressieratio]
      [CPU]
      [RAM]
      [Latency]
RLE

Run-Length Encoding

⬇ Run-Length Encoding

 

Escape value
Trade‑offs
Supereenvoudige implementatie
Snelle compressie
Snelle decompressie
Ghusselede dtaa
Fun!
([A-Z])\1*/g

Inpakken

(\d+)×([A-Z])

Uitpakken

Toepassingen
BMP, PCX, GIF, JPEG, PNG, Webp (rle, lz, others), Video, Audio, Data, AI modellen
HTTP
LZ

Lempel–Ziv '77

LZ77, LZ78, LZMA, LZW, ...

⬇ Lempel–Ziv

 

Trade‑offs
Generiek!
Tekst
CPU / RAM :-(
Implementatie
Recap
Symbolen, letters, karakters, bytes, sinaasappels...

Compressie = encoding
Decompressie = decoding
Huffman

David A. Huffman, 1952

Lijkt op...
Morse code!
Naieve codering
A ➡  - - - - ·
B ➡  - - - · -
C ➡  - - - · ·
D ➡  - - · - -
E ➡  - - · - ·
        
A ➡  0 0 0 0 1
B ➡  0 0 0 1 0
C ➡  0 0 0 1 1
D ➡  0 0 1 0 0
E ➡  0 0 1 0 1

26 letters ≈4,7 Morse codes per karakter

Efficiënte codering
A ➡  · -
B ➡  - · · ·
C ➡  - · - ·
D ➡  - · ·
E ➡  ·

26 letters ≈3,2 Morse codes per karakter

Nederlands: ≈2,7 Morse codes per karakter

Huffman

Nederlands: ≈2,4 bits per karakter

Trade‑offs
Generiek
Veel dezelfde symbolen :-(
Recap
Algemene trade‑offs
Kosten
vs.
Baten
Transformaties
Omkeerbaar
Delta encoding

⬇ Delta encoding

 

Fun!
decode = a => a.reduce((Σ, Δ, ι, Α) => (Α[ι] = Σ + Δ))
XOR
1 1 1     1 1 1        0 0 0  
1 0 0  ⊕  1 1 1  ––>   0 1 1
1 0 0     1 0 0        0 0 0
PNG filters

none, sub, up, average, paeth

BWT

Burrows–Wheeler transform

^BANANA$

Bron: Wikipedia

Rotaties

^ B A N A N A $
$ ^ B A N A N A
A $ ^ B A N A N
N A $ ^ B A N A
A N A $ ^ B A N
N A N A $ ^ B A
A N A N A $ ^ B
B A N A N A $ ^
Sorteer

A N A N A $ ^ B
A N A $ ^ B A N
A $ ^ B A N A N
B A N A N A $ ^
N A N A $ ^ B A
N A $ ^ B A N A
^ B A N A N A $
$ ^ B A N A N A
Laatste kolom

A N A N A $ ^ B
A N A $ ^ B A N
A $ ^ B A N A N
B A N A N A $ ^
N A N A $ ^ B A
N A $ ^ B A N A
^ B A N A N A $
$ ^ B A N A N A
BNN^AA$A
Omkeerbaar!

Oefening voor thuis

MTF

Move-to-front transform

Iteration Sequence List
bananaaa 1 (abcdefghijklmnopqrstuvwxyz)
bananaaa 1,1 (bacdefghijklmnopqrstuvwxyz)
bananaaa 1,1,13 (abcdefghijklmnopqrstuvwxyz)
bananaaa 1,1,13,1 (nabcdefghijklmopqrstuvwxyz)
bananaaa 1,1,13,1,1 (anbcdefghijklmopqrstuvwxyz)
bananaaa 1,1,13,1,1,1 (nabcdefghijklmopqrstuvwxyz)
bananaaa 1,1,13,1,1,1,0 (anbcdefghijklmopqrstuvwxyz)
bananaaa 1,1,13,1,1,1,0,0 (anbcdefghijklmopqrstuvwxyz)

Oefening voor thuis

Mythes
> Ik heb de compressor gemaakt,
> maar de decompressor is nog buggy.
Recursieve compressie
Jan Sloot
Containers
ZIP
AVI
DOCX
JAR
APK
Etc.
Zelf doen

Niet hier!

Canterbury Corpus
tar + gzip

OF

gzip + tar
QUIZ
De Bijbel
Source code
Foto's
Bouwtekeningen
DNA

ACGT

π
Fun!
💣

42.zip

Recap
Compressie is altijd een trade‑off!
mindmap
  root((Datacompressie))
    (Redundantie)
      [Statistisch]
      [Structureel]
    (Entropie)
    (Lossless)
      [Run-Length Encoding]
      [Lempel–Ziv familie]
        [Sliding window]
        [Woordenboek]
      [Huffman]
        [Frequenties]
        [Prefixvrije codes]
    (Lossy)
    (Trade‑offs)
      [Compressieratio]
      [CPU]
      [RAM]
      [Latency]
joriszwart.nl/compression