Domanda qual è una buona metrica per decidere se 2 stringhe sono "abbastanza simili"


Sto lavorando ad un algoritmo molto approssimativo, in prima bozza, per determinare quanto siano simili 2 stringhe. Sto anche usando Levenshtein Distance per calcolare la distanza di modifica tra le stringhe.

Al momento, ciò che sto facendo è prendere il numero totale di modifiche e dividerlo in base alla dimensione della stringa più grande. Se quel valore è al di sotto di una soglia, attualmente impostata casualmente al 25%, allora sono "abbastanza simili".

Tuttavia, questo è totalmente arbitrario e non penso sia un ottimo modo per calcolare la somiglianza. C'è un qualche tipo di equazione matematica o un approccio di probabilità / statistica per prendere i dati di Levenshtein Distance e usarlo per dire "sì, queste stringhe sono abbastanza simili in base al numero di modifiche apportate e alla dimensione delle stringhe"?

Inoltre, la cosa fondamentale qui è che sto usando una soglia arbitraria e preferirei non farlo. Come posso calcolare questa soglia invece di assegnarla in modo da poter dire con sicurezza che sono 2 le stringhe "abbastanza simile"?

AGGIORNARE

Sto confrontando le stringhe che rappresentano una traccia dello stack Java. La ragione per cui voglio farlo è raggruppare un gruppo di tracce dello stack date per similarità e usarlo come filtro per ordinare "cose" :) Questo raggruppamento è importante per un motivo di livello superiore che non posso condividere esattamente pubblicamente.


Finora, il mio algoritmo (pseudo codice) è grosso modo simile a:

/*
 * The input lists represent the Strings I want to test for similarity. The
 * Strings are split apart based on new lines / carriage returns because Java
 * stack traces are not a giant one-line String, rather a multi-line String.
 * So each element in the input lists is a "line" from its stack trace.
 */
calculate similarity (List<String> list1, List<String> list2) {

    length1 = 0;
    length2 = 0;
    levenshteinDistance = 0;

    iterator1 = list1.iterator();
    iterator2 = list2.iterator();

    while ( iterator1.hasNext() && iterator2.hasNext() ) {

        // skip blank/empty lines because they are not interesting
        str1 = iterator1.next();    length1 += str1.length();
        str2 = iterator2.next();    length2 += str2.length();

        levensteinDistance += getLevenshteinDistance(str1, str2);
    }

    // handle the rest of the lines from the iterator that has not terminated

    difference = levenshteinDistance / Math.max(length1, length2);

    return (difference < 0.25) ? true : false; // <- arbitrary threshold, yuck!
}

23
2017-12-09 20:53


origine


risposte:


Che ne dici di usare la somiglianza del coseno? Questa è una tecnica generale per valutare la somiglianza tra due testi. Funziona come segue:

Prendi tutte le lettere di entrambe le stringhe e costruisci una tabella come questa:

Letter | String1 | String2

Questo può essere un semplice hash table o qualsiasi altra cosa.

Nella colonna della lettera metti ogni lettera e nelle colonne della stringa inserisci la loro frequenza all'interno di quella stringa (se una lettera non appare in una stringa il valore è 0).

Si chiama similarità del coseno perché interpreta ciascuna delle due colonne di stringhe come vettori, dove ogni componente è il numero associato a una lettera. Quindi, calcola il coseno dell '"angolo" tra i vettori come:

C = (V1 * V2) / (|V1| * |V2|)

Il numeratore è il prodotto punto, ovvero la somma dei prodotti dei componenti corrispondenti e il denominatore è il prodotto delle dimensioni dei vettori.

Quanto vicino C è a 1 ti dà quanto sono simili le stringhe.

Può sembrare complicato ma sono solo alcune righe di codice una volta capito l'idea.

Vediamo un esempio: considera le stringhe

s1 = aabccdd
s2 = ababcd

La tabella ha il seguente aspetto:

Letter a b c d
s1     2 1 2 2
s2     2 2 1 1

E quindi:

C = (V1 * V2) / (|V1| * |V2|) = 
(2 * 2 + 1 * 2 + 2 * 1 + 2 * 1) / (sqrt(13) * sqrt(10)) = 0.877

Quindi sono "abbastanza" simili.


20
2017-12-09 21:11



Le tracce dello stack sono in un formato suscettibile di analisi. Vorrei solo analizzare le tracce dello stack utilizzando una libreria di analisi e quindi è possibile estrarre qualsiasi contenuto semantico che si desidera confrontare.

Gli algoritmi di similarità saranno più lenti e difficili da eseguire il debug quando le stringhe non vengono confrontate come previsto.


4
2017-12-09 21:27



Ecco la mia opinione su questo - solo una lunga storia da considerare e non necessariamente una risposta al tuo problema:

Ho fatto qualcosa di simile in passato, dove avrei cercato di determinare se qualcuno stesse plagiando semplicemente riordinando le frasi mantenendo lo stesso tipo di messaggio.

1 "i bambini dovrebbero giocare mentre ceniamo"
2 "mentre ceniamo, i bambini dovrebbero giocare"
3 "dovremmo mangiare bambini mentre giochiamo"

Quindi levenshtein non sarebbe di grande utilità qui perché è lineare e ognuno sarebbe notevolmente diverso. La differenza standard avrebbe superato il test e lo studente sarebbe riuscito a farla franca.

Così ho spezzato ogni parola nelle frasi e ricomposto le frasi come array, quindi confrontato l'un l'altro per determinare prima se la parola esisteva in ciascun array e dove era in relazione all'ultimo. Quindi ogni parola controllerebbe il prossimo nell'array per determinare se c'erano parole sequenziali, come nelle frasi di esempio sopra le righe 1 e 2. Quindi, se ci fossero parole sequenziali, comporrei una stringa di ogni sequenza comune a ciascun array e quindi tenterò di trovare le differenze nelle parole rimanenti. Meno parole rimarranno, più è probabile che siano solo più cariche per renderlo meno plagiato.

"mentre ceniamo, penso che i bambini dovrebbero giocare"

Quindi "I think" è valutato e considerato filler basato su un lessico di parole chiave - questa parte è difficile da descrivere qui.

Questo è stato un progetto complesso che ha fatto molto più di quello che ho descritto e non un semplice pezzo di codice che posso facilmente condividere, ma l'idea di cui sopra non è troppo difficile da replicare.

In bocca al lupo. Sono interessato a ciò che altri membri SO hanno da dire sulla tua domanda.


2
2017-12-09 21:31



Dato che la distanza di Levenshtein non è mai maggiore della lunghezza della corda più lunga, cambierei certamente il denominatore da (length1 + length2) a Math.max(length1, length2). Ciò normalizzerebbe la metrica tra zero e uno.

Ora, è impossibile rispondere a ciò che è "abbastanza simile" per le tue esigenze in base alle informazioni fornite. Io personalmente cerco di evitare funzioni di step come hai con il cutoff 0.25, preferendo valori continui da un intervallo noto. Forse sarebbe meglio alimentare i continui valori di "similarità" (o "distanza") in algoritmi di livello superiore invece di trasformare quei valori in quelli binari?


1
2017-12-09 21:42