Encontre um conjunto infinito de strings que são compressíveis melhor do que em $ o (\ log n) $
-
29-09-2020 - |
Pergunta
A tarefa é encontrar um conjunto infinito de strings $ a_1, A_2 \ LDOTS $ , onde $ | a_ {i + 1} |> | a_i | $ e para encontrar um algoritmo de compressão $ F $ para estas cordas, tal que $ | f (a_i) |= O (\ log_2 | a_i |) $ com $ i \ to \ infty $ .
Eu considerei um conjunto de strings com entropia mínima: $ a_1= b, a_2= bb $ , etc. O algoritmo de compressão ideal para essas strings é
Solução
DICA:
Em vez de $ a_i= b ^ i $ , tente $ a_i= b ^ {f (i)} $ para alguma função $ F $ .
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange