Come scegliere il parametro per la codifica di Golomb?

Question

Come scegliere il parametro per la codifica di Golomb?

#1 da (2 voti)

2

Sto cercando di implementare la codifica di Golomb, ma non capisco come sia sintonizzata per ottenere il codice ottimale.

È ha detto che

Golomb coding uses a tunable parameter M to divide an input value into two parts: q, the result of a division by M, and r, the remainder. The quotient is sent in unary coding, followed by the remainder in truncated binary encoding.

Non capisco come dovrei scegliere il parametro M - Non riesco a vedere come la spiegazione in Wikipedia si riferisce ai dati reali. Credo che dovrebbe essere correlato a momenti statistici, è vero?

Ad esempio, se ho questo esempio impostato:
{} 3,4,4,4,3,1,2,2,3,1,2,1,4,1,2,2,2,2,1,1,2,2,1
Credo che M dovrebbe essere molto piccolo per questo tipo di dati. Scommetto che è 1 o 2. La media è ~ 2.2 e la deviazione standard è ~ 1.1. La mia intuizione mi direbbe di scegliere 2.

Un altro set di dati qui:
{} 2,7,11,19,6,2,6,13,11,1,5,2,19,7,6,9,6,7,2,4,5,12,3
Questa volta la media è ~ 7.2 e la deviazione standard è ~ 5.0.

In questo caso 7 è il valore giusto? E dovrei preferire il codice Rice (usare 8 come è una potenza di 2) se ottengo un valore come 7?

Capisco che la divisione sarà più facile se utilizzo la codifica Rice, ma ci sono dei vantaggi nel NON usarla? Voglio dire - in entrambi i casi verranno utilizzati 3 bit per il resto, in che modo il codice Golomb puro potrebbe essere più ottimale di allora?

Ancora una sfumatura: il codice Golomb è per interi non negativi. Se invece ho numeri interi positivi, dovrei invece salvare x-1? Cambierà molto per il primo dei set di dati menzionati.

compression

posta Džuris 22.04.2014 - 10:30

fonte

1 risposta

Leggi altre domande sui tag compression

Integrare XACML PDP? Come si ottengono informazioni rilevanti e utili da un cliente relativamente a un lavoro? [duplicare]

score 2 · Accepted Answer

L'algoritmo Golomb-Rice non specifica come trovare i parametri ottimali, e nel caso generale dovrai cercare di inferire la probabilità a posteriori di occorrenze di simboli nel set di dati per stimare il valore ottimale di M . Nota che è una scelta comune avere M = 2 ^k , una potenza di 2, in quanto la codifica in questo caso è semplice, e quindi discutere k invece. La ricerca del k ottimale viene di solito eseguita in modo esaustivo sul set di dati.

Seguendo quanto sopra ora puoi capire perché l'articolo di wikipedia a cui fai il link non si riferisce a nessun dato reale, ma dice il seguente come un modo di un esempio,

Given an alphabet of two symbols, or a set of two events, P and Q, with probabilities p and (1 − p) respectively, where p ≥ 1/2, Golomb coding can be used to encode runs of zero or more P's separated by single Q's. In this application, the best setting of the parameter M is the nearest integer to \frac{-1}{\log_{2}p}.

Nel caso in cui la probabilità p sia conosciuta , dove abbiamo il precedente equivalente alla distribuzione posteriore, si può dimostrare che esiste un valore più noto per M, ma non altrimenti.

In pratica ciò significa che devi avere una buona idea di come apparirà il tuo set di dati finale, possibilmente aumentando ulteriormente la confidenza con i metodi di ricampionamento (ad esempio, bootstrap), e quindi cercando in modo esaustivo ¹ per il valore ottimale del parametro nei dataset di esempio - il k che riduce al minimo la lunghezza del codice prevista. Quindi utilizzi un valore medio del k che hai deciso per i set di dati futuri. Alcune implementazioni memorizzano una tabella di caratteristiche del set di dati di input e selezionano in modo adattivo (cioè modificano) i parametri del codice quando rilevano che il modello di input si sposta. Ad esempio, è comune valutare le caratteristiche di esecuzione della sequenza di input, media, varianza, ecc. E selezionare di conseguenza quando vengono superate le soglie.

¹ Esistono limiti precisi che possono essere stabiliti per il valore di k per interi di input che seguono determinate distribuzioni, risparmiando sulla pienezza della ricerca esaustiva. Tuttavia, per molti numeri interi in serie di dati reali che devi gestire, la distribuzione non può essere facilmente raggruppata in una comoda approssimazione di una variabile casuale uniforme, ad esempio, hai sentito parlare di legge di Benford ? Ciononostante, si noti che la selezione ottimale dei parametri per la codifica raramente differirebbe in modo significativo nei risultati dalla selezione ottimale, nelle implementazioni pratiche.