Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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. –  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

share|improve this answer
    
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 –  oleksii May 20 '11 at 17:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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