Определить префикс из набора (похожих) строк

Question

У меня есть набор строк, например,

my_prefix_what_ever
my_prefix_what_so_ever
my_prefix_doesnt_matter

Я просто хочу найти самую длинную общую часть этих строк, здесь префикс.Выше результат должен быть

my_prefix_

Строки

my_prefix_what_ever
my_prefix_what_so_ever
my_doesnt_matter

должны приводить к префиксу

my_

Существует ли относительно безболезненный способ в Pythonопределить префикс (без необходимости перебирать каждый символ вручную)?

PS: я использую Python 2.6.3.

Answer 1

Никогда не переписывайте то, что вам предоставляется: os.path.commonprefix делает именно это:

Возвращает самый длинный префикс пути (взятый символ за символом), который является префиксомвсех путей в списке.Если список пуст, вернуть пустую строку ('').Обратите внимание, что это может вернуть недопустимые пути, потому что это работает символ за раз.

Для сравнения с другими ответами, вот код:

# 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

Нед Бэтчелдер , вероятно, прав. Но для удовольствия, вот более эффективная версия ответа phimuemue с использованием 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)

Как оскорбление читабельности, вот однострочная версия:)

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

Вот мое решение:

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

Следующее является рабочим, но, вероятно, довольно неэффективным решением.

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)

Для небольших наборов строк вышеописанное не является проблемой вообще. Но для больших наборов я лично написал бы другое, ручное решение, которое проверяет каждый символ один за другим и останавливается, когда есть различия.

Алгоритмически это приводит к той же процедуре, однако можно избежать создания списка c.

Answer 5

Во второй строке используется функция уменьшения для каждого символа во входных строках. Возвращает список из N + 1 элементов, где N - длина самой короткой входной строки.

Каждый элемент lot является либо (a) входным символом, если все входные строки совпадают в этой позиции, либо (b) None. lot.index (Нет) - это позиция первого Нет в лоте: длина общего префикса. out - это тот общий префикс.

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 6

Просто из любопытства я нашел еще один способ сделать это:

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

Как указал Нед, вероятно, лучше использовать os.path.commonprefix, что довольно элегантная функция.

Answer 7

Вот простое чистое решение.Идея состоит в том, чтобы использовать функцию zip (), чтобы выстроить в ряд все символы, помещая их в список первых символов, список вторых символов, ... список n-ых символов.Затем выполните итерацию каждого списка, чтобы проверить, содержат ли они только 1 значение.

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

output: my_prefix_

Answer 8

Вот еще один способ сделать это, используя OrderedDict с минимальным кодом.

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