Q How do I quantify complexity of a given string? Consider a sample:

AAAAAAAAA     //very easy - meta sample [COMPLEXITY = 0]
KEui£$n9&E    //say random - meta sample [COMPLEXITY = ∞]

To my limited knowledge Kolmogorov Complexity deals with this problem, but it is non-computable. So what measures I can use to approximate the complexity of the string? Could you point me to the right direction or literature for the following problem.

Many thanks!


What people do in practice is compress the strings and use the result as a complexity measure. It only works if the strings are long enough.

It is known that the Lempel-Ziv algorithm used by many compression problems is optimal (up to constants and implementations) for ergodic Markov chains (in their stationary distribution). So if you think that your string is generated by such a process, you can approximate its entropy this way.

This is not the same as lewellen's suggestion. Suppose for example that your string is $0101010101$. This string is easy to compress, but the entropy of its empirical distribution is large. The reason for this discrepancy is that the characters in the string are not independent. In fact, each character is determined by the previous one. That just fits the Markov chain model.

  • $\begingroup$ Let $G(S_i)$ be the number of bits in some compression of string $i$. Then, you can compare $S_1$ and $S_2$ by examining the ratio $\frac{G(S_1) + G(S_2)}{G(S_1 \| S_2)}$, where $\|$ denotes simple concatenation. See scottaaronson.com/blog/?p=791 for a nice discussion. $\endgroup$ – rphv Oct 11 '12 at 23:11

Shannon Entropy has a well defined calculation that can be computed that will approximate Kolmogorov Complexity.

I suggest you read up on the two in depth here: http://homepages.cwi.nl/~paulv/papers/info.pdf

  • $\begingroup$ I tried that, but it turned out that it is not really useful for me. I will have the same H value for these sequences AAABBBCCC and ABCABCABC and ACCCBABAB and BBACCABAC $\endgroup$ – oleksii May 20 '11 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.