Kompresovane strukture podataka

Termin komprimovane struktura podataka nastaje u informatici i podoblastima algoritama , strukturama podataka , kao i teorijske informatike. On se odnosi na strukturu podataka čije su operacije otprilike brzo kao one konvencionalne strukture podataka, ali čija veličina može biti znatno manja. Veličina kompresovanog strukture podataka je obično veoma zavisi od veličine podataka koje treba da budu predstavljene.

Važni primeri komprimovanih struktura podataka uključuje komprimovani sufiks niza^[1]^[2] i FM - indeks^[3] , od kojih oba mogu predstavljati proizvoljni tekst znakova T za Pretragu Šablonom. Za svaki ulaz obrasca P , oni podržavaju operaciju pronalaženja ako i gde se P pojavljuje u T. Vreme pretrage je proporcionalan zbiru dužine obrazac P , veoma sporo - rastući funkciji dužine teksta T , i broj pronađenih podudaranja. Prostor koji zauzimaju je otprilike jednak veličini teksta T u komprimovanom obliku , kao što je to dobijeno predviđanjem Pretrage šablonom ili G-zip. Štaviše , oba strukture podataka su samo-indeksirajuće , u tako da se može rekonstruisati tekst T na uzimajući tekst nasumično , i tako da osnovni tekst može biti odbačen. Drugim rečima , oni istovremeno pružaju komprimovanje i brzo pretraživanje teksta. Oni predstavljaju značajan memorijski napredak u odnosu na konvencionalne metode sufiksom stabla i sufiks niza , koji zauzimaju mnogo više prostora od veličine T. Oni su takođe podržavaju pretragu za proizvoljne obrasce , za razliku od obrnutog indeksiranja , koji može da podrži samo pretrage zasvnovane na reči. Pored toga , obrnuti indeksi nemaju funkciju samo-indeksiranja .

Važno u vezi ovog jeste da sažete strukture podataka, koje koristi prostor otprilike jednak informacionom-teoretski minimum , što je najgori slučaj memorije potrebne za predstavljanje podataka. Nasuprot tome,veličina kompresovanog strukture podataka zavisi od tipa podataka koji su predstavljeni. Kada se podaci mogu kompresovati, kao što je često slučaj u praksi za tekst ,komprimovane strukture podataka mogu zauzeti memorju veoma blizu teorijskog minimuma , i znatno manje prostora nego većina algoritama kompresije .

Reference uredi

^ R. Grossi and J. S. Vitter, Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching], Proceedings of the 32nd ACM Symposium on Theory of Computing, May 2000, 397-406. Journal version in SIAM Journal on Computing, 35(2), 2005, 378-407.
^ R. Grossi, A. Gupta, and J. S. Vitter, High-Order Entropy-Compressed Text Indexes, Proceedings of the 14th Annual SIAM/ACM Symposium on Discrete Algorithms, January 2003, 841-850.
^ P. Ferragina and G. Manzini, Opportunistic Data Structures with Applications, Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, November 2000, 390-398. Journal version in Indexing Compressed Text, Journal of the ACM, 52(4), 2005, 552-581.

[1] R. Grossi and J. S. Vitter, Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching], Proceedings of the 32nd ACM Symposium on Theory of Computing, May 2000, 397-406. Journal version in SIAM Journal on Computing, 35(2), 2005, 378-407.

[2] R. Grossi, A. Gupta, and J. S. Vitter, High-Order Entropy-Compressed Text Indexes, Proceedings of the 14th Annual SIAM/ACM Symposium on Discrete Algorithms, January 2003, 841-850.

[3] P. Ferragina and G. Manzini, Opportunistic Data Structures with Applications, Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, November 2000, 390-398. Journal version in Indexing Compressed Text, Journal of the ACM, 52(4), 2005, 552-581.

[1]

[2]

[3]