Algoritmo para medir la similitud entre dos secuencias de cadenas

Question

¿Cómo puedo medir el porcentaje de similitud entre dos secuencias de cadenas?

Tengo dos archivos de texto y en los archivos allí secuencias se escriben así

Primer archivo:

AAA BBB DDD CCC GGG MMM AAA MMM

Segundo archivo:

acreditación DDD CCC AAA MMM MMM

¿Cómo se mide la similitud entre estos dos archivos en términos de orden de las cadenas?

Por ejemplo en el ejemplo anterior ambos archivos tienen similitud debido a la orden de cuerdas es igual sin embargo, algunas cadenas no están presentes en el archivo-2. ¿Qué algoritmo es el más adecuado para resolver este problema, de modo que pueda medir qué tan similar es el orden de las cadenas, no la frecuencia de las cadenas en dos?

Answer 1

Puede usar el algoritmo Levenstein Distance. Analiza cuántas ediciones se necesitan para transformar una cadena en otra. El artículo This lo explica bastante bien, y se proporciona una implementación de muestra.

copiar y pegar desde 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

puede utilizar la función de pitón SequenceMatcher.ratio que mide la similitud de secuencias como un flotador en el rango [0, 1]. Si T es el número total de elementos en ambas secuencias, y M es el número de coincidencias, esto es 2.0 * M/T. El código principal es el siguiente:

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 

Espero que esto pueda ayudarlo.