Python: Determine el prefijo de un conjunto de cadenas (similares)

Question

Tengo un conjunto de cadenas, p.

my_prefix_what_ever 
my_prefix_what_so_ever 
my_prefix_doesnt_matter 

Simplemente quiero encontrar la porción común más larga de estas cadenas, aquí el prefijo. En lo anterior, el resultado debería ser

my_prefix_ 

Las cuerdas

my_prefix_what_ever 
my_prefix_what_so_ever 
my_doesnt_matter 

debería dar como resultado el prefijo

my_ 

¿Hay una manera relativamente indolora en Python para determinar el prefijo (sin tener para iterar sobre cada personaje manualmente)?

PD: Estoy usando Python 2.6.3.

Answer 1

Nunca reescribir lo que se le proporciona: os.path.commonprefix hace exactamente esto:

Retorno sobre el prefijo más largo (tomado carácter por carácter) que es un prefijo de todas las rutas en la lista. Si la lista está vacía, devuelva la cadena vacía (''). Tenga en cuenta que esto puede devolver rutas no válidas porque funciona un carácter a la vez.

Para la comparación de las otras respuestas, aquí está el código:

# 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

La siguiente es una solución funcional, pero probablemente bastante ineficiente.

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) 

Para pequeños juegos de cuerdas, lo anterior no es un problema en absoluto. Pero para conjuntos más grandes, yo personalmente codificaría otra solución manual que verifica cada carácter uno tras otro y se detiene cuando hay diferencias.

Algorítmicamente, esto produce el mismo procedimiento, sin embargo, uno podría evitar la construcción de la lista c.

Answer 3

aquí está mi solución:

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

Ned Batchelder es probablemente la correcta. Pero por el gusto de hacerlo, esta es una versión más eficiente de la respuesta de phimuemue usando 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) 

como una afrenta a la legibilidad, aquí es una versión de una línea :)

>>> 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 5

Sólo por curiosidad me di cuenta de otra manera de hacer esto:

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_" 

Como Ned señaló que probablemente sea mejor usar os.path.commonprefix, que es una función bastante elegante.

Answer 6

Aquí hay otra forma de hacerlo usando OrderedDict con un código mínimo.

import collections 
import itertools 

def commonprefix(instrings): 
    """ Common prefix of a list of input strings using OrderedDict """ 

    d = collections.OrderedDict() 

    for instring in instrings: 
     for idx,char in enumerate(instring): 
      # Make sure index is added into key 
      d[(char, idx)] = d.get((char,idx), 0) + 1 

    # Return prefix of keys while value == length(instrings) 
    return ''.join([k[0] for k in itertools.takewhile(lambda x: d[x] == len(instrings), d)]) 

Answer 7

La segunda línea de esto emplea la función de reducción en cada carácter en las cadenas de entrada. Devuelve una lista de elementos N + 1 donde N es la longitud de la cadena de entrada más corta.

Cada elemento de mucho puede ser (a) el carácter de entrada, si todo de entrada coinciden con cuerdas en esa posición, o (b) Ninguna. lote.index (Ninguno) es la posición del primer Ninguno en el lote: la longitud del prefijo común. fuera es ese prefijo común.

val = ["axc", "abc", "abc"] 
lot = [reduce(lambda a, b: a if a == b else None, x) for x in zip(*val)] + [None] 
out = val[0][:lot.index(None)] 

Answer 8

Aquí hay una solución de limpieza simple. La idea es usar la función zip() para alinear todos los personajes, poniéndolos en una lista de 1er carácter, lista de 2ndo caracteres, ... lista de enésimo caracteres. Luego itere cada lista para verificar si contienen solo 1 valor.

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

list = [all(x[i] == x[i+1] for i in range(len(x)-1)) for x in zip(*a)] 

print a[0][:list.index(0) if list.count(0) > 0 else len(list)] 

de salida: my_prefix_