Algoritmo per misurare la somiglianza tra due sequenze di stringhe

Question

Come posso misurare la percentuale di somiglianza tra due sequenze di stringhe?

Ho due file di testo e Nei file ci sequenze vengono scritti come

primo file:

AAA BBB DDD CCC GGG MMM AAA MMM

secondo file:

BBB DDD CCC MMM AAA MMM

Come misurare la somiglianza tra questi due file in termini di ordine di stringhe?

Ad esempio nell'esempio precedente entrambi i file hanno somiglianza a causa dell'ordine delle stringhe è uguale tuttavia alcune stringhe mancano nel file-2. Quale algoritmo è più adatto a risolvere questo problema in modo che possa misurare quanto sia simile l'ordine delle stringhe non la frequenza delle stringhe in due?

Answer 1

È possibile utilizzare l'algoritmo Levenstein Distance. Analizza il numero di modifiche necessarie per trasformare una stringa in un'altra. L'articolo This lo spiega abbastanza bene e viene fornita un'implementazione di esempio.

copia incolla da Codeproject:

1. Set n to be the length of s. ("GUMBO") 
    Set m to be the length of t. ("GAMBOL") 
    If n = 0, return m and exit. 
    If m = 0, return n and exit. 
    Construct two vectors, v0[m+1] and v1[m+1], containing 0..m elements. 
2. Initialize v0 to 0..m. 
3. Examine each character of s (i from 1 to n). 
4. Examine each character of t (j from 1 to m). 
5. If s[i] equals t[j], the cost is 0. 
    If s[i] is not equal to t[j], the cost is 1. 
6. Set cell v1[j] equal to the minimum of: 
    a. The cell immediately above plus 1: v1[j-1] + 1. 
    b. The cell immediately to the left plus 1: v0[j] + 1. 
    c. The cell diagonally above and to the left plus the cost: v0[j-1] + cost. 
7. After the iteration steps (3, 4, 5, 6) are complete, the distance is found in the cell v1[m]. 

Answer 2

È possibile utilizzare la funzione di pitone SequenceMatcher.ratio che misura la somiglianza sequenze come un galleggiante nella gamma [0, 1]. Se T è il numero totale di elementi in entrambe le sequenze e M è il numero di corrispondenze, questo è 2.0 * M/T. Il codice principale è il seguente:

from difflib import SequenceMatcher 
text1 = 'AAA BBB DDD CCC GGG MMM AAA MMM' 
text2 = 'BBB DDD CCC MMM AAA MMM' 
s = SequenceMatcher(None, text1, text2) 
similarity = s.ratio() * 100 

Spero che questo possa aiutarti!