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 '123' aus 'a123bcdef' würde dann z.B. so aussehen:

Code:

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

Das Muster '123' aus '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 First . Wenn es da eine gibt, dann schaut man, ob es am Offset des ersten Followers diesen Character gibt, usw.

Findet man alle 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 von 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?

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

[Luckie]

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

[BUG]

Zitat von Luckie:

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

Ich denke nicht

Zitat von Monday:

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 von Monday:

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