Albero di huffman infinito

Question

Dobbiamo derivare una codifica binaria ottimale per l'infinito insieme di simboli $ {s_1, s_2, dots } $. Sono distribuiti è data da$$ p (s_i) = 9 CDOT 10^{-i} $$

La mia intuizione era quella di usare una codifica Huffman. Ovviamente l'algoritmo di codifica Huffman deve prima trovare i due elementi più piccoli, cosa che non possiamo fare. Ma, se immaginiamo l'ultimo passo dell'algoritmo di Huffman, avrebbe i due elementi $ s_1 $ e il supersymbol $ s_2s_3s_4 dots $ con probabilità $0.9$ e $0.1$ rispettivamente. Quindi, (se lasciato è $0$ e il diritto è $1$) simbolo $ s_1 $ otterrebbe la parola $0$. Gli altri simboli avrebbero tutti una parola in codice a partire da $1$. Questo albero è chiaramente simile a sé. Se rappresentiamo alberi binari come tuple con un albero vuoto come nullset $ Varnothing $, abbiamo che questo albero è dato da

$$ t = ( Varnothing, t) $$

Cioè, un ramo sinistro che è vuoto e il ramo destro che è identico all'intero albero. Quindi, otteniamo le parole in codice

$$ s_1 mapsto 0, s_2 mapsto 10, s_3 mapsto 110, s_4 mapsto 1110, dots $$

Ora, so che sono ottimali. Puoi fare una prova per contraddizione dimostrando che cambiare una di queste parole in codice e ancora soddisfare la disuguaglianza di Kraft farà aumentare la lunghezza prevista.

La mia domanda è: è il fatto che questo infinito albero di Huffman sia arrivato alla risposta in una coincidenza o c'è un modo per formalizzare Huffman codificante per un set infinito di simboli.