tìm kiếm các bản lặp dài lặp đi lặp lại trong một chuỗi lớn

Question

Tôi ngây thơ tưởng tượng rằng tôi có thể xây dựng một hậu tố mà tôi giữ số lượt truy cập cho mỗi nút và sau đó các nút sâu nhất có số lượng lớn hơn một là tập hợp kết quả cho.

Tôi có một chuỗi rất dài (hàng trăm megabyte). Tôi có khoảng 1 GB RAM.

Đây là lý do tại sao việc xây dựng một hậu tố trie với dữ liệu đếm là quá không hiệu quả khôn ngoan để làm việc cho tôi. Để báo giá Wikipedia's Suffix tree:

lưu trữ cây hậu tố của chuỗi thường yêu cầu nhiều không gian hơn lưu trữ chuỗi.

Lượng thông tin lớn trong mỗi cạnh và nút làm cho cây hậu tố rất tốn kém, tiêu thụ khoảng 10 đến 20 lần kích thước bộ nhớ của văn bản nguồn trong việc triển khai tốt. Mảng hậu tố làm giảm yêu cầu này thành hệ số bốn, và các nhà nghiên cứu tiếp tục tìm các cấu trúc lập chỉ mục nhỏ hơn.

Và đó là nhận xét của wikipedia trên cây chứ không phải trie.

Tôi làm cách nào để tìm chuỗi được lặp lại lâu dài trong một lượng lớn dữ liệu và trong một khoảng thời gian hợp lý (ví dụ: dưới một giờ trên máy tính để bàn hiện đại)?

(Một số liên kết wikipedia để tránh người đăng chúng là 'câu trả lời': Algorithms on strings và đặc biệt là Longest repeated substring problem ;-))

Answer 1

Cách hiệu quả để thực hiện việc này là tạo chỉ mục các chuỗi con và sắp xếp chúng. Đây là một hoạt động O (n lg n).

BWT nén thực hiện bước này, do đó, vấn đề được hiểu rõ và có radix và suffix (yêu cầu O (n)) triển khai sắp xếp và làm cho nó hiệu quả nhất có thể. Nó vẫn mất một thời gian dài, có lẽ vài giây cho các văn bản lớn.

Nếu bạn muốn sử dụng mã tiện ích, C++ std::stable_sort() Thực hiện nhiều tốt hơn so với std::sort() cho ngôn ngữ tự nhiên (và nhanh hơn nhiều so với C của qsort(), nhưng vì những lý do khác nhau).

Sau đó, truy cập từng mục để xem chiều dài của chuỗi con chung của nó với những người hàng xóm của nó là O (n).

Answer 2

là văn bản này với ngắt lời? Sau đó, tôi muốn nghi ngờ bạn muốn một biến thể của từ khoá trong ngữ cảnh: tạo một bản sao của mỗi dòng n lần cho n từ trong một dòng, phá vỡ mỗi dòng tại mỗi từ; sắp xếp alpha của toàn bộ điều; tìm kiếm lặp lại.

Nếu đó là một chuỗi ký tự dài duy nhất, ví dụ như trình tự DNA sinh học, thì bạn muốn tạo thứ gì đó giống như bộ ba của bạn trên đĩa; xây dựng một bản ghi cho mỗi nhân vật với một đĩa bù đắp cho các nút tiếp theo. Tôi muốn xem Tập 3 của Knuth, mục 5.4, "sắp xếp bên ngoài".

Answer 3

Cách dễ nhất có thể chỉ là plunk down the $100 để có nhiều RAM hơn. Nếu không, bạn có thể sẽ phải xem xét các cấu trúc đĩa được sao lưu để giữ cây hậu tố của bạn.

Answer 4

Bạn có thể xem các cây hậu tố dựa trên đĩa. Tôi đã tìm thấy điều này Suffix tree implementation library thông qua Google, cộng với một loạt các bài viết có thể giúp tự mình triển khai.

Answer 5

Bạn có thể giải quyết vấn đề của mình bằng cách tạo một số suffix array thay thế không? Nếu không, bạn có thể sẽ cần phải sử dụng một trong những cây hậu tố dựa trên đĩa được đề cập trong các câu trả lời khác.

Answer 6

Bạn có thể giải quyết vấn đề này bằng cách chia và chinh phục. Tôi nghĩ rằng đây sẽ là phức tạp thuật toán tương tự như sử dụng một Trie, nhưng có lẽ ít hiệu quả thực hiện khôn ngoan

void LongSubstrings(string data, string prefix, IEnumerable<int> positions) 
{ 
    Dictionary<char, DiskBackedBuffer> buffers = new Dictionary<char, DiskBackedBuffer>(); 
    foreach (int position in positions) 
    { 
     char nextChar = data[position]; 
     buffers[nextChar].Add(position+1); 
    } 

    foreach (char c in buffers.Keys) 
    { 
     if (buffers[c].Count > 1) 
      LongSubstrings(data, prefix + c, buffers[c]); 
     else if (buffers[c].Count == 1) 
      Console.WriteLine("Unique sequence: {0}", prefix + c); 
    } 
} 

void LongSubstrings(string data) 
{ 
    LongSubstrings(data, "", Enumerable.Range(0, data.Length)); 
} 

Sau này, bạn sẽ cần phải thực hiện một lớp mà thực hiện DiskBackedBuffer như vậy mà nó là một danh sách các số, và khi bộ đệm đạt đến một kích thước nhất định, nó sẽ tự ghi ra đĩa bằng cách sử dụng một tệp tạm thời và nhớ lại từ đĩa khi đọc từ đó.

Answer 7

Trả lời câu hỏi của riêng tôi:

Cho rằng một trận đấu dài cũng là một trận đấu ngắn, bạn có thể giao dịch nhiều đèo cho RAM bằng cách đầu tiên tìm kiếm các trận đấu ngắn hơn và sau đó nhìn thấy nếu bạn có thể 'phát triển' những trận đấu.

Cách tiếp cận theo nghĩa đen này là tạo một trie (với số lượng trong mỗi nút) của tất cả các chuỗi của một số độ dài cố định trong dữ liệu. Sau đó, bạn chọn tất cả các nút không phù hợp với tiêu chí của mình (ví dụ: kết quả dài nhất). Sau đó, sau đó thực hiện một lần truy cập tiếp theo thông qua dữ liệu, xây dựng thông tin chi tiết hơn, nhưng không rộng hơn. Lặp lại cho đến khi bạn tìm thấy (các) chuỗi lặp lại dài nhất.

Một người bạn tốt được đề xuất sử dụng băm. Bằng cách băm chuỗi ký tự có độ dài cố định bắt đầu từ mỗi ký tự, bây giờ bạn có vấn đề tìm các giá trị băm trùng lặp (và xác minh sao chép, khi băm bị mất). Nếu bạn phân bổ một mảng độ dài của dữ liệu để giữ giá trị băm, bạn có thể làm những điều thú vị, ví dụ: để xem liệu một trận đấu có dài hơn độ dài dữ liệu cố định của bạn không, bạn chỉ có thể so sánh chuỗi các băm chứ không phải là tái tạo chúng. Vv

Answer 8

Chỉ là một suy nghĩ muộn màng đã xảy ra với tôi ...

Tùy thuộc vào hệ điều hành/môi trường của bạn. (Ví dụ: 64 bit con trỏ & mmap() có sẵn.)

Bạn có thể tạo một cây Suffix rất lớn trên đĩa qua mmap() và sau đó giữ một tập hợp con được truy cập thường xuyên nhất được lưu vào bộ nhớ của cây đó ký ức.

Answer 9

những gì về một chương trình đơn giản như thế này:

S = "ABAABBCCAAABBCCM" 

def findRepeat(S): 
    n = len(S) 
    #find the maxim lenth of repeated string first 
    msn = int(floor(n/2)) 
    #start with maximum length 
    for i in range(msn,1,-1): 
     substr = findFixedRepeat(S, i) 
     if substr: 
      return substr 
    print 'No repeated string' 
    return 0 

def findFixedRepeat(str, n): 
    l = len(str) 
    i = 0 
    while ((i + n -1) < l): 
     ss = S[i:i+n] 
     bb = S[i+n:] 
     try: 
      ff = bb.index(ss) 
     except: 
      ff = -1 

     if ff >= 0: 
      return ss; 
     i = i+1 
    return 0 
print findRepeat(S)