Data Compression. RunLength Encoding. Data Compression. Huffman Coding. Lempel-Ziv Compression, страница 2

Sender

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

_

y

t

h

e

n

_

a

n

d

_

t

h

e

r

e

_

t

h

e

o

r

i

s

e

d

_

t

h

a

t

_

t

h

i

s

_

w

a

s

_

t

h

u

s

_

t

h

e

y

R L L’

25

31

Data Compression

Lempel-Ziv Compression

LEMPEL-ZIV COMPRESSION

Receiver

Sender

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

_

t

h

e

n

_

a

n

d

_

t

h

e

r

e

_

t

h

e

o

r

i

s

e

d

_

t

h

a

t

_

t

h

i

s

_

w

a

s

_

t

h

u

s

t

t

h

e

y

_

R L L’

27

32

Data Compression

Lempel-Ziv Compression

LEMPEL-ZIV COMPRESSION

Receiver

Sender

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

th

e

n

_

a

n

d

_

t

h

e

r

e

_

t

h

e

o

r

i

s

e

d

_

t

h

a

t

_

t

h

i

s

_

w

a

s

_

t

h

u

s

e

t

h

e

y

_

R L L’

28

33

Data Compression

Lempel-Ziv Compression

LEMPEL-ZIV COMPRESSION

Receiver

Sender

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

ey 30 en 34

►

Several further steps ensue…

e

n

_

a

n

d

_

t

h

e

r

e

_

t

h

e

o

r

i

s

e

d

_

t

h

a

t

_

t

h

i

s

_

w

a

s

_

t

h

u

s

t

h

e

y

_

e

n

R L L’

5

34

Data Compression

Lempel-Ziv Compression

LEMPEL-ZIV COMPRESSION

Receiver

Sender

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

ey 30 en 34 e_ 43

►

nd 38

►

►

re 42

re 42

►

►

th 28 the 33

►

_th 40

_th 40

_t 32 _a 36

_t 32 _a 36

►

►

►

►

_th

_th

e

e

o

r

i

s

e

d

_

t

h

a

t

_

t

h

i

s

_

w

a

s

_

t

h

u

s

_

a

n

d

_

t

h

e

r

e

e

o

r

i

s

e

d

_

t

h

a

t

_

t

h

i

s

_

w

a

s

_

t

h

u

s

t

h

e

y

_

e

n

R L L’

40

43

Data Compression

Lempel-Ziv Compression

LEMPEL-ZIV COMPRESSION

Receiver

Sender

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

A special case

(well, nearly)

<stringa><stringa>

<not char1 of stringa>

s

spins

pine

f

f

e

c

t

R L L’

89

92

Data Compression

Lempel-Ziv Compression

LEMPEL-ZIV COMPRESSION

Receiver

Sender

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

A special case

(well, nearly)

<stringa><stringa>

<not char1 of stringa>

spine

e

f

f

e

c

t

R L L’

89

93

Data Compression

Lempel-Ziv Compression

LEMPEL-ZIV COMPRESSION

Receiver

Sender

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

A special case

(well, nearly)

<stringa><stringa>

<not char1 of stringa>

e

f

f

f

e

c

t

e

R L L’

5

94

Data Compression

Lempel-Ziv Compression

LEMPEL-ZIV COMPRESSION

Receiver

Sender

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

A special case

(yes, really!)

<stringa><stringa>

<char1 of stringa>

s

spins

pins

p

l

i

t

t

i

n

g

R L L’

89

92

Data Compression

We are standing up

Lempel-Ziv Compression

LEMPEL-ZIV COMPRESSION

Receiver

Sender

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27