Encuentre un conjunto infinito de cuerdas que sean compresibles mejor que en $ O (\ log n) $ espacio

Question

La tarea es encontrar un conjunto infinito de cadenas $ A_1, A_2 \ LDOTS $ , donde $ | a_ {I + 1} |> | A_I | $ y para encontrar un algoritmo de compresión $ f $ para estas cadenas, de modo que $ | F (A_I) |= O (\ log_2 | a_i |) $ con $ i \ a \ infty $ .

He considerado un conjunto de cadenas con entropía mínima: $ A_1= B, A_2= bb $ , etc. El algoritmo de compresión óptimo para estas cadenas es $ f: a_i \ mapsto | a_i | $ , pero esto comprime cada cadena solo para $ o (log i) $ espacio.

Answer 1

Sugerencia:

en lugar de $ a_i= b ^ i $ , intente $ a_i= b ^ {f (i)} $ para alguna función $ f $ .