Kucing dalam kotak, atau Struktur data ringkas

Apa yang harus saya lakukan jika pohon pencarian telah tumbuh ke seluruh RAM dan akan me-root rak tetangga di ruang server? Apa yang harus dilakukan dengan indeks lapar sumber daya terbalik? Haruskah saya terhubung dengan pengembangan Android jika pengguna menerima "Memori telepon penuh" dan aplikasi ini hanya setengah dari muatan wadah penting?

Secara umum, apakah mungkin untuk memampatkan struktur data sehingga memakan ruang yang jauh lebih sedikit, tetapi tidak kehilangan keunggulan yang melekat? Sehingga akses ke tabel hash tetap cepat, dan pohon seimbang mempertahankan propertinya. Ya kamu bisa! Untuk ini, arah ilmu komputer "struktur data ringkas" muncul, mengeksplorasi representasi kompak dari struktur data. Ini telah berkembang sejak akhir tahun 80-an dan saat ini sedang dalam puncaknya dalam kemuliaan data besar dan beban tinggi.

Sementara itu, akan ada pahlawan di Habr yang dapat berbicara kembali tiga kali berturut-turut
[səkˈsɪŋkt]?

Pintu menuju dunia kekompakan

Jadi, struktur data dianggap kompak (ringkas) jika:

• Ia menempati sejumlah bit yang dekat dengan batas informasi-teoretis.
• Itu tidak memerlukan pembongkaran awal untuk penggunaan penuh.

Ini berarti bahwa algoritma kompresi lossless tidak ada hubungannya dengan struktur data yang kompak. Bagaimanapun, mereka melibatkan mengembalikan data dari keadaan terkompresi untuk diproses.

Implementasi grafik, tabel hash, dan hal-hal lain yang “umum” juga tidak bagus. Ambil setidaknya petunjuk ke elemen anak di pohon pencarian. Mereka memakan tempat-tempat yang layak: $$$O (MN)$ dimana $$$M$ - panjang pointer, dan $$$N$ - jumlah node di pohon. Tetapi implementasi pohon ringkas memungkinkan kita untuk meningkatkan perilaku asimptotik $$$2N + o (N)$ yang dekat dengan batas bawah teoretis $$$2N - Θ (log N)$ untuk kayu dari $$$N$ node. Dengan panjang pointer $$$M = 8$ byte ini berarti pindah dari $$$O (8N)$ ke urutan asimtotik yang sama sekali berbeda - adil $$$2N$ , mengingat hal itu $$$o (N)$ - nilai yang dapat diabaikan relatif terhadap $$$N$ .

Struktur data ringkas (ringkas) adalah representasi terkompresi untuk vektor bit, multiset, grafik planar, dan struktur klasik favorit lainnya. Seringkali mereka statis, dibangun sekali dan tidak berubah saat digunakan. Ada pengecualian - struktur ringkas dengan operasi cepat untuk menambah dan menghapus elemen.

Sebagian besar struktur kompak didasarkan pada konsep kamus ringkas yang dapat diindeks. Ini adalah kasus khusus dari bitmap (bitmap, bitset). Bitmap itu sendiri sangat ideal untuk memeriksa apakah elemen-elemen berada dalam set tertentu. Jika suatu elemen dimasukkan dalam suatu himpunan, maka nilai bit pada indeks yang diberikan diatur ke 1, jika tidak, itu diatur ulang ke 0. Contoh penting adalah inode-bitmap ext4, UFS, dan sistem file Unix lainnya. Ini menyimpan data tentang entri mana dalam tabel inode yang sibuk dan mana yang gratis.

Kamus ringkas yang dapat diindeks adalah bitmap yang sama, tetapi dilengkapi oleh dua operasi: peringkat dan pilih. Operasi-operasi ini adalah gajah-gajah yang menjadi tumpuan dunia ringkas. Secara kasar, peringkat adalah hitungan jumlah elemen, dan pilih adalah pencarian elemen:

• $$$rank_x (i)$ mengembalikan jumlah bit yang sama dengan $$$x$ yang indeksnya terletak pada segmen $$$[0; i]$ . Sejak $$$x$ - nilai bit, maka itu bisa sama secara eksklusif dengan 0 atau 1.
• $$$select_x (j)$ indeks pengembalian $$$j$ sedikit sama dengan $$$x$ . Akal sehat mengatakan bahwa tidak ada kejadian nol, hanya ada yang pertama. Oleh karena itu$$ $ inline $ j> 0 $ inline $ : perhitungan dilakukan dari satu. Juga $$$j$ tidak dapat melebihi jumlah total bit dalam kamus yang sama dengan $$$x$ .

Misalkan kita memiliki kamus yang dapat diindeks di mana 4 dari 7 bit diatur. Lalu $$$rank_1$ dan $$$select_1$ akan mengambil nilai-nilai berikut:

Contoh kamus yang dapat diindeks dan perhitungan untuk itu $$$rank_1$ , $$$select_1$ .

Pembaca yang penuh perhatian akan melihat bahwa pilih adalah kebalikan dari peringkat. Jika $$$rank_1 (5) = 4$ lalu $$$select_1 (4) = 5$ .

Seseorang telah deja vu saat melihat $$$rank_1 (i)$ ? Dan semua karena operasi ini menggeneralisasikan Berat Hamming - jumlah karakter bukan nol dalam urutan. Untuk urutan biner, berat Hamming juga disebut popcount (jumlah populasi).

Peringkat / pilih juga berlaku untuk bit yang dibuang. Ini adalah contoh perhitungan $$$rank_0$ dan $$$select_0$ untuk bit sama dengan 0:

Contoh kamus ringkas yang dapat diindeks dan perhitungan untuk itu $$$rank_0$ , $$$select_0$ .

Melihat pohon menjadi bitik

Kami menggunakan pengetahuan ini untuk membangun pohon awalan yang ringkas! Pohon awalan baik untuk menemukan string dengan awalan. Dengan bantuan mereka, daftar drop-down petunjuk pencarian (sjest) sering diterapkan. Pendekatan untuk ringkas pohon awalan sangat digeneralisasi dan secara maksimal menunjukkan semua kismis struktur kompak. Tidak seperti pohon biner, rumus-rumus tertentu diturunkan yang mengganggu keseluruhan gambar.

Tiga metode representasi kompak pohon paling populer:

• BP (tanda kurung seimbang) - urutan tanda kurung seimbang.
• DFUDS (urutan tingkat unary kedalaman-pertama) - urutan node yang dikodekan unit diurutkan berdasarkan pencarian kedalaman.
• LOUDS (level-ordered unary degree sequences) - urutan node unit-encoded yang diurutkan berdasarkan level.

Apa rantai logis yang mencurigakan dari menerjemahkan "tingkat unary" ke "node single-encoded"? Baiklah kalau begitu. Derajat unary dalam nama-nama ini berarti cara pengkodean simpul pohon dengan urutan unit sesuai dengan jumlah simpul anak, selalu dengan nol di trailer.

Tiga metode mewakili pohon disatukan oleh kehadiran operasi cepat: menemukan orang tua; temukan keturunan pertama; temukan keturunan terakhir; Temukan node yang berdekatan kiri dan kanan. Kemungkinan mendasar dan efektivitas operasi lain berbeda dari metode ke metode.

Mari kita membahas metode LOUDS. Setelah memahaminya, tidak akan sulit untuk berurusan dengan dua lainnya. Selain itu, tahun lalu, pohon LOUDS merayakan ulang tahun ke 30 mereka! Operasi tambahan yang berguna untuk pohon LOUDS diimplementasikan di Indonesia $$$O (1)$ : temukan jumlah turunan dari simpul; menghitung angka turunan simpul di antara semua turunannya (turunan pertama, kedua, $$$i$ th, dll.); untuk menemukan $$$i$ anak mereka. Kerugian dari LOUDS adalah kurangnya algoritma yang efektif untuk menghitung jumlah node subtree.

Inti dari metode ini sederhana: menyimpan kunci node pohon dan semua informasi berharga dalam array biasa, dan mewakili struktur pohon sebagai urutan bit. Total kita memiliki dua struktur statis. Tetapi tidak perlu mengalokasikan memori untuk pointer ke simpul pohon: transisi di antara mereka diimplementasikan menggunakan rumus dengan penggunaan aktif peringkat / pilih.

Peringatan, pohon awalan:

Pohon awalan siap untuk kompresi menggunakan metode LOUDS.

Siapkan pohon untuk presentasi dalam bentuk biner:

1. Pasang pohon ke root palsu. Dia akan segera memainkan perannya.
2. Kami menomori semua node pohon, level demi level, dari kiri ke kanan, seperti pada BFS (pencarian luas pertama). Root palsu diabaikan, dan yang asli diindeks oleh nol.
3. Encode node. Node pohon dikodekan oleh urutan unit yang sesuai dengan keturunan langsung, ditambah nol. Jika simpul memiliki empat anak, maka itu dikodekan sebagai 11110, dan jika tidak ada - sebagai 0. Root palsu dikodekan terlebih dahulu. Ia memiliki satu keturunan, jadi kodenya adalah 10.

Pohon awalan dengan simpul bernomor. Node dikodekan.

Dalam proses level-by-level tree traversal, kamus ringkas yang dapat diindeks dibentuk - urutan bit dari node yang dikodekan yang direkatkan dari atas ke bawah dan dari kiri ke kanan. Kami memiliki urutan 21-bit. By the way, itu disebut LBS (LOUDS Bit String).

Kamus ringkas yang dapat diindeks untuk pohon awalan.

Pohon awalan LOUDS kompak dibangun. LBS untuk kayu dengan $$$N$ node (palsu tidak masuk hitungan) mengambil $$$2N + 1$ sedikit. Yang paling menarik tetap - formula untuk melintasi pohon berubah menjadi bitmap.

Cari anak pertama . Transisi dari sebuah simpul $$$i$ untuk simpul anak pertamanya dilakukan sesuai dengan rumus:

$$

$$firstChild (i) = select_0 (i + 1) - i$$

$$$i$ - ini adalah nomor simpul di lempeng sebelumnya yang ditempel dengan warna ungu.

Temukan keturunan pertama dari simpul dengan indeks 3 (huruf "a"):

$$

$$firsthild (3) = select_0 (3 + 1) - 3 = select_0 (4) - 3 = 9 - 3 = 6$$

Node anak pertama pada indeks 6, dan ini adalah huruf "k". Kami menerapkan rumus untuk akar pohon:

$$

$$firstChild (0) = select_0 (0 + 1) - 0 = select_0 (1) = 1$$

Kami menemukan selembar dengan indeks 1, huruf "dan". Berkonvergensi! Menjadi jelas mengapa root palsu diperlukan: untuk keajaiban pengindeksan node. Untuk menghindari kesalahan aneh sebelum pindah ke turunan node $$$i$ Akan menyenangkan untuk mengetahui jumlah keturunan ini. Memang, untuk dedaunan pohon, yang tidak mengejutkan, formulanya memberikan hasil yang tidak memadai. Untuk menemukan turunan berikutnya setelah yang pertama, Anda perlu menambahkan 1. Untuk indeksnya, ini logis, karena turunan satu simpul selalu berdekatan, tanpa celah. Tetapi ketika mengulanginya, Anda harus berhenti tepat waktu - menentukan keturunan mana yang dianggap sebagai yang terakhir.

Cari keturunan terakhir dari sebuah simpul $$$i$ melewati dalam dua tahap: menentukan indeks unit terakhir dalam kode node - itu yang menunjuk keturunan yang diberikan; dan kemudian menentukan indeks anak itu sendiri:

$$

$$lastChildPos (i) = select_0 (i + 2) -1$$

Setelah menerima indeks unit terakhir dalam kode node, perlu untuk memverifikasi bahwa bit pada indeks ini memang disetel. Jika tidak, maka kesimpulannya menunjukkan dirinya: ini adalah simpul tanpa keturunan, daun. Jika bit sudah diatur, maka lanjutkan lebih lanjut:

$$

$$lastChild (i) = rank_1 (lastChildPos (i) -1)$$

Temukan keturunan terakhir dari simpul 2 (huruf "k").

$$

$$lastChildPos (2) = select_0 (2 + 2) -1 = select_0 (4) -1 = 9-1 = $$$

Bit pada indeks 8 adalah 1, oleh karena itu, simpul 2 bukan daun, dan kita dapat menemukan indeks anak terakhir:

$$

$$lastChild (i) = rank_1 (8-1) = 5$$

Jumlah keturunan. Cara paling sederhana untuk menentukan jumlah turunan adalah dengan mengurangi indeks turunan pertama dari indeks turunan terakhir dari simpul dan menambahkan 1:

$$

$$childrenCount (i) = lasthild (i) - firsthild (i) + 1$$

Tapi misalkan simpulnya $$$i$ ada simpul tetangga $$$i + 1$ terletak di tingkat pohon yang sama dengan $$$i$ . Lalu jumlah keturunannya $$$i$ dapat didefinisikan sebagai perbedaan antara indeks keturunan pertama dari node $$$i + 1$ dan $$$i$ :

$$

$$childrenCount (i) = firsthild (i + 1) - firsthild (i)$$

Keturunan node juga diberi nomor urut. Jika keturunan pertama $$$i$ Apakah itu $$$j$ lalu yang kedua - $$$j + 1$ dan seterusnya ke turunan dari simpul yang bertetangga pada level ini $$$i + 1$ (jika ada).

Jumlah keturunan daun “dan” dengan indeks 1 diharapkan nol:

$$

$$childrenCount (1) = (select_0 (2 + 1) - 2) - (select_0 (1 + 1) - 1) = 3 - 3 = 0$$

Pencarian orang tua untuk sebuah simpul $$$i$ diorganisasikan oleh rumus:

$$

$$parent (i) = rank_0 (select_1 (i + 1) - 1) -1$$

Kami akan menggunakannya untuk mencari induk dari simpul 6 (huruf "k"):

$$

$$parent (6) = rank_0 (select_1 (7) - 1) -1 = rank_0 (9) -1 = 3$$

Ini adalah simpul 3, huruf "a".

Dengan pengetahuan tentang rumus untuk indeks anak dan orang tua, tidak sulit untuk berkeliling seluruh pohon. Hal utama adalah jangan lupa tentang pemrosesan syarat batas untuk akar dan daun.

Beberapa kopeck tentang metode BP dan DFUDS. Kedua metode memiliki asimptotik spasial - $$$2N + o (N)$ bit untuk kayu dari $$$N$ node, dan keduanya serupa dalam representasi simpul pohon dalam bentuk kurung buka dan tutup.

BP (tanda kurung seimbang) mengubah pohon menjadi urutan kurung, pasangan untuk setiap node. Untuk melakukan ini, pohonnya masuk ke dalam; setiap node dikunjungi dua kali. Pada kunjungan pertama, braket pembuka dicatat, pada kunjungan kedua - braket penutup. Di antara mereka ada tanda kurung anak-anak.

Lebih mudah untuk mewakili urutan kurung dalam bentuk bitmap, di mana 1 adalah braket pembuka dan 0 adalah braket penutup. Semua formula untuk bekerja dengan BP dipertajam untuk pencarian cepat. Tidak seperti LOUDS, BP memungkinkan Anda untuk dengan cepat menghitung ukuran subtree dan menentukan leluhur bersama terdekat dari dua node. Tapi temukan $$$i$ Keturunan-jauh lebih rumit daripada di LOUDS.

DFUDS (urutan tingkat unary kedalaman-pertama) mirip dengan BP dan LOUDS. Dengan BP, ia menggabungkan tree walk in depth dan representasi braketnya. Dan prinsip kurung sama dengan prinsip pengkodean node dalam LOUDS. Sebelum melintasi pohon, kami menambahkan satu tanda kurung pembuka ke urutan braket terlebih dahulu. Kemudian, ketika melintasi simpul, kita menulis tanda kurung sesuai dengan jumlah turunan, ditambah satu tanda kurung. Ternyata lokalitas menyimpan keturunan di DFUDS lebih tinggi dari BP. Perhitungan ukuran subtree dan pencarian leluhur bersama terdekat dilakukan untuk $$$O (1)$ . Tetapi menentukan ketinggian subtree dan menemukan orang tua pada $$$j$ level - operasi berat untuk DFUDS.

Untuk lebih jelasnya, kami membandingkan metode LOUDS, BP, dan DFUDS menggunakan mini-tree sebagai contoh.

Simpul pohon diberi nomor oranye seolah-olah berjalan dengan lebar (untuk LOUDS), biru - seperti saat berjalan di kedalaman (untuk BP dan DFUDS).

Tampilan pohon LOUDS, BP, dan DFUDS.

Jangan kaget jika Anda melihat perbedaan formula dalam karya berbahasa Inggris. Di antara matematikawan, ada pecinta pengindeksan mulai dari satu. Dan beberapa pengembang menganggap kata peringkat dan konsonan rentang, sehingga mereka membuat peringkat separuh waktu. $$$[0; i)$ . Karena kebutuhan untuk mempertahankan simetri peringkat / pilih, mereka menghitung $$$pilih (i)$ bagaimana $$$pilih (i + 1)$ . Tetapi beberapa rumus dalam bentuk ini terlihat lebih pendek.

Array jarang: kocok tapi jangan campur

Jarang array adalah struktur lain yang secara harfiah dibuat untuk kompresi. Ukuran array semacam itu terkadang order besarnya lebih besar dari jumlah elemen yang diisi. Dan elemen kosong mengambil nilai default atau ditandai dengan sesuatu seperti nol. Array jarang muncul di cakrawala kapan pun diperlukan untuk menyimpan banyak objek dan hubungan di antara mereka. Grafik teman di jejaring sosial, algoritma peringkat mesin pencari, tabel mirip Excel, simulator rangkaian listrik dengan milyaran transistor dalam sebuah chip segera terlintas dalam pikiran.

Seringkali array seperti itu bersifat cyclopean dalam gaya Lovecraftian, dengan implementasi naif mereka tidak cocok dengan RAM, tetap hampir kosong. Bergantung pada persyaratan memori dan kecepatan, array jarang berubah menjadi tabel hash yang jauh lebih ringkas, daftar adjacency, pohon biner ... atau ringkas.

Katakanlah kita memiliki serangkaian string yang jarang. Lampirkan kamus ringkas yang bisa diindeks. Apa yang akan diberikannya?

Array jarang dengan bitmap.

Sekarang, tanpa mengakses array asli secara langsung, mudah untuk memeriksa apakah ada elemen di dalamnya pada indeks yang diinginkan. Tidak ada yang mencegah menyusutnya array asli dengan membuang semua elemen yang tidak terisi:

Array tanpa elemen kosong.

Menghitung indeks dalam array terkompresi. Setelah memeriksa keberadaan elemen, alangkah baiknya untuk mengakses nilainya dalam array asli, mis. Memetakan indeks $$$i$ dalam indeks kamus yang diindeks $$$j$ dalam array terkompresi. Tidak mengherankan bahwa peringkat digunakan untuk ini:

$$

$$j = rank_1 (i) -1$$

Mari kita periksa bagaimana semuanya dengan elemen ke-8: $$$bitmap [8] = 0$ . Jadi, dalam array asli tidak ada elemen seperti itu. Bagaimana dengan elemen 7? $$$bitmap [7] = 1$ . Dapatkan nilainya: $$$rank_1 (7) - 1 = 3-1 = 2$ . Pada indeks 2 adalah "pergi".

Perhitungan indeks dalam array sumber. Tentunya dalam array Anda perlu mencari elemen berdasarkan nilai! Jika data tidak diurutkan, pencarian dikurangi menjadi pencarian $$$O (N)$ dimana $$$N$ - jumlah elemen yang tidak kosong. Untuk barang yang ditemukan $$$j$ mungkin perlu mendapatkan indeksnya $$$i$ seolah-olah array tidak menyusut. Untuk melakukan ini, gunakan pilih, kebalikan dari peringkat:

$$

$$i = select_1 (j +1)$$

Misalnya, cari baris "C ++". Dalam array kompak, ini terletak di indeks 0. Dan indeksnya di array asli adalah $$$select_1 (0 +1) = 3$ .

Sudah pada contoh dengan garis penghematan memori yang nyata. Jika array dirancang untuk menyimpan kelas dengan banyak bidang, penghematan menjadi jauh lebih signifikan. Selain itu, pencarian dalam array yang kompak lebih cepat daripada yang besar dan jarang: lebih baik di-cache oleh prosesor. Kamus yang diindeks bit lebih cenderung masuk ke dalam baris cache daripada array angka, string, atau tipe kustom yang bagus.

Tentu untuk penyimpanan $$$2 ^ {30}$ metode elemen yang dijelaskan tidak cocok. Penerapannya berakhir di mana masalah dengan pertumbuhan indeks dimulai. Tapi tentu saja, metode ini mengompresi array dan variasinya memiliki ceruk tersendiri. Contoh sehari-hari adalah implementasi protokol BitTorrent. Bitmap berisi informasi tentang segmen file yang diunduh, dan rekan-rekan bertukar indeks segmen mereka. Contoh ruang adalah opsi transmisi data tersegmentasi yang digunakan oleh rover, Voyagers dan stasiun New Horizons, membajak ruang terbuka trans-Neptunus.

Contoh yang dijelaskan tentang ringkasnya pohon awalan dan array jarang dibangun di atas dasar yang sama. Ini didasarkan pada keyakinan yang tak tergoyahkan pada efektivitas operasi peringkat / pilih. Tanpa itu, seluruh teori struktur yang kompak namun cukup cepat meledak di jahitannya. Kecukupan menggunakan struktur kompak di luar disertasi tergantung pada peringkat dan kecepatan pilih.

Bahkan, operasi ini dapat diimplementasikan dengan sangat efisien: peringkat - untuk $$$O (1)$ ; pilih - untuk $$$O (log (log N))$ , yang juga hampir konstan. Dan tentu saja, ini bukan tanpa beberapa trik. Dan karena harus ada sedikit pernyataan dalam pekerjaan dengan plot yang rumit, saya akan berhenti di sini.

Fakta menarik

Apa batas bawah teoritis sumber daya yang diduduki dalam hal teori informasi? Katakanlah struktur data menyimpan banyak $$$N$ elemen. Untuk mengidentifikasi mereka tanpa tabrakan, Anda memerlukan sejumlah bit, tidak kurang dari $$$X = log_2N$ . $$$X$ dan ada batas bawah yang ditentukan oleh rumus Hartley. Dalam beberapa kasus khusus, memiliki informasi tentang sifat data yang disimpan, struktur dapat dikompresi lebih efisien.

Apakah string ringkas merupakan struktur data? Itu berisi $$$N$ karakter dan berakhir dengan karakter ASCII nol. Jadi itu perlu $$$N + 1$ tempat, dan karena itu ... dia ringkas, dan lebih khusus, implisit! Yang membawa kita ke pertanyaan selanjutnya.

Apakah semua struktur ringkas sama kompaknya? Area penelitian ringkas mendefinisikan sebanyak tiga jenis struktur kompak yang berbeda dalam kompleksitas spasial:

• padat - $$$O (N)$ . Kompleksitas linear dari $$$N$ — . «» . . , : . , . , 0 , . $$$O(2N)$ ( 2 , ) select .
• succinct — $$$N + o(N)$ . — , succinct data structures . : (Pascal string), . $$$N + log(N)$ .
• implicit — $$$N + O(1)$ . , . : (heap) . $$$N + 1$ .

? , , . succinct- . , -, FM-, RMQ (range minimum queries), LCP (longest common prefix), , succinct'. -.

Epilog

, , . Dan tidak hanya itu. , , X, .

succinct — , «- ». Succinct — . , , succinct. , . (IME) Google, . MAPS.ME succinct- .

, . ., 97 % -: . 3 %.

Apa selanjutnya

, succinct:

• rank/select Bitmagic Library.
• , succinct. .
• MIT, succinct.
• , 18 .
• , succinct.
• RRR — .

, :

• Proyek Perpustakaan Struktur Data Singkat di C ++.
• Proyek BitMagic di C ++.
• Paket dengan implementasi ringkas Elias-Fano di Python.
• Implementasi beberapa struktur ringkas di Rust.