SequenceMatcher para múltiples entradas, no sólo dos?

Question

pensando en la mejor manera de abordar este problema en particular y si ninguna biblioteca (Python preferentemente, pero puede ser flexible si es necesario).

Tengo un archivo con una cadena en cada línea. Me gustaría encontrar los patrones comunes más largas y sus ubicaciones en cada línea. Sé que puedo usar para comparar SequenceMatcher una línea y dos, uno y tres, etc. y luego correlacionar los resultados, pero si hay algo que ya lo hace?

Lo ideal sería que estos partidos podría aparecer en cualquier parte de cada línea, pero para empezar me puede estar bien con ellos existente en el mismo desplazamiento en cada línea e ir de allí. Algo así como una biblioteca de compresión que tiene una buena API para acceder a la tabla de cadenas podría ser ideal, pero no he encontrado nada hasta el momento que se ajusta a esa descripción.

Por ejemplo, con estas líneas:

\x00\x00\x8c\x9e\x28\x28\x62\xf2\x97\x47\x81\x40\x3e\x4b\xa6\x0e\xfe\x8b
\x00\x00\xa8\x23\x2d\x28\x28\x0e\xb3\x47\x81\x40\x3e\x9c\xfa\x0b\x78\xed
\x00\x00\xb5\x30\xed\xe9\xac\x28\x28\x4b\x81\x40\x3e\xe7\xb2\x78\x7d\x3e

Yo querría ver que 0-1, 10-12 y partido en todas las líneas en la misma posición y la línea 1 [4,5] coincide con la línea 2 [5,6] coincide con línea 3 [7,8].

Gracias,

Answer 1

Si lo que quieres es encontrar subcadenas comunes que se encuentran en el mismo desplazamiento en cada línea, todo lo que necesita es algo como esto:

matches = []
zipped_strings = zip(s1,s2,s3)
startpos = -1
for i in len(zipped_strings):
  c1,c2,c3 = zipped_strings[i]
  # if you're not inside a match, 
  #  look for matching characters and save the match start position
  if startpos==-1 and c1==c2==c3:
    startpos = i
  # if you are inside a match, 
  #  look for non-matching characters, save the match to matches, reset startpos
  elif startpos>-1 and not c1==c2==c3:
    matches.append((startpos,i,s1[startpos:i]))
    # matches will contain (startpos,endpos,matchstring) tuples
    startpos = -1
# if you're still inside a match when you run out of string, save that match too!
if startpos>-1:
  endpos = len(zipped_strings)
  matches.append((startpos,endpos,s1[startpos:endpos]))

Para encontrar el patrón común más larga independientemente de su ubicación, SequenceMatcher suena como la mejor idea, pero en lugar de comparar cadena1 a string2 y luego cadena1 a string3 y tratando de combinar los resultados, acaba de obtener todas las subcadenas comunes de cadena1 y cadena2 ( con get_matching_blocks) y, a continuación, comparar cada resultado de que a string3 para obtener coincidencias entre las tres cadenas.

Answer 2

Es el rendimiento problema?

¿Qué tan grande es su opinión?

Es la longitud mínima de las cadenas para que coincida con 2?

Tenga en cuenta que el ejemplo no es correcto Creo que los resultados esperados no se corresponden con las secuencias de muestras que nos ha facilitado.