Mustererkennung - Markierte Stellen in String

    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

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

    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?

    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

    computer says nooooohhhh!

    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?

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

    640K ought to be enough for anybody. :eek2:

    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.

    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 ?

    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!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!

Benutzerkonto erstellen Anmelden