ابحث عن مجموعة لا حصرية من السلاسل غير القابلة للضغط أفضل من مساحة $ O (\ Log N) $

Question

المهمة هي العثور على مجموعة لا حصر لها من السلاسل $ a_1، a_2 \ Ldots $ ، حيث $ | a_ {I + 1} |> | A_I | $ وعثور على خوارزمية ضغط $ F $ لهذه السلاسل، بحيث $ | f (a_i) |= o (\ log_2 | a_i |) $ مع $ I \ to \ span $ .

قد نظرت في مجموعة من السلاسل مع الحد الأدنى من الانتروبوي: $ 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 $ .