Cây Suffix hoạt động như thế nào?

Question

Tôi sẽ xem qua các chương cấu trúc dữ liệu trong The Algorithm Design Manual và đi qua Cây hậu tố.

Ví dụ trạng thái:

Input:

XYZXYZ$ 
YZXYZ$ 
    ZXYZ$ 
    XYZ$ 
    YZ$ 
    Z$ 
     $ 

Output:

Tôi không thể hiểu làm thế nào cây đó được tạo ra từ các chuỗi đầu vào nhất định. Các cây Suffix được sử dụng để tìm một chuỗi con đã cho trong một Chuỗi đã cho, nhưng cây được cho là giúp gì cho nó? Tôi hiểu một ví dụ khác về một con trie được hiển thị bên dưới, nhưng nếu trie dưới được đầm chặt vào một cây hậu tố, thì nó sẽ trông như thế nào?

Answer 1

Các thuật toán hiệu quả tiêu chuẩn cho xây dựng một cây hậu tố chắc chắn không tầm thường. Thuật toán chính để làm như vậy được gọi là thuật toán của Ukkonen và là một sửa đổi của thuật toán ngây thơ với hai phép chọn lọc bổ sung. Có lẽ bạn nên đọc số this earlier question để biết chi tiết về cách xây dựng nó.

Bạn có thể xây dựng cây hậu tố bằng cách sử dụng các thuật toán chèn tiêu chuẩn trên radix tries để chèn mỗi hậu tố vào cây, nhưng làm như vậy wlil mất thời gian O (n), trong đó có thể tốn kém cho các chuỗi lớn.

Để thực hiện tìm kiếm chuỗi con nhanh, hãy nhớ rằng cây hậu tố là một bộ ba nén của tất cả các hậu tố của chuỗi gốc (cộng với một số điểm cuối chuỗi đặc biệt). Nếu một chuỗi S là một chuỗi con của chuỗi ban đầu T và bạn có một trie của tất cả các hậu tố của T, thì bạn có thể thực hiện tìm kiếm để xem liệu T có phải là tiền tố của bất kỳ chuỗi nào trong bộ ba đó hay không. Nếu vậy, thì T phải là một chuỗi con của S, vì tất cả các ký tự của nó tồn tại trong chuỗi ở đâu đó trong T. Thuật toán tìm kiếm chuỗi con cây hậu tố chính xác là tìm kiếm này được áp dụng cho trie nén, nơi bạn làm theo các cạnh thích hợp ở mỗi bước.

Hy vọng điều này sẽ hữu ích!

Answer 2

Một cây hậu tố về cơ bản chỉ làm gọn các chữ cái cùng với nhau khi không có lựa chọn nào được thực hiện. Ví dụ: nếu bạn nhìn vào bên phải của trie trong câu hỏi của bạn, sau khi bạn đã xem một w, thì thực sự chỉ có hai lựa chọn: was và when. Trong trie, as trong was và hen trong when mỗi cái vẫn có một nút cho mỗi chữ cái. Trong một cây hậu tố, bạn muốn đưa những với nhau thành hai nút giữ as và hen, vì vậy phía bên phải của Trie của bạn sẽ biến thành:

Answer 3

Tôi không thể hiểu được làm thế nào mà cây được tạo ra từ chuỗi đầu vào đã cho.

Bạn về cơ bản tạo ra một bộ ba patricia với tất cả các hậu tố bạn đã liệt kê. Khi chèn vào một bộ ba patricia, bạn tìm kiếm gốc cho một đứa trẻ bắt đầu với char đầu tiên từ chuỗi đầu vào, nếu nó tồn tại bạn tiếp tục xuống cây nhưng nếu không thì bạn tạo một nút mới ra khỏi thư mục gốc.Gốc sẽ có nhiều con dưới dạng các ký tự duy nhất trong chuỗi đầu vào ($, a, e, h, i, n, r, s, t, w). Bạn có thể tiếp tục quá trình đó cho mỗi ký tự trong chuỗi đầu vào.

Cây hậu tố được sử dụng để tìm chuỗi con đã cho trong một chuỗi nhất định, nhưng cây được giúp đỡ như thế nào?

Nếu bạn đang tìm chuỗi con "hen", hãy bắt đầu tìm kiếm từ gốc cho trẻ bắt đầu bằng "h". Nếu độ dài của chuỗi con "h" sau đó tiếp tục xử lý con "h" cho đến khi bạn đến cuối chuỗi hoặc bạn nhận được sự không khớp của các ký tự trong chuỗi đầu vào và chuỗi con "h". Nếu bạn kết hợp tất cả các con "h", tức là đầu vào "hen" khớp với "anh ấy" trong con "h", sau đó chuyển sang con của "h" cho đến khi bạn nhận được "n", nếu nó không tìm thấy một đứa trẻ bắt đầu với "n" thì chuỗi con không tồn tại.

Compact Suffix Trie code:

└── (black) 
    ├── (white) as 
    ├── (white) e 
    │ ├── (white) eir 
    │ ├── (white) en 
    │ └── (white) ere 
    ├── (white) he 
    │ ├── (white) heir 
    │ ├── (white) hen 
    │ └── (white) here 
    ├── (white) ir 
    ├── (white) n 
    ├── (white) r 
    │ └── (white) re 
    ├── (white) s 
    ├── (white) the 
    │ ├── (white) their 
    │ └── (white) there 
    └── (black) w 
     ├── (white) was 
     └── (white) when 

Suffix Tree code:

String = the$their$there$was$when$ 
End of word character = $ 
└── (0) 
    ├── (22) $ 
    ├── (25) as$ 
    ├── (9) e 
    │ ├── (10) ir$ 
    │ ├── (32) n$ 
    │ └── (17) re$ 
    ├── (7) he 
    │ ├── (2) $ 
    │ ├── (8) ir$ 
    │ ├── (31) n$ 
    │ └── (16) re$ 
    ├── (11) ir$ 
    ├── (33) n$ 
    ├── (18) r 
    │ ├── (12) $ 
    │ └── (19) e$ 
    ├── (26) s$ 
    ├── (5) the 
    │ ├── (1) $ 
    │ ├── (6) ir$ 
    │ └── (15) re$ 
    └── (29) w 
     ├── (24) as$ 
     └── (30) hen$