Questo è il primo di una serie di articoli (forse, se ne avrò voglia e tempo) inerenti alla compressione dei dati. La cosa verrà trattata nel modo più pragmatico possibile riducendo all’osso i simbolini matematici.

Per iniziare ho scelto una forma di codifica senza perdita usata generalmente nei fax (insieme ad altra “roba” che vedremo in seguito). L’idea alla base è molto semplice: sequenze di dati contigue ripetute vengono trasformate in una coppia (simbolo, #occorrenze). Ad esempio la stringa aaabbccccc sarà rappresentata da (a,3)(b,2)(c,5). Tra i formati basati su questo principio ricordiamo PackBits di Apple, introdotta con il MacPaint ed usata a volte nei file tiff. Vediamone ora una semplice implementazione in Python.

"""
Created by Jonathan Masci @ Casapiddu.
Copyright (c) 2007. All rights reserved.
"""

import sys

class RLE:
	def encode(self, inputte, outputte):
	 	f = open(inputte, 'r')
		o = open(outputte, 'w')
		t = f.read()
		counter = 0
		lastChar = t[0]
		strout = ""
		for c in t:
			if lastChar == c:
				counter += 1
			else:
				strout += lastChar + str(counter) + ";"
				lastChar = c
				counter = 1
		strout += lastChar + str(counter) + ";"
		lastChar = c
		counter = 1
		o.write(strout)
		o.close()
		f.close()

	def decode(self, inputte, outputte):
		f = open(inputte, 'r')
		o = open(outputte, 'w')
		t = f.read()
		lastChar = ""
		strout = ""
		char = ""
		counter = 0
		state = 0
		for c in t:
			if state == 0: #read the symbol
				char = c
				state = 1
			else:
				if state == 1: #read the occurrences
					if c == ';':
						counter = int(lastChar)
						i = 0
						while i < counter:
							strout += char
							i += 1
						lastChar = ""
						char = ""
						state = 0;
					else:
						lastChar += c
		o.write(strout)
		o.close()
		f.close()		

def main():
	erle = RLE()
	erle.encode('inputte.txt', 'outputte.txt')
	drle = RLE()
	drle.decode('outputte.txt', 'decoded.txt')

if __name__ == '__main__':
    main()

Per provarlo basta copiare il codice e creare un file di input che deve necessariamente chiamarsi inputte.txt (ovviamente sto scherzando però inputte è un bel nome) ed eseguire il comando

python nomesorgente.py

Come vedrete non è che comprima gran che, anzi a volte la dimensione del file aumenta, ma forse con la prossima puntata riusciremo a fare di meglio preprocessando l’input.

Have fun!