[Algoritme (elke taal)] Verschillen tussen 2 strings

[Jurgle]

Ik ben op zoek naar een algoritme dat twee strings met elkaar vergelijkt en de toegevoegde, veranderde of verwijderde tekst aangeeft.

Zoekresultaten op dit onderwerp leveren Levenshtein en dergelijke dingen op, maar die berekenen een score.

Het probleem zit in de complexiteit en dus performance, en als delen van de tekst vaker voorkomen in die tekst. Omdat moeilijk uit te drukken is wat ik precies bedoel geef ik hieronder een voorbeeld van wat ik bedoel (in PHP):

De functie aanroep:

code:

  $result = str_vergelijk($str1, $str2);

Als de input hier is:
1: "Ik woon in Nederland."
2: "Ik heb in Nederland gewoond."

Het resultaat zou bijvoorbeeld kunnen zijn (de vorm van Array is slechts een suggestie):

code:

$result = array(  
                 [0] => array(
                              [0] => 'normaal',  
                              [1] => 'Ik ')  
                 [1] => array(  
                              [0] => 'veranderd',  
                              [1] => 'woon',  
                              [2] => 'heb')  
                 [2] => array(  
                              [0] => 'normaal',  
                              [1] => ' in Nederland ')  
                 [3] => array(  
                              [0] => 'toegevoegd',  
                              [1] => 'gewoond'))

Ik hoop dat hiermee duidelijk is wat ik bedoel en dat iemand een idee heeft hoe dit op te lossen is.

[ Voor 29% gewijzigd door Jurgle op 28-09-2003 20:41 ]

[slm]

In http://nl2.php.net/manual/nl/function.levenshtein.php heeft ene bisqwit een 'toevoeging' op de levenshtein functie geschreven die een beetje doet wat jij wilt.

[Verwijderd]

Het is een beetje moeilijk om uit te leggen, maar misschien dat je wat hebt aan dit voorbeeldje...

PHP:

function compareString($stringA, $stringB)
{
    echo "<code>";

    $stringA = explode(" ", $stringA);
    $stringB = explode(" ", $stringB);
    
    $maximumElements = count($stringA) > count($stringB) ? count($stringA) : count($stringB);

    for($i = 0; $i < $maximumElements; ++$i)
    {
        if($i > (count($stringA) - 1) || $i > (count($stringB) - 1))
        {
            echo "TOEGEVOED     " . $stringA[$i] . $stringB[$i] . "<br>";
        }
        else
        {
            if(strToUpper($stringA[$i]) == strToUpper($stringB[$i]))
            {
                echo "GELIJK        " . $stringA[$i] . "<br>";
            }
            else
            {
                echo "VERANDERD     " . $stringA[$i] . " / " . $stringB[$i] . "<br>";
            }
        }
    }
    
    echo "</code>";
}

Het is al wat oude code die ik nu een beetje heb aangepast, het is dus wat buggy, maar misschien heb je er wat aan. Succes .

[ Voor 10% gewijzigd door Verwijderd op 27-09-2003 15:48 ]

[Jurgle]

Het voorbeeld van php.net klopt aardig, maar is veeeel te langzaam, helaas. Hij zoekt ook nog eens op letterniveau, terwijl woordniveau op zich genoeg is en misschien sneller.

Het probleem bij het algoritme is dat als je in iets toevoegd aan de string, maar niet aan het einde, dat een functie als hierboven de rest als veranderd opvat. Het detecteren van het vervolg van originele tekst in de veranderde string ten opzichte van de eerste string is moeilijk...

[ Voor 31% gewijzigd door Jurgle op 27-09-2003 16:19 ]

[madwizard]

Zou je niet het levenshtein algoritme kunnen gebruiken op woord niveau? Ik heb ooit het algoritme gezien waarbij de uiteindelijke 'kosten' (=afstand) berekend werden met drie verschillende waarden (de kosten voor invoegen, wijzigen en verwijderen apart). Misschien dat je daaruit iets kan afleiden, bijvoorbeeld alle mogelijke combinaties af gaan en de kosten berekenen, dan uiteindelijk de combinatie met de laagste kosten kiezen en daar aan de hand van die 3 verschillend kostende operaties bepalen welke woorden vervangen, toegevoegd of verwijderd moeten worden. Ik weet niet of het algoritme zo werkt dat dit kan maar volgens mij wel...
Ik zal eens kijken of ik die pagina nog kan vinden.

[drm]

[C]:

PHP:

// ...
    $maximumElements = count($stringA) > count($stringB) ? count($stringA) : count($stringB);
// ...

offtopic:
Voor dit soort dingen hebben ze nou functies als max() uitgevonden

En als het dan toch om performance gaat is het beter niet elke keer de count functie aan te roepen maar de resultaten van die aanroepen al in het begin even in hulpvariabelen te zetten, aangezien ze toch constant zijn voor de duur van de functie.

[MisterData]

In PHP is er levenshtein

edit:
lezen MD

[ Voor 21% gewijzigd door MisterData op 27-09-2003 17:16 ]

[thomaske]

MisterData schreef op 27 September 2003 @ 17:02:
In PHP is er levenshtein

offtopic:
Lees de draad voordat je blaat

[djluc]

Dat wisten we al als je het topic gelezen had, dan blijkt ook dat dit niet voldoet. Zie ook de post van slm.

edit:

[ Voor 9% gewijzigd door djluc op 27-09-2003 17:10 ]

[madwizard]

Ik heb wat gevonden denk ik..

Zie: http://www.merriampark.com/ld.htm
Levenhstein wordt berekend door de matrix te initaliseren (step 1 en 2 van bovenstaande url). Daarna wordt voor elk hokje een waarde bepaald, en wel het minimum van de volgende waarden:

1. Waarde van de cel links van de huidige cel + remove_kosten
2. Waarde van de cel boven de huidige cel + insert_kosten
3. Waarde van de cel linksboven de huidige cel + transform_kosten

Transform_kosten zijn niet altijd hetzelfde, het is 0 als je transformt naar hetzelfde teken ('A' wordt 'A' is natuurlijk niet een echt een transformatie), en iets anders (1 meestal) als het echt een andere letter wordt ('A' wordt 'B').

Dit gaat zo door voor de hele matrix en aan het eind staat rechtsonder in de matrix de uiteindelijke kosten. Doordat steeds het minimum is gekozen heb je uiteindelijk de totalen kosten van het minimale pad naar het begin (0,0), waarbij verschillende stappen (rechts, onder, diagonaal) ook verschilende kosten kunnen hebben.

Kijk nu hier:
http://www.sfu.ca/~anoop/...25-Fall-2003/editdist.pdf
(pas op, in deze tekst zijn de target en source string precies andersom neergezet als in de andere tekst boven)

Op pagina 6 staat zo'n matrix als in de andere tekst, maar nu met een pad erbij.. Volgens mij (dit heb ik zelf maar afgeleid, weet niet of het bewezen is enzo maar lijkt me wel logisch) is dit pad het pad dat je zoekt (de optimale manier om van source naar target te komen, of 1 van de even optimale manieren), en bepaalde de richting in elke stap de actie die ondernomen is (insert, transform of remove).

Het pad kun je vinden door rechtsonder te beginnen, en dan steeds van de 3 hokjes links/boven/linksboven eentje te kiezen met de laagste waarde (en dat dan herhaald).

Ik heb even een programmaatje geschreven met een oude levensthein implementatie van mij die de hele matrix aan het eind uitprint.. Hier een voorbeeldje:
(Van ABCD naar AECDF)

De uiteindelijke distance is dus 2 (rechtsonder).

Als je nu de vakjes in het korste pad kleurt (dwz rechtsonder beginnen, en dan herhalend het minimum kiezen van het vakje links/boven/linksboven)), krijg je het volgende:

De tabel daar onder is daar weer van afgeleid: x en y zijn de x en y coordinaten van de gekleurde vakjes. d is de actie ten opzichte van het vorige vakje (s = diagonaal, substitutie/transformatie, i = verticaal, insertion, d = horizontaal, deletion). s en t zijn de letters in de source en target strings op posities x en y (s[x-1], t[y-1] zeg maar).
Lees nu de laatste drie kolommen van de tabel van benen naar boven en je ziet de acties die ondernomen zijn om de string om te zetten:

substitutie van A naar A (telt niet, blijft gelijk)
substitutie van B naar E
substitutie van C naar C (telt ook niet)
substitutie van D naar D (idem)
insertion van D naar F (D slaat nergens op hier, maar F wordt dus toegevoegd)

Nu zal je zien dat dat ook klopt, je begint met ABCD.

A blijft gelijk: ABCD
B wordt E: AECF
C blijft gelijk: AECD
D blijft gelijk: AECD
F wordt toegevoegd: AECDF

En je hebt je doel gevonden! Vervang nu eens de letters met de volgende woorden:

A=ik
B=woon
C=in
D=amsterdam
E=heb
F=gewoond

En je hebt precies wat je zoekt volgens mij

[ Voor 3% gewijzigd door madwizard op 27-09-2003 17:46 ]

[madwizard]

Nog een voorbeeldje: fietsenmaker -> jandeman



fietsenmaker
-ietsenmaker: F weg
jetsenmaker: I wordt J
jatsenmaker: E wordt A
jansenmaker: T wordt N
jandenmaker: S wordt D
jandenmaker: E blijft gelijk
jande-maker: N weg
jandemaker: M blijft gelijk
jandemaker: A blijft gelijk
jandema-er: K verwijderen
jandema-r: E verwijderen
jandeman: R wordt N

[ Voor 8% gewijzigd door madwizard op 27-09-2003 18:06 ]

[flashin]

Lijkt mij goed van je als je dat algoritme in een programma kan schrijven met goede performance, kwil wel graag het eindresultaat zien

[madwizard]

Bij een normale levenshtein functie die alleen een score hoeft te geven kan je het geheugengebruik reduceren tot 2 rijen, omdat je de waardes van oudere rijen nooit meer nodig hebt. Heb ooit eens een aantal implementaties gemaakt (waaronder assembler) die daar gebruik van maakten. Maar als je het pad weer wilt weten zoals hierboven zul je wel de complete matrix in het geheugen moeten houden, dat gebruikt weer meer geheugen.. Op zich nog wel redelijk hoor, 256x256 is bijvoorbeeld 65536 elementen, niet echt een probleem.. Bovendien is het algoritme redelijk complex (m*n) dus het is sowieso niet echt aan te raden voor enorme strings.
Dus Jurgle: Wat is ongeveer je doel van de functie? Zijn de zinnen lang?

Ik zal kijken of ik een C++ implementatie kan maken.

[madwizard]

Okee hier is een implementatie, verre van optimaal maar hij is ook gemaakt op de leesbaarheid. Het pad wordt in omgekeerde volgorde weergegeven, maar het uiteindelijke omdraaien zal het probleem niet zijn.

C++:

#include <iostream>
#include <vector>
#include <iomanip>
#include <limits>
#include <sstream>

using namespace std;

levenshtein(const char *s, const char *t, int n, int m)
{
    vector< vector<int> > d(n+1);   // Cost matrix
    int i, j;                       // Matrix indices

    // Initialize first row with 0..n
    for (i=0;i<=n;i++)
    {
        d[i].resize(m+1);
        d[i][0] = i;
    }

    // Intialize first column with 0..m
    for (j=0;j<=m;j++)
      d[0][j] = j;

    // Cost calculation loop
    for (i=1;i<=n;i++)
    {
        int subCost;
        char sc = s[i-1];
        for(j=1;j<=m;j++)
        {
            if (sc==t[j-1]) // Characters are equal, no cost
                subCost = 0;
            else            // Characters are not equal, costs 1
                subCost = 1;
    
            int left = d[i-1][j] + 1;               // left + deletion cost
            int above = d[i][j-1] + 1;              // above + insertion cose
            int diagonal = d[i-1][j-1] + subCost;   // diagonal + substitution cost
            d[i][j] = min(above, min(left, diagonal)); // Put minimum in current cell
        }
    }

    i = n;
    j = m;

    // Find the optimal path backwards:
    while(!(i==0 && j==0))
    {
        int cur = d[i][j];

        int left     = (i==0) ? numeric_limits<int>::max() : d[i-1][j];
        int above    = (j==0) ? numeric_limits<int>::max() : d[i][j-1];
        int diagonal = (i==0 || j==0) ? numeric_limits<int>::max() : d[i-1][j-1];
        int minimal =  min(above, min(left, diagonal));
        
        // Choose minimal of left, above and diagonal:
        if (diagonal==minimal)
        {
            char sc = s[i-1],
                 tc = t[j-1];
            if (sc==tc)
                cout << "Leave '" << sc << "' the same" << endl;
            else
                cout << "Substitute '" << sc << "' with '" << tc << "'" << endl ;
            i--;
            j--;
        }
        else if (above==minimal)
        {
            cout << "Insert '" << t[j-1] << "'" << endl;
            j--;
        }
        else // left==minimal
        {
            cout << "Delete '" << s[i-1] << "'" << endl;
            i--;
        }

    }
    return d[n][m];
}


int main(int argc, char* argv[])
{
    const char str1[] = "fietsenmaker";
    const char str2[] = "jandeman";
    cout << "Distance is: " << levenshtein(str1, str2, strlen(str1), strlen(str2));
    return 0;
}

Output van bovenstaande is:

code:

Substitute 'r' with 'n'
Delete 'e'
Delete 'k'
Leave 'a' the same
Leave 'm' the same
Delete 'n'
Leave 'e' the same
Substitute 's' with 'd'
Substitute 't' with 'n'
Substitute 'e' with 'a'
Substitute 'i' with 'j'
Delete 'f'
Distance is: 9

edit:
Voor de liefhebbers, een compileerde versie met eigen input:
http://www.madwizard.org/temp/lev.zip

edit:
'blijft hetzelfde' vergeten

[ Voor 45% gewijzigd door madwizard op 27-09-2003 20:10 ]

[Jurgle]

Dudes! Ik denk dat ik hier wel een heel eind mee kom, heel erg bedankt. Ik ga het gebruiken in PHP en zal het eindresultaat posten.

[curry684]

offtopic:
madwizard

[Jurgle]

Ik had het resultaat nog beloofd, bij deze:

PHP:

<?PHP
function levenshteinX($s, $t, $wantArray = 0, $debug = 0)
{
   if(is_array($s))
   {
      $n = count($s);
      $m = count($t);
   }
   else
   {
      $n = strlen($s);
      $m = strlen($t);
   }
   
   $matrix = array();
   
   // Initialize first row with 0..n 
   for($i = 0; $i <= $n; $i++) 
      $d[$i][0] = $i; 

   // Intialize first column with 0..m 
   for($j = 0; $j <= $m; $j++) 
      $d[0][$j] = $j; 

   // Cost calculation loop 
   $maxSubCost = 0;
   for($i = 1; $i <= $n; $i++) 
   { 
      $sc = $s[($i - 1)]; 
      for($j = 1; $j <= $m; $j++) 
      { 
         if(preg_replace('/[[:punct:]]/', '', $sc) == preg_replace('/[[:punct:]]/', '', $t[($j - 1)])) // Characters are equal, no cost 
           $subCost = 0; 
         else            // Characters are not equal, costs 1 
           $subCost = 1; 
         
         $left = $d[($i - 1)][$j] + 1;               // left + deletion cost 
         $above = $d[$i][($j - 1)] + 1;              // above + insertion cose 
         $diagonal = $d[($i - 1)][($j - 1)] + $subCost;   // diagonal + substitution cost 
         $d[$i][$j] = min($above, min($left, $diagonal)); // Put minimum in current cell 
         
         if($d[$i][$j] > $maxSubCost)
            $maxSubCost = $d[$i][$j];
      } 
   } 

   $i = $n; 
   $j = $m; 

   // Find the optimal path backwards:
   if($wantArray)
   {
      $res = array();
      $stappen = 0;
      
      while(!($i == 0 && $j == 0)) 
      { 
         $stappen++;
         $left = ($i == 0)? $maxSubCost : $d[($i - 1)][$j]; 
         $above = ($j == 0)? $maxSubCost : $d[$i][($j - 1)]; 
         $diagonal = ($i == 0 || $j == 0)? $maxSubCost : $d[($i - 1)][($j - 1)]; 
         $minimal =  min($above, min($left, $diagonal)); 

         // Choose minimal of left, above and diagonal: 
         if($diagonal == $minimal) 
         { 
            $sc = $s[($i - 1)];
            $tc = $t[($j - 1)]; 

            if(preg_replace('/[[:punct:]]/', '', $sc) == preg_replace('/[[:punct:]]/', '', $tc)) 
            {
               if($debug) echo "Leave '".$tc."' the same<br>"; 
               $res[] = array('0', $tc);
            }
            else 
            {
               if($debug) echo "Substitute '".$sc."' with '".$tc."'<br>"; 
               $res[] = array('1', $sc, $tc);
            }
            
            $i--; 
            $j--; 
         } 
         else if($above == $minimal) 
         { 
            if($debug) echo "Insert '".$t[($j - 1)]."'<br>"; 
            $res[] = array('+', $t[($j - 1)]);
            $j--; 
         } 
         else // left==minimal 
         { 
            if($debug) echo "Delete '".$s[($i - 1)]."'<br>"; 
            $res[] = array('-', $s[($i - 1)]);
            $i--; 
         } 
      }
      
      $res[] = array($d[$n][$m], $stappen);
      
      $res = array_reverse($res);
      
      return $res;
   }
   return $d[$n][$m];
}

$str1 = "Emerce bericht dat het sturen van ongevraagde e-mails aan Nederlandse bedrijven niet strafbaar wordt als de vernieuwde Telecommunicatiewet wordt aangenomen. Het PvdA-kamerlid Martijn van Dam, degene die dit voorstel had ingediend, stelt op zijn site dat een dergelijke maatregel in strijd zou zijn met Europese wetgeving. Van Dam heeft een viertal wijzigingen van de Telecommunicatiewet voorgesteld, om spammers en telemarketeers het leven moeilijker te maken. Zo zou spam een economisch delict worden waar een boete van 4500 euro opstaat, moet de verzender van reclame kunnen aantonen dat er vooraf om toestemming gevraagd is, en zou aan het eind van telemarketinggesprekken gevraagd moeten worden of iemand in de toekomst opnieuw gebeld wil worden. Het vierde voorstel, het verbieden van spammen aan bedrijven, was onder meer bedoeld om de grote financiële schade die spam bedrijven toebrengt, te verminderen. Van Dam stelt echter dat het intrekken van dat deel van het voorstel nodig is om de andere maatregelen wel door de Kamer te krijgen.";
$str2 = "Emerce bericht dat het sturen van ongevraagde e-mails aan Nederlandse bedrijven niet strafbaar wordt als de vernieuwde Telecommunicatiewet wordt aangenomen. Deze tekst is toegevoegd. Het PvdA-kamerlid M. van Dam, degene die dit voorstel had ingediend, stelt op zijn homepage dat een dergelijke maatregel in strijd zou zijn met Europese wetgeving. Van Dam heeft een viertal wijzigingen van de Telecommunicatiewet voorgesteld, om spammers (hufters) en telemarketeers het leven moeilijker te maken. Zo zou spam een economisch delict worden waar een boete van 4500 euro opstaat, moet de verzender van reclame kunnen aantonen dat er vooraf om toestemming gevraagd is, en zou aan het eind van telemarketinggesprekken gevraagd moeten worden of iemand in de toekomst opnieuw gebeld wil worden. Het vierde voorstel, het verbieden van spammen aan bedrijven, was onder meer bedoeld om de grote financiële schade die spam bedrijven toebrengt, te verminderen. Van Dam stelt echter dat het intrekken van dat deel van het voorstel nodig is om de andere maatregelen wel door de Kamer te krijgen.";

$res = levenshteinX(explode(" ", $str1), explode(" ", $str2), 1);
echo round(($res[0][0]/$res[0][1])*100)."% van de operaties waren wijzigingen...<br>";

for($i = 1; $i < count($res); $i++)
{
   if($res[$i][0] == '0')
      echo $res[$i][1]." ";
   else if($res[$i][0] == '1')
      echo "<span style='background-color: #FFAAAA'>".$res[$i][1]." </span><span style='background-color: #AAFFAA'>".$res[$i][2]." </span>";
   else if($res[$i][0] == '+')
      echo "<span style='background-color: #AAFFAA'>".$res[$i][1]." </span>";
   else if($res[$i][0] == '-')
      echo "<span style='background-color: #FFAAAA'>".$res[$i][1]." </span>";
}
?>

edit:

Oja, de aanroep is:
$mixed = levenshteinX($mixed1, $mixed2, $booleanMode, $booleanDebug)

mixed1 is een array van woorden/alinea's/hoofdstukken/boeken/etc.. OF een string
mixed2 is dezelfde vorm als mixed1
booleanMode is standaard 0, dan gedraagtie zich als de gewonen levenshtein() functie uit PHP, anders geeftie een array terug, met een vorm die duidelijk mag zijn uit het voorbeeld.
booleanDebug.... tsja.

[ Voor 10% gewijzigd door Jurgle op 29-09-2003 12:42 ]

[T-MOB]

offtopic:
$str1 = "System V code";
$str2 = "Linux kernel code";
:-)