Compression

?

?# Keyboard Navigation

## Global Keys

[, < / ], > Jump to previous / next episode

W, K, P / S, J, N Jump to previous / next timestamp

t / T Toggle theatre / SUPERtheatre mode

V Revert filter to original state Y Select link (requires manual Ctrl-c)## Menu toggling

q Quotes
r References
f Filter
y Link
c Credits
## In-Menu and Index Controls

## Quotes and References Menus and Index

Enter Jump to timestamp

## Quotes, References and Credits Menus

o Open URL (in new tab)
## Filter Menu

x, Space Toggle category and focus next

X, ShiftSpace Toggle category and focus previous

v Invert topics / media as per focus## Filter and Link Menus

z Toggle filter / linking mode
## Credits Menu

Enter Open URL (in new tab)

W, K, P / S, J, N Jump to previous / next timestamp

t / T Toggle theatre / SUPERtheatre mode

V Revert filter to original state Y Select link (requires manual Ctrl-c)

a

w

s

s

d

h
j
k
l

←

↑

↓

↓

→

Esc Close menu / unfocus timestamp

X, ShiftSpace Toggle category and focus previous

v Invert topics / media as per focus

•

Welcome to 2016

•

0:04 : Introducing Jeff and Fabian from RAD Game Tools

0:04 : Introducing Jeff and Fabian from RAD Game Tools

0:04 : Introducing Jeff and Fabian from RAD Game Tools

1:36 : RAD's first product, pack.exe

1:36 : RAD's first product, pack.exe

1:36 : RAD's first product, pack.exe

3:10 : Compressing known data (i.e. fudging the numbers)

3:10 : Compressing known data (i.e. fudging the numbers)

3:10 : Compressing known data (i.e. fudging the numbers)

3:25 : Compression zero-point energy

3:25 : Compression zero-point energy

3:25 : Compression zero-point energy

3:57 : Perpetual motion machines

3:57 : Perpetual motion machines

3:57 : Perpetual motion machines

4:10 : Recursive compression

4:10 : Recursive compression

4:10 : Recursive compression

4:17 : More on compressing known data (i.e. fudging the numbers)

4:17 : More on compressing known data (i.e. fudging the numbers)

4:17 : More on compressing known data (i.e. fudging the numbers)

5:18 : Fudged compression discussions

5:18 : Fudged compression discussions

5:18 : Fudged compression discussions

5:28 : Preventing data leakage and cheating

5:28 : Preventing data leakage and cheating

5:28 : Preventing data leakage and cheating

6:00 : Pure form of compression (the compressor size is included in the measurement)

6:00 : Pure form of compression (the compressor size is included in the measurement)

6:00 : Pure form of compression (the compressor size is included in the measurement)

6:21 : Cheating compression by exploiting channels, e.g. NTFS file streams, UDP packet length and zero-padding

6:21 : Cheating compression by exploiting channels, e.g. NTFS file streams, UDP packet length and zero-padding

8:27 : Cheating, but back to the background

8:27 : Cheating, but back to the background

8:27 : Cheating, but back to the background

8:56 : RAD Game Tools' origins as a hardware and software company, and data compression as pure and enthralling

8:56 : RAD Game Tools' origins as a hardware and software company, and data compression as pure and enthralling

10:42 : How did you, Fabian, get interested in compression?

10:42 : How did you, Fabian, get interested in compression?

10:42 : How did you, Fabian, get interested in compression?

10:56 : Discovering theories of data compression and Huffman coding^{1}

10:56 : Discovering theories of data compression and Huffman coding^{1}

10:56 : Discovering theories of data compression and Huffman coding^{1}

11:44 : What is the way to think about the compression family?

11:44 : What is the way to think about the compression family?

11:44 : What is the way to think about the compression family?

13:02 : What compression is about: Modelling (or Prediction, from David Stafford) and Residual Cleanup

13:02 : What compression is about: Modelling (or Prediction, from David Stafford) and Residual Cleanup

15:23 : Modelling the possible input before fixing up to match the actual input

15:23 : Modelling the possible input before fixing up to match the actual input

15:23 : Modelling the possible input before fixing up to match the actual input

16:05 : Multiple prediction passes

16:05 : Multiple prediction passes

16:05 : Multiple prediction passes

16:33 : Lossy vs Lossless compression?

16:33 : Lossy vs Lossless compression?

16:33 : Lossy vs Lossless compression?

17:12 : Lossy compression as an early-stopping scheme

17:12 : Lossy compression as an early-stopping scheme

17:12 : Lossy compression as an early-stopping scheme

20:35 : Defining error

20:35 : Defining error

20:35 : Defining error

20:49 : Networking errors, and lossless as general-purpose

20:49 : Networking errors, and lossless as general-purpose

20:49 : Networking errors, and lossless as general-purpose

22:21 : What is your mental model of compression?

22:21 : What is your mental model of compression?

22:21 : What is your mental model of compression?

22:35 : Compression as modelling

22:35 : Compression as modelling

22:35 : Compression as modelling

23:31 : Measuring compression performance

23:31 : Measuring compression performance

23:31 : Measuring compression performance

24:17 : Undecidable minimum file size

24:17 : Undecidable minimum file size

24:17 : Undecidable minimum file size

24:39 : You're asking "how small can this set of things get?"

24:39 : You're asking "how small can this set of things get?"

24:39 : You're asking "how small can this set of things get?"

25:04 : Deterministic but impractical optimal LZ parse

25:04 : Deterministic but impractical optimal LZ parse

25:04 : Deterministic but impractical optimal LZ parse

26:12 : "How small in general?" is impossible to answer

26:12 : "How small in general?" is impossible to answer

26:12 : "How small in general?" is impossible to answer

26:41 : Encoding the compressor in the general space, and Kolmogorov complexity^{2}

26:41 : Encoding the compressor in the general space, and Kolmogorov complexity^{2}

26:41 : Encoding the compressor in the general space, and Kolmogorov complexity^{2}

28:19 : Feature trade-offs

28:19 : Feature trade-offs

28:19 : Feature trade-offs

29:26 : The decoder is the description, and compressor complexity may prevent optimal solutions

29:26 : The decoder is the description, and compressor complexity may prevent optimal solutions

29:26 : The decoder is the description, and compressor complexity may prevent optimal solutions

30:12 : The decoder is the specification, e.g. MPEG-1 and MPEG-2

30:12 : The decoder is the specification, e.g. MPEG-1 and MPEG-2

30:12 : The decoder is the specification, e.g. MPEG-1 and MPEG-2

32:03 : File size variance, and optimisable routines

32:03 : File size variance, and optimisable routines

32:03 : File size variance, and optimisable routines

33:41 : Bink 2 format dictated by Xbox 360

33:41 : Bink 2 format dictated by Xbox 360

33:41 : Bink 2 format dictated by Xbox 360

33:57 : No sponsors

33:57 : No sponsors

33:57 : No sponsors

34:14 : Modelling vs Statistical?

34:14 : Modelling vs Statistical?

34:14 : Modelling vs Statistical?

34:48 : Modelling vs Statistical

34:48 : Modelling vs Statistical

34:48 : Modelling vs Statistical

35:43 : Internalising the idea of prediction

35:43 : Internalising the idea of prediction

35:43 : Internalising the idea of prediction

37:11 : Modelling examples: 1) Similar adjacent pixels in JPEG images

37:11 : Modelling examples: 1) Similar adjacent pixels in JPEG images

37:11 : Modelling examples: 1) Similar adjacent pixels in JPEG images

39:00 : Modelling examples: 2) Dictionary methods in text compression, e.g. LZ77 and LZ78^{3}

39:00 : Modelling examples: 2) Dictionary methods in text compression, e.g. LZ77 and LZ78^{3}

39:00 : Modelling examples: 2) Dictionary methods in text compression, e.g. LZ77 and LZ78^{3}

39:54 : LZ77^{4}and LZ78^{5} was a watershed moment

39:54 : LZ77^{4}and LZ78^{5} was a watershed moment

39:54 : LZ77^{4}and LZ78^{5} was a watershed moment

40:26 : Statistical compression with stochastic modelling, e.g. Huffman^{6}

40:26 : Statistical compression with stochastic modelling, e.g. Huffman^{6}

40:26 : Statistical compression with stochastic modelling, e.g. Huffman^{6}

42:12 : How would you define the split between LZ and Huffman?

42:12 : How would you define the split between LZ and Huffman?

42:12 : How would you define the split between LZ and Huffman?

42:41 : LZ understandability using a Markov model^{7}

42:41 : LZ understandability using a Markov model^{7}

42:41 : LZ understandability using a Markov model^{7}

44:15 : Prediction vs encoding example: 0-255 gradient image

44:15 : Prediction vs encoding example: 0-255 gradient image

44:15 : Prediction vs encoding example: 0-255 gradient image

45:15 : The predictor tries to regularise the data?

45:15 : The predictor tries to regularise the data?

45:15 : The predictor tries to regularise the data?

46:18 : Predicted structure, and random residual

46:18 : Predicted structure, and random residual

46:18 : Predicted structure, and random residual

47:35 : Separating prediction and cleanup

47:35 : Separating prediction and cleanup

47:35 : Separating prediction and cleanup

48:46 : Science vs art?

48:46 : Science vs art?

48:46 : Science vs art?

48:56 : Science vs art

48:56 : Science vs art

48:56 : Science vs art

50:16 : Charles is in Hawaii^{8}

50:16 : Charles is in Hawaii^{8}

50:16 : Charles is in Hawaii^{8}

51:23 : Lumpy compressors, e.g. LZ4

51:23 : Lumpy compressors, e.g. LZ4

51:23 : Lumpy compressors, e.g. LZ4

52:20 : What do you mean by bit packing?

52:20 : What do you mean by bit packing?

52:20 : What do you mean by bit packing?

52:37 : LZ77 symbol decode, in terms of bit packing

52:37 : LZ77 symbol decode, in terms of bit packing

52:37 : LZ77 symbol decode, in terms of bit packing

53:50 : Decode efficiency

53:50 : Decode efficiency

53:50 : Decode efficiency

54:30 : Hybrid command data stream

54:30 : Hybrid command data stream

54:30 : Hybrid command data stream

55:00 : Rich Geldreich thinks of compression as specifying a virtual machine

55:00 : Rich Geldreich thinks of compression as specifying a virtual machine

55:00 : Rich Geldreich thinks of compression as specifying a virtual machine

55:38 : Caring about the executable size

55:38 : Caring about the executable size

55:38 : Caring about the executable size

55:56 : Compile optimisation

55:56 : Compile optimisation

55:56 : Compile optimisation

56:29 : Improvements found by Charles in Oodle's parse

56:29 : Improvements found by Charles in Oodle's parse

56:29 : Improvements found by Charles in Oodle's parse

57:17 : LZ parse

57:17 : LZ parse

57:17 : LZ parse

59:11 : Speed choices

59:11 : Speed choices

59:11 : Speed choices

59:35 : Having multiple ways to say the same thing is an underestimation of the probability

59:35 : Having multiple ways to say the same thing is an underestimation of the probability

59:35 : Having multiple ways to say the same thing is an underestimation of the probability

1:00:00 : What do you mean by getting the probabilities right?

1:00:00 : What do you mean by getting the probabilities right?

1:00:00 : What do you mean by getting the probabilities right?

1:00:24 : A Markov model^{9} has no ambiguity, and multiple ways to same the same thing is wasteful

1:00:24 : A Markov model^{9} has no ambiguity, and multiple ways to same the same thing is wasteful

1:00:24 : A Markov model^{9} has no ambiguity, and multiple ways to same the same thing is wasteful

1:02:38 : Useful redundancy

1:02:38 : Useful redundancy

1:02:38 : Useful redundancy

1:04:52 : Optimal parse

1:04:52 : Optimal parse

1:04:52 : Optimal parse

1:05:30 : Incremental compression

1:05:30 : Incremental compression

1:05:30 : Incremental compression

1:06:02 : So there is no such thing as search for optimal parse if the compressor is perfect?

1:06:02 : So there is no such thing as search for optimal parse if the compressor is perfect?

1:06:02 : So there is no such thing as search for optimal parse if the compressor is perfect?

1:06:26 : High-end statistical symmetrical compression vs asymmetric LZ^{10}

1:06:26 : High-end statistical symmetrical compression vs asymmetric LZ^{10}

1:06:26 : High-end statistical symmetrical compression vs asymmetric LZ^{10}

1:08:14 : So arithmetic encoding is a solved problem?

1:08:14 : So arithmetic encoding is a solved problem?

1:08:14 : So arithmetic encoding is a solved problem?

1:08:45 : Arithmetic encoding is mathematical

1:08:45 : Arithmetic encoding is mathematical

1:08:45 : Arithmetic encoding is mathematical

1:09:50 : Art vs Science

1:09:50 : Art vs Science

1:09:50 : Art vs Science

1:10:50 : Evidence of improvement potential, e.g. prepending a byte to an input file

1:10:50 : Evidence of improvement potential, e.g. prepending a byte to an input file

1:10:50 : Evidence of improvement potential, e.g. prepending a byte to an input file

1:12:43 : So searches can get stuck in local maxima?

1:12:43 : So searches can get stuck in local maxima?

1:12:43 : So searches can get stuck in local maxima?

1:13:24 : Bugs in complex but correct systems

1:13:24 : Bugs in complex but correct systems

1:13:24 : Bugs in complex but correct systems

1:14:15 : Do you gauge how close you're getting to optimal size?

1:14:15 : Do you gauge how close you're getting to optimal size?

1:14:15 : Do you gauge how close you're getting to optimal size?

1:14:40 : Oodle^{11} compression levels

1:14:40 : Oodle^{11} compression levels

1:14:40 : Oodle^{11} compression levels

1:15:52 : Compression decoder optimisation

1:15:52 : Compression decoder optimisation

1:15:52 : Compression decoder optimisation

1:17:10 : Instruction-level parallelism

1:17:10 : Instruction-level parallelism

1:17:10 : Instruction-level parallelism

1:17:51 : Port blockage

1:17:51 : Port blockage

1:17:51 : Port blockage

1:18:22 : Instruction-level parallelism, and dependency

🖌

1:18:22 : Instruction-level parallelism, and dependency

🖌

1:18:22 : Instruction-level parallelism, and dependency

🖌

1:21:03 : Huffman serial dependency

🖌

1:21:03 : Huffman serial dependency

🖌

1:21:03 : Huffman serial dependency

🖌

1:23:52 : Increasing instruction-level parallelism by doing multiple decodes concurrently

1:23:52 : Increasing instruction-level parallelism by doing multiple decodes concurrently

1:23:52 : Increasing instruction-level parallelism by doing multiple decodes concurrently

1:24:16 : Unrolling a loop in data-order

1:24:16 : Unrolling a loop in data-order

1:24:16 : Unrolling a loop in data-order

1:24:31 : Six streams for six dependent instructions, plus SIMD

🖌

1:24:31 : Six streams for six dependent instructions, plus SIMD

🖌

1:24:31 : Six streams for six dependent instructions, plus SIMD

🖌

1:27:22 : Tweaked modern compressors

1:27:22 : Tweaked modern compressors

1:27:22 : Tweaked modern compressors

1:27:30 : Thank you, Jeff and Fabian

1:27:30 : Thank you, Jeff and Fabian

1:27:30 : Thank you, Jeff and Fabian

⏬

Next: 'Compression Followup'

⏬