Trova un insieme infinito di stringhe che sono compresse meglio rispetto a $ o (\ log n) $ spazio

Question

L'attività è trovare un insieme infinito di stringhe $ a_1, a_2 \ ldots $ , dove $ | A_ {I + 1} |> | A_i | $ e per trovare un algoritmo di compressione $ f $ per queste stringhe, tale che $ | f (A_I) |= o (\ log_2 | A_I |) $ con $ I \ to \ INFTY $ . Ho considerato un set di stringhe con entropia minima: $ A_1= B, A_2= BB $ , ecc. L'algoritmo di compressione ottimale per queste stringhe è $ f: a_i \ mapsto | A_i | $ , ma questo comprime ogni stringa solo su $ o (\ log i) $ Spazio.

Answer 1

Suggerimento:

invece di $ a_i= b ^ i $ , prova $ a_i= b ^ {f (i)} $ per alcune funzioni $ f $ .