Найдите бесконечный набор строк, которые сжимаются лучше, чем в $ O (\ log n) $ space

Question

Задача - найти бесконечный набор строк $ a_1, a_2 \ ldots $ , где $ | a_ {I + 1} |> | a_i | $ и найти алгоритм сжатия $ f $ для этих строк, так что $ | f (a_i) |= o (\ log_2 | a_i |) $ с $ 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 $ .