Nếu các vấn đề về bộ nhớ của bạn nằm trong việc tạo cây hậu tố, bạn có chắc là bạn cần nó không? Bạn có thể tìm thấy tất cả các trận đấu trong một chuỗi đơn như thế này:
word=get_string(4**12)+"$"
def matcher(word, match_string):
positions = [-1]
while 1:
positions.append(word.find(match_string, positions[-1] + 1))
if positions[-1] == -1:
return positions[1:-1]
print matcher(word,'AAAAAAAAAAAA')
[13331731, 13331732, 13331733]
print matcher('AACTATAAATTTACCA','AT')
[4, 8]
máy của tôi là khá cũ, và điều này mất 30 giây để chạy, với 4^12 chuỗi. Tôi đã sử dụng một mục tiêu 12 chữ số để có một số trận đấu. Ngoài ra giải pháp này sẽ tìm thấy kết quả chồng chéo - nên có bất kỳ.
Here là một mô-đun cây hậu tố bạn có thể thử, như thế này:
import suffixtree
stree = suffixtree.SuffixTree(word)
print stree.find_substring("AAAAAAAAAAAA")
Thật không may, máy tính của tôi là quá chậm chạp trong việc kiểm tra này ra đúng với chuỗi dài. Nhưng có lẽ một khi hậu tố được xây dựng, các tìm kiếm sẽ rất nhanh, vì vậy đối với số lượng lớn các tìm kiếm, nó sẽ là một cuộc gọi tốt. Hơn nữa find_substring chỉ trả lại kết quả trùng khớp đầu tiên (không biết đây có phải là vấn đề không, tôi chắc chắn bạn có thể điều chỉnh nó dễ dàng).
Cập nhật: Chia chuỗi thành cây hậu tố nhỏ hơn, như vậy tránh được các vấn đề bộ nhớ
Vì vậy, nếu bạn cần phải làm 10 triệu tìm kiếm trên 4^12 chuỗi dài, chúng ta rõ ràng không muốn chờ đợi cho 9,5 năm (tìm kiếm đơn giản tiêu chuẩn, lần đầu tiên tôi đề xuất, trên máy chậm của tôi ...). Tuy nhiên, chúng tôi vẫn có thể sử dụng cây hậu tố (do đó nhanh hơn rất nhiều), VÀ tránh các vấn đề về bộ nhớ. Chia chuỗi lớn thành các khối có thể quản lý được (mà chúng ta biết bộ nhớ máy có thể đối phó với) và biến một đoạn thành cây hậu tố, tìm kiếm nó 10 triệu lần, sau đó loại bỏ đoạn đó và di chuyển sang đoạn tiếp theo. Chúng ta cũng cần nhớ tìm kiếm chồng chéo giữa mỗi đoạn.Tôi đã viết một số mã để làm điều này (Nó giả định chuỗi lớn để được tìm kiếm, word là một bội số của chuỗi có thể quản lý tối đa, max_length, bạn sẽ phải điều chỉnh mã để kiểm tra phần còn lại ở cuối, nếu đây là không phải như vậy):
def split_find(word,search_words,max_length):
number_sub_trees = len(word)/max_length
matches = {}
for i in xrange(0,number_sub_trees):
stree = suffixtree.SuffixTree(word[max_length*i:max_length*(i+1)])
for search in search_words:
if search not in matches:
match = stree.find_substring(search)
if match > -1:
matches[search] = match + max_length*i,i
if i < number_sub_trees:
match = word[max_length*(i+1) - len(search):max_length*(i+1) + len(search)].find(search)
if match > -1:
matches[search] = match + max_length*i,i
return matches
word=get_string(4**12)
search_words = ['AAAAAAAAAAAAAAAA'] #list of all words to find matches for
max_length = 4**10 #as large as your machine can cope with (multiple of word)
print split_find(word,search_words,max_length)
Trong ví dụ này tôi giới hạn chiều dài cây hậu tố tối đa dài 4^10, cần khoảng 700MB. Sử dụng mã này, cho một chuỗi dài 4^12, 10 triệu lượt tìm kiếm sẽ mất khoảng 13 giờ (tìm kiếm đầy đủ, với 0 kết quả phù hợp, vì vậy nếu có kết quả khớp thì sẽ nhanh hơn). Tuy nhiên, như một phần của điều này chúng ta cần phải xây dựng 100 cây hậu tố, mà sẽ mất khoảng.100 * 41 giây = 1 giờ.
Vì vậy, tổng thời gian chạy là khoảng 14 giờ, không có vấn đề về bộ nhớ ... Cải thiện lớn trên 9,5 năm. Lưu ý rằng tôi đang chạy trên CPU 1.6GHz với RAM 1 GB, vì vậy bạn nên có khả năng làm tốt hơn thế này!
Tôi không quen thuộc với cây hậu tố và triển khai của bạn không cho tôi manh mối về cách thức hoạt động của nó. Tôi khuyên bạn nên sử dụng thư viện, ví dụ: [pytst] (http://nicolas.lehuen.com/category/pytst/). – MattH
Gợi ý: một cấu trúc cây sẽ liên quan đến dicts lồng nhau. –