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 に答える