Codifica aritmetica rispetto alla precisione numerica della macchina

Question

Codifica aritmetica rispetto alla precisione numerica della macchina

#1 da (4 voti)
#2 da (1 voti)

4

Quando si suddividono gli intervalli per la codifica aritmetica, lo scenario peggiore è che l'intervallo finale avrà la dimensione 2^(1-n) , dove n è il numero di simboli univoci che si codificano. Questo raggiungerà i limiti della precisione della macchina, quando si usano i normali tipi di dati, molto rapidamente: ad esempio, ho realizzato un'implementazione JavaScript e si interrompe dopo aver codificato circa 15 caratteri!

Dato che questo è piuttosto limitante, come fanno i codec a risolvere questo problema?

Codifica [molto] brevi blocchi, entro i limiti della macchina, e concatenali insieme? Ciò aggiungerà un sovraccarico.
Utilizzare tipi non nativi con precisione arbitraria? Questo sarà lento.
Qualcos'altro? ...

coding arithmetic numeric-precision compression

posta Xophmeister 21.12.2012 - 12:59

fonte

2 risposte

1

Mentre la parte "aritmetica" del nome "codifica aritmetica" è utile perché spiega come funziona il sistema, non dovremmo assumere che il "numero" codificato sia mai effettivamente utilizzato o utile come numero. Infatti, nel caso generale, è solo un flusso di bit.

Quindi non penso che la dimensione del tipo di dati numerici che può essere gestito in modo nativo sia davvero un problema. Si codifica spingendo i bit all'estremità di un flusso che può essere arbitrariamente grande e si decodifica leggendo quel flusso.

risposta data 21.12.2012 - 13:07

fonte

Leggi altre domande sui tag coding arithmetic numeric-precision compression

Va bene simulare più oggetti in una classe? Dovremmo convalidare una transizione di stato prima di tentare nel modello di stato?

score 4 · Accepted Answer

Secondo Wikipedia:

Rather than try to simulate infinite precision, most arithmetic coders instead operate at a fixed limit of precision which they know the decoder will be able to match, and round the calculated fractions to their nearest equivalents at that precision. [...]

A process called renormalization keeps the finite precision from becoming a limit on the total number of symbols that can be encoded. Whenever the range is reduced to the point where all values in the range share certain beginning digits, those digits are sent to the output. For however many digits of precision the computer can handle, it is now handling fewer than that, so the existing digits are shifted left, and at the right, new digits are added to expand the range as widely as possible.