Domande di codifica aritmetica

3

Ho letto il codice aritmetico e, mentre capisco come funziona, tutte le guide e le istruzioni che ho letto iniziano con qualcosa del tipo:

Set up your intervals based upon the frequency of symbols in your data; i.e., more likely symbols get proportionally larger intervals.

La mia domanda principale è, una volta che ho codificato i miei dati, presumibilmente devo anche includere questo modello statistico con la codifica, altrimenti i dati compressi non possono essere decodificati. È corretto? Non vedo questo accennato da nessuna parte - il più che ho visto è che è necessario includere il numero di iterazioni (cioè simboli codificati) - ma a meno che manchi qualcosa, anche questo mi sembra necessario. / p>

Se questo è vero, questo ovviamente aggiungerà un sovraccarico all'output finale. A che punto questo supera i benefici della compressione (ad esempio, se sto provando a comprimere solo poche migliaia di bit)? Anche la scelta della dimensione del simbolo farà una differenza significativa (ad es., Se guardo le parole a 2 bit, piuttosto che gli ottetti completi / qualunque cosa)?

    
posta Xophmeister 17.12.2012 - 13:31
fonte

2 risposte

2

In genere l'overhead di includere il modello statistico viene evitato utilizzando un approccio adattivo. L'encoder e il decoder iniziano nello stesso stato predefinito e si adattano ai dati. Ciò consente al decoder di tracciare la codifica. Un esempio potrebbe iniziare con 128 intervalli uniformi per ogni carattere ascii in [0..127]. Quindi la logica dell'encoder è:

 while (there is data)

      encode the char to a symbol

      increment that chars count

      update the model

 end while

Il decodificatore segue la logica simile:

 while (there is data)

      decode the symbol to a char

      increment that chars count

      update the model

 end while

In pratica, la codifica aritmetica richiede molto tempo per ottenere guadagni marginali nelle prestazioni di compressione. Un decodificatore video H.264 su cui ho lavorato è rallentato di circa un terzo a causa della codifica aritmetica.

    
risposta data 17.12.2012 - 20:53
fonte
1

Penso che l'approccio descritto da @CWallach sia il modo più comune per gestirlo, ma ha due potenziali svantaggi, dal momento che aggiorni continuamente il modello durante la codifica e la decodifica:

  1. È un po 'più lento.
  2. È (ancora più difficile) fare un accesso casuale.

Alcuni schemi mettono il codebook nella parte anteriore del file di dati. Ciò aggiungerebbe un sovraccarico a file molto piccoli, anche se potreste potenzialmente fare qualcosa di intelligente come trasmettere il più piccolo file compresso + libro di codici o il file originale.

Infine, un libro di codici fisso potrebbe funzionare abbastanza bene per alcune applicazioni. Il testo inglese, per esempio, ha una struttura di caratteri piuttosto tipica, e un modello addestrato su un grande corpus probabilmente funzionerebbe piuttosto bene se applicato a un altro documento di grandi dimensioni. Detto questo, i documenti piccoli o atipici potrebbero non comprimere bene.

Ricordo vagamente un vecchio programma di compressione (di epoca BBS) che aveva opzioni per fare tutte e tre queste opzioni. Penso che avesse anche diversi libri di codice integrati per diversi tipi di file. Sfortunatamente, non riesco a ricordare come si chiamava, ma aggiornerò se lo faccio!

    
risposta data 17.12.2012 - 22:56
fonte

Leggi altre domande sui tag