Cách thức và thời điểm tạo liên kết hậu tố trong cây hậu tố?

Question

Có ai cho tôi một ví dụ về cách thức và thời điểm tạo liên kết hậu tố trong cây hậu tố không?

Nếu chuỗi của tôi là ABABABC, nhưng hãy sử dụng ví dụ khác nếu ví dụ đó tốt hơn.

Hy vọng sẽ cung cấp một số hình ảnh để minh họa từng bước.

rất đánh giá cao.

Answer 1

Để hiểu điều này, thu hồi đầu tiên rằng có ba loại nút trong một cây hậu tố:

• Gốc
• nút nội
nút
• Leaf

Trong đồ thị bên dưới, là cây hậu tố cho ABABABC, vòng tròn màu vàng là gốc, các màu xám, xanh lam và xanh lá cây là nội bộ các nút và các nút nhỏ màu đen là .

Có hai điều quan trọng cần lưu ý:

• nút nội bộ luôn có nhiều hơn 1 đi cạnh. Tức là, các nút bên trong đánh dấu các phần của cây nơi xảy ra phân phát phân nhánh.

• Phân nhánh xảy ra ở bất kỳ đâu chuỗi lặp lại có liên quan và chỉ ở đó. Đối với bất kỳ nút nội bộ X nào, chuỗi dẫn từ gốc đến X phải xuất hiện trong chuỗi đầu vào ít nhất nhiều lần vì có cạnh đi từ X.

Ví dụ: Chuỗi dẫn đến nút màu xanh là ABAB. Thật vậy, chuỗi này xuất hiện hai lần trong chuỗi đầu vào: Tại vị trí 0 và tại vị trí 2. Và đó là lý do tại sao nút màu xanh tồn tại.

Bây giờ về các liên kết hậu tố:

1. Nếu chuỗi s dẫn đến một số nút X bên dài hơn 1 nhân vật, cùng chuỗi trừ ký tự đầu tiên (gọi s _-1) cũng phải ở trong cây (đó là hậu tố là hậu tố, vì vậy hậu tố của bất kỳ chuỗi nào của nó phải là trong cây cũng vậy).

   Ví dụ: Cho s = ABAB, chuỗi dẫn đến nút màu xanh lam. Sau đó, sau khi xóa ký tự đầu tiên, s _-1 là BAB. Và thực sự là chuỗi được tìm thấy trong cây, quá. Nó dẫn đến nút màu xanh lá cây .

2. Nếu một số chuỗi s dẫn đến một nút nội bộ, rút ​​ngắn phiên bản của nó _-1phải dẫn đến một nút nội bộ (gọi nó X _-1) là tốt. Tại sao? Bởi vì s phải xuất hiện ít nhất hai lần trong chuỗi đầu vào, vì vậy s _-1 phải xuất hiện ít nhất là nhiều lần (vì nó là một phần của s: bất cứ nơi nào s xuất hiện, s _-1 cũng phải xuất hiện). Nhưng nếu s _-1 xuất hiện nhiều lần trong chuỗi nhập, thì phải có một nút nội bộ cho nó.

3. Trong bất kỳ tình huống như vậy, một liên kết đặc biệt kết nối với X để X _-1 là một liên kết hậu tố.

Lưu ý: Do (1) và (2) ở trên, mỗi nội nút X có một nhãn từ gốc đến X của hơn 1 ký tự phải có một hậu tố liên kết đến chính xác một nút nội bộ khác.

Ví dụ:

Đây là cây hậu tố tương tự như trước; các đường chấm chấm biểu thị các liên kết hậu tố .Nếu bạn bắt đầu ở nút màu xanh và đi theo hậu tố các liên kết từ đó (từ xanh dương, xanh lục đến xám đầu tiên đến xám thứ hai), và xem các chuỗi dẫn từ gốc tới mỗi nút, bạn sẽ xem :

ABAB -> BAB -> AB -> B 
(blue)  (green)  (gray1)  (gray2) 

Đây là lý do tại sao chúng được gọi là hậu tố liên kết (toàn bộ chuỗi là gọi suffix chuỗi).

Chúng phù hợp với điều gì?

Chúng phù hợp với nhiều điều đáng ngạc nhiên. Tuy nhiên, họ đóng một vai trò đặc biệt trong Ukkonen's algorithm for suffix tree construction, cụ thể trong Quy tắc 3 mô tả ở đó: Sau khi chèn một nhân vật cuối cùng của một số hậu tố s tại một số điểm X, thuật toán cần phải chèn nhân vật cuối cùng của hậu tố s _-1 trong O (1) lần. Trong để thực hiện điều đó, nó sử dụng liên kết hậu tố để chuyển ngay đến địa điểm X _-1 và thực hiện chèn.

Nhưng, lưu ý rằng không cần thiết phải đặt các liên kết hậu tố trong cây hậu tố. Chúng không phải là một phần của định nghĩa cây hậu tố — chúng chỉ là các liên kết đặc biệt được sử dụng bởi một số thuật toán xây dựng hoặc sử dụng các cây hậu tố.

---

Về hạch ký tự duy nhất: gì nếu có một nút X bên trong có chuỗi (ví dụ: các chuỗi trên đường đi từ gốc đến X) bao gồm chỉ có một nhân vật? Theo định nghĩa trên, X sau đó không có liên kết hậu tố. Tuy nhiên, bạn có thể giả định rằng nếu nó có một liên kết hậu tố, nó sẽ trỏ đến nút gốc. Hơn nữa: Nếu, theo định nghĩa trên, một nút bên trong không có liên kết hậu tố, nó phải là một nút ký tự đơn, vì vậy bạn luôn có thể giả định rằng nếu không có liên kết hậu tố nào có mặt tại một nút bên trong thì nó phải là một đơn nút ký tự, và do đó, nút đại diện cho hậu tố s _-1 là nút gốc. (Một số thuật toán thực sự có thể thêm một liên kết hậu tố rõ ràng trỏ đến nút gốc trong trường hợp này.) Nhờ j_random_hacker cho nhận xét về điều này.