$ o (\ log n) $ space보다 더 잘 압축 가능한 무한한 문자열 세트를 찾으십시오.

Question

태스크는 무한한 문자열 세트 $ a_1, a_2 \ ldots $ 을 찾는 것입니다. 여기서 $ | a_ {i + 1} |> | a_i | $ 및 압축 알고리즘 $ f $ f $ 이 $ | f (a_i) |= o (\ log_2 | a_i |) $ i \ tofty $ . 나는 $ 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 $ .