SequenceMatcher pour plusieurs entrées, pas seulement deux?

Question

s'interrogeant sur la meilleure façon d'aborder ce problème particulier et si des bibliothèques (python de préférence, mais je peux être flexible si besoin est).

J'ai un fichier avec une chaîne sur chaque ligne. Je voudrais trouver les plus longs motifs communs et leurs emplacements dans chaque ligne. Je sais que je peux utiliser SequenceMatcher pour comparer les lignes 1 et 2, 1 et 3, etc., et ensuite corréler les résultats, mais s'il y a quelque chose qui le fait déjà?

Idéalement, ces correspondances apparaîtraient n'importe où sur chaque ligne, mais pour les débutants, je peux être correct avec eux existant au même décalage dans chaque ligne et aller de là. Quelque chose comme une bibliothèque de compression qui a une bonne API pour accéder à sa table de chaînes pourrait être idéal, mais je n'ai rien trouvé jusqu'à présent qui corresponde à cette description.

Par exemple, avec ces lignes:

\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 

Je voudrais voir que 0-1 et 10-12 match toutes les lignes à la même position et line1 [4,5] correspond à la ligne 2 [5 , 6] correspond à line3 [7,8].

Merci,

Answer 1

Si tout ce que vous voulez est de trouver des sous-chaînes communes qui sont au même décalage dans chaque ligne, tout ce que vous avez besoin est quelque chose comme ceci:

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])) 

Pour trouver le plus long modèle commun indépendamment de leur emplacement, SequenceMatcher ne ressemble à la meilleure idée, mais au lieu de comparer string1 à string2 puis string1 à string3 et d'essayer de fusionner les résultats, il suffit d'obtenir toutes les sous-chaînes courantes de string1 et string2 (avec get_matching_blocks), puis comparez chaque résultat à string3 pour obtenir des correspondances entre les trois chaînes.

Answer 2

Est-ce votre performance de problème?

Quelle est la taille de votre saisie?

La longueur minimale des chaînes correspond-elle à 2? Notez que votre exemple n'est pas correct Je pense que les résultats attendus ne correspondent pas aux exemples de chaînes que vous avez fournis.