Trouvez un ensemble infini de chaînes qui sont mieux compressables qu'en $ o (\ journal n) $ espace

Question

La tâche consiste à trouver un ensemble infini de chaînes $ a_1, a_2 \ ldots $ , où $ | a_ {i + 1} |> | a_i | $ et pour trouver un algorithme de compression $ f $ pour ces chaînes, telle que $ | f (a_i) |= O (\ log_2 | A_I |) $ avec $ i \ to \ to \ \ / p>

J'ai considéré comme un ensemble de chaînes avec une entropie minimale: $ a_1= b, a_2= bb $ , etc. L'algorithme de compression optimale pour ces chaînes est $ F: A_I \ MAPSTO | A_I | $ , mais cela comprime chaque chaîne uniquement à $ o (\ Connect i) $ espace.

Answer 1

indice:

au lieu de $ a_i= b ^ i $ , essayez $ a_i= b ^ {f (i)} $ ^ pour une fonction $ f $ .