%Title: Run-length encoding con Ruby
%Author: Andrea Ganduglia
%Date: 2009-06-11 05:36:02
%Copyright: (c)2009 Andrea Ganduglia

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

<code>
~$ banner -w 20 W > Hello.txt
~$ cat Hello.txt
                  #
                ###
            #######
       #######
       ##
         #####
     ######
          ##
              ### #
                  #
</code>

Il file ''Hello.txt'' contiene una stringa di 167 bytes, formata da solo tre caratteri: ''SPACE'', ''#'', ''NEW LINE'' che compressa in RLE diventa:

<code>
18 #
16 3#
12 7#
7 7#
7 ##
9 5#
5 6#
10 ##
14 3# #
18 #
</code>

Questa nuova stringa occupa solo 58 bytes ed \`e facilmente decodificabile: si prenda ad esempio la penultima linea: "''14 3# #\n''". L'espressione RLE ci dice che abbiamo 14 caratteri ''SPACE'', 3 caratteri ''#'', 1 carattere ''SPACE'' (letterale), 1 carattere ''#'' (letterale) e 1 carattere ''NEW LINE'' (letterale) [20 bytes espressi con 8 bytes].

Trascrivendo queste indicazioni otteniamo:

<code>
01234567890123456789 (caratteri sulla linea)
              ### #
</code>

La stringa RLE \`e stata ottenuta utilizzando il coder Ruby listato poco sotto. Questo coder non converte tutti i caratteri della stringa, ma solo quelli ripetuti almeno 3 volte di seguito, la misura minima perch\`e RLE sia efficace.

{|| Compressioni RLE
{|! Stringa originale | Stringa RLE | Bytes Stringa originale | Bytes Stringa RLE | Spazio occupato
{|XX A |XX 1A |XX 1 |XX 2 |DX +100\%
{|XX AA |XX 2A |XX 2 |XX 2 |DX 0\%
{|XX AAA |XX 3A |XX 3 |XX 2 |DX -33.3\%
{|XX AAAA |XX 4A |XX 4 |XX 2 |DX -50\%

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. 

<code>
#!/usr/bin/ruby
#
# rle_coder (v.0.3) 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.gsub(/\\([0-9])/,"\\\\\\1").split('')
	for i in 0..(str.size-1)
		# Fine del ciclo
		if c > 0 && str[i] != s
			o << "#{c}#{s}"
			c = 0; s = nil;
		end
		# Continuo
		if c > 0 && str[i] == s
			c = c+1
		end
		# Inizio il ciclo
		if c == 0 && str[i+1] == str[i] && str[i+2] == str[i] && str[i] =~ /\D/
			s = str[i]
			c = c+1
		end
		# Niente
		if c == 0 && s == nil
			if str[i] =~ /\d/
				o << "\\#{str[i]}"
			else
				o << str[i]
			end
		end
	end
	# Ultimi caratteri
	if c > 0
		o << "#{c}#{s}"
	end
	return o.to_s
end

def rle_decode(str)
    o = []
    str = str.scan(/\\[0-9]{1}|[0-9]+[A-z\W]{1}|[A-z\W]{1}/)
    str.each do |s|
        if s =~ /[0-9]+./
            i = s.scan(/([0-9]+)(.)/)
            o << "#{i[0][1]*i[0][0].to_i}"
        elsif s =~ /\\[0-9]{1}/
            o << "#{s.gsub(/^\\/,'')}"
        else
            o << s
        end
    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 ee
</code>

== 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 263 bytes.

<code>
Message-ID: <29835.1244718219@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: DQElqmRrExLq9ZYWd9ZkIA==

Qk1mTjYARjMAXDgzAGQzAGQzAAEAEAADMwAgTgAAEwsAABMLMTEA+AAA4AcAAB83ADkwODb/
fe95zvOcEIQQhPOcec597zE4Mv997/OcilIEITQABCGKUvOcfe8xNzj/fe/znIZcMTEyAIZc
MfOcfe8xNzb/ec6KUjE2AIpSec4xNzb/85wEITE2AAQh85wxNzb/EIQyMAAQhDE3Nv8QhDIw
ABCEMTc2//OcBCExNgAEIfOcMTc2/3nOilIxNgCKUnnOMTc2/33v85yGXDExMgCGXDHznH3v
MTc4/33v85yKUgQhNAAEIYpS85x97zE4Mv9973nO85wQhBCE85x5zn3vODY5OP8=

-----
</code>

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

<code>munpach white.pack</code>

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

<code>
ruby rle_coder d white.rle > white.bmp
display white.bmp
</code>