Algorithmus zum Messen der Ähnlichkeit zwischen zwei Sequenzen von Strings

Question

Wie kann ich Ähnlichkeitsprozentsatz zwischen zwei Sequenzen von Strings messen?

Ich habe zwei Textdateien und in Dateien dort Sequenzen geschrieben wie

Erste Datei:

AAA BBB DDD CCC GGG MMM AAA MMM

Zweite Datei:

BBB DDD CCC MMM AAA MMM

Wie Ähnlichkeit zwischen diesen beiden Dateien in Reihenfolge der Zeichenfolgen gemessen?

Zum Beispiel im obigen Beispiel haben beide Dateien Ähnlichkeit aufgrund der Reihenfolge der Strings ist gleich aber einige Strings fehlen in Datei-2. Welcher Algorithmus ist am besten geeignet, um dieses Problem zu lösen, so dass ich messen kann, wie ähnlich die Reihenfolge der Strings nicht die Frequenz der Strings in zwei ist?

Answer 1

Sie könnten den Levenstein Distance Algorithmus verwenden. Es analysiert, wie viele Bearbeitungen erforderlich sind, um eine Zeichenfolge in eine andere umzuwandeln. This Artikel erklärt es ziemlich gut, und eine Beispielimplementierung wird zur Verfügung gestellt.

Copy Paste aus 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

können Sie Python verwenden SequenceMatcher.ratio Funktion, die die Sequenzen Ähnlichkeit als Schwimmer im Bereich [0, 1] misst. Wenn T ist die Gesamtzahl der Elemente in beiden Sequenzen und M ist die Anzahl der Übereinstimmungen ist dies 2.0 * M/T. Der Hauptcode ist wie folgt:

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 

Ich hoffe, das könnte Ihnen helfen!