FilesExpand file tree

 master

/

ppm-compress.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

89 lines (74 loc) · 2.98 KB

 master

/

ppm-compress.py

Copy path

Top

File metadata and controls

• Code
• Blame

89 lines (74 loc) · 2.98 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

#

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

#

# Usage: python ppm-compress.py InputFile OutputFile

# Then use the corresponding ppm-decompress.py application to recreate the original input file.

# 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.

#

# Copyright (c) Project Nayuki

#

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

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

#

import contextlib, sys

import arithmeticcoding, ppmmodel

python3 = sys.version_info.major >= 3

# Must be at least -1 and match ppm-decompress.py. Warning: Exponential memory usage at O(257^n).

MODEL_ORDER = 3

# Command line main application function.

def main(args):

# Handle command line arguments

if len(args) != 2:

sys.exit("Usage: python ppm-compress.py InputFile OutputFile")

inputfile = args[0]

outputfile = args[1]

# Perform file compression

with open(inputfile, "rb") as inp, \

contextlib.closing(arithmeticcoding.BitOutputStream(open(outputfile, "wb"))) as bitout:

compress(inp, bitout)

def compress(inp, bitout):

# 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).

enc = arithmeticcoding.ArithmeticEncoder(32, bitout)

model = ppmmodel.PpmModel(MODEL_ORDER, 257, 256)

history = []

while True:

# Read and encode one byte

symbol = inp.read(1)

if len(symbol) == 0:

break

symbol = symbol[0] if python3 else ord(symbol)

encode_symbol(model, history, symbol, enc)

model.increment_contexts(history, symbol)

if model.model_order >= 1:

# Prepend current symbol, dropping oldest symbol if necessary

if len(history) == model.model_order:

history.pop()

history.insert(0, symbol)

encode_symbol(model, history, 256, enc) # EOF

enc.finish() # Flush remaining code bits

def encode_symbol(model, history, symbol, enc):

# 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".

for order in reversed(range(len(history) + 1)):

ctx = model.root_context

for sym in history[ : order]:

assert ctx.subcontexts is not None

ctx = ctx.subcontexts[sym]

if ctx is None:

break

else: # ctx is not None

if symbol != 256 and 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.order_minus1_freqs, symbol)

# Main launcher

if __name__ == "__main__":

main(sys.argv[1 : ])