Variabilität einer Symbolfolge bewerten

[Jay1980]

volkard schrieb:

Sind AAAAAABBBC und AABBBAAAAC gleich?

Ja! Anordnung ist nicht entscheidend.

AAAAAB und EEEEED sollen auch den gleichen Score liefern!

[CStoll]

Und wie sieht es aus mit "AAAAAB" vs. "AAABBB"?

[volkard]

Jay1980 schrieb:

volkard schrieb:

Sind AAAAAABBBC und AABBBAAAAC gleich?

Ja! Anordnung ist nicht entscheidend.

AAAAAB und EEEEED sollen auch den gleichen Score liefern!

Gut.
Schau mal, ob http://de.wikipedia.org/wiki/Entropie_(Informationstheorie) in die gewünschte Richtung geht.

[Jay1980]

Unterschiedlich .... je mehr gleiche Symbole, desto 'besser'.

[icarus2]

Ich bin mir nicht ganz sicher, ob ich die Anforderung an den Algorithmus richtig verstanden habe. Aber wie wärs mit der Levenshtein-Distanz?

Das Problem drüfte sein, dass die Reihenfolge der Zeichen keine Rolle spielt. Das könntest du wahrscheinlich mit Sortieren der Zeichenkette beheben.

[Jay1980]

Hähä mit der Entropie muss ich mich schon genug befassen, ich hoffte auf eine einfachere, leichter nachvollziehbare Score-Ermittlung.

[Jay1980]

icarus2 schrieb:

Ich bin mir nicht ganz sicher, ob ich die Anforderung an den Algorithmus richtig verstanden habe. Aber wie wärs mit der Levenshtein-Distanz?

Das Problem drüfte sein, dass die Reihenfolge der Zeichen keine Rolle spielt. Das könntest du wahrscheinlich mit Sortieren der Zeichenkette beheben.

Distanz denke ich geht in die falsche Richtung, ich will die beiden Strings nicht vergleichen, sondern nur bewerten. Vielleicht sollte ich für einen Score einfach die Menge der unterschiedlichen Symbole zählen und zur Stringlänge ins Verhältnis setzen ... das klingt mir aber doch etwas 'ungenau'.

[CStoll]

Jay1980 schrieb:

Distanz denke ich geht in die falsche Richtung, ich will die beiden Strings nicht vergleichen, sondern nur bewerten. Vielleicht sollte ich für einen Score einfach die Menge der unterschiedlichen Symbole zählen und zur Stringlänge ins Verhältnis setzen ... das klingt mir aber doch etwas 'ungenau'.

Das würde auf den Ansatz von ipsec hinauslaufen - und nach der Berechnung wären AAAB und AABB gleich gut (enthalten beide zwei verschiedene Symbole bei einer Gesamtlänge von 4).

Aber den String in eine Liste von Buchstaben-Häufigkeiten zu zerlegen wäre eventuell ein guter Ansatz - danach kannst du z.B. die maximale oder mittlere Häufigkeit verwenden (oder auch die Entropie berechnen).

[volkard]

Jay1980 schrieb:

Distanz denke ich geht in die falsche Richtung, ich will die beiden Strings nicht vergleichen, sondern nur bewerten. Vielleicht sollte ich für einen Score einfach die Menge der unterschiedlichen Symbole zählen und zur Stringlänge ins Verhältnis setzen ... das klingt mir aber doch etwas 'ungenau'.

Ja, das wäre ja nur das addieren der relativen Wahrscheinlichkeiten.

Symbolfolge 1:
6 x A; 3 x B; 1 x C;

Symbolfolge 2:
3 x D; 2 x E; 1 x F; 1 x A; 1 x G 1 x K 1 x L

Oder
Symbolfolge 1:
6/10 3/10 1/10
Summe: 1

Symbolfolge 2:
3/10 2/10 1/10 1/10 1/10 1/10 1/10
Summe:1

Vielleicht summiere die Quadrate der relativen Wahrscheinlichkeiten.

Symbolfolge 1:
6/10 3/10 1/10
SummeDerQudrate: 46/100

Symbolfolge 2:
3/10 2/10 1/10 1/10 1/10 1/10 1/10
SummeDerQuadrate: 18/100

[Jay1980]

Danke das mit dem Quadrieren der relativen Wahrscheinlichkeiten klingt gut, das probiere ich mal ...