Wie misst man die Komplexität eines Strings?

8

Ich habe ein paar lange Strings (~ 1.000.000 Zeichen). Jede Zeichenfolge enthält nur Symbole aus dem definierten Alphabet, z. B.

%Vor%

Beispielzeichenfolgen

%Vor%

Q Mit welchen Maßnahmen kann ich die Komplexität dieser Strings quantifizieren? Ich kann sehen, dass S1 weniger komplex ist als S3, aber wie kann ich das programmatisch von .NET aus machen? Jeder Algorithmus oder Punkt auf das Werkzeug / die Literatur würde sehr geschätzt werden.

Bearbeiten

Ich habe versucht Shannon Entropie, aber es stellte sich heraus, dass es nicht wirklich nützlich für mich ist. Ich habe denselben H Wert für diese Sequenzen AAABBBCCC und ABCABCABC und ACCCBABAB und BBACCABAC stark>

Das habe ich getan     
oleksii 21.05.2011, 20:55
quelle

1 Antwort

11

Das Komprimieren der Strings mithilfe von Standardtechniken wie z. B. zip gibt einen guten Hinweis auf die Komplexität.

Gute Kompressionsrate ≈ geringere Komplexität
Schlechte Kompressionsrate ≈ höhere Komplexität

    
aioobe 21.05.2011, 20:57
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Kann JRebel Änderungen in Maven-Abhängigkeiten erneut bereitstellen?