$ O（\ log n）$ spaceよりも圧縮できない文字列の無限の文字列を見つける

Question

タスクは、無限の文字列 $ a_1、a_2 \ ldots $ を見つけることです。ここで、 $ | a_ {I + 1} |> | A_I | $ と圧縮アルゴリズム $ f $ を見つけるために、 $ | | F（a_i）|= o（\ log_2 | a_i | span class=" math-container "> $ i \ to \ infty $ 。

エントロピーの一連の文字列を検討しました。 $ A_1= b、a_2= bb $ などの $ f：a_i \ mapsto | a_i | $ ですが、これは $ o（\ log i）$ スペース。

Answer 1

ヒント：

$ a_i= b ^ i $ の代わりに $ a_i= b ^ {f（i）} $関数 $ f $ 。