Codifica aritmetica, il simbolo di terminazione e la stringa vuota

Question

Supponiamo che l'alfabeto sorgente sia A, B, C con A come simbolo di terminazione e quindi l'intervallo dell'unità è corrispondentemente diviso come [0, P (A), P (A) + P (B), 1].

Le stringhe costituivano da un mucchio di B e la fine c con un A (il simbolo di terminazione) è valido per la codifica. Le stringhe con un A in centro sono considerate non valide per la codifica.

Quindi è facile costruire stringhe con codifiche che si trovano nell'intervallo [P (A), 1). Ma la codifica aritmetica assegna qualsiasi stringa una codifica nell'intervallo [0, P (A))? La stringa vuota potrebbe qualificarsi come codificata a un bitString che si trova in [0, P (A))? Poiché la stringa vuota può essere pensata come la stringa "A" o come solo il simbolo di terminazione.

Poiché lo spazio dedicante alla codifica della stringa vuota sembrerebbe inutile perché non avere la prima divisione dell'intervallo dell'unità essere [0, (P (B) -P (A)) / (1-P (A)), 1] che corrisponde alla mappatura [P (A), P (A) + P (B), 1] da riempire sull'intervallo dell'unità. Quindi le successive divisioni di raffinazione utilizzerebbero [0, P (A), P (A) + P (B), 1] come al solito.

Answer 1

Sì, la stringa vuota sarebbe in quell'intervallo (cioè, 0).Questo è ridondante in quanto puoi anche dedurre che la stringa è zero dalla lunghezza della lunghezza della rappresentazione codificata, in modo da poterlo escludere.Più in generale, se riesci a dedurre che qualsiasi simbolo è impossibile, in base alle porzioni precedenti della stringa, quindi è possibile escluderla (dare gli altri simboli più intervalli) e salvare un piccolo spazio.Ma se l'unico caso in cui fai questo è con il primo simbolo, allora il risparmio dello spazio è probabile che sia troppo trascurabile per giustificare la complessità di un caso speciale.