confronto stringhe

[phollia]

Salve,

mi servirebbe confrontare due stringhe (una di controllo e l'altra da confrontare) ed evidenziare le differenze.
In pratica mi servirebbe poter confrontare le stringhe

1. rossadisera
2. rosso.di.sera
3. rossdisera
4. rossodisera

con una stringa di controllo [ rossodisera ] e avere come risposta qualcosa del genere:

1. rossadisera
2. rosso.di.sera
3. ross[o]disera
4. rossodisera [OK]

Oppure, in casi complessi tipo questo

rosso..di.sa ==> rosso..di.s[er]a

come fare?



Pensavo ad una analisi lettera per lettera, ma mentre nel caso 1 la cosa è semplice, in caso si caratteri in più (caso 2) o in meno (caso 3) non so come fare.

Per il caso 1 potrebbe essere qualcosa tipo:

        <?php
        $stringa_di_controllo = "rossodisera";
        $stringa_da_verificare = "rossadisera";
        
        //$stringa_da_verificare = "rossodisera";
        
        $risultato = "";
        $errori = false;
        
        for($c = 0; $c < strlen($stringa_da_verificare); $c++) 
        {
            if( substr($stringa_da_verificare, $c, 1) == substr($stringa_di_controllo, $c, 1) )
            {
                $risultato .= substr($stringa_da_verificare, $c, 1);
            }
            else
            {
                $errori = true;
                $risultato .= '<span class="errore">' . substr($stringa_da_verificare, $c, 1) . '</span>';
            }
        }


        
        if( $errori ) 
        {
            echo $risultato;
        }
        else
        {
            echo $risultato . ' [<span class="ok">OK</span>]';
        }
        ?>

Suggerimenti?

[alemoppo]

Non è un problema facile. A quest'ora poi direi che non posso pensarci!

Però, ti suggerirei di guardare questa discussione.

Ciao!

[mzanella]

Non solo non è un problema facile, ma non è nemmeno un problema ben definito, dunque non può esistere un algoritmo per risolverlo.
Ad esempio, cosa deve succedere per la stringa di controllo trincea ed il testo citarne?

[trin]citarne[a]
[trincea]citarne

sono entrambe "soluzioni" accettabili, nessuna delle due migliore dell'altra in assoluto.

Altro controesempio, astratto ma efficace, per la stringa di controllo abcabcabc ed il testo abc, per cui le seguenti soluzioni sono tutte accettabili:

abc[abcabc]
[abc]abc[abc]
[abcabc]abc
abcabcabc
abcabcabc
abcabcabc
...

Per avere un problema ben definito (e un algoritmo) hai bisogno di specificare un ordine di preferenza tra sostituzione, inserimento, cancellazione e potenzialmente altri fattori. Gli algoritmi classici da considerare sono:

• Distanza di Levenshtein
• Distanza di Damerau-Levenshtein
• Algoritmo di Needleman-Wunsch
• Algoritmo di Smith-Waterman

Probabilmente quello più adatto al tuo caso è il Needleman-Wunsch.

[phollia]

Anche se non esplicitamente dichiarato, mi sembra abbastanza limpido lo scopo della richiesta, ovvero mettere a confronto una risposta ad un gioco, in maniera visiva (per sapere se giusta o errata basta un semplice confronto, in questo caso mostrare anche l'errore).
Pur rimanendo valide tutte le "aggravanti", nel caso specifico mi pare siano abbastanza fuori luogo, potendosi far ricadere gli errori nelle fattispecie elencate. Certo, nulla è da escludere a priori, ma sono eventualità talmente remote da poterle trascurare.

Ecco quindi circoscritto e spiegato il campo.
Che sia un problema di non facile soluzione ne sono cosciente, ma la risposta di mzanella mi sembra meno circoscritta del problema stesso, proprio perchè, a mio avviso, l'intento era abbastanza chiaro.

[mzanella]

Certo, il problema è estremamente chiaro. Chiaro e non ben definito, queste due espressioni non si escludono a vicenda.

L'esempio trincea - citarne non era casuale: sono anagrammi, il che può mettere in difficoltà "soluzioni" euristiche. In quel caso come ci si deve comportare? Considerare citarne del tutto sbagliata o "salvare" le lettere c ed e?
Lo stesso per l'esempio abcabcabc, astratto ma paradigmatico dei casi di ripetizioni all'interno di una frase. Sul momento non avevo trovato un esempio "linguistico", ma ne esistono di realistici. Come grosse ossa nella fossa confrontato con ossi:

[gr]ossi[e ossa nella fossa]
[grosse ]ossi[a nella fossa]
[grosse ossa nella f]ossi[a]
[gr]o[sse os]s[a nella fo]si[sa]

O fatto il misfatto contro affatto (uso <...> per indicare una sostituzione):

[fatto il m]<is>fatto
affatto[ il misfatto]

la risposta di mzanella mi sembra meno circoscritta del problema stesso

Nauralmente! Gli algoritmi citati nell'altro messaggio risolvono problemi più generali del tuo dunque, per definizione, risolvono anche il tuo. Si tratta solo di prenderne uno ed istanziarlo al tuo caso specifico, il che è, a mio avviso, preferibile rispetto ad inventarsi da zero un approccio euristico incompleto.

[calcmore]

Ciao, facendo un po di prove ho ottenuto questo:



ti lascio il codice...

<?php
$str =  'ROSSO DI SERA';
$str2 = 'ROXSSO DDDDDDI SHERA';
//$str2 = 'ROSSA DI SERA';

echo '<br>'.$str.'<br>';
echo $str2.'<br><br>';
echo 'risultati scansione:<br>';

if (strlen($str) == strlen($str2)) // stringhe di uguale lunghezza
for ($k=0; $k < strlen($str); $k += 1)
    if ($str[$k] != $str2[$k])
        echo '<font color="red">'.$str2[$k].'</font>'; // evidenzia le lettere errate
    else
        echo $str2[$k];

if (strlen($str) < strlen($str2)) // seconda stringa piu' lunga
  {
     $k = 0; $k3 = 0;
     while ($k < strlen($str))
      {
          for ($k2 = 0; $k2 < strLen($str2); $k2 += 1)
           {
              if ($str[$k] == $str2[$k3+$k2])
                         break;
                  else
                         echo '<font color="red">'.$str2[$k3+$k2].'</font>';    // evidenzia le lettere errate             
           }    
        echo $str2[$k3+$k2];
        $k = $k + 1;
        $k3 = $k3 + $k2 + 1;
            
      }
  }    


?>

praticamente $k è la posizione sulla prima stringa, la quale viene confrontata con la posizione della seconda stringa, che è rappresentata $k2+$k3...non so se è chiaro...

[alemoppo]

Ma hai provato con il codice che ti ho indicato?

http://alemoppo.altervista.org/LABS/...b=rosso..di.sa

<?php
function computeDiff($from, $to)
{
    $diffValues = array();
    $diffMask = array();

    $dm = array();
    $n1 = count($from);
    $n2 = count($to);

    for ($j = -1; $j < $n2; $j++) $dm[-1][$j] = 0;
    for ($i = -1; $i < $n1; $i++) $dm[$i][-1] = 0;
    for ($i = 0; $i < $n1; $i++)
    {
        for ($j = 0; $j < $n2; $j++)
        {
            if ($from[$i] == $to[$j])
            {
                $ad = $dm[$i - 1][$j - 1];
                $dm[$i][$j] = $ad + 1;
            }
            else
            {
                $a1 = $dm[$i - 1][$j];
                $a2 = $dm[$i][$j - 1];
                $dm[$i][$j] = max($a1, $a2);
            }
        }
    }

    $i = $n1 - 1;
    $j = $n2 - 1;
    while (($i > -1) || ($j > -1))
    {
        if ($j > -1)
        {
            if ($dm[$i][$j - 1] == $dm[$i][$j])
            {
                $diffValues[] = $to[$j];
                $diffMask[] = 1;
                $j--;  
                continue;              
            }
        }
        if ($i > -1)
        {
            if ($dm[$i - 1][$j] == $dm[$i][$j])
            {
                $diffValues[] = $from[$i];
                $diffMask[] = -1;
                $i--;
                continue;              
            }
        }
        {
            $diffValues[] = $from[$i];
            $diffMask[] = 0;
            $i--;
            $j--;
        }
    }    

    $diffValues = array_reverse($diffValues);
    $diffMask = array_reverse($diffMask);

    return array('values' => $diffValues, 'mask' => $diffMask);
}
function diffline($line1, $line2)
{
    $diff = computeDiff(str_split($line1), str_split($line2));
    $diffval = $diff['values'];
    $diffmask = $diff['mask'];

    $n = count($diffval);
    $pmc = 0;
    $result = '';
    for ($i = 0; $i < $n; $i++)
    {
        $mc = $diffmask[$i];
        if ($mc != $pmc)
        {
            switch ($pmc)
            {
                case -1: $result .= '</del>'; break;
                case 1: $result .= '</ins>'; break;
            }
            switch ($mc)
            {
                case -1: $result .= '<del>'; break;
                case 1: $result .= '<ins>'; break;
            }
        }
        $result .= $diffval[$i];

        $pmc = $mc;
    }
    switch ($pmc)
    {
        case -1: $result .= '</del>'; break;
        case 1: $result .= '</ins>'; break;
    }

    return $result;
}

echo '<p>Originale: '.$_GET['a'].'</p><p>Da confrontare: '.$_GET['b'].'</p>'.PHP_EOL;

echo diffline($_GET['a'],$_GET['b']);

Ciao!

[phollia]

@alemoppo: avevo aperto il link ma non ho avuto il tempo di approfondire, ma ti ringrazio garantendoti di approfondire al più presto.

@calcmore: Grazie. Do' un'occhiata anche al tuo codice.

@mzanella: Il tuo discorso non fa una piega in generale. Ti ripeto però che dovendo essere un algoritmo che mostra visivamente la corrispondenza tra una stringa (di risposta) e un'altra (risolutiva) le situazioni estreme non le considero nemmeno.
La situazione è questa: Gioco (ad es. un indovinello) la cui soluzione è "la pasta". Ora un giocatore può scrivere correttamente "la pasta", oppure può, sbagliando, scrivere "la.pasta" oppure "le paste" o solo "pasta".
Ora "normalizzando" (ovvero riducendole ai "minimi termini" eliminando gli spazi e sostituendo le accentate con le corrispondenti vocali non accentate) le due stringhe possono essere confrontate. E in situazioni come questa, non avrai mai (a meno di scrivere lucciole per lanterne) situazioni estreme e comunque il confronto sarà "posizionale" ovvero dando peso alla posizione delle singole lettere nella frase e quindi l'esempio trincea/citarne sarebbe del tutto errato (ed anche fuori contesto).
Certamente sistemi più complessi risolvono anche questi, ma val la pena usare il bazooka per uccidere una zanzara, o, per quanto improbabile, finanche un leone?
Ti ringrazio, sempre e comunque, lo sprone anche sull'approccio ai problemi aiuta a crescere, ma in questo caso, forse, il passo sarebbe troppo.

[mzanella]

Forse mi sono spiegato male io
Ci riprovo! Nel primo messaggio hai mostrato tre casi in cui le risposte contengono rispettivamente una sostituzione, due inserimenti ed una rimozione. Poi un quarto caso, più complesso, con tre inserimenti e due rimozioni, suggerendo che le tre operazioni si possono mescolare arbitrariamente.
Hai descritto (immagino involontariamente) esattamente le operazioni di base degli algoritmi di Levenshtein e degli altri citati.

Ciò che mancava era il come trattare certi casi.
Supponiamo pure di voler ignorare i casi "limite", ovvero "lucciole per lanterne", cioè parole "troppo" diverse: allora bisogna capire quant'è questo "troppo". Ma per farlo bisogna avere uno strumento per misurare la somiglianza tra due stringhe, il che riporta al punto di partenza. Per evitare il circolo vizioso basta fare un piccolo passo ed assegnare un ordine di preferenza (o costo) alle operazioni. Molto banalmente "se devi scegliere tra a[bca]b e ab[cab], preferisci la prima".

Ma questo porta esattamente agli algoritmi di cui parlavo. D'altronde, se si chiamano algoritmi per il confronto tra stringhe un motivo ci sarà, no?

Riguardo alla "complessità", qualsiasi sia la soluzione che adotterai sarà necessariamente almeno tanto complessa quanto uno qualunque degli algoritmi classici (per motivi che ometto per brevità). I codici mostrati da calcmore ed alemoppo, ad esempio, sono già più lunghi della distanza di Levenshtein...
Un po' come quando usi la funzione sort di PHP: potresti definirne una ad-hoc per il tuo vettore, ma alla fine ti renderesti conto che il codice sarebbe per la maggior parte identico a quello della funzione sort ma meno generale.