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

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

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

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