Run-length encoding con Ruby

Il Run-lenght encoding (RLE) è un tipo di compressione lossless piuttosto primitivo, ma comunque efficace con stringhe che contengono lunghe sequenze di byte identici. Ad esempio:

~$ echo -n "AAAAAAAAAAAABBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDDD" > Hello.txt

Il file Hello.txt contiene una stringa di 61 bytes, formata da solo quattro caratteri: A, B, C e D che compressa in RLE diventa:

A12B15C17D17

Questa nuova stringa occupa solo 12 bytes ed è facilmente decodificabile. L'espressione RLE ci dice che abbiamo il caratte A ripetuto 12 volte, B 15 volte, C 17 volte ed infine D 17 volte. RLE dunque ci permette di esprimere i 61 bytes della stringa iniziale con appena 12 bytes.

La stringa RLE è stata ottenuta utilizzando il coder Ruby listato poco sotto. Questo coder converte tutti i caratteri in RLE, compresi i caratteri ripetuti una sola volta ed i numeri (i numeri e il carattere \ vengono protetti con il carattere \, quindi la compressione RLE occupa un byte in più ovvero +2 nella formula poco sotto).

Compressioni RLE
Stringa originale	Stringa RLE	Bytes Stringa originale	Bytes Stringa RLE	Spazio occupato
A	1A	1	2	+100%
AA	2A	2	2	0%
AAA	3A	3	2	-33.3%
AAAA	4A	4	2	-50%

In genere, quindi, una sequenza di caratteri m ripetuto n volte compressa con RLE occupa:

$LaTeX code: S_m = ceil \left ( \frac{log(n)}{log(10)} \right ) + 1$

mentre l'intera stringa occuperà:

$LaTeX code: \sum_{k=2} = S_0 + S_1 + S_2 + S_n$

Vedi: http://en.wikipedia.org/wiki/Run-length_encoding

Codice

Il codice qui sotto funziona abbastanza bene con i file di testo e i file BMP.

#!/usr/bin/ruby
#
# rle_coder (v.0.5) RLE Encoder/Decoder 
# (c)2009 Andrea Ganduglia - www.frequenze.it
# GPL Software
# Released under GPL3 - www.gnu.org

def rle_encode(str)
	o = []; c = 0; s = nil;
	str = str.split('')
	for i in 0..str.size
		# Fine del ciclo
		if c > 0 && str[i] != s
			if s =~ /\d/ || s == "\\"
				o << "\\#{s}#{c}"
			else
				o << "#{s}#{c}"
			end
			c = 0; s = nil;
		end
		# Continuo
		if c > 0 && str[i] == s
			c = c+1
		end
		# Inizio il ciclo
		if c == 0
			s = str[i]
			c = c+1
		end
	end
	return o.to_s
end

def rle_decode(str)
	o = []
	str = str.scan(/\\\\[0-9]+|\\[0-9]{1}[0-9]+|[A-z\W]{1}[0-9]+/)
	str.each do |s|
		if s[0].chr == "\\"
			c = s[1].chr
			n = s[2..(s.size-1)]
		else
			c = s[0].chr
			n = s[1..(s.size-1)]
		end
		o << "#{c*n.to_i}"
	end
	return o.to_s
end

e = "usage: rlt_coder [e|d] [FILE]"
t_file = ARGV[1]
if File.file?(t_file)
	f = File.new(t_file).read
else
	puts e
	exit
end

if ARGV[0] == "d"
	e = rle_decode(f)
end

if ARGV[0] == "e"
	e = rle_encode(f)
end

print e

Un file Bitmap

I file BMP sono i migliori da comprimere con questo metodo. Ho creato un file BMP bianco con un punto nero al centro di 100x100px che pesa 20070 bytes, mentre la sua versione RLE pesa solo 414 bytes.

Message-ID: <18420.1245155412@openclose.it>
Mime-Version: 1.0
Subject: RLE di white.bmp
Content-Type: multipart/mixed; boundary="-"

This is a MIME encoded message.  Decode it with "munpack"
or any other MIME reading software.  Mpack/munpack is available
via anonymous FTP in ftp.andrew.cmu.edu:pub/mpack/
---
Content-Type: application/octet-stream; name="white.rle"
Content-Transfer-Encoding: base64
Content-Disposition: inline; filename="white.rle"
Content-MD5: H5In+ifZc7tFYrbVuqWzzg==

QjFNMWYxTjEANkYxADNcODEAM2QxADNkMQAzATEAMRAxADEDMQAzIDFOMQAyEzELMQAyEzEL
MQAxMfgxADLgMQcxADIfMQA3/zk0ODh9Me8xeTHOMfMxnDEQMYQxEDGEMfMxnDF5Mc4xfTHv
Mf8xODJ9Me8x8zGcMYoxUjEEMSExADQEMSExijFSMfMxnDF9Me8x/zE3OH0x7zHzMZwxhjFc
MTEAMTKGMVwxMfMxnDF9Me8x/zE3NnkxzjGKMVIxADE2ijFSMXkxzjH/MTc28zGcMQQxITEA
MTYEMSEx8zGcMf8xNzYQMYQxADIwEDGEMf8xNzYQMYQxADIwEDGEMf8xNzbzMZwxBDEhMQAx
NgQxITHzMZwx/zE3NnkxzjGKMVIxADE2ijFSMXkxzjH/MTc2fTHvMfMxnDGGMVwxMQAxMoYx
XDEx8zGcMX0x7zH/MTc4fTHvMfMxnDGKMVIxBDEhMQA0BDEhMYoxUjHzMZwxfTHvMf8xODJ9
Me8xeTHOMfMxnDEQMYQxEDGEMfMxnDF5Mc4xfTHvMf84Mjk2

-----

Copiare questo testo in un file white.pack e fare:

munpach white.pack

si ottiene il file codificato RLE del file white.bmp, quindi:

ruby rle_coder d white.rle > white.bmp
display white.bmp

Migliorare la compressione

Il Run-lenght encoding può essere migliorato e molto, seguendo un approccio un poco piu` furbo (presente nella versione 0.3 del coder presentato) e prevendendo che non tutti i caratteri vengano compressi, ma solo quelli ripetuti un numero significativo di volte (per esempio 3 volte). In questo modo non si ottiene mai un frammento di stringa più pesante dell'originale, anche se si cede qualcosa in compatibilità ed è necessario un decoder più sofisticato.