AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

gleiche Zahlenfolgen im Array untersuchen

Offene Frage von "Sendrix"
Ein Thema von Sendrix · begonnen am 5. Okt 2011 · letzter Beitrag vom 16. Okt 2011
Antwort Antwort
Seite 3 von 4     123 4   
Jumpy

Registriert seit: 9. Dez 2010
Ort: Mönchengladbach
1.717 Beiträge
 
Delphi 6 Enterprise
 
#21

AW: gleiche Zahlenfolgen im Array untersuchen

  Alt 6. Okt 2011, 08:58
Hallo Ralph,

vielen Dank für Deine Hilfe. Leider komme ich nicht ganz klar mit Deiner Lösung.
Ich verstehe das so.

Du legst eine Stringliste an und gehst für jedes Element des Arrays der Tiefe entsprechend durch das Array und hängst die Elemente in der Kettenliste aneinander.
Dann überprüfst Du in InListe ob die Kette in der Kettenliste schon vorhanden ist. Wenn nein dann schreibst Du Kette in die Kettenliste.

Ich versteh das so nicht ganz, könntest Du mir das bitte ein wenig erklären?

Sendrix(Sebastian)
Hallo Sebastian,
ich spar mir mal die Mühe, da zum einen meine Variante in jedem Fall mehr liefert als du eigentlich brauchst, nämlich alle möglichen Kombinationen und Längen von Sequenzen und zum anderen die Lösung von Sir Rufo auf der selben Kernidee beruht aber professioneller umgesetzt ist. Die Verwendung von Bytesequenzen (TBytes)(wußte gar nicht das es sowas gibt) erspart das mühsame Rumgetrickse mit Ketten in Stringlisten.

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

Es ist glaub ich noch nicht ganz klar geworden, welches Verhalten du eigentlich möchtest, was du genau finden möchtest, vor allem da es einige potentiell interessante Fälle gibt, wie z.B. den von Medium in #18.
Ralph

Geändert von Jumpy ( 6. Okt 2011 um 09:51 Uhr)
  Mit Zitat antworten Zitat
BoolString

Registriert seit: 2. Feb 2009
Ort: Varel
70 Beiträge
 
RAD-Studio 2009 Pro
 
#22

AW: gleiche Zahlenfolgen im Array untersuchen

  Alt 6. Okt 2011, 09:52
Bezug nehmend auf die Beiträge #12, #16, #18 wird im allgemeinen erst eine 2d Ergebnismatrix erzeugt und in dieser werden dann Diagonalen (einer eintsprechenden Intensität) abseits der Hauptdiagonale gesucht. Die Länge der Diagonalen gibt die Anzahl der aufeinanderfolgenden Elemente wieder, der Abstand von der Hauptdiagonale (senkrecht zu den Achsen) die Distanz der ähnlichen/identischen (Teil-)Sequenzen; ähnlich wie man es in Beitrag #16 sehen kann...

Das Problem der Selbstähnlichkeiten/Teilmusterrekurrenzen bleibt bestehen. Man kann beliebig viele Kombinationen konstruieren, bei denen ein entsprechendes System mehr Informationen zur Erzeugung deiner 'richtigen' Lösung benötigt. Falls du alle Ähnlichkeiten haben willst, bleibt dir eigentlich nur die Geschichte mit der 2d Matrix -> Hier (Figure 6).

Jan
  Mit Zitat antworten Zitat
Benutzerbild von Sir Rufo
Sir Rufo

Registriert seit: 5. Jan 2005
Ort: Stadthagen
9.454 Beiträge
 
Delphi 10 Seattle Enterprise
 
#23

AW: gleiche Zahlenfolgen im Array untersuchen

  Alt 6. Okt 2011, 10:01
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
Kaum macht man's richtig - schon funktioniert's
Zertifikat: Sir Rufo (Fingerprint: ‎ea 0a 4c 14 0d b6 3a a4 c1 c5 b9 dc 90 9d f0 e9 de 13 da 60)
  Mit Zitat antworten Zitat
Sendrix

Registriert seit: 5. Okt 2011
9 Beiträge
 
#24

AW: gleiche Zahlenfolgen im Array untersuchen

  Alt 6. Okt 2011, 17:37
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)
  Mit Zitat antworten Zitat
Jumpy

Registriert seit: 9. Dez 2010
Ort: Mönchengladbach
1.717 Beiträge
 
Delphi 6 Enterprise
 
#25

AW: gleiche Zahlenfolgen im Array untersuchen

  Alt 7. Okt 2011, 09:45
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.
Ralph
  Mit Zitat antworten Zitat
Benutzerbild von ibp
ibp

Registriert seit: 31. Mär 2004
Ort: Frankfurt am Main
1.511 Beiträge
 
Delphi 7 Architect
 
#26

AW: gleiche Zahlenfolgen im Array untersuchen

  Alt 7. Okt 2011, 11:33
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
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#27

AW: gleiche Zahlenfolgen im Array untersuchen

  Alt 7. Okt 2011, 15:01
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
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#28

AW: gleiche Zahlenfolgen im Array untersuchen

  Alt 7. Okt 2011, 19:16
Hab auch noch einen:

Delphi-Quellcode:
function FindSubList (const SubList, List: TStringList; const Index: integer): integer;
var
  I, J, A, B: integer;
begin
  Result:= 0;
  A:= List.Count;
  B:= SubList.Count;
  I:= Index;
  if I < 0 then Exit;
  if B = 0 then Exit;
  while (Result = 0) and (I <= A-B) do
  begin
    J:= 0;
    if (List[I] = SubList[J]) then
    begin
      while (J < B-1) and (List[I+J+1] = SubList[J+1]) do Inc(J);
      if J = B-1 then Result:= B;
    end;
    Inc(I);
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  SubList, List: TStringList;
  I, J, K, N, A: integer;
  Result: string;
begin
  N:= 0;
  Result:= '';

  List:= TStringList.Create;
  List.Add('1');
  List.Add('2');
  List.Add('3');
  List.Add('4');
  List.Add('9');
  List.Add('8');
  List.Add('7');
  List.Add('1');
  List.Add('2');
  List.Add('3');
  List.Add('4');
  List.Add('6');
  List.Add('2');
  List.Add('3');
  List.Add('4');
  List.Add('9');
  List.Add('8');
  List.Add('7');

  SubList:= TStringList.Create;
  for I:= 0 to List.Count-2 do
    for J:= I+1 to List.Count-1 do
    begin
      SubList.Clear;
      for K:= I to J do SubList.Add(List[K]);
      A:= FindSubList(SubList, List, J);
      if A > N then
      begin
        N:= A;
        Result:= SubList.Text;
      end;
    end;
  SubList.Free;

  List.Free;

  ShowMessage ('Tiefe= '+IntToStr(N)+#13+Result);
end;

Geändert von Bjoerk ( 7. Okt 2011 um 20:07 Uhr) Grund: Ausgabe
  Mit Zitat antworten Zitat
Sendrix

Registriert seit: 5. Okt 2011
9 Beiträge
 
#29

AW: gleiche Zahlenfolgen im Array untersuchen

  Alt 8. Okt 2011, 14:37
Hallo,

vielen Dank für eure rege Beteiligung. Ich mußte das ein oder andere im Netz erstmal nachlesen um überhaupt verstehen zu können was sich dahinter verbirgt.

Zur Frage von Jumpy aus Beitrag #25 : Es soll tatsächlich mit dem nächsten Element fortgefahren werden, also Element für Element, in Deinem Beitrag Möglichkeit B. Wenn aber eine Folge eine (kleinere)Teilfolge einer anderen, bereits vorhandenen Folge ist, was im unteren Beispiel von Jumpy bei elementweiser vorgehensweise so wäre, dann ist diese Teilfolge nicht relevant.

Ich bleibe beim Beispiel von Jumpy:
1 2 3 4 9 8 7 1 2 3 4 6 2 3 4 9 8 7

1234 -> 1234
234987 -> 234987
34987 -> 34987 TeilFolge von 234987 damit nicht relevant
4987 -> 4987 TeilFolge von 234987 damit nicht relevant
987 -> 987 TeilFolge von 234987 damit nicht relevant
87 - > 87 TeilFolge von 234987 damit nicht relevant

weiter mit der 7 -> Keine Folge
weiter mit der 1 -> Keine Folge

234 -> 234 TeilFolge von 234987 damit nicht relevant
34 -> 34 TeilFolge von 234987 damit nicht relevant

weiter mit der 4 -> Keine Folge
weiter mit der 6 -> Keine Folge
weiter mit der 2 -> Keine Folge
weiter mit der 3 -> Keine Folge
weiter mit der 4 -> Keine Folge
weiter mit der 9 -> Keine Folge
weiter mit der 8 -> Keine Folge
weiter mit der 7 -> Keine Folge


In dem Beispiel liegen also effektiv 2 Folgen vor.
Es soll so lange gesucht werden bis sich die Folgen nicht mehr gleichen. Suche immer nur in eine Richtung.

Danke auch für den Sourecode. Die schaue ich mir alle an und lerne dabei auch ne Menge. Den SoureCode von Sir Rufo muß ich erst noch ein wenig anpassen da ich noch mit Delphi 5 arbeite. Beim Code von blauweis hab ich festgestellt das er sehr lange sucht und auch findet was er soll, irgendwo hab ich da eventuell auch einen Fehler eingebaut glaube ich, bei Array > 250 Elemente gehts bei mir nicht weiter und das Programm kommt nicht zurück. Den letzten Code von Bjoerk schau ich mir noch an. Ich muß dazu sagen das ich die Codes damit nicht bewerten möchte, das könnte ich gar nicht beurteilen, ich wollte damit nur ausdrücken das ich mich intensiv damit beschäftige und dabei verschiedene Methodenkennenlerne.

Vielen Dank und schönes Wochenende,
Sendrix(Sebastian)
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#30

AW: gleiche Zahlenfolgen im Array untersuchen

  Alt 8. Okt 2011, 23:36
Wenn du alle Results haben möchtest, dann kann man z.B. die bereits gefundenen aus der Liste rauslöschen.

Delphi-Quellcode:
function FindSubList(const SubList, List: TStringList; var Index: integer): integer;
var
  I, J, A, B: integer;
begin
  Result:= 0;
  A:= List.Count;
  B:= SubList.Count;
  I:= Index;
  if I < 0 then Exit;
  if B = 0 then Exit;
  if B > A then Exit;
  while (Result = 0) and (I <= A-B) do
  begin
    J:= 0;
    if (List[I] = SubList[J]) then
    begin
      while (J < B-1) and (List[I+J+1] = SubList[J+1]) do Inc(J);
      if J = B-1 then
      begin
        Result:= B;
        Index:= I;
      end;
    end;
    Inc(I);
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  SubList, List: TStringList;
  I, J, K, N, N1, J1, Index: integer;
  Result: string;
  done: boolean;
begin
  List:= TStringList.Create;
  SubList:= TStringList.Create;
  try
    List.Add('1');
    List.Add('2');
    List.Add('3');
    List.Add('4');
    List.Add('9');
    List.Add('8');
    List.Add('7');
    List.Add('1');
    List.Add('2');
    List.Add('3');
    List.Add('4');
    List.Add('6');
    List.Add('2');
    List.Add('3');
    List.Add('4');
    List.Add('9');
    List.Add('8');
    List.Add('7');
    repeat
      N:= 1;
      Result:= '';
      for I:= 0 to List.Count-2 do
        for J:= I+1 to List.Count-1 do
        begin
          SubList.Clear;
          for K:= I to J do SubList.Add(List[K]);
          J1:= J;
          N1:= FindSubList(SubList, List, J1);
          if N1 > N then
          begin
            N:= N1;
            Index:= J1;
            Result:= SubList.Text;
          end;
        end;
      done:= true;
      if N > 1 then
      begin
        ShowMessage('Tiefe= '+IntToStr(N)+#13+Result);
        done:= false;
        for I:= Index to N+Index-1 do List.Delete(Index);
      end;
    until done;
  finally
    List.Free;
    SubList.Free;
  end;
end;
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 06:47 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf