Perlu ikhtisar yang baik untuk algoritme Struktur Data Ringkas

(sudah bertanya di situs utama , tetapi meminta juga di sini untuk cakupan yang lebih baik, maaf)

Karena saya tahu tentang Struktur Data Singkat, saya sangat membutuhkan tinjauan yang baik tentang perkembangan terkini di bidang itu.

Saya telah googled dan membaca banyak artikel yang bisa saya lihat di atas hasil google atas permintaan dari atas kepala saya. Saya masih curiga saya telah melewatkan sesuatu yang penting di sini.

Berikut adalah topik yang menarik bagi saya:

1. Pengkodean singkat dari pohon biner dengan operasi yang efisien untuk mendapatkan induk, anak kiri / kanan, jumlah elemen dalam subtree.

   Pertanyaan utama di sini adalah sebagai berikut: semua pendekatan yang saya tahu mengasumsikan node pohon disebutkan dalam urutan pertama (seperti dalam karya perintis di daerah ini Jacobson, G. J (1988). Struktur data statis singkat), yang tidak tampaknya sesuai untuk tugas saya. Saya berurusan dengan pohon biner besar yang diberikan dalam tata letak kedalaman-pertama dan indeks simpul kedalaman-pertama adalah kunci untuk properti simpul lainnya, jadi mengubah tata letak pohon memiliki beberapa biaya bagi saya yang ingin saya meminimalkan. Oleh karena itu minat untuk mendapatkan referensi untuk karya-karya mempertimbangkan tata letak BF kemudian lain.

2. Array item dengan panjang variabel besar dalam memori eksternal. Array tidak berubah: Saya tidak perlu menambah / menghapus / mengedit item. Satu-satunya persyaratan adalah O (1) waktu akses elemen dan overhead serendah mungkin, lebih baik daripada pendekatan offset dan ukuran langsung. Berikut adalah beberapa statistik yang saya kumpulkan tentang data khas untuk tugas saya:

   jumlah barang yang khas - ratusan juta, hingga puluhan miliar;

   sekitar 30% item memiliki panjang tidak lebih dari 1 bit ;

   40% -60% item memiliki panjang kurang dari 8 bit;

   hanya beberapa persen item yang memiliki panjang antara 32 dan 255 bit (255 bit adalah batasnya)

   panjang item rata-rata ~ 4 bit +/- 1 bit.

   distribusi panjang barang lainnya secara teori dimungkinkan, tetapi semua kasus yang praktis menarik memiliki statistik yang mendekati yang dijelaskan di atas.

Tautan ke artikel dengan kompleksitas apa pun, tutorial tentang ketidakjelasan apa pun, perpustakaan C / C ++ yang kurang lebih didokumentasikan, - apa pun yang berguna bagi Anda dalam tugas serupa atau apa yang tampak seperti itu oleh tebakan Anda yang berpendidikan - semua hal seperti itu sangat dihargai.

Memperbarui : Saya lupa menambahkan pertanyaan 1: pohon biner yang saya tangani tidak dapat diubah. Saya tidak memiliki persyaratan untuk mengubah mereka, semua yang saya butuhkan hanya melintasi mereka dengan berbagai cara selalu bergerak dari node ke anak-anak atau ke orang tua, sehingga biaya rata-rata operasi tersebut adalah O (1).

Juga, tipikal tree memiliki milyaran node dan tidak sepenuhnya disimpan dalam RAM.

Saya berasumsi bahwa Anda tertarik pada struktur data memori eksternal yang ringkas dan efisien dalam praktiknya. Dalam hal ini, Anda mungkin bisa mendapatkan apa yang Anda inginkan dengan beberapa teknik dasar dan beberapa teknik.

Untuk pohon, saya akan mulai dengan membaca Arroyuelo et al.: Pohon Singkat dalam Praktek . Makalah ini membahas pepohonan dalam memori utama, tetapi sebagian besar teknik dapat digunakan dalam memori eksternal dengan pilihan yang sama seperti di bawah ini.

Adapun pertanyaan kedua Anda, pilihan paling penting adalah memutuskan penyandian yang Anda gunakan untuk item. Mengingat distribusi yang Anda jelaskan, saya akan coba dulu menggunakan$\gamma$-kode atau$\delta$-kode . Ketika Anda telah memilih pengkodean, langkah selanjutnya adalah menyandikan array dalam ukuran blok$B$, di mana ukuran blok dipilih sehingga disk acak membaca ukuran $B$ efisien dalam praktiknya.

Untuk menemukan blok yang benar dengan cepat, Anda memerlukan kamus peringkat yang berada di memori utama. Dengan asumsi Anda miliki$n$ item, Anda membangun urutan biner $S$ panjangnya $n$dimana $S[i] = 1$ barang iff $i$memulai blok baru. Pengkodean celah mengkompres urutan dengan baik; Gupta et al .: Struktur data terkompresi: kamus dan tindakan yang menyadari data memberikan salah satu contoh indeks tersebut. Jika Anda ingin menemukan item$j$, maka Anda perlu mengambil blokir $rank(j)$ dan decode untuk mendapatkan item.

Jika Anda ingin menjaga indeks peringkat kecil, Anda harus membuat ukuran blok cukup besar (mungkin kilobyte atau puluhan kilobyte), membuat solusi dasar di atas intensif CPU. Ini dapat diatasi dengan menambahkan sedikit overhead ke blok yang disimpan pada disk. Pada dasarnya Anda menerapkan solusi yang sama secara rekursif, sehingga setiap blok disk menyimpan sejumlah blok kecil serta indeks peringkat lainnya. Ketika Anda telah mengambil blok disc yang benar, Anda menggunakan indeks peringkat di dalamnya untuk menemukan blok kecil yang tepat untuk memecahkan kode, bukannya mendekode seluruh blok. Dengan indeks sekunder ini, akses acak mungkin menjadi I / O-terikat bahkan dengan solid-state drive tercepat yang tersedia.