String Vergleich mit größt Möglichen Muster

Hallo ich benötige einen kleinen Tipp bezüglich eines Algorithmus den es sicher schon gibt.

Ich möchte 2 Zeichenketten nach einem Muster überprüfen. ein Beispiel soll dies verdeutlichen:

string s1 = "tokenblakroneiikkpdp"
string s2 = "tokenbkroniikkAutopdp"

Raus kommen soll nun folgendes. Das im string 2 das "la" fehlt, sowie das "e" bei krone, sowie das Auto zuviel drin ist. Daher einfach eine Liste mit z.B. Point Objekten, mit index und Length.

Gibt es dafür schon was fertiges was man nur noch anpassen muss?

etwas fertiges gibt es nciht im framework aber sicherlich irgendwo im netz. aber das ist dennoch recht simpel umzusetzen. kannst du auch locker selbst machen.

lass eine while schleife laufen und iteriere durch die strings und lass 2 counter mitlaufen (indexcounter für die stringzugriffe). ist ein zeichen nciht im aktuellen counterindex des anderen strings enthalten, zählst du nur den ersten counter hoch und schreibst die buchstaben in einen temporären stringbuilder.

Hallo,

ich denke das wäre eine Anwendung des Longest common subsequence problem, da Programme wie Diff darauf passieren und soetwas soll ja erreicht werden (außer ich habe die Frage falsch interpretiert).

mfG Gü

Ja soweit so gut, das problem nur ist das es in beide Richtungen gehen muss, daher es gibt strings die sind in s1 und in s2 nicht und andersrum. Irgendwie hab ich da eine denkblockade

Hallo,

jenachdem wie Du den Vergleich implementierst, wäre es dann eine einfache Methode ihn 2x durchzuführen und dabei die Reihenfolge der Strings zu tauschen.

Das ist natürlich eine gute Idee, ich werd das mal probieren.

Hallo rollerfreak2,

das Longest common subsequence problem ist schon dem Namen nach symmetrisch. Auch das genannte Diff arbeitet symmetrisch, findet also Unterschiede in beide Richtungen. Du musst also da nichts vertauschen und zweimal durchführen. Du muss den Algorithmus nur korrekt implementieren.

herbivore

Eigentlich sollte der Longest common subsequence algorithmus auch gehen, nur irgendwie liefert die nicht die richtigen Ergebnisse.

public void GetDiffTreeFromBacktrackMatrix(int[,] lcsMatrix, string s1, string s2, int i, int j)
{
    if (i > 0 && j > 0 && s1[i - 1] == s2[j - 1])
    {
        GetDiffTreeFromBacktrackMatrix(lcsMatrix, s1, s2, i - 1, j - 1);
        Console.WriteLine("  " + s1[i - 1]);
    }
    else
    {
        if (j > 0 && (i == 0 || lcsMatrix[i, j - 1] >= lcsMatrix[i - 1, j]))
        {
            GetDiffTreeFromBacktrackMatrix(lcsMatrix, s1, s2, i, j - 1);
            Console.WriteLine("+ " + s2[j - 1]);
        }
        else if (i > 0 && (j == 0 || lcsMatrix[i, j - 1] < lcsMatrix[i - 1, j]))
        {
            GetDiffTreeFromBacktrackMatrix(lcsMatrix, s1, s2, i - 1, j);
            Console.WriteLine("- " + s1[i - 1]);
        }
    }
}


public static int[,] GetLongestCommonSubsequenceMatrix(string s1, string s2)
{
    int[,] lcsMatrix = new int[s1.Length, s2.Length];
    char letter1, letter2;

    for (int i = 0; i < s1.Length; i++)
    {
        for (int j = 0; j < s2.Length; j++)
        {
            letter1 = s1[i];
            letter2 = s2[j];

            if (letter1 == letter2)
            {
                if ((i == 0) || (j == 0))
                    lcsMatrix[i, j] = 1;
                else
                    lcsMatrix[i, j] = 1 + lcsMatrix[i - 1, j - 1];
            }
            else
            {
                if ((i == 0) && (j == 0))
                    lcsMatrix[i, j] = 0;
                else if ((i == 0) && !(j == 0))
                    lcsMatrix[i, j] = Math.Max(0, lcsMatrix[i, j - 1]);
                else if (!(i == 0) && (j == 0))
                    lcsMatrix[i, j] = Math.Max(lcsMatrix[i - 1, j], 0);
                else if (!(i == 0) && !(j == 0))
                    lcsMatrix[i, j] = Math.Max(lcsMatrix[i - 1, j], lcsMatrix[i, j - 1]);
            }
        }
    }

    return lcsMatrix;
}


//call

string s1 = "ich weiß e nicht genau";
string s2 = "ich weiß es nict genau";
  
GetDiffTreeFromBacktrackMatrix(GetLongestCommonSubsequenceMatrix(s1, s2), s1, s2, s1.Length, s2.Length);

Ich möchte hier als Ergebniss nur haben (s) zuwenig, (h) zuviel. Aber das Ergebniss lautet +s -c -h +c. Aber das c kommt doch in beiden vor, das soll gar nicht mit matchen. Anscheinend steig ich noch nicht richtig hinter den Algorihtmus. Ein weiteres Problem ist das wenn die Strings beide unterschiedliche längen haben, und das letzte Zeichen nicht überein stimmt dann gibt es ein index out auf bounds exception lcsMatrix[i - 1, j] weil ja j ein zu groß ist. Ich muss gestehen ich habe den Algo von hier.

Weiß einer von euch meinen Fehler?

Hallo rollerfreak2,

find ich ehrlich gesagt ein bisschen dreist, dass du erst den Algorithmus kopierst und dann uns die Fehler darin suchen lassen willst. Das solltest du bitte selber tun. Wenn du den Algorithmus noch nicht verstehst, dann musst du dich eben etwas damit beschäftigen.

herbivore

Hallo,

Fortsetzung von herbivores Antwort:

...oder die Kommentare im Link verfolgen und dort weiterschauen 😉

mfG Gü

Hallo herbivore,

es geht nicht darum das ihr den Fehler sucht, sondern das Ihr mir bestätigt das der Algorithmus das 'c' einmal als fehlend im string s1 und einmal als zuviel im string s2 korrekt berechnet, bzw. das dies nicht der Fall sein sollte.

Edit: Das hat mir sehr geholfen den Algorithmus zu verstehen.

Falls es noch jemand gebrauchen kann, hier mal ein mögliche Lösung:

public static int[,] GetLongestCommonSubsequenceMatrix(string s1, string s2)
{
    int[,] lcsMatrix = new int[s1.Length + 1, s2.Length + 1];
    char letter1, letter2;

    for (int i = s1.Length - 1; i >= 0; i--)
    {
        for (int j = s2.Length - 1; j >= 0; j--)
        {
            letter1 = s1[i];
            letter2 = s2[j];

            if (letter1 == letter2)
            {
                if ((i == s1.Length - 1) || (j == s2.Length - 1))
                    lcsMatrix[i, j] = 1;
                else
                    lcsMatrix[i, j] = 1 + lcsMatrix[i + 1, j + 1];
            }
            else
            {
                if ((i == s1.Length - 1) && (j == s2.Length - 1))
                    lcsMatrix[i, j] = 0;
                else if ((i == s1.Length - 1) && !(j == s2.Length - 1))
                    lcsMatrix[i, j] = Math.Max(0, lcsMatrix[i, j + 1]);
                else if (!(i == s1.Length - 1) && (j == s2.Length - 1))
                    lcsMatrix[i, j] = Math.Max(lcsMatrix[i + 1, j], 0);
                else if (!(i == s1.Length - 1) && !(j == s2.Length - 1))
                    lcsMatrix[i, j] = Math.Max(lcsMatrix[i + 1, j], lcsMatrix[i, j + 1]);
            }
        }
    }

    return lcsMatrix;
}

public static double GetDiffTreeFromBacktrackMatrix(int[,] arr, string s1, string s2)
{
    int x = 0, y = 0;
    while (x < s1.Length && y < s2.Length)
    {
        if (s1[x] == s2[y])
        {
            Console.WriteLine(string.Format("  {0}", s1[x]));
            x++;
            y++;
        }
        else if (arr[x, y + 1] > arr[x + 1, y])
        {
            Console.WriteLine(string.Format("- {0}", s2[y]));
            y++;
        }
        else
        {
            Console.WriteLine(string.Format("+ {0}", s1[x]));
            x++;
        }
    }
    if (x < s1.Length)
    { 
        for (int i = x; i < s1.Length; i++)
        {
            Console.WriteLine(string.Format("+ {0}", s1[i]));
        }
    }
    else if (y < s2.Length)
    {
        for (int j = y; j < s2.Length; j++)
        {
            Console.WriteLine(string.Format("- {0}", s2[j]));
        }
    }

    return (double)count / Math.Max(s1.Length, s2.Length) * 100;
}


//caller
public int Main()
{
    int[,] arr = GetLongestCommonSubsequenceMatrix(s1, s2);
    double d = GetDiffTreeFromBacktrackMatrix(arr, s1, s2);
}