[Gottzilla]

ich brauche einen Algorithmus um zwei Texte auf Differenzen zu überprüfen. D. h. es muss nicht nur beachtet werden, ob der Buchstabe an einer gewissen Stelle ein anderer ist, wie an der selben Stelle im Vergleichstext, sondern es muss auch noch beachtet werden, wenn ein Buchstabe zu viel und zu wenig ist. Und dann soll wieder ab dort weitergemacht werden, ab wann der Text wieder korekt ist. Denn sonst ist ja z. B. bei nem vergessenen Buchstaben der komplette restliche Text falsch. Hat da jemand eine Ahnung?ich brauche einen Algorithmus um zwei Texte auf Differenzen zu überprüfen. D. h. es muss nicht nur beachtet werden, ob der Buchstabe an einer gewissen Stelle ein anderer ist, wie an der selben Stelle im Vergleichstext, sondern es muss auch noch beachtet werden, wenn ein Buchstabe zu viel und zu wenig ist. Und dann soll wieder ab dort weitergemacht werden, ab wann der Text wieder korekt ist. Denn sonst ist ja z. B. bei nem vergessenen Buchstaben der komplette restliche Text falsch. Hat da jemand eine Ahnung?

[3qualizer]

Diff (1) wäre ein Ansatz. Allerdings afaik nur Zeilenweise.

(1) http://www.bmsi.com/java/#diff

[Gottzilla]

Weißt du wie das funktioniert (also die Vorgehensweise)? Hast du damit schonmal gearbeitet?

[Sym]

Ist ein Text immer korrekt und der andere evtl. fehlerhaft? Oder können auch beide Texte fehlerhaft sein? Evtl. sogar komplett unterschiedlich?

[Gottzilla]

Nein, einer ist immer korrekt und der andere kann fehlerhaft sein.

[Gottzilla]

Hab mir da jetzt mal was zusammengebaut ... nur funktioniert das nicht immer. Kann da mal jemand drüberschauen?

PHP-Code:

 static int differenz(String str1, String str2)  {
  
  str1 = str1.replaceAll("\n", " \n") + " ";
  str2 = str2.replaceAll("\n", " \n") + " ";
  int str1F = 0; 
  int str2F = 0; 
  int fehler = 0; 
  int lange = 0; 
  boolean fertig = false; 
  if (str1.length() <= str2.length()) { 
   lange = str1.length(); 
  } 
  else { 
   lange = str2.length(); 
  }
  try {
   for (int i = 0; i < lange && fertig == false; i++) { 
    if (str1.charAt(str1F) != str2.charAt(str2F) && fertig == false) { 
     int soweit = 0; 
     int test1 = str1F; 
     int test2 = str2F; 
     fehler++; 
     while (fertig == false && str1.charAt(test1) != str2.charAt(test2)) { 
      soweit++; 
      if (test1 < lange && test2 < lange) {
       if (str1.charAt(test1) != str2.charAt(test2) && fertig == false) { 
        for (int durch = 0; durch != soweit; durch++) { 
         test1++; 
         test2++; 
        } 
       }
      }
      if (test1 < lange && test2 < lange) {
       if (str1.charAt(test1) != str2.charAt(test2) && fertig == false) { 
        test1 = str1F; 
        test2 = str2F; 
        for (int durch = 0; durch != soweit; durch++) { 
         test1++; 
        } 
       }
      }
      if (test1 < lange && test2 < lange) {
       if (str1.charAt(test1) != str2.charAt(test2) && fertig == false) { 
        test1 = str1F; 
        test2 = str2F; 
        for (int durch = 0; durch != soweit; durch++) { 
         test2++; 
        } 
       }    
      } 
      if (test1 >= lange || test2 >= lange) {
       fertig = true;
      }
     }
     str1F = test1;
     str2F = test2;
    }
    str1F++; 
    str2F++;
    if (str1F >= lange || str2F >= lange) { 
     fertig = true; 
    }
   } 
  }
  catch (Exception e) {
   System.out.println(e);
  }
  return fehler; 
 } 


[edit] Hab mal den aktuellen Code eingefügt ...

[3qualizer]

Zitat von Hobbit_im_Blutrausch

Weißt du wie das funktioniert (also die Vorgehensweise)? Hast du damit schonmal gearbeitet?

Mit dem "Konsolen-Diff" von GNU/Linux arbeite ich jeden Tag (*patch-aholic ist* *g*).
Die Java-Variante die ich verlinkt hab, hatt ich noch nicht anschauen können... denk aber das sie ähnlich funktioniert:

I have translated the GNU Diff algorithm to a Java class.

[Gottzilla]

Danke, aber ich benutze nur nicht gerne Classen die ich nicht wenigstens Verstehe. Deswegen würde ich gerne den Algorithmus verstehen. Der Code ist aber so unverständlich (man siehe allein die Variablennamen) geschrieben, dass ich mich da wahrscheinlich nur wenn gar nichts anderes geht einlesen werde.

[Gottzilla]

So, hab mal ein bisschen weiter geforscht und habe das hier http://www.igi.tugraz.at/oaich/animations/lcs/lcs.html gefunden. Das scheint so auch wunderbar zu funktionieren. Also versuch ich es gerade nachzubauen. Bin im Moment so weit, dass ich das 2 Dimensionale Array mit Werten befülle. Die Werte stimmen auch, bis ein Buchstabe vergessen oder zuviel ist. Wie kann ich meinen Code erweitern, dass das mit Berückstichtig wird? Oder habe ich gar komplett den falschen Ansatz? Hier mein aktueller Code:

PHP-Code:

public class diffTest { 
    
   public static void main(String[] args) { 
       
      String str1 = "Fehlt"; 
      String str2 = "Fehlt"; 
      int fehler = 0; 
      int stelle = 1; 
      int[][] check = new int[str1.length() + 1][str2.length() + 1]; 
      for (int a = 0; a < str1.length() + 1; a++) { 
         check[a][0] = 0; 
      } 
      for (int a = 0; a < str2.length() + 1; a++) { 
         check[0][a] = 0; 
      } 
      for (int a = 1; a < str1.length() + 1; a++) { 
         for (int b = a; b < str2.length() + 1; b++) { 
            if (str1.charAt(a - 1) == str2.charAt(b - 1)) { 
               for (int c = b; c < str2.length() + 1; c++) { 
                  check[a][c] = b - (stelle - 1); 
               } 
               for (int c = a; c < str1.length() + 1; c++) { 
                  check[c][a] = b - (stelle - 1); 
               } 
            } 
            else { 
               for (int c = b; c < str2.length() + 1; c++) { 
                  check[a][c] = b - stelle; 
               } 
               for (int c = a; c < str1.length() + 1; c++) { 
                  check[c][a] = b - stelle; 
               } 
               stelle++; 
            } 
            b = str2.length() + 1; 
         } 
      } 
      for (int a = str1.length(); a >= 0; a--) { 
         for (int b = 0; b < str2.length() + 1; b++) { 
            System.out.print(check[a][b]); 
         } 
         System.out.println(); 
      } 
   } 
} 


[Gottzilla]

Hab jetzt eine Denk ich verwertbare Ausgabe, nur weiß ich nicht wie ich sie auswerte. Mein aktueller Code:

PHP-Code:

public class diffTest { 
    
   public static void main(String[] args) { 
        
      String str1 = "Fehler"; 
      String str2 = "Fehler"; 
      int fehler = 0; 
      int[][] check = new int[str1.length()][str2.length()]; 
      for (int a = 0; a < str1.length(); a++) { 
         for (int b = 0; b < str2.length(); b++) { 
            if (str1.charAt(a) == str2.charAt(b)) { 
               check[a][b] = 1; 
            } 
         } 
      } 
      for (int a = str1.length() - 1; a >= 0; a--) { 
         for (int b = 0; b < str2.length(); b++) { 
            System.out.print(check[a][b]); 
         } 
         System.out.println(); 
      }     
   } 
} 


In diesem Beispiel wird

000001
010010
000100
001000
010010
100000

ausgegeben. D. h. dass alles richtig ist, da von rechts oben diagonal bis links unten alles mit 1ern voll steht. Nur wie werte ich das in anderen Fällen am Besten aus? könne ja auch z. B. so dastehen:

Fehler => Fdhler

000001
000010
000100
001000
000010
100000

oder so:

Fehler => Fler

0001
0010
0100
0000
0010
1000

usw.

Ich poste mal den Link zur aktuellen Seite im andern Forum, damit die die es interessiert auf dem aktuellen Stand sind:
http://www.java-forum.org/de/viewtop...6313&start=105

Viel Spaß beim Lesen der Seiten

Hier noch der Link zu dem ganz gut funktionierenden Algorithmus:
http://www.java-forum.org/de/viewtopic.php?t=17114

[Gottzilla]

Ah, ich hasse diese Verlinkungen . Und da ich sowieso seit gestern krank geschrieben bin und nichts besseres zu tun habe:

PHP-Code:

 class Levenshtein { 
 static int diff(String orig, String eing) { 
  int matrix[][] = new int[orig.length() + 1][eing.length() + 1]; 
  for (int i = 0; i < orig.length() + 1; i++) { 
   matrix[i][0] = i; 
  } 
  for (int i = 0; i < eing.length() + 1; i++) { 
   matrix[0][i] = i; 
  } 
  for (int a = 1; a < orig.length() + 1; a++) { 
   for (int b = 1; b < eing.length() + 1; b++) { 
    int right = 0; 
    if (orig.charAt(a - 1) != eing.charAt(b - 1)) { 
     right = 1; 
    } 
    int mini = matrix[a - 1][b] + 1; 
    if (matrix[a][b - 1] + 1 < mini) { 
     mini = matrix[a][b - 1] + 1; 
    } 
    if (matrix[a - 1][b - 1] + right < mini) { 
     mini = matrix[a - 1][b - 1] + right; 
    } 
    matrix[a][b] = mini; 
   } 
  } 
  return matrix[orig.length()][eing.length()]; 
 } 
}