Python: détermine le préfixe d'un ensemble de chaînes (similaires)

Question

J'ai un ensemble de chaînes de caractères, par exemple

my_prefix_what_ever
my_prefix_what_so_ever
my_prefix_doesnt_matter

Je veux simplement trouver la plus longue partie commune de ces chaînes, ici le préfixe. Ci-dessus le résultat devrait être

my_prefix_

Les cordes

my_prefix_what_ever
my_prefix_what_so_ever
my_doesnt_matter

devrait se traduire dans le préfixe

my_

Est-il relativement indolore en Python pour déterminer le préfixe (sans avoir à répéter sur chaque personnage manuellement)?

PS: je suis à l'aide de Python 2.6.3.

Answer 1

Ne réécrivez jamais ce qui vous est fourni: os.path.commonprefix fait exactement ceci:

os.path.commonprefix (liste): Renvoie le préfixe de chemin le plus long (pris caractère par caractère), préfixe de tous les chemins de la liste. Si liste est vide, retourne la chaîne vide (''). Notez que cela peut renvoyer des chemins incorrects car cela fonctionne caractère par caractère.

Pour la comparaison avec les autres réponses, voici le code:

 # Return the longest prefix of all list elements.
def commonprefix(m):
    "Given a list of pathnames, returns the longest common leading component"
    if not m: return ''
    s1 = min(m)
    s2 = max(m)
    for i, c in enumerate(s1):
        if c != s2[i]:
            return s1[:i]
    return s1
 

Answer 2

Ned Batchelder est sans doute vrai. Mais pour le plaisir, voici une façon plus efficace de la version de phimuemue's réponse à l'aide de itertools.

import itertools

strings = ['my_prefix_what_ever', 
           'my_prefix_what_so_ever', 
           'my_prefix_doesnt_matter']

def all_same(x):
    return all(x[0] == y for y in x)

char_tuples = itertools.izip(*strings)
prefix_tuples = itertools.takewhile(all_same, char_tuples)
''.join(x[0] for x in prefix_tuples)

Comme un affront à la lisibilité, voici une version d'une ligne :)

>>> from itertools import takewhile, izip
>>> ''.join(c[0] for c in takewhile(lambda x: all(x[0] == y for y in x), izip(*strings)))
'my_prefix_'

Answer 3

Voici ma solution:

 a = ["my_prefix_what_ever", "my_prefix_what_so_ever", "my_prefix_doesnt_matter"]

prefix_len = len(a[0])
for x in a[1 : ]:
    prefix_len = min(prefix_len, len(x))
    while not x.startswith(a[0][ : prefix_len]):
        prefix_len -= 1

prefix = a[0][ : prefix_len]
 

Answer 4

Ce qui suit est une solution de travail, mais probablement assez inefficace.

 a = ["my_prefix_what_ever", "my_prefix_what_so_ever", "my_prefix_doesnt_matter"]
b = zip(*a)
c = [x[0] for x in b if x==(x[0],)*len(x)]
result = "".join(c)
 

Pour les petits ensembles de chaînes, ce qui précède ne pose aucun problème. Mais pour les plus grands ensembles, je codifierais personnellement une autre solution manuelle qui vérifie chaque caractère un par un et s’arrête en cas de différences.

Algorithmiquement, cela donne la même procédure, cependant, on pourrait éviter de construire la liste c .

Answer 5

Juste par curiosité, j'ai trouvé une autre façon de faire:

 def common_prefix(strings):

    if len(strings) == 1:#rule out trivial case
        return strings[0]

    prefix = strings[0]

    for string in strings[1:]:
        while string[:len(prefix)] != prefix and prefix:
            prefix = prefix[:len(prefix)-1]
        if not prefix:
            break

    return prefix

strings = ["my_prefix_what_ever","my_prefix_what_so_ever","my_prefix_doesnt_matter"]

print common_prefix(strings)
#Prints "my_prefix_"
 

Comme Ned l'a souligné, il est probablement préférable d'utiliser os.path.commonprefix , ce qui est une fonction assez élégante.