gleiche Zahlenfolgen im Array untersuchen

[Sir Rufo]

Zitat von Jumpy:

Voraussetzung ist natürlich, dass du nur Bytegroße Zahlen in deinem Array hast, aber deine genannten Beispiele lassen darauf schließen.

Ich habe bewusst darauf geachtet eben keine Konvertierung der Daten vorzunehmen.
Damit ist hierfür sogar eine generische Umsetzung denkbar, die dann beliebige Datentypen verarbeiten kann

[Sendrix]

Also zunächst möchte ich mich unbedingt bei allen bedanken für eure Hilfsbereitschaft, die ganzen Codebeispiele und Lösungsvorschläge. Finde ich wirklich sehr nett von euch. Ich war da wirklich in einer Sackgasse und jetzt habe ich viele verschiedene Ansätze zum ausprobieren. Hab mir alles sorgfältig durchgelesen allerdings noch nicht alles verstanden bin aber aktuell bei der Umsetzung.

Auch die Dot-Plot's finde ich sehr interessant, vielen Dank für den Hinweis, wenn auch erstmal viel Stoff.

Die 2 DMatrix ist auch ein vielversprechender Ansatz den ich mir aber ganz ehrlich gesagt nicht zutraue umzusetzen.

Zu der Frage der Sequenzen und das mehrfach "verwenden" von Elementen habe ich folgende Definition bekommen.

Eine Folge gilt als Folge wenn mindestens 2 aufeinander folgende Elemente übereinstimmen (also in der gleichen Reihenfolge erneut vorkommen). Die Folge soll solange fortgesetzt werden wie Elemente sich in den Folgen (ursprüngliche Folge, gefunden Folge) gleichen. Endelement kann nicht Startelement sein, das dürfte bedeuten das mehrfach Verwendung nicht erlaubt ist.

Das Beispiel war: 1 2 3 1 2 3 1 Nach der mir vorliegenden Problembeschreibung gilt
dann 2 x 1 2 3 und 1 x 1.

Ich bin mir aber auch nicht sicher ob meine Auftraggeber das alles so bedacht haben wie Ihr. Deswegen werde ich da nochmal Rücksprache halten dank eurer Anmerkung. Bisher gehe ich davon aus das es so sein soll wie ich es oben beschrieben habe. Sollte es sich doch anders ergeben, wovon ich momentan aber nicht ausgehe, schreib ich dazu hier noch eine Ergänzung.

Jetzt werde ich mal eine Lösung implementieren und mit verschiedenen beireits vorhandenen Daten testen. Bin gespannt was dabei rauskommt. Wenn es euch nicht stört werd ich das dann hier im Thread mal posten.

Viele Dank nochmal an alle!
Sendrix(Sebastian)

[Jumpy]

Zitat von Sendrix:

Jetzt werde ich mal eine Lösung implementieren und mit verschiedenen beireits vorhandenen Daten testen. Bin gespannt was dabei rauskommt. Wenn es euch nicht stört werd ich das dann hier im Thread mal posten.

Im Gegenteil. Ich denke, dass alle die hier mitgeholfen haben, gerne wissen wollen was rauskommt.

Bzgl. der Sequenzen nochmal ein Beispiel

1 2 3 4 9 8 7 1 2 3 4 6 2 3 4 9 8 7

Du startest mit der 1 und kriegst die Kette 1 2 3 4 und findest die zweimal.

Wie gehts dann weiteer?

A)
Machst du dann mit dem nächsten Element nach der Kette weiter? Das wäre dann die 9 und du findest die Kette 9 8 7 (auch 2x).

oder:

B)
Gehst du aber Element für Element durch, d.h. jedes Element kann start einer Kette sein, würdest du als zweites nicht mit der 9 sondern der 2 weitermachen. Da findest du dann die Kette 2 3 4 9 8 7 (2x). Die längste Kette in dem Beispiel überhaupt, die dir bei Methode A aber entgangen wäre.

[ibp]

Zitat von Jumpy:

Bzgl. der Sequenzen nochmal ein Beispiel

1 2 3 4 9 8 7 1 2 3 4 6 2 3 4 9 8 7

Du startest mit der 1 und kriegst die Kette 1 2 3 4 und findest die zweimal.

Wie gehts dann weiteer?

im ersten Post spricht er bei den Ketten von Nachfolgern!

Also:
1234
1234
234

[negaH]

das wonach du suchtst nennt sich mathematisch Korrelation, hier genauer Autokorrelation = AKF. Je nachdem wie du diese benutzt kanst du exakte Übereinstimmungen finden oder eine Aussage darüber treffen wie hoch die Übereinstimmung eines Musters mit dem gesuchten Muster ist und wo im Datenstrom das gesuchte Muster auftaucht mit einer gegebenen Übereinstimmung zum Suchmuster.

In deinem Fall möchtest du 100%'tige Übereinstimmung zum Suchmuster haben.

Alle bisherigen Vorschläge hier wurden mit NP-vollständigen Algorithmen umgesetzt. Die AKF kann aber wie bei der DFT mit Hilfe der FFT (Teile&Herrsche-Taktik) beschleunigt werden. Zb. mit Hilfe der Walsh-Hadamard-Transfomation kann man die Korrelation und damit das Suchen des Musters von O(n^2) auf O(n * ln(n)) reduzieren.

Naja und dann gibts noch die Wavelets und auch die FFT mit der man solche Mustervergleiche ebenfalls effizienter durchführen kann.

Gruß Hagen

[BUG]

Zitat von negaH:

NP-vollständigen Algorithmen umgesetzt

Eine der seltenen Gelegenheiten Hagen mal zu korrigieren
Entscheidungsprobleme können in NPC sein.
Für Algorithmen gibt es nur Laufzeiten.

Zitat von Sendrix:

Noch was anderes:
Immer wenn ich mich im Forum anmelde und auf einen Beitrag antworten möchte lande ich wieder bei der Anmeldung obwohl ich bereits in der OnlineListe zu sehn bin. Irgendwann wenn ich dann zum x ten mal auf Anmelden geklickt hab klappts dann.

Cookies an? Evtl. mal das "angemeldet bleiben" Kästchen aktivieren.