SequenceMatcher pour plusieurs entrées, pas seulement deux?
-
23-09-2019 - |
Question
interroger sur la meilleure façon d'aborder ce problème particulier et si des bibliothèques (python de préférence, mais je peux faire preuve de souplesse en cas de besoin).
J'ai un fichier avec une chaîne sur chaque ligne. Je voudrais trouver les modèles et leurs emplacements dans chaque ligne la plus longue communs. Je sais que je peux utiliser pour comparer SequenceMatcher ligne un et deux, un et trois, ainsi de suite et ensuite établir une corrélation entre les résultats, mais s'il y a quelque chose qui fait déjà?
Idéalement, ces résultats semblent ne importe où sur chaque ligne, mais pour commencer je peux être bien 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îne peut être idéal, mais je ne l'ai pas trouvé quoi que ce soit à ce jour qui correspond à 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 line2 [5,6] correspond line3 [7,8].
Merci,
La solution
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 le plus long modèle commun indépendamment de leur emplacement, SequenceMatcher ne sonne comme la meilleure idée, mais au lieu de comparer chaine1 à STRING2 puis chaine1 à String3 et d'essayer de fusionner les résultats, juste obtenir tous les sous-chaînes communes de string1 et string2 ( avec get_matching_blocks), puis comparer chaque résultat de ce à string3 pour obtenir les matchs entre les trois chaînes.
Autres conseils
Votre performance problème?
Quelle est votre contribution?
est la longueur minimale des chaînes pour correspondre à 2?
Notez que votre exemple est pas correct, je pense que les résultats que vous attendez ne correspondent pas aux chaînes d'échantillons que vous avez fournies.