(유사한) 문자열 집합에서 접두사 결정

(유사한) 문자열 집합에서 접두사 결정

---

예를 들어 문자열 세트가 있습니다.

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 2.6.3을 사용하고 있습니다.

---

제공된 내용을 다시 작성하지 마십시오. 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

---

Ned Batchelder 가 옳을 것입니다. 그러나 그것의 재미를 위해, 여기를 사용하는 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_'

---

내 해결책은 다음과 같습니다.

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]

---

다음은 작동하지만 아마도 상당히 비효율적 인 솔루션입니다.

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.

---

호기심에서 나는 이것을하는 또 다른 방법을 알아 냈습니다.

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

Ned가 지적했듯이 os.path.commonprefix꽤 우아한 기능인를 사용 하는 것이 더 낫습니다 .

---

The second line of this employs the reduce function on each character in the input strings. It returns a list of N+1 elements where N is length of the shortest input string.

Each element in lot is either (a) the input character, if all input strings match at that position, or (b) None. lot.index(None) is the position of the first None in lot: the length of the common prefix. out is that common prefix.

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

---

Here is another way of doing this using OrderedDict with minimal code.

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

---

Here's a simple clean solution. The idea is to use zip() function to line up all the characters by putting them in a list of 1st characters, list of 2nd characters,...list of nth characters. Then iterate each list to check if they contain only 1 value.

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_

참고URL : https://stackoverflow.com/questions/6718196/determine-prefix-from-a-set-of-similar-strings