Özlü (Succinct) veri yapıları

• Performans optimizasyonu için makaleler okurken Succinct Data Structures (özlü veri yapıları) kavramıyla ilk kez karşılaşıldı
• İlgili makaleleri ararken tanınmış araştırmacı Prof. Gonzalo Navarro ile doğrudan iletişim kuruldu
• Mevcut diziler, hash map'ler, ağaçlar vb. ile karşılaştırıldığında bu tür veri yapılarının neden yaygın kullanılmadığı sorgulandı
• Buna dair kısa bir açıklama yapılmak isteniyor

Succinct Data Structures'a genel bakış

• Genel veri sıkıştırmaya benzer şekilde veriyi sıkıştırarak saklar, ancak sıkıştırılmış haldeyken de doğrudan kullanılabilir
• Mevcut sıkıştırma yöntemlerinden farkı: veriye sıkıştırmayı açmadan erişilebilir ve veri üzerinde işlem yapılabilir
• Son 25 yılda yoğun biçimde araştırılan bir alan

Rust'ta kullanım

• Sistem programlama tarafında performans ve bellek kullanımı önemli olduğundan, bu veri yapıları büyük fayda sağlayabilir
• Mevcut araştırmalar ağırlıklı olarak C++ üzerinde yapılmış olsa da, Rust tarafında da uygulamalar ortaya çıkmaya başladı
• Rust geliştiricileri için faydalı olabilecek bazı kütüphaneler tanıtılıyor

Bit Vectors (bit vektörleri)

• Bit dizisi örneği: [0, 1, 0, 1, 1, 0, 1, 0]
• 64 bitlik bir sistemde 64 bit tek bir tamsayı içinde saklanabildiği için alan tasarrufu sağlar
• Bit vektörünün kendisi özlü bir yapı değildir, ancak onu verimli kullanmanın yolları vardır

Rank/Select Bit Vector

• Rank işlemi: belirli bir indisten önce 1 değerinin kaç kez göründüğünü hesaplar
  • Örnek: rank(3) → 2
• Select işlemi: belirli sıradaki 1 değerinin bulunduğu konumu döndürür
  • Örnek: select(2) → 3
• O(1) zaman karmaşıklığı ile çalıştırılabilir
• Bellek ek yükü düşüktür ve büyük string'lerle çalışırken kullanışlıdır
• Kullanım örnekleri
  • Büyük bir string'i küçük string parçalarına bölerek saklarken faydalıdır
  • Belirli bir indisin hangi alt string'e ait olduğunu verimli şekilde bulabilir
  • Sıkıştırılmış depolama yöntemi sayesinde bellek kullanımını azaltırken hızlı arama sunar
• Rust kütüphaneleri
  • vers: yüksek performans ve minimum ek yük sunar
  • sucds: SArray gibi seyrek (sparse) uygulamaları destekler
  • vers, verimli veri yapısı oluşturma konusunda güçlüdür ve gelecekte seyrek uygulamaları da desteklemeyi planlamaktadır

Wavelet Matrix (wavelet matrisi)

• Rank/Select kavramını daha büyük alfabeler içeren veri kümelerine genişletir
• Örneğin: DNA dizi analizi (A, C, G, T) veya metin arama (UTF-8 karakterleri, 256 sembol)
• Rank/Select bit vektörü temelinde çalışır
• Rust kütüphaneleri
  • vers içinde wavelet matrisi uygulaması bulunur

FM-Index (sıkıştırılmış string indeksi)

• Büyük miktarda metin verisini sıkıştırarak saklarken aynı zamanda arama işlevi sunar
• Temel işlevler:
  • count(pattern): belirli bir desenin (string) kaç kez geçtiğini hesaplar
  • locate(pattern): bu desenin geçtiği tüm indisleri döndürür
• DNA dizi araması ve büyük ölçekli metin araması için kullanışlıdır
• Rust kütüphaneleri
  • fm-index kütüphanesi kullanılabilir
  • Daha önce fid kullanılıyordu, ancak vers'e geçildikten sonra performans artışı görüldü

Balanced Parentheses (dengeli parantez gösterimi)

• Ağaç yapısını düğüm başına 2 bit düzeyinde sıkıştırarak saklar
• Örnek ağaç:

   a  
 /   \  
b     c  

• (()()) biçiminde gösterilebilir
• 1 (açık parantez) ve 0 (kapalı parantez) olarak dönüştürülebilir: 110100
• Rank/Select işlemleri kullanılarak ağaç içi gezinme işlemleri optimize edilir
• Rust kütüphaneleri
  • vers paketinin dev-bp dalında uygulanıyor

Uygulama: XML saklama ve işleme

• XML, dengeli parantez gösterimi kullanılarak saklanabilir
• XML etiketlerini (p, div vb.) verimli işlemek için Rank/Select bit vektörü kullanılır
• FM-Index ile metin arama performansı artırılır

Sonuç

• Özlü veri yapıları, düşük bellek kullanımı ile hızlı işlemleri aynı anda sunar
• Araştırmalar C++ tarafında yoğunlaşmış olsa da Rust'ta da aktif biçimde uygulanıyorlar
• Araştırmacılar ve açık kaynak geliştiricileriyle iş birliği yapılırken pek çok olasılık keşfedildi
• Gelecekte bilgisayar biliminin çeşitli alanlarında daha yaygın kullanılma potansiyeline sahipler

[qwqwhs]

Wavelet kullanan sıkıştırma yapıları, Djvu'da standart olarak yaygın biçimde kullanılıyor. Görüntü sıkıştırması gerçekten çok başarılı.

[GN⁺]

Hacker News görüşleri

• Gonzalo Navarro'ya e-posta gönderip soru sordum ve bunun sonucunda birlikte bir makale yazdık

  • Onun bir başka makalesi, birkaç zarif fikri birleştirerek bitvektör rank/select'in basit bir uygulamasını ele alıyor
  • Bu dönemde özlü veri yapılarıyla çok ilgilendim ve çeşitli bitvektör türleri ile wavelet matrix'i uygulayan bir Rust kütüphanesi yazdım
  • Veri görselleştirme açısından, alan açısından verimli veri yapılarının istemci tarafında büyük veri kümelerinin etkileşimli keşfini kökten iyileştirip iyileştiremeyeceğini merak ettim

• Bu alanda 30 yıldan uzun süredir bulunuyorum ama "özlü veri yapıları" diye bir şeyi ilk kez duydum

  • Bu gönderiyi görmeseydim muhtemelen bunu hiç öğrenmeyecektim
  • Bu veri yapılarının grafik işleme için pratik uygulamaları varsa önemli bir keşif olabilir
  • Bu konu bana çekici geliyor

• Özlü veri yapıları, veri kümesi belleğe sığıyorsa geleneksel yapılardan daha hızlı olmayabilir

  • Ancak büyük veri kümelerinde depolamaya erişim süresi baskın olduğundan özlü veri yapıları avantajlıdır
  • Özlü ağaçlar birer sanat eseri gibi

• Özlü veri yapıları kavramını ilk kez Edward Kmett'ten duydum

  • Kendisi tanınmış bir Haskell kütüphane geliştiricisi ve uzun zaman önce özlü veri yapıları hakkında bir konuşma yapmıştı

• Özlü veri yapıları çok eğlenceli

  • Bunu Zig ile uyguladım; ana uygulama, öğe başına 4 bitten az kullanan minimal perfect hash function
  • Bu tür algoritmaları uygulamak sihir gibi

• Navarro'nun kitabı mükemmel bir derleme çalışması

  • Erik Demaine'in özlü veri yapıları hakkındaki dersleri de harika

• Bu sabahı özlü veri yapıları üzerine okuyarak geçirdim ve bellek verimliliği şaşırtıcı

  • Büyük XML dosyalarını ayrıştırdığım bir projede çok fazla RAM tüketiyorum
  • Wavelet matrix kavramı metin odaklı işler için umut verici görünüyor

• Büyük struct'ların bellek içi düğüm gösterimini verimli hale getirmenin bir yolu var

  • Seyrek kullanılan alanlar için offset'ler ayrılır ve alanın varlığını göstermek için bitmask kullanılır
  • Masking ve popcount hızlı erişim sağlar

• Marisa trie çok havalı ve kullanışlı bir özlü veri yapısı

  • High Performance Python kitabında da geçiyor

• Özlü veri yapıları için benim temel kütüphanem SDSL-Lite