Knobelaufgabe ?

[TBT]

Hat jemand eine Idee, wie man effizient die Unterschiede zwischen 2 Strings ermittlen kann?
Ich möchte die Unterschiede farblich hervorheben, und zwar am liebsten in der Art, daß
die Teile die im ersten String, aber nicht im zweiten sind grün markiert werden,
und die Teile die im zweiten aber nicht im ersten sind rot.
Also so:

dies ist der [color=green]1[/color]. Text [color=green]blabla[/color]

dies ist der [color=red]2[/color]. Text [color=red]hallo[/color]

es würde mir auch schon reichen, wenn er mir anzeigt, was sich beim zweiten gegenüber
dem ersten geändert hat.

Jede Idee willkommen

[Titus]

Unter Linux/Unix gibt´s ein schönes Tool namens diff.
Bei DOS heißt das fc, Zeilennummern gibt´s hier mit /n

könnte man beides ausnutzen, indem man die beiden Texte als Datei schreibt (jedes Zeichen eine Zeile), das Tool mit exec aufruft und die Ausgabe auswertet.

Ansonsten:

1) Auf http://www.dcs.shef.ac.uk/~cloughie/programs/ nach "Heckel" suchen, runterladen und C-Code nach PHP übersetzen.
2) http://crl.nmsu.edu/~mleisher/ucdata.html
3) http://www.pnylab.com/pny/papers/str...pare/main.html

oder

4) http://www.google.de/search?hl=de&q=...a=lr%3Dlang_de

[MoRtAlAn]

versuch mal das, das sollte auch gehen (allerdings nur für 2 Strings!):

<?php
/**
* Stringvergleich
*
* Vergleicht 2 Strings und gibt Wortunterschiede farbig aus
*
* @author Marco Jahn <mortalan@php-resource.de>
*/
/**
* Vergleicht die Strings
*
* @var string $string1 Ausgangssatz (welche Wörter kommen nicht in $string2 vor)
* @var string $string2 Vergleichssatz
* @var string $color Farbwert für nicht gefundene Worte
*/
function stringVergleich($string1,$string2,$color) {
    $as1 = explode(" ",$string1);
    $as2 = explode(" ",$string2);
    $ii = count($as1);
    $i = 0;
    do {
        if (!in_array($as1[$i],$as2)) {
            $nas1[$i] = "<font color=\"".$color."\">".$as1[$i]."</font>";
        } else {
            $nas1[$i] = $as1[$i];
        }
        $i++;
    } while ($i < $ii);
    $fs = join(" ",$nas1);
    return $fs;
}

$satz1 = "dies ist der 1. Text blabla";
$satz2 = "dies ist der 2. Text hallo bla";

echo stringVergleich($string1 = $satz1,$string2 = $satz2, $color = "#ff0000");
echo "<br>";
echo stringVergleich($string1 = $satz2,$string2 = $satz1, $color = "teal");
?>

[TBT]

@mortalan nicht schlecht, aber sorry, nicht ganz

function stringVergleich($string1,$string2,$color) {
    $as1 = explode(" ",$string1);
    $as2 = explode(" ",$string2);
    $ii = count($as1);
    $i = 0;
    do {
        if (!in_array($as1[$i],$as2)) {
            $nas1[$i] = "<font color=\"".$color."\">".$as1[$i]."</font>";
        } else {
            $nas1[$i] = $as1[$i];
        }
        $i++;
    } while ($i < $ii);
    $fs = join(" ",$nas1);
    return $fs;
}

$text1="Software & Support Verlag GmbH is going to publish an International version of the PHP Magazin. This magazine was 
initiated after growing interest for an English magazine after the German version has been around for a few months. PHP 
Magazine not only informs about the scripting language itself, but also about related technologies such as the Apache Web 
Server, database blabla technologies, XML and other innovative internet technologies. Different sections within the magazine 
are oriented towards the specific question areas with which a web developer is confronted in daily practice. The first issue 
will be published in December 31 and the frequency of issues is two months. You will be able to subscribe on the website which 
will open shortly.";
$text2="Software & Support Verlag GmbH is going to publish an International version of the PHP Magazin. This magazine was 
initiated after growing interest for an English magazine after the German version has been around for a few months. PHP 
Magazine not only informs you about the scripting language itself, but also about related technologies such as the Apache Web 
Server, database technologies, XML1 and other innovative internet technologies. Different sections within the magazine are 
oriented towards the specific questions areas 51 with you can which a web developer is confronted in daily practice. The first 
issue will be published in December and the frequency of issues is two months. You will be able to subscribe on the website 
which will open shortly.";

echo stringVergleich($text1,$text2, $color = "#ff0000");
echo "<br><br><br>";
echo stringVergleich($text2,$text1, $color = "teal"); 

ergibt:

Software & Support Verlag GmbH is going to publish an International version of the PHP Magazin. This magazine was 
initiated after growing interest for an English magazine after the German version has been around for a few months. PHP 
Magazine not only informs about the scripting language itself, but also about related technologies such as the Apache Web 
Server, database [color=ff0000]blabla[/color] technologies, [color=ff0000]XML[/color] and other innovative internet technologies. 
Different sections within the magazine [color=ff0000]are[/color] [color=ff0000]oriented[/color] towards the specific 
[color=ff0000]question[/color] areas with which a web developer is confronted in daily practice. The first [color=ff0000]issue[/color] [color=ff0000]
will[/color] be published in December [color=ff0000]31[/color] and the frequency of issues is two months. You will be able to 
subscribe on the website which [color=ff0000]will[/color] open shortly.


Software & Support Verlag GmbH is going to 
publish an International version of the PHP Magazin. This magazine was 
initiated after growing interest for an English magazine after the German version has been around for a few months. PHP 
Magazine not only informs [color=teal]you[/color] about the scripting language itself, but also about related technologies such 
as the Apache Web Server, database technologies, [color=teal]XML1[/color] and other innovative internet technologies. Different 
sections within the magazine [color=teal]are[/color] [color=teal] oriented[/color] towards the specific [color=teal]questions[/color] 
areas [color=teal]51[/color] with [color=teal]you[/color] [color=teal]can[/color] which a web developer is confronted in 
daily practice. The first [color=teal]issue[/color] will be published in December and the frequency of issues is two months. 
You will be able to subscribe on the website [color=teal]
which[/color] will open shortly.

noch 5 min, hab da auch gleich was fertig

[MoRtAlAn]

mh...

noch nen trim() um überflüssige leerzeichen rauszunehmen...

soll question und questions (beispiel) auch gemeldet werden oder nicht ??

wenn nicht, mal mit soundex probieren!

außerdem, besser als nichts

gruss

[TBT]

hab jetzt das hier

$text1="Software & Support Verlag GmbH is going to publish an International version of the PHP Magazin. This magazine was 
initiated after growing interest for an English magazine after the German version has been around for a few months. PHP 
Magazine not only informs about the scripting language itself, but also about related technologies such as the Apache Web 
Server, database blabla technologies, XML and other innovative internet technologies. Different sections within the magazine 
are oriented towards the specific question areas with which a web developer is confronted in daily practice. The first issue 
will be published in December 31 and the frequency of issues is two months. You will be able to subscribe on the website which 
will open shortly.";
$text2="Software & Support Verlag GmbH is going to publish an International version of the PHP Magazin. This magazine was 
initiated after growing interest for an English magazine after the German version has been around for a few months. PHP 
Magazine not only informs you about the scripting language itself, but also about related technologies such as the Apache Web 
Server, database technologies, XML1 and other innovative internet technologies. Different sections within the magazine are 
oriented towards the specific questions areas 51 with you can which a web developer is confronted in daily practice. The first 
issue will be published in December and the frequency of issues is two months. You will be able to subscribe on the website 
which will open shortly.";

$array1=explode(" ",str_replace(array("  ","\\r","\\n"),array(" ","",""),$text1));
$array2=explode(" ",str_replace(array("  ","\\r","\\n"),array(" ","",""),$text2));

while(list($key1,$value1)=each($array1)){
    reset($array2);
    $i=$startfrom=0;
    while(list($key2,$value2)=each($array2)){
        if($key2<$startfrom)continue;
        if($value1==$value2){
            unset($array1[$key1],$array2[$key2]);
            $startfrom=$key2;
            break;
        }
    }
}
$safe1=explode(" ",$text1);
reset($array1);
while(list($key1,)=each($array1))
    $safe1[$key1]="<font color=green>".$safe1[$key1]."</font>";
$safe2=explode(" ",$text2);    
reset($array2);
while(list($key2,)=each($array2))
    $safe2[$key2]="<font color=red>".$safe2[$key2]."</font>";
    
echo implode(" ",$safe1)."<br><br><br>".implode(" ",$safe2); 

ergibt:

Software & Support Verlag GmbH is going to publish an International version of the PHP Magazin. This magazine was 
initiated after growing interest for an English magazine after the German version has been around for a few months. PHP 
Magazine not only informs about the scripting language itself, but also about related technologies such as the Apache Web 
Server, database [color=green]blabla[/color] technologies, [color=green]XML[/color] and other innovative internet technologies. 
Different sections within the magazine are oriented towards the specific [color=green]question[/color] areas with which a web 
developer is confronted in daily practice. The first issue will be published in December [color=green]31[/color] and the frequency of issues is two months.
You will be able to subscribe on the website which will open shortly.


Software & Support Verlag GmbH is going to publish an International version of the PHP Magazin. This magazine was 
initiated after growing interest for an English magazine after the German version has been around for a few months. PHP 
Magazine not only informs [color=red]you[/color] about the scripting language itself, but also about related technologies such as the Apache Web 
Server, database technologies, [color=red]XML1[/color] and other innovative internet technologies. 
Different sections within the magazine are oriented towards the specific [color=red]questions[/color] areas [color=red]51[/color] with [color=red]you[/color] [color=red]can[/color] which a web 
developer is confronted in daily practice. The first issue will be published in December and the frequency of issues is two months.
You will be able to subscribe on the website which will open shortly.

aber bei anderen String klappt es auch nicht 100%-ig

[MoRtAlAn]

mh... der matcht allerdings ein bisschen besser so...

mh... hast du ne ahnung, wie man den miteinbauen könnte ??levenshtein

[TBT]

so noch nen bissel optimiert,
läuft jetzt 5-6mal schneller als meine obere Variante

$array1=explode(" ",str_replace(array("  ","\r","\n"),array(" ","",""),$text1));
$array2=explode(" ",str_replace(array("  ","\r","\n"),array(" ","",""),$text2));
$max1=count($array1);
$max2=count($array2);
$startfrom=0;
for($i1=0;$i1<$max1;++$i1){
    for($i2=$startfrom;$i2<$max2;++$i2){
        if($array1[$i1]==$array2[$i2]){
            unset($array1[$i1],$array2[$i2]);
            $startfrom=$i2+1;
            break;
        }
    }
}

$safe1=explode(" ",$text1);
reset($array1);
while(list($key1,)=each($array1))
    $safe1[$key1]="<font color=green>".$safe1[$key1]."</font>";
$safe2=explode(" ",$text2);    
reset($array2);
while(list($key2,)=each($array2))
    $safe2[$key2]="<font color=red>".$safe2[$key2]."</font>";
echo implode(" ",$safe1)."<br><br><br>".implode(" ",$safe2)."<br><br>"; 

[TBT]

Achtung!

der Algorythmus hat einen ganz großen Hacken.
Er versagt total bei folgender Beispielkonstellation

$text1="Hallo Dies ist ein Text und kein einzelnes Wort";
$text2="Dies ist ein Text und kein einzelnes Wort Hallo"; 

[MoRtAlAn]

logisch, er überprüft ja nicht den "standort" des Wortes!

mh...

man müßte folgendes Einbauen:
- Vergleich der Position des Wortes
- ist ein Wort nicht vorhanden, muss es markiert werden, darf allerdings nicht mitgezählt werden, da sonst alle folgenden Wörter gekennzeichnet werden

[TBT]

ich hab da ein einen "schaukelnden" Algorythmus gedacht.
dh.

als erstes wird die Postition des Wortes aus text1 in text2 gesucht.
ist dies nicht das nächste Wort (also gleicher Text) wird die Gegenprobe
gemacht. dh das aktuelle Wort aus text2 in text1 gesucht.

Der kleinere Abstand von beiden wird dann als Ergebniss zum weiterarbeiten genutzt.

[MoRtAlAn]

mh.. auchne idee, müßte man mal testen, was mehr Performance braucht ?!

[Troublegum]

PS: es heisst Algorithmus, nicht Algorythmus.

[TBT]

Original geschrieben von Troublegum
PS: es heisst Algorithmus, nicht Algorythmus.

bei mir heißt es AlgoRythmus, weil er schaukelt ja

[TBT]

schaukel, schaukel, schaukel

$array1 = explode(" ", str_replace(array("  ", "\r", "\n"), array(" ", "", ""), $text1));
$array2 = explode(" ", str_replace(array("  ", "\r", "\n"), array(" ", "", ""), $text2));
$max1 = count($array1);
$max2 = count($array2);

$start1 = $start2 = 0;
$jump1 = $jump2 = 0;
while($start1 < $max1 && $start2 < $max2){
    $pos11 = $pos12 = $start1;
    $pos21 = $pos22 = $start2;
    $diff2 = 0; 
    // schaukel 1. Array hoch
    while($pos11 < $max1 && $array1[$pos11] != $array2[$pos21]){
        ++$pos11;
    } 
    // Ende des 1 Arrays erreicht ?
    if($pos11 == $max1){
        $start2++;
        continue;
    } 
    // Gegenschaukel wenn übersprunge Wörter
    if(($diff1 = $pos11 - $pos21) > 1){
        while($pos22 < $max2 && $array1[$pos12] != $array2[$pos22]){
            ++$pos22;
        }
        $diff2 = $pos22 - $pos12 + $jump2;
    } 
    // Ende des 2 Arrays erreicht ?
    if($pos22 == $max2){
        $start1++;
        continue;
    }
    $diff1 += $jump1; 
    // Auswertung der Schaukel
    if($diff1 >= $diff2 && $diff2){
        unset($array1[$pos12], $array2[$pos22]);
        $start1 = $pos12 + 1;
        $start2 = $pos22 + 1;
        $jump2 = $diff2;
    }else{
        unset($array1[$pos11], $array2[$pos21]);
        $start1 = $pos11 + 1;
        $start2 = $pos21 + 1;
        $jump1 = $diff1;
    }
}
$safe1 = explode(" ", $text1);
reset($array1);
while(list($key1,) = each($array1)){
    $safe1[$key1] = "<font color=green>" . $safe1[$key1] . "</font>";
}
$safe2 = explode(" ", $text2);
reset($array2);
while(list($key2,) = each($array2)){
    $safe2[$key2] = "<font color=red>" . $safe2[$key2] . "</font>";
}
echo implode(" ", $safe1) . "<br><br><br>" . implode(" ", $safe2) . "<br><br>"; 

habe bis jetzt keinen Text gefunden, bei dem nicht sinnvoll markiert wurde