gleiche Zahlenfolgen im Array untersuchen

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