Distanza di Levenshtein: come gestire meglio le parole scambiando posizioni?

Question

Ho avuto qualche successo nel confrontare le stringhe usando la funzione PHP levenshtein .

Tuttavia, per due stringhe che contengono sottostringhe con posizioni scambiate, l'algoritmo le considera come sottostringhe completamente nuove.

Ad esempio:

levenshtein("The quick brown fox", "brown quick The fox"); // 10 differences

sono considerati come avere meno in comune di:

levenshtein("The quick brown fox", "The quiet swine flu"); // 9 differences

Preferirei un algoritmo che vedesse che i primi due erano più simili.

Come potrei realizzare una funzione di confronto in grado di identificare le sottostringhe che hanno cambiato posizione in quanto distinte dalle modifiche?

Un possibile approccio a cui ho pensato è di mettere tutte le parole nella stringa in ordine alfabetico, prima del confronto. Ciò toglie l'ordine originale delle parole dal confronto. Un aspetto negativo di questo, tuttavia, è che cambiare solo la prima lettera di una parola può creare un'interruzione molto più grande di quanto dovrebbe causare un cambiamento di una singola lettera.

Quello che sto cercando di ottenere è confrontare due fatti su persone che sono stringhe di testo libero e decidere quanto è probabile che questi fatti indichino lo stesso fatto. I fatti potrebbero essere la scuola frequentata da qualcuno, ad esempio il nome del datore di lavoro o l'editore. Due record possono avere la stessa scuola scritta diversamente, parole in un ordine diverso, parole extra, ecc., Quindi la corrispondenza deve essere un po 'confusa se vogliamo fare una buona ipotesi che si riferiscano alla stessa scuola. Finora funziona molto bene per gli errori di ortografia (sto usando un algoritmo fenetico simile al metafono in cima a tutto questo) ma molto male se cambi l'ordine delle parole intorno a cui sembrano comuni in una scuola: " xxx college " vs " college of xxx " ;.

Answer 1

N-grammi

Usa N-grammi , che supportano multipli- trasposizione dei caratteri in tutto il testo .

L'idea generale è di dividere le due stringhe in questione in tutte le possibili sottostringhe di 2-3 caratteri (n-grammi) e di trattare il numero di n-grammi condivisi tra le due stringhe come metrica di somiglianza. Questo può quindi essere normalizzato dividendo il numero condiviso per il numero totale di n-grammi nella stringa più lunga. Questo è banale da calcolare, ma abbastanza potente.

Per le frasi di esempio:

A. The quick brown fox
B. brown quick The fox
C. The quiet swine flu

A e B condividono 18 2-grams

A e C condividono solo 8 2 grammi

su 20 totale possibile.

Questo è stato discusso in modo più dettagliato nella Gravano et al. carta .

tf-idf e somiglianza del coseno

Un'alternativa non così banale, ma fondata sulla teoria dell'informazione sarebbe usare il termine termine frequenza – frequenza inversa del documento (tf-idf) per pesare i token, costruire vettori di frasi e quindi utilizzare somiglianza del coseno come metrica di somiglianza.

L'algoritmo è:

1. Calcola le frequenze token di 2 caratteri (tf) per frase.
2. Calcola le frequenze delle frasi inverse (idf), che è un logaritmo di un quoziente del numero di tutte le frasi nel corpus (in questo caso 3) diviso per il numero di volte in cui un particolare token appare su tutte le frasi. In questo caso th è in tutte le frasi, quindi ha un contenuto di informazioni pari a zero (log (3/3) = 0).
3. Produce la matrice tf-idf moltiplicando le celle corrispondenti nelle tabelle tf e idf.
4. Infine, calcola la matrice di somiglianza del coseno per tutte le coppie di frasi, dove A e B sono pesi dalla tabella tf-idf per i token corrispondenti. L'intervallo è compreso tra 0 (non simile) e 1 (uguale).
   
   

Modifiche di Levenshtein e Metaphone

Per quanto riguarda le altre risposte. Damerau – Levenshtein supporta solo la trasposizione di due adiacenti personaggi. Metaphone è stato progettato per abbinare parole che suonano allo stesso modo e non per la corrispondenza di somiglianza.

Answer 2

È facile. Usa semplicemente la Damerau-Levenshtein sulle parole anziché sulle lettere.

Answer 3

Esplodi su spazi, ordina l'array, implora, quindi esegui il Levenshtein.

Answer 4

Puoi anche provare questo. (solo un suggerimento aggiuntivo)

$one = metaphone("The quick brown fox"); // 0KKBRNFKS
$two = metaphone("brown quick The fox"); // BRNKK0FKS
$three = metaphone("The quiet swine flu"); // 0KTSWNFL

similar_text($one, $two, $percent1); // 66.666666666667
similar_text($one, $three, $percent2); // 47.058823529412
similar_text($two, $three, $percent3); // 23.529411764706

Questo mostrerà che il 1o e il 2o sono più simili di uno e tre e due e tre.

Answer 5

Ho implementato levenshtein in un controllo ortografico.

Quello che stai chiedendo è contare le trasposizioni come 1 modifica.

Questo è facile se si desidera contare solo trasposizioni di una parola. Tuttavia, per la trasposizione delle parole 2 o più, l'aggiunta all'algoritmo è lo scenario peggiore ! (Max (wordorder1.length (), wordorder2.length ())) . Aggiungere un sottoalgoritmo non lineare a un algoritmo già quadratico non è una buona idea.

Ecco come funzionerebbe.

if (wordorder1[n] == wordorder2[n-1])
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1, workarray[x-2, y-2]);
}
  else
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1);
}

SOLO per toccare trasposizioni. Se vuoi tutte le trasposizioni, per ogni posizione dovresti lavorare all'indietro da quel punto confrontando

1[n] == 2[n-2].... 1[n] == 2[0]....

Quindi capisci perché non lo includono nel metodo standard.

Answer 6

Prendi questa risposta e apporta la seguente modifica:

void match(trie t, char* w, string s, int budget){
  if (budget < 0) return;
  if (*w=='\0') print s;
  foreach (char c, subtrie t1 in t){
    /* try matching or replacing c */
    match(t1, w+1, s+c, (*w==c ? budget : budget-1));
    /* try deleting c */
    match(t1, w, s, budget-1);
  }
  /* try inserting *w */
  match(t, w+1, s + *w, budget-1);
  /* TRY SWAPPING FIRST TWO CHARACTERS */
  if (w[1]){
    swap(w[0], w[1]);
    match(t, w, s, budget-1);
    swap(w[0], w[1]);
  }
}

Questo è per la ricerca nel dizionario in un trie, ma per la corrispondenza con una sola parola, è la stessa idea. Stai eseguendo operazioni dirette e, in qualsiasi momento, puoi apportare qualsiasi modifica desideri, a condizione che tu gli dia un costo.

Answer 7

Elimina le parole duplicate tra le due stringhe e poi usa Levenshtein.

Answer 8

Credo che questo sia un ottimo esempio dell'uso di un motore di ricerca dello spazio vettoriale .

in questa tecnica, ogni documento diventa essenzialmente un vettore con tante dimensioni quante sono le parole diverse in tutto il corpus; documenti simili occupano quindi le aree vicine in quello spazio vettoriale. una bella proprietà di questo modello è che le query sono anche solo documenti: per rispondere a una query, devi semplicemente calcolare la loro posizione nello spazio vettoriale e i tuoi risultati sono i documenti più vicini che puoi trovare. sono sicuro che ci sono soluzioni get-and-go per PHP là fuori.

per fuzzificare i risultati dallo spazio vettoriale, potresti prendere in considerazione la tecnica di elaborazione del linguaggio naturale derivante / simile e utilizzare levenshtein per costruire query secondarie per parole simili che si verificano nel tuo vocabolario generale.

Answer 9

Se la prima stringa è A e la seconda è B:

1. Dividi A e B in parole
2. Per ogni parola in A, trova la migliore parola corrispondente in B (usando levenshtein)
3. Rimuovi quella parola da B e inseriscila in B * nello stesso indice della parola corrispondente in A.
4. Ora confronta A e B *

Esempio:

A: The quick brown fox
B: Quick blue fox the
B*: the Quick blue fox

Puoi migliorare il passaggio 2 eseguendolo in più passaggi, trovando inizialmente solo corrispondenze esatte, quindi trovando corrispondenze ravvicinate per le parole in A che non hanno ancora un compagno in B *, quindi meno corrispondenze ravvicinate, ecc.