Determinazione dell'algoritmo di compressione migliore da utilizzare per una serie di byte

Question

Per un mio progetto personale, sto scrivendo una piccola classe per comprimere e decomprimere da un formato piuttosto oscuro. Ho le specifiche complete, ma non è questo il problema.

Innanzitutto, questo "formato" utilizza un set di 6 diversi tipi di compressione nonché blocchi non compressi di dati byte. I formati sono RLE, una derivazione di RLE in cui il numero aumenta ogni byte (ad esempio 3, 4, 5, ...), un RLE a 16 bit, una copia LZ, una copia LZ inversa e una copia LZ Xor ' d con 255. Non è la più pulita delle specifiche, ma non l'ho nemmeno progettata.

La mia routine di compressione dovrebbe includere un array compreso tra 1 e 65535 byte e (si spera) comprimerlo il più possibile. Il mio precedente tentativo a questo semplicemente calcolato, partendo da qualsiasi indice nel flusso non compresso, quale delle tecniche di compressione sopra fornirà la migliore compressione, e quindi comprime per quanto molti byte quel metodo comprimerà all'array di byte compressi prima di ripetere dal nuovo indice "non compresso", ad esempio:

{0,0,0,1,2,3,4}

L'algoritmo prima leggeva che all'inizio c'erano tre zeri, quindi emetteva la codifica RLE per loro che la specifica utilizzata, e quindi a partire dal quarto elemento, leggeva che l'incremento di RLE avrebbe coperto l'1,2 , 3,4 'abbastanza bene e comprimilo prima di tornare.

Il problema riassunto è che mentre si cerca di scoprire le migliori specifiche da usare, la routine è molto lenta anche su array di piccoli (20-30) byte. Qualcuno può aiutare con suggerimenti su come potrei guardare a ottimizzare questo, o se ci sono ulteriori informazioni che potrei fornire per aiutare?

Answer 1

Sembra che quello che stai cercando di fare sia elaborare un gran numero di possibilità di compressione per ogni possibile segmento (chiamiamo la tua lunghezza variabile 1-64K blocchi di segmenti) del file. Correggimi se sbaglio, ma stai elaborando la migliore compressione per il primo segmento dalle seguenti scelte (il metodo 0 non è compresso):

• metodo di compressione 0, lunghezza 1 byte.
• metodo di compressione 1, lunghezza 1 byte.
• :::::
• metodo di compressione 6, lunghezza 1 byte.
• metodo di compressione 0, lunghezza 2 byte.
• metodo di compressione 1, lunghezza 2 byte.
• :::::
• metodo di compressione 6, lunghezza 65534 byte.
• metodo di compressione 0, lunghezza 65535 byte.
• metodo di compressione 1, lunghezza 65535 byte.
• metodo di compressione 2, lunghezza 65535 byte.
• metodo di compressione 3, lunghezza 65535 byte.
• metodo di compressione 4, lunghezza 65535 byte.
• metodo di compressione 5, lunghezza 65535 byte.
• metodo di compressione 6, lunghezza 65535 byte.

Ci vorrà molto tempo (circa 420.000 tentativi di compressione per segmento). Se è quello che stai facendo, farai meglio a scegliere una singola dimensione del segmento (ad esempio, 64 K) e ad applicare ciascuno dei sette metodi di compressione per scegliere il migliore. Quindi, per ciascun segmento, genera il metodo "quot" byte seguito dai dati compressi.