Iterador run-length

La codificació run-length és una forma molt coneguda de compressió de dades en què seqüències de dades amb el mateix valor consecutiu s’emmagatzemen com un únic valor més el seu recompte. Per exemple, si s’aplica la codificació run-length a la cadena de caràcters

hoooolaaaaaaaaaaaaaaa

s’obtindrà

1h4o1l15a

que s’interpreta com una hac, quatre os, una ela, quinze as. Ens proposem de fer una sèrie d’eines Python per a codificar i descodificar cadenes de caràcters utilitzant aquest mètode.

1. Escriviu el generador iter_codifica(it) que rep com a paràmetre un iterador it i produeix una seqüència de tuples (n, e), essent n el nombre de valors consecutius de e en la seqüència produïda per l’iterador it:

   >>> i1 = iter('hoooolaaaaaaaaaaaaaaa')
   >>> for t in iter_codifica(i1):
   ...     print (t, end=' ')
   (1, 'h') (4, 'o') (1, 'l') (15, 'a')
   >>> i2 = iter('BBBNBBBBBNNNBNNNNNNNBBBB')
   >>> for t in iter_codifica(i2):
   ...     print (t, end=' ')
   (3, 'B') (1, 'N') (5, 'B') (3, 'N') (1, 'B') (7, 'N') (4, 'B')
   

   Per a implementar aquesta funció una possibilitat és utilitzar groupby del mòdul itertools i la funció predefinida map.

2. Escriviu la funció tuples2string que, donat un iterador que genera una seqüencia de tuples \((n_1,x_1) (n_2, x_2) \cdots (n_f,x_f)\), essent \(n_i\) un enter positiu i \(x_i\) un caràcter qualsevol, retorni l’string \(n_1x_1n_2x_2 \cdots n_fx_f\):

   >>> i1 = iter([(1, 'h'), (4, 'o'), (1, 'l'), (15, 'a')])
   >>> tuples2string(i1)
   '1h4o1l15a'
   >>> i2 = iter([(3, 'B'),(1, 'N'),(5, 'B'),(3, 'N'),(1, 'B'),(7, 'N'),(4, 'B')])
   >>> tuples2string(i2)
   '3B1N5B3N1B7N4B'
   

3. Utilitzeu les dues funcions anteriors per a dissenyar la funció codifica que, donada una cadena de caràcters, retorna la seva codificació run-length:

   >>> codifica('hoooolaaaaaaaaaaaaaaa')
   '1h4o1l15a'
   >>> codifica('BBBNNNBNBBBBNNNBB')
   '3B3N1B1N4B3N2B'
   

4. Escriviu el generador tuples(it) que rep com a paràmetre un iterador o iterable it i produeix una seqüència de tuples (n,s), essent n un nombre que representa l’enter que hi ha abans de la cadena de caràcters que cal repetir i s la cadena de caràcters que cal repetir:

   >>> itc = iter(['1','0','a','b','b','a','5','7','z'])
   >>> it = tuples(itc)
   >>> for t in it:
   ...     print (t, end=' ')
   ...
   (10, 'abba') (57, 'z')
   >>> it = tuples('3abcd12w6xyz4fi')
   >>> for t in it:
   ...     print (t, end=' ')
   ...
   (3, 'abcd') (12, 'w') (6, 'xyz') (4, 'fi')
   

   Noteu que un seguit de caràcters dígits acabat amb un caràcter que no és un dígit formen la primer part de la tupla, mentre que el seguit de caràcters no dígits acabats amb un caràcter dígit o el final de l’iterador formen la segona part.

5. Escriviu la funció tuplesAstring(it) que, donat un iterador que genera una seqüència de tuples \((n_1,s_1) (n_2,s_2) \cdots (n_f,c_f)\), essent \(n_i\) un enter positiu i \(s_i\) un string, retorni el string resultant de concatenar, per cada tupla, el string \(s_i\) repetit \(n_i\) vegades:

   >>> it = iter([(3, 'abcd'),(12, 'w'),(6, 'xyz'),(4, 'fi')])
   >>> s = tuplesAstring(it)
   >>> print(s)
   abcdabcdabcdwwwwwwwwwwwwxyzxyzxyzxyzxyzxyzfifififi
   

6. Utilitzeu les dues funcions anteriors per a dissenyar la funció descodifica que, donat un string codificat en run-length, retorna l’string original:

   >>> s = descodifica('3abcd2w9xyz4fi')
   >>> print(s)
   abcdabcdabcdwwxyzxyzxyzxyzxyzxyzxyzxyzxyzfifififi