Cây Suffix và Tries. Sự khác biệt là gì?

Tôi đang đọc khoảng Tries thường được gọi là cây Tiền tố và Suffix Trees.
Mặc dù tôi đã tìm thấy mã cho một Trie Tôi không thể tìm thấy một ví dụ cho một Suffix Tree. Ngoài ra tôi nhận được cảm giác rằng mã mà xây dựng một Trie là giống như một cho một Suffix Tree với sự khác biệt duy nhất mà trong trường hợp trước đây chúng tôi lưu trữ tiền tố nhưng trong hậu tố sau này.
Điều này có đúng không? Bất cứ ai có thể giúp tôi rõ ràng điều này trong đầu của tôi? Một mã ví dụ sẽ giúp ích rất nhiều!Cây Suffix và Tries. Sự khác biệt là gì?

Nguồn

2012-12-15 Cratylus

TL; DR Cây hậu tố của chuỗi là [patricia trie] (https://en.wikipedia.org/wiki/Radix_tree) của tất cả hậu tố. Điều đặc biệt duy nhất về nó là các nhãn cạnh là các chuỗi của chuỗi gốc, vì vậy chúng có thể được biểu diễn như một cặp chỉ mục và chỉ lấy không gian cố định. Đây cũng là lý do tại sao nó có thể được xây dựng trong thời gian tuyến tính. –

Một cây hậu tố có thể được xem như một cấu trúc dữ liệu được xây dựng trên đầu trang của một trie, thay vì chỉ thêm chuỗi vào trie, bạn cũng sẽ thêm mọi hậu tố có thể của chuỗi đó. Ví dụ, nếu bạn muốn chỉ số chuỗi chuối trong một cây hậu tố, bạn sẽ xây dựng một Trie với chuỗi kí tự sau:

banana 
anana 
nana 
ana 
na 
a

Khi đã xong, bạn có thể tìm kiếm bất kỳ n-gram và xem nếu nó hiện diện trong chuỗi được lập chỉ mục của bạn. Nói cách khác, tìm kiếm n-gram là tìm kiếm tiền tố của tất cả các hậu tố có thể có của chuỗi của bạn.

Đây là cách đơn giản và chậm nhất để xây dựng cây hậu tố. Nó chỉ ra rằng có nhiều biến thể fancier trên cấu trúc dữ liệu này cải thiện trên cả hai hoặc cả không gian và thời gian xây dựng. Tôi không đủ thông thạo trong miền này để cung cấp tổng quan nhưng bạn có thể bắt đầu bằng cách xem xét suffix arrays hoặc lớp học này advanced data structures (bài 16 và 18).

Điều này answer cũng thực hiện một công việc tuyệt vời giải thích một biến thể của cấu trúc dữ liệu này.

Nguồn

2012-12-15 16:52:40

Đây là những gì tôi nghi ngờ. Trie được sử dụng để xây dựng cây hậu tố và đó là lý do tại sao hầu hết các sách giáo khoa chỉ cung cấp mã cho các lần thử. Nhưng đây là trường hợp triển khai trường hợp xấu nhất? – Cratylus

@Cratylus Cây Suffix hữu ích nhất trên các chuỗi rất lớn (ví dụ: lập chỉ mục tất cả các công trình của Shakespeare) trong đó không gian O (n^2) và thời gian xây dựng đơn giản là không cắt nó. May mắn thay, những giới hạn có thể được hạ xuống khá một chút. –

Nếu bạn tưởng tượng một Trie trong đó bạn đặt một số hậu tố của từ, bạn sẽ có thể truy vấn nó cho các chuỗi của chuỗi rất dễ dàng. Đây là ý tưởng chính đằng sau hậu tố cây, về cơ bản nó là một "hậu tố trie".

Nhưng sử dụng cách tiếp cận ngây thơ này, việc xây dựng cây này cho một chuỗi có kích thước n sẽ là O (n^2) và mất nhiều bộ nhớ.

Vì tất cả các mục của cây này là hậu tố của cùng một chuỗi, chúng chia sẻ rất nhiều thông tin, do đó, có các thuật toán tối ưu hóa cho phép bạn tạo chúng hiệu quả hơn. Ví dụ, thuật toán của Ukkonen cho phép bạn tạo một cây hậu tố trực tuyến trong độ phức tạp thời gian O (n).

Nguồn

2012-12-15 17:18:29

Vì vậy, bạn đang nói hậu tố cây và cố gắng hậu tố là như nhau? – batman

Sự khác biệt rất đơn giản. Một cây hậu tố có ít nút "giả" hơn so với hậu tố trie. Các nút giả này là các ký tự đơn giúp tăng hoạt động tra cứu tại cây

Nguồn

2016-01-11 22:24:23 curious

Cây Suffix và Tries. Sự khác biệt là gì?

Trả lời

Các vấn đề liên quan