CODEWITHSUNDEEP
.netalgorithmstringcomplexity-theoryapproximation
oleksii
oleksii

Reputation: 35925

How to measure complexity of a string?

I have a few long strings (~ 1.000.000 chars). Each string only contains symbols from the defined alphabet, for example

A = {1,2,3}

Sample strings

string S1 = "1111111111 ..."; //[meta complexity] = 0
string S2 = "1111222333 ..."; //[meta complexity] = 10
string S3 = "1213323133 ..."; //[meta complexity] = 100

Q What kind of measures can I use to quantify the complexity of these strings? I can see that S1 is less complex than S3, but how can I do that programmatically from .NET? Any algorithm or point to the tool/literature would be greatly appreciated.

Edit

I tried Shannon entropy, 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

This is what I ended up doing

Upvotes: 10

Views: 1587

Answers (1)

aioobe
aioobe

Reputation: 421160

Compressing the strings using standard techniques such as zip gives a good indication of the compexity.

Good compression rate ≈ lower complexity
Bad compression rate ≈ higher complexity

Upvotes: 13

Related Questions