9

我有几个长字符串（~ 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值

这就是我最终做的

4

1 回答 1

13

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

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

于 2011-05-21T20:57:27.807 回答