Muster in String

[Monday]

Hallo,

ich möchte ein Muster in zwei Strings herausfinden.

Ich habe zwei Strings: Beispiel:
A) a123bcdef
B) ghij123kl

Möglich wäre auch
A) a1b2cd3ef
B) ghi1j2kl3

usw.

Ich weiß nicht, welches Muster es ist oder wie lange, ich weiß nur das in beiden Strings eine Zeichenfolge/Muster (im Beispiel 123) gleich sind. Und möchte herausfinden, welcher es ist.

Gibt es hierfür eine Funktion? Und falls nicht, welcher Weg ist hierfür am geschicktesten für die Lösung?

Was ich sicher weiß, das die Strings immer 100 Zeichen lang sind.

Ich habe erst gedacht, das ich String A mittels Bruteforce aufteile und dann die einzelnen Elemente mit String B vergleiche. Aber hab festgestellt dass das er ein laaangwieriger Weg ist,...
gibt es einen einfacheren Weg?

LG
Monday

[BUG]

In 100 Zeichen langen Strings gibt es potenziell Unmengen an gemeinsamen Teilzeichenketten. Man denke nur an die einzelnen Zeichen.

Suchst du nur die längste gemeinsame Teilzeichenkette?


EDIT: Ok, ich hatte das Problem falsch verstanden :?
Als erstes könntest du alle Zeichen entfernen, die nicht in beiden Zeichenketten vorkommen.

[Sir Rufo]

Das Zauberwort heißt hier Permutation.

Dazu brauchst einen Algorithmus, der die alle möglichen Muster aus einem String generiert.

Die Muster kann man ja als Zeichen und ein Array darstellen.

Delphi-Quellcode:

TFollower = record
  Character: Char;
  Offset: Integer;
end;

TPattern = record
  First: Char;
  Followers: array of TFollower;
end;

Das Muster

Delphi-Quellcode:

'123'

aus

Delphi-Quellcode:

'a123bcdef'

würde dann z.B. so aussehen:

Code:

{ 
  "First": "1",
  "Follower": [
    { 
      "Character": "2",
      "Offset": 1 
    },
    { 
      "Character": "3",
      "Offset": 2 
    } 
  ] 
}

Das Muster

Delphi-Quellcode:

'123'

aus

Delphi-Quellcode:

'a1b2cd3ef'

würde dann z.B. so aussehen:

Code:

{ 
  "First": "1",
  "Follower": [
    { 
      "Character": "2",
      "Offset": 2 
    },
    { 
      "Character": "3",
      "Offset": 5 
    } 
  ] 
}

Die Suche in den anderen Strings ist dann relativ einfach. Man sucht nach der Position von

Delphi-Quellcode:

First

. Wenn es da eine gibt, dann schaut man, ob es am Offset des ersten

Delphi-Quellcode:

Followers

diesen

Delphi-Quellcode:

Character

gibt, usw.

Findet man alle

Delphi-Quellcode:

Follower

, dann hat man einen Match.

Auch wenn es nur 100 Zeichen in einem String sind, die Anzahl der Permutationen in der Breite von 1 bis 100 wird da schon gewaltig werden. Die sollte man versuchen sinnvoll einzuschränken.

z.B. Die gesuchten Muster sind zwischen 3 und 5 Zeichen lang. Das würde die Verarbeitungsgeschwindigkeit dramatisch verkürzen (man findet aber auch nur diese Muster).

[Dejan Vu]

Ich glaube, das sind keine Permutationen, sondern Kombinationen (oder Variationen, irgendwie so)
Auf jeden Fall gibt es in einer Zeichenkette der Länge n so ziemlich n!/(n-k)! Muster der Länge k.
Das ist ne Menge, aber machbar.

Oder irre ich?

[Sir Rufo]

Zitat:

Zitat von Dejan Vu (Beitrag 1322742)

Ich glaube, das sind keine Permutationen, sondern Kombinationen (oder Variationen, irgendwie so)
Auf jeden Fall gibt es in einer Zeichenkette der Länge n so ziemlich n!/(n-k)! Muster der Länge k.
Das ist ne Menge, aber machbar.

Oder irre ich?

Da kannst durchaus Recht haben ... (ich sollte da mal eine Autokorrektur eintragen :stupid:)

[Luckie]

Würde da nicht auch ein pos bzw. posex reichen?

[BUG]

Zitat:

Zitat von Luckie (Beitrag 1322751)

Würde da nicht auch ein pos bzw. posex reichen?

Ich denke nicht :stupid:

Zitat:

Zitat von Monday (Beitrag 1322726)

Möglich wäre auch
A) a1b2cd3ef
B) ghi1j2kl3

Mein gedanklicher Ansatz wäre: Schreibe die beiden Zeichenketten untereinander und verbinde die gleichen Zeichen zwischen den Wortern mit einer geraden Linie. Alle Linien (bzw. deren Zeichen) die sich mit keiner anderen kreuzen sind auf jeden Fall im längsten Muster.

Nun wäre die Frage, ob es eine gute Strategie gibt, um kreuzende Linien zu entfernen oder ob man da "dummes" Brute-Force machen muss.

EDIT/PS: Die Idee ist hier: Die kreuzenden Linien zeigen wo Zeichen in beiden Wörtern in unterschiedlicher Reihenfolge vorkommen.

[Dejan Vu]

Der Ansatz von Sir Rufo führt auf jedem Fall zum Ziel. Meine Rechnung (wenn sie denn stimmt) zeigt, das Brute Force bei nicht zu langen Zeichenketten durchaus funktionieren könnte. Natürlich kann man die Kandidaten eingrenzen. Hier ein Ansatz in C#

Code:

    internal class VariationMatcher
    {
        private readonly string _text1;

        private readonly string _text2;
        private readonly List<string> _patterns=new List<string>(); 

        public IEnumerable<string> Patterns { get { return _patterns; } }

        public VariationMatcher(string text1, string text2)
        {
            this._text1 = text1;
            this._text2 = text2;
        }

        public void Find(int minSubLength, int maxSubLength)
        {
            for (int subLength = minSubLength; subLength <= maxSubLength; subLength++)
                ScanPattern(_text1, "", 0, subLength);
        }

        private void ScanPattern(string text, string pattern, int i, int remaining)
        {
            if (remaining == 0)
            {
                FindPattern(_text2, pattern,"",0);
            }
            else
                for (int j = i; j <= text.Length - remaining; j++)
                    ScanPattern(text, pattern + text[j], j + 1, remaining - 1);
        }

        private void FindPattern(string text, string patternToMatch, string pattern, int i)
        {
            if (pattern.Length == patternToMatch.Length)
                _patterns.Add(pattern);
            else
            {
                char charToMatch = patternToMatch[pattern.Length];
                for (int j = i; j <= text.Length - patternToMatch.Length + pattern.Length; j++)
                    if (text[j] == charToMatch)
                        FindPattern(text, patternToMatch, pattern + charToMatch, j + 1);
            }
        }
    }

Verwendung

Code:

var matcher = new VariationMatcher ("a1b2cd3ef","ghi1j2kl3");
matcher.Find (3,3); // Nur pattern der Länge 3
Console.Writeln(string.Join ("\r\n",matcher.Patterns);

Edit: Sorry, kein Delphi zur Hand. sollte 1:1 in Delphi übersetzbar sein.

[jobo]

Zitat:

Zitat von Monday (Beitrag 1322726)

ich möchte ein Muster in zwei Strings herausfinden.

Ich habe zwei Strings: Beispiel:
A) a123bcdef
B) ghij123kl

Möglich wäre auch
A) a1b2cd3ef
B) ghi1j2kl3

usw.

Ich weiß nicht, welches Muster es ist oder wie lange, ich weiß nur das in beiden Strings eine Zeichenfolge/Muster (im Beispiel 123) gleich sind.

"usw." finde ich nicht sehr erschöpfend in der Beschreibung. Klar scheint ja die feste Zeichenfolge zu sein, was aber gilt als Muster? Geht das genauer?

[Sir Rufo]

Mit meinem Mustererkennungblick sehe ich *123*

• a123bcdef
• ghij123kl

und *1?2??3*

• a1b2cd3ef
• ghi1j2kl3

oder als weiteres Beispiel *AA??A*

• lkrAAkfAj
• kAA34Appp

[jobo]

Klar, mit einer gewissen Empathie oder musterhaften analytischen Fähigkeiten kann man da schon Muster erkennen.
Aber ist das mustergültig? :)

Vor allem das "usw." schwächt die Aussagekraft der beiden Beispiele.
Auch eine steigende oder fallende Anzahl von Zeichen ergibt bspw. bei Wiederholung ein Muster, da sind der Fantasie wenig Grenzen gesetzt.

Außerdem finde ich meine Frage pädagogisch wertvoll.

Oder ist das Muster gültig?

• a1b2cd3ef
• ghi1j2kl3

Vielleicht sogar, ohne dass die darin enthaltenen nummerischen Zeichen für sich bereits ein Muster ergeben?

[BUG]

Wenn jemand genau 100 Zeichen lange Strings hat und solche Beispiele gibt, hoffe ich doch sehr auf einen einigermaßen durchdachten Anwendungsfall beim TE.
Es würde vielleicht helfen, wenn er sich wieder melden würde :stupid:

[Monday]

Ja ich meine das so wie Sir Rufo es auch gesehen hat. Das "usw." sollte nur heißen, dass eben verschiedene Muster möglich sind und nicht exakt so aussehen wie in dem Beispiel.

Und ja, ich dachte an die längste Musterkette.

Ich habe inzwischen die Idee, dass man einen der String durch den anderen von links nach rechts durchlaufen lässt und dann die Zeichen vergleicht. Irgendwann müsste sich dann theoretisch das Muster herauskristalisieren. Evtl. reicht es auch einen der Strings nach Rechts und nach Links zu schieben. Ich weiß nicht, ob die Idee verständlich ist. Bin gerade über den Code, aber habe noch nichts lauffähiges das ich zeigen kann.

(Anwendung: In einem Analyseprogramm, dass solche Zeichenfolgen ausgibt, will ich so Auffälligkeiten in der Ausgabe finden.)

[Luckie]

Ich werfe noch mal reguläre Ausdrücke in die Runde.

[SMO]

Und ich werfe mal längster gemeinsamer Substring in die Runde.
Denn wenn ich Monday recht verstehe, möchter er in diese Richtung, aber mit Wildcards im Suchmuster. Könnte schwierig werden.

[BUG]

Wenn ich das richtig sehe, dann sucht er den längsten String, dessen Zeichen in dieser Reihenfolge in beiden Eingabestrings vorkommen.

Oder anders formuliert: Suche den längsten String, so das man diesen String aus beiden Eingabestrings erhalten kann, indem man Zeichen löscht.

Ist das nun richtig oder nicht? Nur der Montag wird die Antwort bringen :mrgreen:

[p80286]

Zitat:

Zitat von BUG (Beitrag 1322838)

Wenn ich das richtig sehe, dann sucht er den längsten String, dessen Zeichen in dieser Reihenfolge in beiden Eingabestrings vorkommen.

Das könnte so sein. Aber Sir Rufo hat ja auch *1?2?3* als Muster identifiziert, da ist dann die Frage, was ist ein Muster, oder anders herum welche Bedingung muß eine Zeichenkombination erfüllen, damit sie ein Muster ist?

Gruß
K-H

[Dejan Vu]

Hat jemand mal meine Klasse aus probiert? Wenn man die etwas umschreibt, bekommt man tatsächlich die längsten Variationen (nein, keine Substrings, keine Muster, schlicht und ergreifend und mathematisch korrekt: Variationen) zweier Zeichenketten.

Code:

    internal class VariationMatcher
     {
         private readonly string _text1;
         private readonly string _text2;

         private readonly List<string> _patterns=new List<string>(); 

         public IEnumerable<string> Patterns { get { return _patterns; } }

         public VariationMatcher(string text1, string text2)
         {
             this._text1 = text1;
             this._text2 = text2;
         }

         public void FindLongestVariation()
         {
             for (int subLength = _text.Length; subLength >2; subLength--)
             {
                 ScanPattern(_text1, "", 0, subLength);
                 if (_Patterns.Any()) 
                   return;
              }
         }

         private void ScanPattern(string text, string pattern, int i, int remaining)
         {
             if (remaining == 0)
             {
                 FindPattern(_text2, pattern,"",0);
             }
             else
                 for (int j = i; j <= text.Length - remaining; j++)
                     ScanPattern(text, pattern + text[j], j + 1, remaining - 1);
         }

         private void FindPattern(string text, string patternToMatch, string pattern, int i)
         {
             if (pattern.Length == patternToMatch.Length)
                 _patterns.Add(pattern);
             else
             {
                 char charToMatch = patternToMatch[pattern.Length];
                 for (int j = i; j <= text.Length - patternToMatch.Length + pattern.Length; j++)
                     if (text[j] == charToMatch)
                         FindPattern(text, patternToMatch, pattern + charToMatch, j + 1);
             }
         }
     }

Nun nur noch 'FindLongestVariation' aufrufen und sich das Ergebnis in 'Patterns' anschauen.

[BUG]

Zitat:

Zitat von p80286 (Beitrag 1322839)

was ist ein Muster, oder anders herum welche Bedingung muß eine Zeichenkombination erfüllen, damit sie ein Muster ist?

Genau deshalb hab ich ja den Vorschlag gemacht. Das wäre eine konkrete Definition mit der man arbeiten könnte.

Ich hab bloß den Eindruck, das hier viele Muster lesen und dann gleich "Muster - Suchmuster - Regulärer Ausdruck" denken, während die Beispiele imho gar nicht so aussehen.

[Perlsau]

Im Grunde ist alles ein Muster. Anders ausgedrückt: Es gibt praktisch nichts, das sich nicht als Muster definieren ließe. Es geht doch aber darum, was der TE eigentlich sucht. Man kann nicht nach irgend einem Muster suchen, sondern immer nur nach einem ganz bestimmten Muster, das vor der Suche eindeutig und unmißverständlich zu definieren ist. So lange der TE diese Definition nicht liefert, ist jeder weitere Kommentar dazu reinste Spekulation.

[Sir Rufo]

So richtig explizit wurde es nicht gesagt, darum muss man hier ein wenig interpretieren.

Ein Muster wird dargestellt in einer Kombination aus Platzhaltern und Zeichen.

• Delphi-Quellcode:

  *

  => 0-n Zeichen
• Delphi-Quellcode:

  ?

  => genau ein Zeichen

Ein Muster das mit

Delphi-Quellcode:

*?

startet oder mit

Delphi-Quellcode:

?*

endet ist nicht zulässig.

Ein Muster liegt dann vor, wenn in einer gegebenen String-Menge in allen Strings Zeichen an einer beliebigen Stelle im gleichen Abstand vorkommen. Das Muster selber muss mindestens 2 Zeichen breit sein (Platzhalter werden nicht mitgezählt).

Beispiel:

Die gegebene String-Menge

Code:

1234567890
blhe1234j6
f1234k67id

und die (in allen Strings) vorkommenden Muster:

Code:

*12*
*1?3*
*1??4*
*123*
*1?34*
*12?4*
*1234*
*1????6*
*12???6*
...
*123??6*
*1234?6*

Das längste Muster ist das Muster, wo die Musterbreite abzüglich der Platzhalterzeichen ein Maximum aufweist. Dieses könnten aber auch mehrere Muster sein.

In dem Beispiel wäre das

Delphi-Quellcode:

*1234?6*

[BUG]

Zitat:

Zitat von BUG (Beitrag 1322841)

Ich hab bloß den Eindruck, das hier viele Muster lesen und dann gleich "Muster - Suchmuster - Regulärer Ausdruck" denken, während die Beispiele imho gar nicht so aussehen.

Zitat:

Zitat von Sir Rufo (Beitrag 1322843)

Ein Muster wird dargestellt in einer Kombination aus Platzhaltern und Zeichen.

Genau das meinte ich :tongue: :mrgreen:

Nicht jedes "Muster" was jemand finden möchte ist regulär, und dem TE geht es explizit um eine bestimmte Art von Gemeinsamkeiten zwischen zwei Strings, wobei die konkreten Zeichen nicht feststehen. Wahrscheinlich ist der Begriff "Muster" an der Stelle einfach irreführend.

Zitat:

Zitat von Monday (Beitrag 1322726)

Ich weiß nicht, welches Muster es ist oder wie lange, ich weiß nur das in beiden Strings eine Zeichenfolge/Muster (im Beispiel 123) gleich sind. Und möchte herausfinden, welcher es ist.

Zitat:

Zitat von Perlsau (Beitrag 1322842)

So lange der TE diese Definition nicht liefert, ist jeder weitere Kommentar dazu reinste Spekulation.

Jup, wobei es auch sein könnte das der TE auch nicht genau weiß was er eigentlich möchte :mrgreen:

[Perlsau]

Zitat:

Zitat von BUG (Beitrag 1322844)

Zitat:

Zitat von Perlsau (Beitrag 1322842)

So lange der TE diese Definition nicht liefert, ist jeder weitere Kommentar dazu reinste Spekulation.

Jup, wobei es auch sein könnte das der TE auch nicht genau weiß was er eigentlich möchte :mrgreen:

Diesem Eindruck kann ich mich ebenfalls nicht verschließen. Bei gefühlt 30% der Anfragen muß man erst einmal herauszufinden suchen, was der Fragesteller eigentlich erreichen möchte – und ich spreche jetzt nicht von den Fällen, in denen der Fragesteller mehr oder weniger absichtlich falsch verstanden wird oder dessen Thread in eine Richtung drängt, die stark von der Fragestellung abweicht und am Ende nichts mehr damit zu tun hat.

Selbstverständlich möchte ich hier keinem den Spaß & die Freude daran, sich über ein be- oder geliebtes Thema auszulassen, verderben :gruebel:
Die eigentliche, bislang unvollständige Frage wird auf diese Weise und ohne weitere Erklärungen des TE jedoch nicht wirklich einer Lösung nähergebracht :cyclops:

[Monday]

Jetzt hab ich was geschrieben, das wohl auch funktioniert. Vielleicht kann das auch jemand so gebrauchen:

Zum Testen eine Form mit Memo1 und Button1. Der . dient als Platzhalter.

Code:

function vergleich(erster,zweiter: string): string;
var
  a: integer;
begin
  Result := '';

  if length(erster) <> length(zweiter) then begin Result := ''; exit; end;

  for a := 1 to Length(erster) do begin
    if erster[a] = zweiter[a] then begin
      Result := Result+erster[a];
    end;
    if erster[a] <> zweiter[a] then begin
      Result := Result+'.';
    end;
  end;
end;

function mustersuche(erster, zweiter: string): string; // Eigentliche FUnktion
var
  a,max: integer;
  temp_zweiter,temp, anzeige,muster_temp: string;
begin
 temp := '';
 for a := 1 to Length(erster) do begin   temp := temp + '.';  end;

 temp_zweiter := temp + zweiter + temp;
 max := length(temp_zweiter)-length(temp);

  for a := 0 to max-1 do begin
     Delete(temp_zweiter, 1, 1);
     anzeige := Copy(temp_zweiter,1,length(temp));

     muster_temp := vergleich(erster,anzeige);
     muster_temp := StringReplace(muster_temp, '.', '', [rfReplaceAll, rfIgnoreCase]);
     if muster_temp <> '' then begin
       Form1.Memo1.Lines.Add(anzeige + ' Gefundenes Muster -> '+ vergleich(erster,anzeige)); // Nur Treffer ansehen
     end;
     //Form1.Memo1.Lines.Add(anzeige + ' Gefundenes Muster -> '+ vergleich(erster,anzeige)); //kompletten vorgang ansehen
  end;
end;



procedure TForm1.Button1Click(Sender: TObject);
begin
  mustersuche('a1b2cd3ef','ghi1j2kl3'); // ergibt => .1.2..3..
  mustersuche('a123bcdef','ghij123kl'); // ergibt => .123.....

  ShowMessage('Fertig');
end;

[Monday]

Ich wusste nicht das der Begriff "Muster" solche Verwirrungen auslöst. Es ist manchmal Schwierig es genau zu definieren, deshalb auch die Beispiele damit es einfacher ist zu verstehen. Ist Muster/Suchmuster/Gemeinsamkeiten/Kombinationen nicht einfach nur Begrifflichkeiten die in etwa dasselbe ausdrücken? Mir schien der Begriff Muster hier verständlich. Vielleicht könnte man diese Aufgabe auch mit regulären Ausdrücken lösen - ich weiß es nicht - dazu kenne ich mich mit regulären Ausdrücken zuwenig aus.

[Namenloser]

Erinnert mich an "diff", bloß mit einzelnen Zeichen statt Zeilen. "Longest common subsequence" wurde hier schon genannt und kommt auf das gleiche raus, aber ich wollte es trotzdem noch mal in den Raum werfen. Das Beispiel in dem verlinkten Abschnitt finde ich auch recht anschaulich. Du suchst im Grunde genau die Stellen, die dort freigelassen wurden.

[D-User]

apropos Muster:

suchen die bei Seti Project nicht auch ein Muster in einem etwas längeren String?