.net - 如何衡量字符串的复杂度？

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

Q 我可以使用什么样的措施来量化这些字符串的复杂性？我可以看到 S1 没有 S3 复杂，但我如何从 .NET 以编程方式做到这一点？任何算法或工具/文献的指向将不胜感激。

编辑

我尝试了香农熵，但事实证明它对我来说并不是很有用。我将对这些序列 AAABBBCCC 和 ABCABCABC 以及 ACCCBABAB 和 BBACCABAC 具有相同的H 值强>

---

This is what I ended up doing

Answer 1

使用 zip 等标准技术压缩字符串可以很好地指示复杂性。

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