Cos'è questo algoritmo di compressione? (Simile a RLE)

In Run Length Encoding (RLE), una grande serie di informazioni è codificata memorizzando la quantità di consecutivi sequenze. Un esempio canonico è:

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

diventa

12W1B12W3B24W1B14W

Sto usando un algoritmo che è simile, ma leggermente diverso.

I dati da codificare sono un array associativo. Se ordinato, appare come segue:

[{A:1},{B:1},{C:1},{D:1},{E:1},{F:2},{G:2},{H:2},{I:2},{M:3},{N:3},{O:3},{W:4},{X:4}]

Posso comprimerlo usando intervalli semiaperti:

[{[A,F):1},{[F,J):2},{[M,P):3},{[W,Y):4}]

Se conto gli spazi vuoti, ho solo bisogno di descrivere le partizioni e posso rimuovere il valore finale degli intervalli:

[{A:1},{F:2},{J:-},{M:3},{P:-},{W:4},{Y:-}]

E ora posso scrivere questo come una singola stringa:

A1F2J-M3P-W4Y-

Se non avessi completato questa procedura e registrato solo ogni elemento separatamente, avrei:

A1B1C1D1E1F2G2H2I2M3N3O3W4X4

Quindi c'è una compressione significativa, che sarà più drammatica, più i valori consecutivi sono nei dati di origine.

Note:

• I personaggi sono solo per illustrazione; Funziona anche con gli array di byte.

• Mantenere l'ordine in caso di inversione dell'algoritmo non è un requisito, in quanto l'input è un tipico array associativo, come in HashTable o Dictionary , e la sequenza solitamente non è garantita in questi tipi di dati.

• È abbastanza semplice cercare un valore dalla stringa codificata senza doverlo decodificare completamente. Per esempio, posso trovare N=3 scansionando ogni altro carattere, cercando il primo carattere che è maggiore di N (che sarebbe P ) e prendendo il valore dalla voce precedente. Questo può essere fatto con la ricerca lineare o binaria.

Domande

1. È un algoritmo noto?

2. È solo una variazione della codifica Run Length?

3. Se non è RLE, ha un suo nome canonico?

Non sto chiedendo se funziona o no, lo so già. Sto semplicemente chiedendo se questo algoritmo ha un suo nome o se è solo una variazione su RLE.