Struktur Data Succinct

 (blog.startifact.com)
20 poin oleh GN⁺ 2025-03-07 | 2 komentar | Bagikan ke WhatsApp
  • Saat membaca makalah untuk optimasi performa, penulis pertama kali menemukan konsep Succinct Data Structures (struktur data succinct)
  • Saat mencari makalah terkait, penulis sempat berkomunikasi langsung dengan profesor Gonzalo Navarro, seorang peneliti ternama
  • Muncul pertanyaan mengapa struktur data semacam ini tidak banyak digunakan, tidak seperti array, hash map, tree, dan sebagainya
  • Tulisan ini mencoba menjelaskannya secara singkat

Gambaran umum Succinct Data Structures

  • Mirip dengan kompresi data pada umumnya, data disimpan dalam bentuk terkompresi, tetapi tetap bisa digunakan secara langsung bahkan saat masih terkompresi
  • Perbedaannya dengan metode kompresi biasa: data dapat diakses dan dimanipulasi tanpa didekompresi
  • Ini adalah bidang yang telah diteliti secara aktif selama 25 tahun terakhir

Pemanfaatan di Rust

  • Dalam system programming, performa dan penggunaan memori sangat penting, sehingga struktur data semacam ini berpotensi sangat berguna
  • Riset yang ada selama ini lebih banyak dilakukan di C++, tetapi implementasi di Rust juga mulai bermunculan
  • Penulis memperkenalkan library yang dapat membantu para pengembang Rust

Bit Vectors (vektor bit)

  • Contoh array bit: [0, 1, 0, 1, 1, 0, 1, 0]
  • Pada sistem 64-bit, 64 bit dapat disimpan dalam satu integer sehingga menghemat ruang
  • Vektor bit itu sendiri bukan struktur succinct, tetapi ada cara untuk memanfaatkannya secara efisien

Rank/Select Bit Vector

  • Operasi Rank: menghitung berapa kali angka 1 muncul sebelum indeks tertentu
    • Contoh: rank(3) → 2
  • Operasi Select: mengembalikan posisi kemunculan 1 ke-n
    • Contoh: select(2) → 3
  • Dapat dijalankan dengan kompleksitas waktu O(1)
  • Overhead memori kecil, dan berguna saat menangani string berukuran besar
  • Contoh penggunaan
    • Berguna saat menyimpan string besar yang dibagi ke unit string kecil
    • Dapat menemukan secara efisien substring mana yang memuat indeks tertentu
    • Dengan metode penyimpanan terkompresi, penggunaan memori bisa dikurangi sambil tetap memungkinkan pencarian cepat
  • Library Rust
    • vers: memberikan performa tinggi dan overhead minimal
    • sucds: mendukung implementasi sparse seperti SArray
    • vers unggul dalam pembuatan struktur data yang efisien dan direncanakan akan mendukung implementasi sparse di masa depan

Wavelet Matrix

  • Memperluas konsep Rank/Select ke data dengan alfabet yang lebih besar
  • Contoh: analisis sekuens DNA (A, C, G, T) atau pencarian teks (karakter UTF-8, 256 simbol)
  • Bekerja berdasarkan Rank/Select bit vector
  • Library Rust
    • vers menyertakan implementasi wavelet matrix

FM-Index (indeks string terkompresi)

  • Mendukung fitur pencarian sambil menyimpan data teks dalam jumlah besar secara terkompresi
  • Fitur utamanya:
    • count(pattern): menghitung berapa kali pola tertentu (string) muncul
    • locate(pattern): mengembalikan semua indeks tempat pola tersebut muncul
  • Berguna untuk pencarian sekuens DNA dan pencarian teks skala besar
  • Library Rust
    • Dapat menggunakan library fm-index
    • Sebelumnya menggunakan fid, tetapi setelah migrasi ke vers, performanya meningkat

Balanced Parentheses (representasi tanda kurung seimbang)

  • Menyimpan struktur tree dalam bentuk terkompresi hingga sekitar 2 bit per node
  • Contoh tree:
   a  
 /   \  
b     c
  • Dapat direpresentasikan dalam bentuk (()())
  • Bisa diubah menjadi 1 (kurung buka) dan 0 (kurung tutup): 110100
  • Memanfaatkan operasi Rank/Select untuk mengoptimalkan operasi penelusuran di dalam tree
  • Library Rust
    • Sedang diimplementasikan pada branch dev-bp milik vers

Aplikasi: penyimpanan dan pemrosesan XML

  • XML dapat disimpan menggunakan representasi tanda kurung seimbang
  • Untuk menangani tag XML (p, div, dll.) secara efisien, dapat digunakan Rank/Select bit vector
  • Menggunakan FM-Index untuk meningkatkan performa pencarian teks

Kesimpulan

  • Struktur data succinct menawarkan penggunaan memori rendah dan operasi cepat secara bersamaan
  • Walau banyak diteliti di C++, implementasinya juga makin aktif di Rust
  • Penulis menemukan banyak kemungkinan lewat kolaborasi dengan peneliti dan pengembang open source
  • Ke depan, kemungkinan besar akan dipakai lebih luas di berbagai bidang ilmu komputer

Bacaan terkait

2 komentar

 
qwqwhs 2025-03-09

Struktur terkompresi yang memanfaatkan Wavelet telah digunakan dengan baik sebagai standar di Djvu. Kompresi gambarnya benar-benar luar biasa.
 
GN⁺ 2025-03-07
Komentar Hacker News

  • Saya mengirim email kepada Gonzalo Navarro untuk mengajukan pertanyaan, dan hasilnya kami akhirnya menulis makalah bersama

    • Makalahnya yang lain membahas implementasi sederhana rank/select bitvector dengan menggabungkan beberapa ide yang elegan
    • Pada masa itu saya sangat tertarik pada struktur data ringkas dan menulis library Rust yang mengimplementasikan berbagai tipe bitvector dan wavelet matrix
    • Dari sudut pandang visualisasi data, saya penasaran apakah struktur data yang hemat ruang dapat secara mendasar meningkatkan eksplorasi interaktif dataset besar di sisi klien

  • Saya sudah berkecimpung di bidang ini lebih dari 30 tahun, tetapi ini pertama kalinya saya mendengar istilah "struktur data ringkas"

    • Jika tidak melihat postingan ini, mungkin saya tidak akan mengetahuinya
    • Jika struktur data ini punya aplikasi praktis dalam pemrosesan graf, ini bisa menjadi penemuan penting
    • Topik ini terasa menarik

  • Struktur data ringkas mungkin tidak lebih cepat daripada struktur konvensional jika dataset muat di memori

    • Tetapi pada dataset besar, waktu akses penyimpanan menjadi faktor dominan sehingga struktur data ringkas lebih menguntungkan
    • Pohon ringkas itu seperti karya seni

  • Saya pertama kali mendengar konsep struktur data ringkas dari Edward Kmett

    • Dia adalah pengembang library Haskell yang terkenal, dan dulu pernah memberikan ceramah tentang struktur data ringkas

  • Struktur data ringkas itu sangat menyenangkan

    • Saya mengimplementasikannya dengan Zig, dan implementasi utamanya adalah fungsi hash sempurna minimal yang menggunakan elemen kurang dari 4 bit
    • Mengimplementasikan algoritme seperti ini terasa seperti sihir

  • Buku Navarro adalah survei yang luar biasa

    • Kuliah Erik Demaine tentang struktur data ringkas juga sangat bagus

  • Saya menghabiskan pagi ini mempelajari struktur data ringkas, dan efisiensi memorinya mengejutkan

    • Saya sedang mengerjakan proyek yang menganalisis file XML besar dan sangat menguras RAM
    • Konsep wavelet matrix tampak menjanjikan untuk pekerjaan yang berpusat pada teks

  • Ada cara untuk membuat representasi node dalam memori untuk struct besar menjadi efisien

    • Alokasikan offset untuk field yang jarang digunakan dan gunakan bitmask untuk menunjukkan keberadaan field
    • Masking dan popcount memungkinkan akses yang cepat

  • Marisa trie adalah struktur data ringkas yang sangat keren dan berguna

    • Ini juga disebutkan dalam buku High Performance Python

  • Library dasar saya untuk struktur data ringkas adalah SDSL-Lite