Компресоване структуре података

Из Википедије, слободне енциклопедије

Термин компримоване структура података настаје у информатици и подобластима алгоритама , структурама података , као и теоријске информатике . Он се односи на структуру података чије су операције отприлике брзо као оне конвенционалне структуре података, али чија величина може бити знатно мања. Величина компресованог структуре података је обично веома зависи од величине података које треба да буду представљене.

Важни примери компримованих структура података укључује компримовани суфикс низа[1][2] и ФМ - индекс[3] , од којих оба могу представљати произвољни текст знакова Т за Претрагу Шаблоном . За сваки улаз обрасца П , они подржавају операцију проналажења ако и где се П појављује у Т. Време претраге је пропорционалан збиру дужине образац П , веома споро - растући функцији дужине текста Т , и број пронађених подударања . Простор који заузимају је отприлике једнак величини текста Т у компримованом облику , као што је то добијено предвиђањем Претраге шаблоном или Г-зип. Штавише , оба структуре података су само-индексирајуће , у тако да се може реконструисати текст Т на узимајући текст насумично , и тако да основни текст може бити одбачен . Другим речима , они истовремено пружају компримовање и брзо претраживање текста. Они представљају значајан меморијски напредак у односу на конвенционалне методе суфиксом стабла и суфикс низа , који заузимају много више простора од величине Т. Они су такође подржавају претрагу за произвољне обрасце , за разлику од обрнутог индексирања , који може да подржи само претраге засвноване на речи . Поред тога , обрнути индекси немају функцију само-индексирања .

Важно у вези овог јесте да сажете структуре података, које користи простор отприлике једнак информационом-теоретски минимум , што је најгори случај меморије потребне за представљање података . Насупрот томе,величина компресованог структуре података зависи од типа података који су представљени . Када се подаци могу компресовати, као што је често случај у пракси за текст ,компримоване структуре података могу заузети меморју веома близу теоријског минимума , и знатно мање простора него већина алгоритама компресије .



Референце[уреди]

  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.