Huffman encode PGM image

huffman1.py

#!/usr/bin/env python3
import math
import sys
from operator import itemgetter

pgmfile = sys.argv[1]

with open(pgmfile, 'rb') as f:
    # parse PGM header
    f.readline()
    w, h = [int(n) for n in f.readline().decode('ascii').split()]
    maxval = int(f.readline().decode('ascii'))
    bpp = math.ceil(math.log2(maxval + 1))
    print(f'size={w}x{h} maxval={maxval} bpp={bpp}')

    # make histogram of pixels
    pixmap = f.read()
    histo = [0] * (maxval + 1)
    for v in pixmap:
        histo[v] += 1
    print(f'histogram={histo}')
    histo = [(v, c) for v, c in enumerate(histo)]

    # make huffman tree
    hufftree = histo
    while 1 < len(hufftree):
        hufftree = sorted(hufftree, key=itemgetter(1))
        v1, c1 = hufftree.pop(0)
        v2, c2 = hufftree.pop(0)
        node = ([v1, v2], c1 + c2)
        hufftree.insert(0, node)
    hufftree = hufftree[0][0]
    # assign huffman code
    huffcode = [''] * (maxval + 1)
    def assign_code(node, prefix):
        if isinstance(node, int):
            huffcode[node] = prefix
            return
        assign_code(node[0], prefix + '0')
        assign_code(node[1], prefix + '1')
    assign_code(hufftree, '')
    print(f'huffcode={huffcode}')

    # entropy
    entropy = 0
    for v, c in histo:
        entropy += c * len(huffcode[v])
    entropy /= w * h
    ratio_n = bpp / entropy
    ratio_c = 100 * entropy / bpp
    print(f'huffman entropy={entropy:.4f} ratio=1:{ratio_n:.4f} ({ratio_c:.3f}%)')

    # entropy (ideal)
    entropy = 0
    for v, c in histo:
        p = c / (w * h)
        entropy += -p * math.log2(p)
    ratio_n = bpp / entropy
    ratio_c = 100 * entropy / bpp
    print(f'ideal entropy={entropy:.4f} ratio=1:{ratio_n:.4f} ({ratio_c:.3f}%)')

huffman2.py

#!/usr/bin/env python3
import math
import sys
from operator import itemgetter

pgmfile = sys.argv[1]

with open(pgmfile, 'rb') as f:
    # parse PGM header
    f.readline()
    w, h = [int(n) for n in f.readline().decode('ascii').split()]
    maxval = int(f.readline().decode('ascii'))
    bpp = math.ceil(math.log2(maxval + 1))
    print(f'size={w}x{h} maxval={maxval} bpp={bpp}')

    # make histogram of "difference of adjacent pixel"
    pixmap = f.read()
    symbols = (2 * maxval + 1)
    histo = [0] * symbols
    prev = 0
    for v in pixmap:
        diff = v - prev
        histo[maxval + diff] += 1
        prev = v
    print(f'histogram={histo}')
    histo = [(v, c) for v, c in enumerate(histo)]

    # make huffman tree
    hufftree = histo
    while 1 < len(hufftree):
        hufftree = sorted(hufftree, key=itemgetter(1))
        v1, c1 = hufftree.pop(0)
        v2, c2 = hufftree.pop(0)
        node = ([v1, v2], c1 + c2)
        if 0 < c1 + c2:
            hufftree.insert(0, node)
    hufftree = hufftree[0][0]
    # assign huffman code
    huffcode = [''] * symbols
    def assign_code(node, prefix):
        if isinstance(node, int):
            huffcode[node] = prefix
            return
        assign_code(node[0], prefix + '0')
        assign_code(node[1], prefix + '1')
    assign_code(hufftree, '')
    print(f'huffcode={huffcode}')

    # entropy
    entropy = 0
    for v, c in histo:
        entropy += c * len(huffcode[v])
    entropy /= w * h
    ratio_n = bpp / entropy
    ratio_c = 100 * entropy / bpp
    print(f'huffman entropy={entropy:.4f} ratio=1:{ratio_n:.4f} ({ratio_c:.3f}%)')

    # entropy (ideal)
    entropy = 0
    for v, c in histo:
        p = c / (w * h)
        entropy += -p * math.log2(p) if 0 < c else 0
    ratio_n = bpp / entropy
    ratio_c = 100 * entropy / bpp
    print(f'ideal entropy={entropy:.4f} ratio=1:{ratio_n:.4f} ({ratio_c:.3f}%)')