[C] codifica RLE

[tenbota87]

Salve a tutti..
avrei bisogno di un piccolo aiuto..

dovrei fare un progetto che utilizza la compressione RLE.
Essa consiste nel contare i caratteri ripetuti consecutivamente e salvare questo numero con la lettera corrispondente.

Ad esempio la stringa ddfffm diventa d2f31m

Il mio problema è il salvataggio del numero e della lettera in maniera efficiente, cercando di limitare il più possibile lo spazio occupato.

Sono riuscito a implementare banalmente il salvataggio, ma la mia soluzione richiede troppo spazio e tempo di esecuzione.

Qualcuno potrebbe aiutarmi gentilmente? Grazie per la vostra disponibilità

[WarDuck]

Posta il codice che hai scritto ;).

Premesso che non sono un esperto di codifica, detta così, non credo tu possa fare di meglio rispetto alle specifiche.

Se RLE prevede quel tipo di codifica, e tu lo devi applicare alla lettera credo che ulteriori ottimizzazioni escano fuori dalle specifiche che hai richiesto.

Comunque ora che mi viene in mente potresti codificare i numeri non come testo ma come bit.

Ad esempio la stringa "255" occupa 3 byte, ovvero 3*8 = 24bit.

Il numero 255 è rappresentabile da una codifica ad 8 bit e quindi può occupare 3 volte meno, risparmiando ben 2 byte :D.

Una cosa carina sarebbe utilizzare una codifica adattativa sulla base dell'alfabeto che hai e sulla base del massimo numero di ripetizioni che trovi, ti richiederebbe 2 passate, ma potresti arrivare a risparmiare più spazio.

Ad esempio se trovi che il numero massimo di ripetizioni è 15, potresti usare uno schema del tipo:


8-bit lettera | 4-bit numero | 8-bit lettera | 4-bit numero ...


In questo caso con 2 lettere risparmi un byte.

Cosa importante: nell'header del file creato devi specificare la lunghezza in bit del campo numerico. Quindi aggiungi all'inizio del file magari 8 bit di intestazione (questi saranno sempre fissi perché devi sapere quanto leggere).

[Mirkolo]

Tempo fa avevo scritto una libreria per aprire file PSD (Photoshop) in C. Lì utilizzano la codifica PackedBits di Apple, che in sostanza è un ibrido tra RLE e la copia dei dati senza alcuna compressione. Se l'input varia di byte in byte la codifica RLE diventa inutilmente esosa. Il trucco sta nel partire con un codice di escape, se questo vale meno di 128 i seguenti n+1 byte devono essere copiati così come sono, se vale 128 non viene considerato, se vale più di 128 il byte successivo va ripetuto 257-n volte (quindi al massimo 257-129 = 128 volte). E così via.

Se il buffer ha tutti caratteri uguali ottieni un rapporto di compressione tendente a 1:128, mentre se sono tutti diversi hai un sovrapprezzo da pagare di x/128 byte, se x è la dimensione del buffer.