Variabilität einer Symbolfolge bewerten

[Jay1980]

Servus,

ich habe zwei Wörter, etwa: AAAAAABBBC und DDDEFAGEKL . Jetzt suche ich ein Verfahren, das beiden Wörtern einen Score gibt. Der Score soll die Verteilung widerspiegeln, wie viel Variation im Wort steckt.

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; ...

=> Symbolfolge 1 soll als 'gefestigter' gescort werden!

Welche Algorithmen gibt es für derlei Probleme?

Danke vorab.

[volkard]

Sind AAAAAABBBC und AABBBAAAAC gleich?

[ipsec]

Wenn ich dich richtig verstanden habe, reicht wohl ein einfaches unique mit anschließenden Längenvergleich (das kürzere entstehende Wort hat weniger Variationen). Wenn die Vergleichswörter unterschiedliche Längen haben, muss man die Längen nach dem unique natürlich relativ zu den Originallängen setzen.
Ein darauf aufbauendes, sehr ähnliches Verfahren: man zähle die Stellen in jedem Wort, wo zwei unterschiedliche Buchstaben aufeinanderfolgen und vergleiche diese Anzahlen - im Prinzip genau das gleiche wie unique , möglicherweise aber etwas performanter, da nichts kopiert werden muss.

[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 ...