Thuật toán xây dựng chuỗi hậu tố hiện đại nhất là gì?

Question

Tôi đang tìm kiếm thuật toán xây dựng nhanh suffix-array. Tôi quan tâm đến việc dễ triển khai và tốc độ thô hơn độ phức tạp tiệm cận (tôi biết rằng một mảng hậu tố có thể được xây dựng bằng cây hậu tố trong thời gian O (n), nhưng phải mất rất nhiều không gian; bad-O xấu nhất trường hợp phức tạp-O, nhưng chạy khá nhanh trong thực tế). Tôi không quan tâm các thuật toán tạo ra một mảng LCP như là một sản phẩm phụ, vì tôi vẫn cần một cho các mục đích của riêng tôi.

Tôi đã tìm thấy taxonomy of various suffix array construction algorithms nhưng đã lỗi thời. Tôi đã nghe nói về SA-IS, qsufsort và BPR, nhưng tôi thực sự không biết chúng so sánh với nhau như thế nào, cũng như không có thuật toán nào tốt hơn nữa. Xem xét trường nóng của mảng hậu tố có vẻ như thế nào ngay bây giờ, tôi hy vọng rằng một số thuật toán khác đã thay thế các thuật toán đó kể từ khi chúng được xuất bản. Tôi dường như nhớ lại đang gặp một bài báo mô tả một thuật toán nhanh được gọi là "chia nhỏ", nhưng tôi không thể tìm thấy nó ngay bây giờ cho cuộc sống của tôi.

Vì vậy, trạng thái hiện tại của nghệ thuật là gì? Lý tưởng nhất, tôi muốn một danh sách ngắn các thuật toán tốt nhất hiện tại (với các liên kết, nếu có thể) và tổng quan nhanh về điểm mạnh và điểm yếu tương đối của chúng.

Answer 1

Hiện tại, nhà xây dựng Suffix-Array tốt nhất được biết đến là LibDivSufSort, bởi Yuta Mori: http://code.google.com/p/libdivsufsort/

Nó sử dụng phương pháp Induced Sorting (về cơ bản, sau khi phân loại tất cả các chuỗi bắt đầu bằng "A *", bạn có thể tạo ra sortings của chuỗi "BA *" "CA *" "DA * "vv)

Nó được ca ngợi ở khắp mọi nơi cho hiệu quả của nó ciency và xử lý tốt đẹp của các trường hợp thoái hóa. Nó cũng là nhanh nhất, và sử dụng số lượng tối ưu của bộ nhớ (5N). Giấy phép là không phô trương, vì vậy thuật toán này được tích hợp vào một số chương trình khác, chẳng hạn như thư viện nén libbsc ví dụ, bởi Ilya Grebnov. http://libbsc.com/default.aspx

Đối với mục đích so sánh, các bạn sẽ tìm thấy một Suffix Mảng chuẩn nén liên kết ở trang này: http://code.google.com/p/libdivsufsort/wiki/SACA_Benchmarks và trang này http://homepage3.nifty.com/wpage/benchmark/index.html

Các benchmark cũng liệt kê nhiều người khác xứng đáng thực hiện SACA. Tuy nhiên, vì cả lý do giấy phép và hiệu quả, tôi khuyên bạn nên sử dụng libdivsufsort trong số đó.

Chỉnh sửa: Rõ ràng, MSufsort được cho là đang hướng tới phiên bản 4 sớm, và được cho là trở nên khá nhanh hơn Divsufsort. Nếu điều đó đúng, nó sẽ trở thành một nhà vô địch SACA mới. Tuy nhiên, chúng tôi chưa có ngày phát hành và đây sẽ là nội dung alpha. Vì vậy, nếu bạn cần một thực hiện đã được chứng minh bây giờ, libdivsufsort vẫn là sự lựa chọn tốt nhất.Lưu ý rằng những "triển khai SACA tốt nhất" này không sử dụng "một thuật toán xây dựng", nhưng kết hợp một số thủ thuật tối ưu hóa, khiến chúng khó có thể tóm tắt được.

Answer 2

Bạn có thể xem xét:

Một tour du lịch nhanh chóng trên các mảng hậu tố và mảng hậu tố nén R Grossi - lý thuyết khoa học máy tính, 2011

thuật toán mảng hậu tố Có lẽ mới được không còn được phát triển với tốc độ bạn tưởng tượng. Để được trên các cạnh chảy máu, tôi sẽ đề nghị Nhìn vào cấu trúc dữ liệu được sử dụng cùng với các mảng suffiix và nhìn vào giấy tờ trên toán học liên quan đến mảng hậu tố: Schürmann, Munro, He, vv

Answer 3

http://code.google.com/p/libdivsufsort/source/browse/wiki/SACA_Benchmarks.wiki cung cấp danh sách các thuật toán nhanh nhất mà bạn muốn.

Triển khai của kvark là nhanh nhất trong hầu hết các trường hợp trong điểm chuẩn ở trên. Bạn có thể tìm mã trên http://www.kvatom.com/archon.

libdivsufsort là sự kết hợp giữa thuật toán của CNTT và quy trình đăng của Induced Sorting. Một tập con của hậu tố được chọn giống như thuật toán phân loại gây ra, nhưng thay vì đệ quy giải quyết nó bằng cách phân loại gây ra, chúng được sắp xếp theo thuật toán của CNTT.

libdivsufsort và việc thực hiện của kvark đều dựa trên thuật toán của CNTT.

Thuật toán của KA tương tự như thuật toán của CNTT, xuất hiện ở 99. Cả hai đều chia hậu tố thành 2 loại: loại S hoặc loại L. Nếu hậu tố thứ i nhỏ hơn (i + 1) hậu tố, đó là loại S; nếu không thì đó là loại L. Sau khi sắp xếp tất cả các kiểu hậu tố S, chúng ta có thể suy ra thứ tự của tất cả các hậu tố loại L, sau đó chúng ta đã hoàn thành.

Sự khác biệt giữa thuật toán của KA và thuật toán CNTT là: KA sử dụng đệ quy để sắp xếp các phân đoạn, trong khi thuật toán của IT thu hút loại sắp xếp Multikey Quicksort/MSD/insertion.