On Coding Complexity of Combinatorial Sources

Let $X$ be a dictionary consisting of binary words of length $n$. We show that there exists a linear one-to-one coding of $X$ with words of length $l\leq 2\log|X|+\log (n/\log|X|)$, whose program complexity equals $l$.