gleiche Zahlenfolgen im Array untersuchen

[Sendrix]

Guten Tag,

ich bin zwar kein Delphi Neuling mehr, allerdings treffe ich immer wieder auf Problemstellungen die ich alleine leider nicht lösen kann.

Aktuell habe ich das Problem das ich Arrayelemente miteinander vergleichen muß. Grundsätzlich natürlich keine große Aktion das eine mit dem anderen Element zu vergleichen.

In diesem Fall handelt es sich jedoch um Zahlenfolgen die in einem unsortierten Array of Byte verglichen werden sollen. Unsortiert weil die Position bzw. die Zahlenreihenfolge der Zahlen in dem Array wichtig sind bei der Weiterverarbeitung.

Beispiel: Als erstes soll untersucht werden ob das erste Element des Arrays ein weiteres mal im Array vorhanden ist. Wenn nein dann soll mit dem zweiten Element neu begonnen werden. Wenn ja soll untersucht werden ob das Element das auf das erste Element im Array folgt auch bei dem gefundenen Element als Nachfolger vorhanden ist. Wenn ja geht es dann weiter mit dem dritten Element. Ist das dritte Element das gleiche wie bei dem gefundenen Element wo bereits das erste und zweite Element übereinstimmen. Das soll dann immer so weitergehen bis zu definierbaren Tiefe.

Man erhält dann letztlich eine Übersicht ob Zahlenfolgen/ketten mehrfach in einem Array vorhanden sind und mit welcher Tiefe die Folgen identisch miteinander sind.

Ich habe es bereits mit verschachtelten For Schleifen versucht aber bei der Untersuchung ab der dritten Zahl komme ich nicht mehr weiter. ich verirre mich irgendwie in den Schleifen. Als nächstes habe ich versucht erst eine Kopie des Arrays anzulegen und mir dadurch mehr Übersicht erhofft. Allerdings komme ich auch hier nicht weiter. Immer wenn eine Zahlenfolgen doppelt vorhanden ist muß ja der nächste Wert verglichen werden und dadurch lande ich immer wieder bei einer unübersichtlichen und nicht funktionierenden For Schleifen Variante. Es gelingt mir auch nicht das ganze bis zu einer beliebigen Tiefe durchzuführen da ich für jede weitere Zahl eine neue For Schleife benötige.

Hoffe ich konnte das Problem einigermaßen verständlich beschreiben.

Ich glaube das ich mich ein wenig verirrt habe vor lauter Schleifen und würde mich über Hilfe sehr freuen.

Viele Grüße,
Sendrix

[Darlo]

Zitat:

Zitat von Sendrix (Beitrag 1128576)

Wenn ja soll untersucht werden ob das Element das auf das erste Element im Array folgt auch bei dem gefundenen Element als Nachfolger vorhanden

Tut mir leid, ich verstehe es auch nach dem fünften mal lesen nicht :?:

[DeddyH]

Gott sei Dank, ich dachte schon, ich sei zu blöd und nur ich würde das nicht verstehen.

[Jumpy]

Hallo hier mal als Denkansatz, so wie ich das Problem verstanden habe:
Array heißt bei mir das Hauptarray, das irgendwie übergeben wird oder global ist.
Tiefe, hier :=5 ist die maximale Ketten-Tiefe.

Edit: Statt der InListe-Funktion kann man auch eine Find-Funktion o.ä. der TStringList nehemn. Hab gerade kein Delphi, drum weiß ich nit, obs da was gab und wie das dann ggf. heißt.

Edit: Achja, hab vergessen die Ergebnisse auszugeben, die ja dann in den beiden Stringlisten stehen.

Delphi-Quellcode:

var:
  i, j, k, l :Integer;
  Tiefe : Integer;
  Kette : String
  Kettenliste:TStringlist;
  Anzahlliste:TStringlist;
function InListe(const KT : String):Boolean;
begin
  Result:=false;
  For l = 0 To Kettenliste.Count-1 do
    if Kettenliste[l]=Kette then Result:=true;
end
function Vorkommenszahl(const KT : String):Integer;
begin
  //Die Funktion ist mir aus dem Kopf zu kompliziert:
  //Kette in Elemente zerlegen, Anz. Elemente bestimmen
  //Elemente in DynArray speichern
  //Das "Hauptarray" Array durchgehen und in Schleifen mit den Elementen von DynArray vergleichen
  //Wenn passende Kette gefunden wird einen Counter hochgezählt
end
begin
Tiefe:=5;
Kettenliste:=TStringlist.Create(nil);
Anzahlliste:=TStringlist.Create(nil);
For i:=0 To Array.Count-1 do
  begin
  For j:=0 To Tiefe-1 do
    begin
    Kette:='';
    For k = 0 to j do
      Kette:=Kette+IntToStr(Array[i+k])+';';
    if not InListe(Kette) then
      begin
      Kettenliste.Add(Kette);
      Anzahlliste.Add(IntToStr(Vorkommenzahl(Kette)))
      end;
    end;
  end;
end;

[Sendrix]

Sorry wenn es doch zu unverständlich war. Ich versuche es einfach mal mit einem kleinen Beispiel.

Ein Array mit 10 Elementen.

1, 2, 3, 4, 5, 9, 2, 3, 5, 9

Das erste Element, die Zahl 1 existiert nur einmal im Array.
Das zweite Element, die Zahl 2 existiert noch ein weiteres mal im Array. Auf das zweite Element, also auf die 2 folgt die Zahl 3. Jetzt muß überprüft werden ob bei der gefundenen Zahl 2 auch die 3 als nächstes Element folgt.
Wenn das so ist muß überprüft werden ob die nächste Zahl vom Anfang des Arrays, in diesem Fall die Zahl 4 auch bei der "bisher gefundenen Zahlenfolge 2, 3, " folgt.

Das Ergebnis wäre also das die Zahlenfolge 2,3, in dem Array mehrfach vorhanden ist.

Es entstehen also Zahlenfolgen die eventuell mehrfach im Array vorkommen.

[Jumpy]

Achso. Dann muss meine obige Lösung dahingehend angepasst werden, das z.B. alle Ketten, die nur aus einem Element bestehen nachher gelöscht werden, sowie auch alle Ketten mit mehr als einem Element, die aber nur einmal vorkommen.

Alternativ kann man natürlich direkt j erst bei 1 anfangen lassen und erst wenn Vorkommenzahl(Kette)>1 ist die Kette in die Liste aufnehmen. Mach das mal:

Delphi-Quellcode:

var:
  i, j, k, l, temp :Integer;
  Tiefe : Integer;
  Kette : String
  Kettenliste:TStringlist;
  Anzahlliste:TStringlist;
function InListe(const KT : String):Boolean;
begin
  Result:=false;
  For l = 0 To Kettenliste.Count-1 do
    if Kettenliste[l]=Kette then Result:=true;
end
function Vorkommenszahl(const KT : String):Integer;
begin
  //Die Funktion ist mir aus dem Kopf zu kompliziert:
  //Kette in Elemente zerlegen, Anz. Elemente bestimmen
  //Elemente in DynArray speichern
  //Das "Hauptarray" Array durchgehen und in Schleifen mit den Elementen von DynArray vergleichen
  //Wenn passende Kette gefunden wird einen Counter hochgezählt
end
begin
Tiefe:=5;
Kettenliste:=TStringlist.Create(nil);
Anzahlliste:=TStringlist.Create(nil);
For i:=0 To Array.Count-1 do
  begin
  For j:=1 To Tiefe-1 do
    begin
    Kette:='';
    For k = 0 to j do
      Kette:=Kette+IntToStr(Array[i+k])+';';
    if not InListe(Kette) then
      begin
      temp:=Vorkommenzahl(Kette);
      if temp>1 then
        begin    
        Kettenliste.Add(Kette);
        Anzahlliste.Add(IntToStr(temp))
        end;
      end;
    end;
  end;
end;

[p80286]

so mal in unreine gedacht,
nimm zwei pointer und laß beide über Deine datenmenge laufen ungefähr so etwas:

Delphi-Quellcode:

p1,p2:^array[0..4] of char;

p1:=@Array[0];
p2:=@array[sucheindexgleich];
if p1^=p2^ then showmessage"Gleiche werte gefunden"

Gruß
K-H

[FredlFesl]

Was ist mit der Sequence
1 2 3 4 1 2 3 4

Welches Ergebnis willst Du?
1234 kommt 2x vor (also nur die längste Subsequenz),
oder
12 kommt 2x vor,
23 kommt 2x vor
34 kommt 2x vor
123 kommt 2x vor
234 kommt 2x vor
1234 kommt 2x vor (also alle Subsequenzen)?

[Sendrix]

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)

[Sendrix]

Hallo FredlFesl,

Danke für Deine Frage, hab ich nicht genau formuliert, sorry. Mir geht es schon darum die längste zusammenhängende, identische Folge herauszufinden.
Das wäre dann also 2 x 1234.

Die, ich nenne Sie mal Zwischenfolgen oder Tiefe (2 x 12 oder 2 x 23 ...) sollen nur dann "erkannt" werden wenn die "Tiefe" bei z.B. 2 oder 3 gleichen aufeinanderfolgenden Elementen beendet werden soll.
Grundsätzlich gilt (1234), also soviele Elemente wie identisch sind, alles andre ist erstmal optional. Mit der Option der variablen Tiefe hab ich es überhaupt noch nicht hinbekommen. Bisher hab ich lediglich geschafft 2 in Folge vorkommende Elemente nochmal im Array zu finden. Bei mehr wie 2 endet es für mich im Schleifenwirrwarr.

Gruß
Sendrix

[Sendrix]

Hallo K-H,

Danke für Deinen Beitrag. Wenn ich das richtig verstehe läuft Dein Vergleich auf den Index des Array hinaus. Es geht aber nicht um den gleichen Index sondern um die gleichen Elemente des Arrays. Es kann ja sein das die Zahlenfolge 1 2 3 4 irgendwo im Array nochmal vorkommt und das herauszufinden ist mein Ziel.

Vieel Grüße,
Sendrix

[BoolString]

Das große Problem ist tatsächlich, wenn man Sequenzen hat, die als Teilsequenzen in einer größeren wieder auftauchen. Das ist ein Standardproblem, z.B. in der Genetik und ein weites Forschungsfeld. Letztlich ist eine visuelle Kontrolle immer ein sehr gutes Hilfsmittel. Ein hier verwendetes Verfahren nennt sich Dot-Plot und sollte nicht mit der gleichnamigen Darstellungsmethode verwechselt werden. Ein paar Algorithmen und Spielzeuge hierzu findest du bei mir unter:

- Hintergrund und Algos
- Software zum Ausprobieren


Für numerische Sequenzen gibt es eine sehr gute Arbeit von Marwan und Co.:

- Recurrence plots
- Graphische Darstellung

Ist vermutlich nicht genau das, was du suchtest, aber vielleicht etwas zum weiter drüber nachdenken/nutzen...

Jan

[blauweiss]

Hallo Sendrix,

ich würde es folgendermaßen angehen:

1. eine Routine (Funktion bzw. Methode falls Du ein Objekt daraus machen willst) "GetStringFromHere"
function GetStringFromHere(StartIndex, TokenCount: integer): string;
-> liefert Konkatenation von "TokenCount" Bestandteilen (natürlich beschränkt durch Listenende) ab StartIndex in der Liste

2. eine Routine "GetMatchIndex"
function GetMatchIndex(OriginIndex, TokenCount: integer): integer;
-> for-Schleife über alle Indizes (OriginIndex aussparen!), Abprüfung auf Gleichheit via GetStringFromHere
-> liefert -1 für keinen Match, ansonsten den Index des Matches

3. eine Routine "GetAnyMatchIndex"
function GetAnyMatchIndex(TokenCount: integer): integer;
-> for-Schleife über alle Indizes, Abprüfung auf Match via GetMatchIndex(Laufvariable, TokenCount)

3. eine Routine "FindBiggestMatch"
function FindBiggestMatch(aList: TStringList): integer;
-> Start mit TokenCount auf großem Wert (aList.Count falls je nur 1 Buchstabe, sonst irgendwas sinnvoll Großes (maximal Length(aList.Text))
-> per while-Schleife runter(!)zählen, um auf Match zu prüfen via GetAnyMatchIndex(TokenCount)

Die Implementation überlasse ich Dir, dürfte ja unschwer sein... 8-)

Gruß
blauweiss

[ibp]

2 Ideen:
1) Wie wäre es denn, wenn du einfach aufeinanderfolgende Sequenzen (n,n+1,n+2,..,n+k) aus deiner Folge in eine gesonderte Liste schreibst, diese sortierst und dann untersuchst?

2) Bitmasken könnte auch eine Überlegung Wert sein!

[blauweiss]

Hab's doch mal eben implementiert, weil es mich selber interessiert hat.

Delphi-Quellcode:

function GetStringFromHere(aList: TStringList;
                           StartIndex, TokenCount: integer): string;
var
  i: integer;
begin
  Result := aList[StartIndex]; // Achtung keine Abprüfung auf < 0 oder > aList.Count-1 ...!!
  for i := StartIndex+1 to StartIndex+TokenCount-1 do
    if (i > aList.Count-1) then
      break
    else
      Result := Result + aList[i];
end;

function GetMatchIndex(aList: TStringList;
                       OriginIndex, TokenCount: integer): integer;
var
  s: string;
  i: integer;
begin
  Result := -1;
  s := GetStringFromHere(aList, OriginIndex, TokenCount);
  for i := 0 to aList.Count-1 do
    if (i <> OriginIndex) then
      if (s = GetStringFromHere(aList, i, TokenCount)) then
        begin
          Result := i;
          break;
        end;
end;

function GetAnyMatchIndex(aList: TStringList;
                          TokenCount: integer): integer;
var
  i: integer;
begin
  Result := -1;
  for i := 0 to aList.Count-1 do
    if (GetMatchIndex(aList, i, TokenCount) <> -1) then
      begin
        Result := i;
        break;
      end;
end;

function FindBiggestMatch(aList: TStringList): integer;
var
  TokenCount: integer;
  MatchIndex: integer;
begin
  Result := 0;
  TokenCount := Length(aList.Text);
  while (TokenCount >= 1) do
    begin
      MatchIndex := GetAnyMatchIndex(aList, TokenCount);
      if (MatchIndex <> -1) then
        begin
          ShowMessage('Größter Match "' + GetStringFromHere(aList, MatchIndex, TokenCount) +
                      '" bei Index ' + IntToStr(MatchIndex) + #13#10 +
                      'Anzahl Zeichen: ' + IntToStr(TokenCount));
          Result := TokenCount;
          break;
        end;
      dec(TokenCount);
    end;
end;

Aufruf z.B.:

Delphi-Quellcode:

  aList := TStringList.Create;
  // aList füllen ... try..except sparen oder auch nicht
  if (FindBiggestMatch(aList) < 1) then
    ShowMessage('Keine Matches gefunden');
  aList.Free;

Gruß
blauweiss

[Klaus01]

Guten Abend,

würde es denn nicht auch schon ausreichen, wenn maximal nach einer 2 Ziffernfolge sucht
und das Array damit in Einzelschritten absucht.

In der angehängten Grafik wird deutlich, dass damit auch größere zusammenhängende Ziffernfolgen finden kann.

Grüße
Klaus

[Sir Rufo]

Wie wäre es damit? ;)

Das sucht alle gleichen heraus und gibt diese in ein Array (die Folge und die gefundene Anzahl).
Die längsten Folgen werden als erstes gefunden. Somit könnte man auch bei einer gefundenen einfach abbrechen.

Delphi-Quellcode:

unit model.ByteFolge;

interface

uses
  SysUtils;

type
  TByteSequence = record
    Sequence : TBytes;
    Count : Integer;
    function AsString : string;
  end;

  TByteSequences = array of TByteSequence;

function FindByteSequences( AByteArray : TBytes; ADepth : Integer = 0 ) : TByteSequences;

implementation

function Match( a, b : TBytes ) : Boolean;
var
  idx : Integer;
begin
  Result := ( Length( a ) = Length( b ) );
  if not Result
  then
    Exit;

  for idx := low( a ) to high( a ) do
    begin
      Result := Result and ( a[idx] = b[idx] );
      if not Result
      then
        Break;
    end;
end;

function IndexOfSequence( ASequence : TBytes; AList : TByteSequences ) : Integer;
var
  idx : Integer;
begin
  Result  := - 1;
  for idx := low( AList ) to high( AList ) do
    begin
      if Match( ASequence, AList[idx].Sequence )
      then
        begin
          Result := idx;
          Break;
        end;
    end;
end;

procedure AddSequence( ASequence : TBytes; var AList : TByteSequences );
var
  idx : Integer;
begin
  idx := IndexOfSequence( ASequence, AList );
  if idx < 0
  then
    begin
      SetLength( AList, Length( AList ) + 1 );
      idx                 := high( AList );
      AList[idx].Sequence := Copy( ASequence, low( ASequence ) );
      AList[idx].Count    := 1;
    end
  else
    begin
      AList[idx].Count := AList[idx].Count + 1;
    end;
end;

function FindByteSequences( AByteArray : TBytes; ADepth : Integer ) : TByteSequences;
var
  lSearchFor :   TBytes;
  lSearchIn :    TBytes;
  lCompare :     TBytes;
  lSearchIndex : Integer;
  lSearchPos :   Integer;
begin
  if ( Length( AByteArray ) div 2 < ADepth ) or ( ADepth = 0 )
  then
    Result := FindByteSequences( AByteArray, Length( AByteArray ) div 2 )
  else if ADepth >= 2
  then
    begin

      for lSearchIndex := low( AByteArray ) to high( AByteArray ) - ADepth * 2 + 1 do
        begin

          lSearchFor := Copy( AByteArray, lSearchIndex, ADepth );

          if IndexOfSequence( lSearchFor, Result ) < low( Result )
          then
            begin

              lSearchIn := Copy( AByteArray, lSearchIndex + ADepth );

              for lSearchPos := low( lSearchIn ) to high( lSearchIn ) - ADepth + 1 do
                begin
                  lCompare := Copy( lSearchIn, lSearchPos, ADepth );
                  if Match( lSearchFor, lCompare )
                  then
                    AddSequence( lSearchFor, Result );
                end;
            end;
        end;

      if ADepth > 2
      then
        Result := FindByteSequences( AByteArray, ADepth - 1 );

    end;
end;

{ TByteSequence }

function TByteSequence.AsString : string;
var
  idx : Integer;
begin
  Result  := '';
  for idx := low( Sequence ) to high( Sequence ) do
    begin
      if Result <> ''
      then
        Result := Result + ', ';
      Result   := Result + IntToHex( Sequence[idx], 2 );
    end;
  Result := '[ ' + Result + ' ] ' + IntToStr( Count );
end;

end.

[Medium]

Noch ein netter Fall: 1 2 3 1 2 3 1

Ist das 2x 1 2 3 und 1x 1
oder 2x 1 2 3 1 wobei die mittlere 1 2-fach verwendet wird?

Die Frage ist also: Darf mehrfach verwendet werden? Kommt auf den Einsatzzweck an, aber das Problem sollte einem bewusst sein.

[Sir Rufo]

Zitat:

Zitat von Medium (Beitrag 1128693)

Noch ein netter Fall: 1 2 3 1 2 3 1

Ist das 2x 1 2 3 und 1x 1
oder 2x 1 2 3 1 wobei die mittlere 1 2-fach verwendet wird?

Die Frage ist also: Darf mehrfach verwendet werden? Kommt auf den Einsatzzweck an, aber das Problem sollte einem bewusst sein.

Ja gute Frage :)

Um das zu finden muss der Start-Index für das lSearchIn geändert werden, dann werden die auch gefunden.

Delphi-Quellcode:

// statt
lSearchIn := Copy( AByteArray, lSearchIndex + ADepth );
// muss dann das genommen werden
lSearchIn := Copy( AByteArray, lSearchIndex + 1 );

[UliBru]

Wie wäre es mit einem etwas anderen Ansatz?
Bei einem Array der Länge n (n sei als gerade Zahl angenommen) könnte es maximal 2 Sequenzen der Länge n/2 geben. Wenn die Sequenzen gleich sind ist auch die Summe gleich.
Um nun die maximale Tiefe festzustellen bildet man ausgehend von n/2 Summanden bis runter zu 2 Summanden die jeweilige Summe. Man muss dann anschliessend nur die Sequenzen vergleichen, die eine gleiche Summe aufweisen.
Bei einer vorgegebenen gewünschten Tiefe x bildet man eben eben gleitend die Summen über x Werte.

Beispiel: Array = 1, 2, 3, 4, 5, 9, 2, 3, 5, 9
Tiefe x = 3
Summenwerte = 6, 9, 12, 18, 16, 14, 10, 17 => alle Werte unterschiedlich, damit x <> 3
Tiefe x = 2
Summenwerte = 3, 5, 7, 9, 14, 11, 5, 8, 14
Es zeigen sich mit 5 und 14 jeweils zwei identische Summen. Die weitere Untersuchung ergibt die Sequenzen 2, 3 und 5, 9.

Es müssen also nur Sequenzen mit gleichen Summen untersucht werden. Natürlich fallen dann Sequenzen mit veränderter Reihenfolge aber gleicher Summe dabei raus.

[Jumpy]

Zitat:

Zitat von Sendrix (Beitrag 1128629)

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.

[BoolString]

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

[Sir Rufo]

Zitat:

Zitat von Jumpy (Beitrag 1128739)

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:shock: 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:

Zitat von Sendrix (Beitrag 1128917)

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:

Zitat von Jumpy (Beitrag 1129016)

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

[Bjoerk]

Hab auch noch einen: 8-)

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;

[Sendrix]

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)

[Bjoerk]

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;

[Sendrix]

Hallo Bjoerk,

Danke für den Source. Probleme hab ich mit dem Verständnis, dem Nachvollziehen der Funktion FindSubList. Wie kommt man auf sowas ? Mir ist das bisher nicht gelungen gedanklich nachzubauen. Funktionieren tut's sehr gut nur kapier ich es nicht ganz und frage mich wie man auf so einen Algorithmus kommt.
Kannst Du mir dazu eventuell ein paar Zeilen zum besseren Verständnis schreiben ?

Danke,

Viele Grüße,
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.

[BUG]

Zitat:

Zitat von negaH (Beitrag 1129132)

NP-vollständigen Algorithmen umgesetzt

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

Zitat:

Zitat von Sendrix (Beitrag 1130335)

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.

[Bjoerk]

Zitat:

Zitat von Sendrix (Beitrag 1130335)

Hallo Bjoerk,

Danke für den Source. Probleme hab ich mit dem Verständnis, dem Nachvollziehen der Funktion FindSubList. Wie kommt man auf sowas ? Mir ist das bisher nicht gelungen gedanklich nachzubauen. Funktionieren tut's sehr gut nur kapier ich es nicht ganz und frage mich wie man auf so einen Algorithmus kommt.
Kannst Du mir dazu eventuell ein paar Zeilen zum besseren Verständnis schreiben ?

Danke,

Viele Grüße,
Sendrix

Ist nichts anders als PosEx, jedoch bei 0 statt 1 beginnend und für Stringlisten statt für Strings .

Versuche vielleicht deshalb erst die normale PosEx zu verstehen (ist etwas anschaulicher und fast das gleiche).

Delphi-Quellcode:

function PosEx (const Substr, S: string; const Index: integer): integer;
var
  I, J, A, B: integer;
begin
  Result:= 0;
  A:= Length(S);
  B:= Length(Substr);
  I:= Index;
  if I < 1 then Exit;
  if B = 0 then Exit;
  if B > A then Exit;
  while (Result = 0) and (I <= A-B+1) do
  begin
    J:= 1;
    if S[I] = Substr[J] then
    begin
      while (J < B) and (S[I+J] = Substr[J+1]) do Inc(J);
      if J = B then Result:= I;
    end;
    Inc(I);
  end;
end;

Fange bei I an. J ist zunächst 1. Wenn das I. Zeichen von S mit dem (immer) 1. Zeichen von Substr übereinstimmt, dann hast du eine Chance, Substr zu finden [if S[I] = Substr[J] then]. Probiere dann, ob weitere Zeichen von S und Substr auch übereistimmen. Ansonsten mache an der I+1. Position von S weiter und probiere das selbe, solange, bis Substr nicht mehr in S reinpasst oder du ein Ergebnis ungleich Null hast [while (Result = 0) and (I <= A-B+1) do]. Wenn das Ergebnis Null ist, konnte der Sustr nicht gefunden werden. (Man setzt in der Regel Result vorab auf Null, wenn mögliche Ergebnisse bei 1 beginnen, auf -1, wenn mögliche Ergebnisse ab 0 möglich sind.)

Wenn also das I. Zeichen von S mit dem 1. Zeichen von Substr übereinstimmt, dann mache folgendes (J ist immer noch 1): Ist das I+J. Zeichen von S mit dem J+1. Zeichen von Substr identisch, dann erhöhe J um eins. J ist dann also J+1. Mache das ganze solange, wie dieser Vergleich gelingt oder das letzte Zeichen von Substr erreicht ist [while (J < B) and (S[I+J] = Substr[J+1]) do Inc(J)]. Ist diese Bedingung B-1 mal erfüllt, das erste Zeichen haben wir bereits vorher abgefragt, dann ist J gleich B (Länge von Substr). In diesem Falle hast du Substr gefunden. Gib als Ergebnis die Stelle zurück, wo die erfolgreiche Suche begonnen hat [if J = B then Result:= I]. Result ist jetzt nicht mehr Null und die function wird beendet.

[Sendrix]

Hallo Bjoerk,

jetzt hab ich es kapiert. Der hinweis auf PosEx war wirklich hilfreich. Das hab ich mir genau angesehn und konnte es dann mit Deiner beschreibung gut auf Deinen Sourcecode übertragen und verstehn. So langsam komme ich weiter. Danke für Deine / Eure Tips und Hilfe.

Sendrix