Компримовани суфикс низа

У рачунарству, компримовани суфикс низа (енгл. Compressed suffix array) је компримована структура података за проналажење модела. Имајући у виду текст T од n карактера из Σ азбуке, компримовани суфикс низа подржава тражење произвољних образаца у Т. За улаз обрасца P од m карактера, време за тражење је једнако до n пута вишег реда ентропије текста Т , плус неки додатни делови бита за складиштење емпиријског статистичког модела и О(n).

Оригинални пример компримованог суфикса низа решавао је дугогодишњи отворени проблем показујући да је брзо проналажење модела било могуће коришћењем само линеарно-просторне структуре података, наиме, пропорционално са величином текста Т, које заузима $O(n\,{\log |\Sigma |})$ бита. Конвенционални суфикс низа и суфикс дрво користе $\Omega (n\,{\log n})$ бита, што је знатно веће. Основа за структуру података је рекурзивно распадање користећи "комшијску функцију", која омогућава да се суфикс низа представља једном половином његове дужине. Конструкција се понавља више пута док резултујући суфикс низа не користи линеарни број битова. Следећи рад је показао да је стварни простор за складиштење био везан за нулти ред ентропије и да индекс подржава само-индексирање.. Заузимање меморије је додатно побољшано што је довело до постизања крајњег циља - вишег реда ентропије. Компресија се постиже поделом комшијске функције контекстима вишег реда, и збијање сваке партиције са таласастим стаблом. Коришћење простора је изузетно конкурентно у пракси са другим компресорима, а такође подржава брзо проналажење модела.

Приступи меморији, створени од стране компримованог суфикса низова и других компримованих структура података за проналажење модела, углавном нису локализовани, па према томе ове структуре података су биле изузетно тешко ефикасно дизајниране за употребу у екстерној меморији. Недавни напредак помоћу геометријског дуалитета користи предности блокирања приступа који обезбеђују дискови да значајно убрза I/O време.