Visualizzazione risultati 1 fino 9 di 9
Like Tree1Likes
  • 1 Post By mzanella

Discussione: confronto stringhe

  1. #1
    phollia non è connesso Utente giovane
    Data registrazione
    05-02-2015
    Messaggi
    68

    Predefinito confronto stringhe

    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

    Codice:
    1. rossadisera
    2. rosso.di.sera
    3. rossdisera
    4. rossodisera
    con una stringa di controllo [ rossodisera ] e avere come risposta qualcosa del genere:

    Codice:
    1. rossadisera
    2. rosso.di.sera
    3. ross[o]disera
    4. rossodisera [OK]
    Oppure, in casi complessi tipo questo

    Codice:
    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:

    Codice PHP:
    <?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?
    Ultima modifica di phollia : 16-08-2018 alle ore 23.54.29

  2. #2
    L'avatar di alemoppo
    alemoppo non è connesso Staff AV
    Data registrazione
    24-08-2008
    Residenza
    PU / BO
    Messaggi
    22,067

    Predefinito

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

    Però, ti suggerirei di guardare questa discussione.

    Ciao!

  3. #3
    mzanella non è connesso AlterGuru
    Data registrazione
    29-12-2015
    Messaggi
    1,954

    Predefinito

    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?
    Codice:
    [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:
    Codice:
    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:

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

    I suggerimenti che do più spesso:


  4. #4
    phollia non è connesso Utente giovane
    Data registrazione
    05-02-2015
    Messaggi
    68

    Predefinito

    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.

  5. #5
    mzanella non è connesso AlterGuru
    Data registrazione
    29-12-2015
    Messaggi
    1,954

    Predefinito

    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:
    Codice:
    [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):
    Codice:
    [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.
    Ultima modifica di mzanella : 17-08-2018 alle ore 13.59.50

    I suggerimenti che do più spesso:


  6. #6
    calcmore non è connesso Utente giovane
    Data registrazione
    05-05-2018
    Messaggi
    69

    Predefinito

    Ciao, facendo un po di prove ho ottenuto questo:



    ti lascio il codice...

    Codice PHP:
    <?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...
    Ultima modifica di calcmore : 17-08-2018 alle ore 17.31.12

  7. #7
    L'avatar di alemoppo
    alemoppo non è connesso Staff AV
    Data registrazione
    24-08-2008
    Residenza
    PU / BO
    Messaggi
    22,067

    Predefinito

    Ma hai provato con il codice che ti ho indicato?

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

    Codice PHP:
    <?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!
    Ultima modifica di alemoppo : 17-08-2018 alle ore 16.07.15

  8. #8
    phollia non è connesso Utente giovane
    Data registrazione
    05-02-2015
    Messaggi
    68

    Predefinito

    @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.
    Ultima modifica di phollia : 17-08-2018 alle ore 17.13.27

  9. #9
    mzanella non è connesso AlterGuru
    Data registrazione
    29-12-2015
    Messaggi
    1,954

    Predefinito

    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.
    programmazioned likes this.

    I suggerimenti che do più spesso:


Regole di scrittura

  • Non puoi creare nuove discussioni
  • Non puoi rispondere ai messaggi
  • Non puoi inserire allegati.
  • Non puoi modificare i tuoi messaggi
  •