Mustererkennung - Markierte Stellen in String

entropie

Ich hab' eine Datenstruktur die "markierte" Stellen in einem Text repräsentiert.

Man könnte sich das ganze auch als Array gefüllt mit Nullen (nicht markiert) und Einsen (markiert) vorstellen...

Mein Problem ist:
Wie kann man "Häufungen" von Markierungen feststellen?

So ein Array könnte etwa folgendermaßen aussehen:
{0,0,0,1,1,0,0,1,0,0,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1,0,1,1,0,1,1,1,0}

Visuelle Typen können sich vorstellen, dass Textstellen mit markiert sind...
Ein Mensch würde hier sofort erkennen, dass Bereiche "roter" sind als Andere. Bei obigem Beispiel wäre die Stellen 22 bis 34 eine Meldung wert.

Ich weiß, dass es klassische Mustererkennung ist, nur konnte ich so nichts passendes finden.

Konkret muss ich das in java implementieren...
Wenn mir jemand einen Hinweis auf einen Algorithmus oder eine Bibliothek geben kann, wäre ich sehr dankbar.

vielen Dank
Martin

JohnFoo

Häufungen? Meinst du die Anzahl der markierten Gruppen zählen? Falls du das meinst könntest du dir einfach ein Flag "marked" auf "true" setzen wenn du einen 1er Bereich betrittst, stellst ihn wieder zurück sobald du die nächste 0 ausliest und erzählst den Zähler der Markierungen um 1.

Oder ich hab' dich missverstanden ..

entropie

Stellen zählen ist zu wenig...

Ich will eine Funktion, die mir die Bereiche ausgibt, wo auffällig viel markiert worden ist... ob das jetzt eine Markierung ist oder mehere ist egal.

Die Ausgabe könnte in dieser Art erfolgen:
Zwischen Stelle 1500 und Stelle 2000 sind 75% markiert -> ergo ist sie verdächtig.

Ich arbeite eh schon an einem Verfahren, das den betrachteten Bereich in Relation zu den enthaltenen markierten Stellen in Relation setzt, aber das ist mir nicht "intelligent genug.

Hm. Jemand eine Idee?

Martinez

ich glaub du musst die groesse des zu untersuchenden bereichs festlegen. sonst wirds kompiziert. ich mein in zB

Code

0001010011001110010

sind global gesehen weniger 1er als 0er, betrachetet man es aber lokal (sagen wir -/+ 2) sind im Bereich der drei aufeinanderfolgenden 1er eben diese in Ueberzahl.
Was genau soll den der algo untersuchen?

lg

entropie

Im Prinip ist genau das das Thema, ich tu mir halt schwer damit, es genau zu formulieren.

Ich will quasi eine künstliche Intelligenz, die am besten ohne zusätzliche Informationen so ein Array klassifiziert und Ausspuckt.

Aber wahrscheinlich wird es am einfachsten sein, so Parameter wie Mindestlänge und Mindestanteil an Einsen festzulegen.

Einsprüche?

Swoncen

Du MUSST definieren, was eine Häufung ist und wie groß bzw. klein die Bereiche sein sollen, sonst kannst du ja nicht sagen, dass es eine Häufung ist. Was sind schon viele einser? Ich kann sagen 2 einser hintereinander is schon eine Häufung, oder 100 Einser von 110 Stellen ist eine Häufung. Besonders intelligent muss das ja nicht sein..

a9bejo

Ich denke es wird einfacher, wenn man die Haeufung/Population mit der Frage formuliert: "Wieviele Nuller hintereinander sind denn innerhalb einer Population erlaubt?" Man muss nur definieren was keine Markierung ist und da die Grenzen ziehen. Eine markierte Stelle darf dann beliebig lang oder kurz sein.

Mit diesem Ansatz komme ich z.B. auf diese Loesung. Wenn die Anzahl der erlaubten Nuller in einer Population dem Programm nicht als Argument mitgegeben werden, dann berechne ich sie durch:

N = F(0) / F(1)

Wobei N die erlaubten Nuller innerhalb einer Population ist und F(X) die Laenge der groessten aufeinanderfolgenden Sequenz von X.

NickK

Zitat von Swoncen

Du MUSST definieren, was eine Häufung ist und wie groß bzw. klein die Bereiche sein sollen, sonst kannst du ja nicht sagen, dass es eine Häufung ist. Was sind schon viele einser? Ich kann sagen 2 einser hintereinander is schon eine Häufung, oder 100 Einser von 110 Stellen ist eine Häufung. Besonders intelligent muss das ja nicht sein..

wie wärs mit dem bestimmen aller häufungen, ordnen derselben nach länge der häufung und melden der ersten 10 prozent ?

oder melden aller häufungen die länger als die durchschnittliche häufungslänge sind ?

a9bejo

Zitat von NickK

wie wärs mit dem bestimmen aller häufungen, ordnen derselben nach länge der häufung und melden der ersten 10 prozent ?

oder melden aller häufungen die länger als die durchschnittliche häufungslänge sind ?

Bekommst du dann nicht immer als erstes Ergebnis den gesamten String zurueck? Weil der ist ja immer die laengste Haeufung. Ausserdem ist, wenn ich mich jetzt nicht irre, das Berechnen aller moeglichen Haeufungen ein Theta(n^2) Problem. Meine Heuristik von oben war z.B. linear.

Jetzt mitmachen!