Cấu trúc dữ liệu súc tích (Succinct)

 (blog.startifact.com)
20 điểm bởi GN⁺ 2025-03-07 | 2 bình luận | Chia sẻ qua WhatsApp
  • Trong lúc đọc các bài báo để tối ưu hiệu năng, tôi lần đầu tiếp cận khái niệm Succinct Data Structures (cấu trúc dữ liệu súc tích)
  • Khi tìm các bài báo liên quan, tôi đã trực tiếp trao đổi với giáo sư Gonzalo Navarro, một nhà nghiên cứu nổi tiếng trong lĩnh vực này
  • Khác với mảng, hash map, cây và các cấu trúc quen thuộc khác, tôi bắt đầu tự hỏi vì sao những cấu trúc dữ liệu này lại chưa được sử dụng rộng rãi
  • Vì vậy tôi muốn giải thích ngắn gọn về chủ đề này

Tổng quan về Succinct Data Structures

  • Tương tự như nén dữ liệu thông thường, dữ liệu được lưu ở dạng nén, nhưng vẫn có thể được sử dụng trực tiếp ngay trong trạng thái đã nén
  • Điểm khác với cách nén truyền thống: có thể truy cập và thao tác dữ liệu mà không cần giải nén
  • Đây là một lĩnh vực đã được nghiên cứu rất sôi nổi trong 25 năm gần đây

Ứng dụng trong Rust

  • Trong lập trình hệ thống, hiệu năng và mức dùng bộ nhớ rất quan trọng, nên những cấu trúc dữ liệu này có tiềm năng đặc biệt hữu ích
  • Các nghiên cứu trước đây chủ yếu được thực hiện bằng C++, nhưng hiện nay cũng đã bắt đầu xuất hiện các bản triển khai trong Rust
  • Bài viết giới thiệu một số thư viện có thể hữu ích cho các lập trình viên Rust

Bit Vectors (vector bit)

  • Ví dụ mảng bit: [0, 1, 0, 1, 1, 0, 1, 0]
  • Trên hệ thống 64 bit, có thể lưu 64 bit trong một số nguyên duy nhất, nhờ đó tiết kiệm không gian
  • Bản thân vector bit không phải là một cấu trúc succinct, nhưng có những cách khai thác nó hiệu quả

Rank/Select Bit Vector

  • Phép toán Rank: tính xem trước một chỉ mục nhất định đã xuất hiện bao nhiêu bit 1
    • Ví dụ: rank(3) → 2
  • Phép toán Select: trả về vị trí xuất hiện của bit 1 thứ n
    • Ví dụ: select(2) → 3
  • Có thể thực thi với độ phức tạp thời gian O(1)
  • Overhead bộ nhớ thấp, rất hữu ích khi xử lý chuỗi lớn
  • Trường hợp sử dụng
    • Hữu ích khi lưu trữ một chuỗi lớn dưới dạng các chuỗi con nhỏ hơn
    • Có thể tìm hiệu quả xem một chỉ mục cụ thể thuộc về chuỗi con nào
    • Nhờ cách lưu trữ nén, có thể giảm mức dùng bộ nhớ mà vẫn tìm kiếm nhanh
  • Thư viện Rust
    • vers: cung cấp hiệu năng cao và overhead tối thiểu
    • sucds: hỗ trợ các triển khai thưa (sparse) như SArray
    • vers có thế mạnh ở việc xây dựng cấu trúc dữ liệu hiệu quả, và dự kiến sẽ hỗ trợ cả triển khai thưa trong tương lai

Wavelet Matrix (ma trận wavelet)

  • Mở rộng khái niệm Rank/Select sang dữ liệu có bảng chữ cái lớn hơn
  • Ví dụ: phân tích chuỗi DNA (A, C, G, T) hoặc tìm kiếm văn bản (ký tự UTF-8, 256 ký hiệu)
  • Hoạt động dựa trên Rank/Select bit vector
  • Thư viện Rust
    • vers có bao gồm triển khai ma trận wavelet

FM-Index (chỉ mục chuỗi nén)

  • Lưu trữ lượng lớn dữ liệu văn bản ở dạng nén đồng thời vẫn hỗ trợ chức năng tìm kiếm
  • Các chức năng cốt lõi:
    • count(pattern): tính số lần xuất hiện của một mẫu cụ thể (chuỗi)
    • locate(pattern): trả về tất cả các chỉ mục nơi mẫu đó xuất hiện
  • Hữu ích trong tìm kiếm chuỗi DNA và tìm kiếm văn bản quy mô lớn
  • Thư viện Rust
    • Có thể sử dụng thư viện fm-index
    • Trước đây dùng fid, nhưng sau khi chuyển sang vers thì hiệu năng đã được cải thiện

Balanced Parentheses (biểu diễn ngoặc cân bằng)

  • Nén và lưu trữ cấu trúc cây ở mức 2 bit cho mỗi nút
  • Cây ví dụ:
   a  
 /   \  
b     c
  • Có thể biểu diễn dưới dạng (()())
  • Có thể chuyển thành 1 (ngoặc mở) và 0 (ngoặc đóng): 110100
  • Tận dụng phép toán Rank/Select để tối ưu các thao tác duyệt trong cây
  • Thư viện Rust
    • Đang được triển khai trên nhánh dev-bp của vers

Ứng dụng: lưu trữ và xử lý XML

  • Có thể lưu XML bằng cách dùng biểu diễn ngoặc cân bằng
  • Để xử lý hiệu quả các thẻ XML (p, div v.v.), có thể dùng Rank/Select bit vector
  • Dùng FM-Index để cải thiện hiệu năng tìm kiếm văn bản

Kết luận

  • Cấu trúc dữ liệu succinct đồng thời mang lại mức dùng bộ nhớ thấp và phép toán nhanh
  • Dù đã có nhiều nghiên cứu trong C++, chúng cũng đang được hiện thực tích cực trong Rust
  • Việc cộng tác với các nhà nghiên cứu và lập trình viên mã nguồn mở đã mở ra rất nhiều tiềm năng
  • Nhiều khả năng chúng sẽ được sử dụng rộng rãi hơn trong nhiều lĩnh vực khoa học máy tính trong tương lai

Bài viết liên quan

2 bình luận

 
qwqwhs 2025-03-09

Cấu trúc nén sử dụng Wavelet đang được dùng rất tốt như một tiêu chuẩn trong Djvu. Khả năng nén ảnh thực sự rất xuất sắc.
 
GN⁺ 2025-03-07
Ý kiến trên Hacker News

  • Tôi đã gửi email cho Gonzalo Navarro để hỏi vài điều, và kết quả là cuối cùng chúng tôi đã cùng viết một bài báo

    • Một bài báo khác của ông ấy xử lý cách triển khai đơn giản của rank/select trên bit vector bằng cách kết hợp một vài ý tưởng thanh lịch
    • Trong giai đoạn đó, tôi trở nên rất hứng thú với cấu trúc dữ liệu succinct và đã viết một thư viện Rust triển khai nhiều kiểu bit vector và wavelet matrix
    • Từ góc nhìn trực quan hóa dữ liệu, tôi tự hỏi liệu các cấu trúc dữ liệu tiết kiệm không gian có thể cải thiện căn bản việc khám phá tương tác các tập dữ liệu lớn ở phía client hay không

  • Tôi đã ở trong lĩnh vực này hơn 30 năm nhưng đây là lần đầu tiên tôi nghe đến "cấu trúc dữ liệu succinct"

    • Nếu không thấy bài đăng này thì có lẽ tôi đã không biết đến nó
    • Nếu cấu trúc dữ liệu này có ứng dụng thực tế trong xử lý đồ thị thì đây có thể là một phát hiện quan trọng
    • Chủ đề này tạo cảm giác rất hấp dẫn

  • Cấu trúc dữ liệu succinct có thể không nhanh hơn cấu trúc truyền thống khi tập dữ liệu vừa trong bộ nhớ

    • Nhưng với các tập dữ liệu lớn, thời gian truy cập lưu trữ chiếm ưu thế nên cấu trúc dữ liệu succinct có lợi hơn
    • Cây succinct giống như một tác phẩm nghệ thuật

  • Tôi lần đầu nghe về khái niệm cấu trúc dữ liệu succinct từ Edward Kmett

    • Ông ấy là một nhà phát triển thư viện Haskell nổi tiếng và đã có một bài nói chuyện về cấu trúc dữ liệu succinct từ lâu

  • Cấu trúc dữ liệu succinct rất thú vị

    • Tôi đã triển khai chúng bằng Zig, và phần triển khai chính là hàm băm hoàn hảo tối thiểu dùng các phần tử nhỏ hơn 4 bit
    • Việc triển khai những thuật toán như thế này giống như phép màu

  • Cuốn sách của Navarro là một tài liệu khảo cứu rất xuất sắc

    • Bài giảng của Erik Demaine về cấu trúc dữ liệu succinct cũng rất hay

  • Tôi đã dành cả buổi sáng để tìm hiểu về cấu trúc dữ liệu succinct, và hiệu quả bộ nhớ của chúng thật đáng kinh ngạc

    • Tôi đang dùng rất nhiều RAM trong một dự án phân tích các tệp XML lớn
    • Khái niệm wavelet matrix có vẻ đầy hứa hẹn cho các công việc thiên về văn bản

  • Có một cách để làm cho biểu diễn nút trong bộ nhớ của các struct lớn hiệu quả hơn

    • Gán offset cho các trường ít khi dùng và dùng bitmask để biểu thị sự tồn tại của trường
    • Masking và popcount cho phép truy cập nhanh

  • Marisa trie là một cấu trúc dữ liệu succinct rất ngầu và hữu ích

    • Nó cũng được nhắc đến trong cuốn High Performance Python

  • Thư viện nền tảng tôi dùng cho cấu trúc dữ liệu succinct là SDSL-Lite