FilesExpand file tree

 master

/

PpmCompress.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

107 lines (92 loc) · 3.75 KB

 master

/

PpmCompress.java

Copy path

Top

File metadata and controls

• Code
• Blame

107 lines (92 loc) · 3.75 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

/*

* Reference arithmetic coding

* Copyright (c) Project Nayuki

*

* https://www.nayuki.io/page/reference-arithmetic-coding

* https://github.com/nayuki/Reference-arithmetic-coding

*/

import java.io.BufferedInputStream;

import java.io.BufferedOutputStream;

import java.io.File;

import java.io.FileInputStream;

import java.io.FileOutputStream;

import java.io.IOException;

import java.io.InputStream;

import java.util.Arrays;

/**

* Compression application using prediction by partial matching (PPM) with arithmetic coding.

* <p>Usage: java PpmCompress InputFile OutputFile</p>

* <p>Then use the corresponding "PpmDecompress" application to recreate the original input file.</p>

* <p>Note that both the compressor and decompressor need to use the same PPM context modeling logic.

* The PPM algorithm can be thought of as a powerful generalization of adaptive arithmetic coding.</p>

*/

public final class PpmCompress {

// Must be at least -1 and match PpmDecompress. Warning: Exponential memory usage at O(257^n).

private static final int MODEL_ORDER = 3;

public static void main(String[] args) throws IOException {

// Handle command line arguments

if (args.length != 2) {

System.err.println("Usage: java PpmCompress InputFile OutputFile");

System.exit(1);

return;

}

File inputFile = new File(args[0]);

File outputFile = new File(args[1]);

// Perform file compression

try (InputStream in = new BufferedInputStream(new FileInputStream(inputFile));

BitOutputStream out = new BitOutputStream(new BufferedOutputStream(new FileOutputStream(outputFile)))) {

compress(in, out);

}

}

// To allow unit testing, this method is package-private instead of private.

static void compress(InputStream in, BitOutputStream out) throws IOException {

// Set up encoder and model. In this PPM model, symbol 256 represents EOF;

// its frequency is 1 in the order -1 context but its frequency

// is 0 in all other contexts (which have non-negative order).

ArithmeticEncoder enc = new ArithmeticEncoder(32, out);

PpmModel model = new PpmModel(MODEL_ORDER, 257, 256);

int[] history = new int[0];

while (true) {

// Read and encode one byte

int symbol = in.read();

if (symbol == -1)

break;

encodeSymbol(model, history, symbol, enc);

model.incrementContexts(history, symbol);

if (model.modelOrder >= 1) {

// Prepend current symbol, dropping oldest symbol if necessary

if (history.length < model.modelOrder)

history = Arrays.copyOf(history, history.length + 1);

System.arraycopy(history, 0, history, 1, history.length - 1);

history[0] = symbol;

}

}

encodeSymbol(model, history, 256, enc); // EOF

enc.finish(); // Flush remaining code bits

}

private static void encodeSymbol(PpmModel model, int[] history, int symbol, ArithmeticEncoder enc) throws IOException {

// Try to use highest order context that exists based on the history suffix, such

// that the next symbol has non-zero frequency. When symbol 256 is produced at a context

// at any non-negative order, it means "escape to the next lower order with non-empty

// context". When symbol 256 is produced at the order -1 context, it means "EOF".

outer:

for (int order = history.length; order >= 0; order--) {

PpmModel.Context ctx = model.rootContext;

for (int i = 0; i < order; i++) {

if (ctx.subcontexts == null)

throw new AssertionError();

ctx = ctx.subcontexts[history[i]];

if (ctx == null)

continue outer;

}

if (symbol != 256 && ctx.frequencies.get(symbol) > 0) {

enc.write(ctx.frequencies, symbol);

return;

}

// Else write context escape symbol and continue decrementing the order

enc.write(ctx.frequencies, 256);

}

// Logic for order = -1

enc.write(model.orderMinus1Freqs, symbol);

}

}