Chuỗi con chung dài nhất từ ​​hơn hai chuỗi - Python

Question

Tôi đang tìm thư viện Python để tìm chuỗi con dài nhất từ ​​một tập hợp các chuỗi. Có hai cách để giải quyết vấn đề này:

• sử dụng cây hậu tố
• sử dụng lập trình năng động.

Phương pháp triển khai không quan trọng. Điều quan trọng là nó có thể được sử dụng cho một tập hợp các chuỗi (không chỉ hai chuỗi).

Answer 1

Những chức năng ghép nối sẽ tìm ra chuỗi chung dài nhất trong bất kỳ mảng độc đoán của chuỗi:

def long_substr(data): 
    substr = '' 
    if len(data) > 1 and len(data[0]) > 0: 
     for i in range(len(data[0])): 
      for j in range(len(data[0])-i+1): 
       if j > len(substr) and is_substr(data[0][i:i+j], data): 
        substr = data[0][i:i+j] 
    return substr 

def is_substr(find, data): 
    if len(data) < 1 and len(find) < 1: 
     return False 
    for i in range(len(data)): 
     if find not in data[i]: 
      return False 
    return True 


print long_substr(['Oh, hello, my friend.', 
        'I prefer Jelly Belly beans.', 
        'When hell freezes over!']) 

Không nghi ngờ gì các thuật toán có thể được cải thiện và tôi đã không có một rất nhiều tiếp xúc với Python, do đó, có lẽ nó có thể được hiệu quả hơn cú pháp là tốt, nhưng nó nên làm công việc.

CHỈNH SỬA: xếp hàng thứ hai là hàm is_substr như được J.F. Sebastian trình bày. Cách sử dụng vẫn như cũ. Lưu ý: không thay đổi thuật toán.

def long_substr(data): 
    substr = '' 
    if len(data) > 1 and len(data[0]) > 0: 
     for i in range(len(data[0])): 
      for j in range(len(data[0])-i+1): 
       if j > len(substr) and all(data[0][i:i+j] in x for x in data): 
        substr = data[0][i:i+j] 
    return substr 

Hope this helps,

Jason.

Answer 2

def common_prefix(strings): 
    """ Find the longest string that is a prefix of all the strings. 
    """ 
    if not strings: 
     return '' 
    prefix = strings[0] 
    for s in strings: 
     if len(s) < len(prefix): 
      prefix = prefix[:len(s)] 
     if not prefix: 
      return '' 
     for i in range(len(prefix)): 
      if prefix[i] != s[i]: 
       prefix = prefix[:i] 
       break 
    return prefix 

Từ http://bitbucket.org/ned/cog/src/tip/cogapp/whiteutils.py

Answer 3

# this does not increase asymptotical complexity 
# but can still waste more time than it saves. TODO: profile 
def shortest_of(strings): 
    return min(strings, key=len) 

def long_substr(strings): 
    substr = "" 
    if not strings: 
     return substr 
    reference = shortest_of(strings) #strings[0] 
    length = len(reference) 
    #find a suitable slice i:j 
    for i in xrange(length): 
     #only consider strings long at least len(substr) + 1 
     for j in xrange(i + len(substr) + 1, length + 1): 
      candidate = reference[i:j] # ↓ is the slice recalculated every time? 
      if all(candidate in text for text in strings): 
       substr = candidate 
    return substr 

Disclaimer này cho biết thêm rất ít câu trả lời jtjacques'. Tuy nhiên, hy vọng, điều này sẽ dễ đọc hơn và nhanh hơn và nó không phù hợp với nhận xét, do đó tại sao tôi đăng câu trả lời này trong câu trả lời. Tôi không hài lòng về số shortest_of, phải trung thực.

Answer 4

Bạn có thể sử dụng mô-đun SuffixTree là trình bao bọc dựa trên việc triển khai ANSI C của các cây hậu tố tổng quát. Module này là dễ dàng để xử lý ....

Hãy xem tại địa chỉ: here

Answer 5

tôi thích điều này cho is_substr, như tôi đã tìm thấy nó một chút dễ đọc hơn và trực quan:

def is_substr(find, data): 
    """ 
    inputs a substring to find, returns True only 
    if found for each data in data list 
    """ 

    if len(find) < 1 or len(data) < 1: 
    return False # expected input DNE 

    is_found = True # and-ing to False anywhere in data will return False 
    for i in data: 
    print "Looking for substring %s in %s..." % (find, i) 
    is_found = is_found and find in i 
    return is_found 

Answer 6

Nếu ai đó đang tìm kiếm một phiên bản tổng quát mà cũng có thể lấy danh sách các chuỗi các đối tượng tùy ý:

def get_longest_common_subseq(data): 
    substr = [] 
    if len(data) > 1 and len(data[0]) > 0: 
     for i in range(len(data[0])): 
      for j in range(len(data[0])-i+1): 
       if j > len(substr) and is_subseq_of_any(data[0][i:i+j], data): 
        substr = data[0][i:i+j] 
    return substr 

def is_subseq_of_any(find, data): 
    if len(data) < 1 and len(find) < 1: 
     return False 
    for i in range(len(data)): 
     if not is_subseq(find, data[i]): 
      return False 
    return True 

# Will also return True if possible_subseq == seq. 
def is_subseq(possible_subseq, seq): 
    if len(possible_subseq) > len(seq): 
     return False 
    def get_length_n_slices(n): 
     for i in xrange(len(seq) + 1 - n): 
      yield seq[i:i+n] 
    for slyce in get_length_n_slices(len(possible_subseq)): 
     if slyce == possible_subseq: 
      return True 
    return False 

print get_longest_common_subseq([[1, 2, 3, 4, 5], [2, 3, 4, 5, 6]]) 

print get_longest_common_subseq(['Oh, hello, my friend.', 
            'I prefer Jelly Belly beans.', 
            'When hell freezes over!']) 

Answer 7

Điều này có thể được thực hiện ngắn hơn:

def long_substr(data): 
    substrs = lambda x: {x[i:i+j] for i in range(len(x)) for j in range(len(x) - i + 1)} 
    s = substrs(data[0]) 
    for val in data[1:]: 
    s.intersection_update(substrs(val)) 
    return max(s, key=len) 

bộ được (có thể) được triển khai dưới dạng bản đồ băm, điều này làm cho điều này không hiệu quả chút nào. Nếu bạn (1) thực hiện một datatype thiết lập như một trie và (2) chỉ cần lưu trữ postfixes trong trie và sau đó buộc mỗi nút là một endpoint (điều này sẽ tương đương với việc thêm tất cả các substrings), THEN trong lý thuyết tôi sẽ đoán em bé này là bộ nhớ khá hiệu quả, đặc biệt là kể từ khi giao lộ của cố gắng là siêu dễ dàng.

Tuy nhiên, đây là tối ưu hóa ngắn và sớm là gốc của một lượng đáng kể thời gian lãng phí.