Come si possono calcolare i parametri ottimali per uno schema di codifica start-step-stop?

Question

Un codice start-step-stop è una tecnica di compressione dei dati utilizzata per comprimere numeri relativamente piccoli.

Il codice funziona come segue: ha tre parametri, start, step e stop. Inizio determina la quantità di bit utilizzati per calcolare i primi numeri. Il passo determina quanti bit aggiungere alla codifica quando si esauriscono e si ferma determina il numero massimo di bit utilizzati per codificare un numero.

Quindi la lunghezza di una codifica è data da l = start + step * i.

La " i " il valore di un particolare codice è codificato usando unario. Cioè, un numero di 1 bit seguito da uno 0 bit di terminazione. Se abbiamo raggiunto lo stop, allora possiamo eliminare lo 0 bit finale. Se i è zero, scriviamo solo lo 0 bit.

Quindi un (1, 2, 5) codice start-step-stop funzionerebbe come segue:

Valore 0, codificato come: 0 0
Valore 1, codificato come: 0 1
Valore 2, codificato come: 10 000
Valore 9, codificato come: 10 111
Valore 10, codificato come: 11 00000
Valore 41, codificato come: 11 11111

Quindi, dato un file contenente più numeri, come possiamo calcolare i codici di avvio-arresto-stop ottimali per quel file? I parametri ottimali sono definiti come quelli che daranno il massimo rapporto di compressione.

Answer 1

Questi " start-step-stop " i codici sembrano un modo diverso di chiamare codici Huffman . Vedi la tecnica di base per una descrizione dello pseudo-codice per il loro calcolo.

In sostanza questo è ciò che fa l'algoritmo:

Prima di iniziare la codifica Huffman devi raccogliere le statistiche di ogni simbolo che comprimerai (la loro frequenza totale nel file da comprimere).

Dopo aver creato un albero binario utilizzando tali informazioni in modo che il più frequentemente i simboli usati sono nella parte superiore dell'albero (e quindi usano meno bit) e in modo tale che nessuna codifica abbia un prefisso codice . Dal momento che se una codifica ha un prefisso comune potrebbero esserci delle decompressioni di ambiguità.

Alla fine della codifica di Huffman il tuo valore iniziale sarà la profondità del nodo foglia più superficiale, il tuo passo sarà sempre 1 (logicamente questo ha senso, perché dovresti forzare più bit di quelli che ti servono, basta aggiungerne uno alla volta ,) e il valore di arresto sarà la profondità del nodo foglia più profondo.

Se le statistiche di frequenza non sono ordinate, ci vorrà O (nlog n), se sono ordinate per frequenza può essere fatto in O (n).

I codici Huffman sono garantiti per avere la migliore compressione media per questo tipo di codifica:

  

Huffman è stato in grado di progettare di più   metodo di compressione efficiente di questo   tipo: nessun'altra mappatura dell'individuo   simboli sorgente a stringhe univoche di   i bit produrranno una media più piccola   dimensione dell'uscita quando il simbolo reale   le frequenze concordano con quelle abituate   crea il codice.

Questo dovrebbe aiutarti a implementare la soluzione ideale al tuo problema.

Modifica: sebbene simile, questo non è ciò che l'OP stava cercando.

Questo documento accademico del creatore di questi codici descrive una generalizzazione di codici start-step-stop, codici start-stop. Tuttavia, l'autore descrive brevemente come ottenere un avvio-passaggio-arresto ottimale verso la fine della sezione 2. Implica l'utilizzo di una variabile casuale statistica o il finanziamento della forza bruta la combinazione migliore. Senza alcuna conoscenza preliminare del file l'algoritmo è O ((log n) ^ 3).

Spero che questo aiuti.

Answer 2

L'approccio che ho usato era una semplice soluzione di forza bruta. L'algoritmo ha seguito questi passaggi di base:

1. Conta la frequenza di ciascun numero nel file. Nello stesso passaggio, calcola la quantità totale di numeri nel file e determina il numero più grande come maxNumber.

2. Calcola la probabilità di ciascun numero come la sua frequenza divisa per la quantità totale di numeri nel file.

3. Determina " ottimoStop " uguale a log2 (maxNumber). Questo è il numero ideale di bit che dovrebbe essere usato per rappresentare maxNumber come nella teoria dell'informazione di Shannon e quindi una stima ragionevole della quantità massima ottimale di bit utilizzati nella codifica di un determinato numero.

4. Per ogni " inizio " valore compreso tra 1 e "optimumStop" ripetere i passaggi 5 - 7:

5. Per ogni "passaggio" valore da 1 a (" optimumStop " - " start ") / 2, ripetere il passaggio 6 & amp; 7:

6. Calcola il "quot" stop " valore più vicino a " optimumStop " che soddisfa stop = start + step * i per un numero intero i.

7. Calcola il numero medio di bit che verrebbero utilizzati da questa codifica. Questo può essere calcolato come la probabilità di ciascun numero moltiplicata per la sua lunghezza in bit nella codifica data.

8. Scegli la codifica con il numero medio più basso di bit.