Python: Xác định tiền tố từ một tập hợp các chuỗi (tương tự)

Question

Tôi có một tập hợp các chuỗi, ví dụ:

my_prefix_what_ever 
my_prefix_what_so_ever 
my_prefix_doesnt_matter 

Tôi chỉ muốn tìm phần phổ biến nhất của các chuỗi này, tại đây tiền tố. Ở phía trên kết quả nên

my_prefix_ 

Các chuỗi

my_prefix_what_ever 
my_prefix_what_so_ever 
my_doesnt_matter 

nên dẫn đến việc tiền tố

my_ 

Có một cách tương đối không đau bằng Python để xác định tiền tố (mà không cần phải thế nào để lặp qua từng ký tự một cách thủ công)?

PS: Tôi đang sử dụng Python 2.6.3.

Answer 1

Không bao giờ viết lại những gì được cung cấp cho bạn: os.path.commonprefix thực hiện chính xác này:

Return tiền tố con đường dài nhất (lấy nhân vật theo từng ký tự) đó là tiền tố của tất cả các đường dẫn trong danh sách. Nếu danh sách trống, hãy trả lại chuỗi trống (''). Lưu ý rằng điều này có thể trả lại đường dẫn không hợp lệ vì nó hoạt động một ký tự tại một thời điểm.

Để so sánh các câu trả lời khác, đây là các mã:

# 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

Sau đây là giải pháp làm việc, nhưng có lẽ không hiệu quả.

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) 

Đối với các chuỗi nhỏ, điều trên không có vấn đề gì cả. Nhưng đối với các bộ lớn hơn, cá nhân tôi sẽ viết mã khác, giải pháp thủ công để kiểm tra từng nhân vật một và dừng lại khi có sự khác biệt.

Về mặt thuật toán, điều này mang lại cùng một quy trình, tuy nhiên, người ta có thể tránh việc xây dựng danh sách c.

Answer 3

Đây là giải pháp của tôi:

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 có lẽ là đúng. Nhưng đối với những niềm vui của nó, đây là một phiên bản hiệu quả hơn của câu trả lời của phimuemue bằng cách sử dụng 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) 

Là một sỉ nhục đối với khả năng đọc, sau đây là một phiên bản một dòng :)

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

Chỉ vì tò mò tôi đã tìm ra một cách khác để làm điều này:

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

Như Ned đã chỉ ra rằng có lẽ tốt hơn nên sử dụng os.path.commonprefix, một chức năng khá thanh lịch.

Answer 6

Dưới đây là một cách khác để thực hiện việc này bằng cách sử dụng OrderedDict với mã tối thiểu.

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

Dòng thứ hai của hàm này sử dụng hàm reduce trên mỗi ký tự trong chuỗi đầu vào. Nó trả về một danh sách các phần tử N + 1 trong đó N là chiều dài của chuỗi đầu vào ngắn nhất.

Mỗi phần tử trong lô là (a) ký tự nhập, nếu tất cả chuỗi đầu vào khớp với vị trí đó hoặc (b) Không. lot.index (Không) là vị trí của đầu tiên Không có trong lô: chiều dài của tiền tố chung. ra là tiền tố phổ biế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

Đây là giải pháp đơn giản. Ý tưởng là sử dụng hàm zip() để xếp hàng tất cả các ký tự bằng cách đặt chúng trong danh sách các ký tự 1, danh sách ký tự thứ 2, ... danh sách các ký tự thứ n. Sau đó lặp lại từng danh sách để kiểm tra xem chúng có chứa chỉ 1 giá trị không.

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

đầu ra: my_prefix_