如何衡量字符串的复杂性？

Question

我有一些长串(约1.000.000个字符).例如,每个字符串仅包含来自定义的字母表的符号

A = {1,2,3}

示例字符串

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

问:我可以使用哪种措施来量化这些字符串的复杂性？我可以看到S1没有S3那么复杂,但我怎么能以编程方式从.NET做到这一点？任何算法或指向工具/文献将非常感激.

编辑

我试过Shannon熵,但事实证明它对我来说并不是真的有用.我将对这些序列AAABBBCCC和ABCABCABC以及ACCCBABAB和BBACCABAC具有相同的H值

---

这就是我最终做的事情

Answer 1

使用诸如zip之类的标准技术压缩字符串可以很好地指示复杂性.

压缩率好≈低复杂度
压缩率差≈更高的复杂度