Problema di codifica aritmetica

Question

Problema di codifica aritmetica

#1 da (2 voti)

3

Da alcuni giorni sto combattendo il mio modo di implementare la codifica aritmetica. Ho trovato un'ottima fonte di informazioni che mi ha fatto capire come dovrebbe funzionare. Per farla breve, implementa la codifica aritmetica sugli interi utilizzando due registri: ALTO e BASSO. Quel registro memorizza una frazione, es.

HIGH = 98765 //means 0.98765(9)
LOW = 91234 // means 0.91234(0)

Poi arriva la magia, quando i numeri più significativi corrispondono (in questo caso sarebbero 9 secondi) vengono stampati. Per me è tutto chiaro.

Tuttavia, quando prendiamo il seguente esempio

                         HIGH    LOW    RANGE   CUMULATIVE OUTPUT

Initial state           99999  00000   100000
Encode B (0.2-0.3)      29999  20000
Shift out 2             99999  00000   100000    .2
Encode I (0.5-0.6)      59999  50000             .2
Shift out 5             99999  00000   100000    .25
Encode L (0.6-0.8)      79999  60000   20000     .25 //here starts problems
Encode L (0.6-0.8)      75999  72000             .25 //how possible?
Shift out 7             59999  20000   40000     .257
Encode SPACE (0.0-0.1)  23999  20000             .257
Shift out 2             39999  00000   40000     .2572
Encode G (0.4-0.5)      19999  16000             .2572
Shift out 1             99999  60000   40000     .25721
Encode A (0.1-0.2)      67999  64000             .25721
Shift out 6             79999  40000   40000     .257216
Encode T (0.9-1.0)      79999  76000             .257216
Shift out 7             99999  60000   40000     .2572167
Encode E (0.3-0.4)      75999  72000             .2572167
Shift out 7             59999  20000   40000     .25721677
Encode S (0.8-0.9)      55999  52000             .25721677
Shift out 5             59999  20000             .257216775
Shift out 2                                      .2572167752
Shift out 0                                      .25721677520

Non so davvero come siano realizzate le linee marcate sui computer, sulla carta è facile, poiché:

/* 
    range, HIGH, LOw - integer
    symbol->high, symbol->low - real
*/
HIGH = HIGH - (range - symbol->high*range)
LOW = LOW + range*symbol->low

Ma sui computer? L'inaccuratezza del numero reale arriva e i miei intervalli sono molto diversi.

[0; 99999)  100000  b   [0.2; 0.3)
[20000; 29999)  100000  ===> 2
[0; 99999)  100000  i   [0.5; 0.6)
[50000; 59998)  100000  ===> 5 //inaccuracy
[0; 99989)  99990   l   [0.6; 0.8)
[59993; 79990)  19998   l   [0.6; 0.8)
[71991; 75990)  19998   ===> 7
[19910; 59909)  40000       [0; 0.1)
[19910; 23908)  3999    g   [0.4; 0.5)
[21509; 21908)  3999    ===> 2
[15090; 19089)  3999    ===> 1
[50900; 90899)  40000   a   [0.1; 0.2)
[54900; 58898)  40000   ===> 5
[49000; 88989)  39990   t   [0.9; 1)
[84991; 88988)  39990   ===> 8
[49910; 89889)  39980   e   [0.3; 0.4)
[61904; 65900)  39980   ===> 6
[19040; 59009)  39970   s   [0.8; 0.9)
[51016; 55011)  39970   ===> 5
zakodowano: 257215865

Apprezzerei qualsiasi aiuto.

c++ coding

posta Robin92 12.05.2013 - 10:06

fonte

1 risposta

Leggi altre domande sui tag c++ coding

Esiste un nome per la scuola di pensiero dietro ai test di scrittura? [chiuso] Codifica in ASCII in cui non è nota la codifica originale della stringa

score 2 · Accepted Answer

In questi casi non dovresti usare il virgola mobile.

Le probabilità possono essere rappresentate come numeri razionali con denominatore 10^something , questo consente di dividere esattamente l'intervallo corrente senza errori di arrotondamento.

Quindi nel tuo caso 0.6 diventa 6/10, 0.8 - 8/10. Come conserverai queste cose è la tua scelta. Di solito viene utilizzata una sorta di formato a virgola fissa. Ad esempio, memorizzi 60 e sai che questo è in realtà probability*100 , quindi ogni volta che moltiplica per questo, dividi anche per 100.

Si noti inoltre che in seguito si verificherà un altro tipo di overflow - quando non è possibile spostare nulla, ma il numero di cifre non consente di dividere l'intervallo senza errori di arrotondamento. In questi casi, si consente o meno l'imprecisione nell'intervallo di divisione o si restringe artificialmente per rendere possibile lo spostamento. Se la decodifica fa tutto nello stesso modo, questo non influisce sulla correttezza, ma riduce la compressione un po '.