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

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

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

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

Референце

1. R. Grossi and J. S. Vitter, Compressed Suffix Arrays and Suffix Trees, with Applications to Text Indexing and String Matching, SIAM Journal on Computing, 35(2), 2005, 378-407. An earlier version appeared in Proceedings of the 32nd ACM Symposium on Theory of Computing, May 2000, 397-406.
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. K. Sadakane, Compressed Text Databases with Efficient Query Algorithms Based on the Compressed Suffix Arrays, Proceedings of the International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, vol. 1969, Springer, December 2000, 410-421.
4. L. Foschini, R. Grossi, A. Gupta, and J. S. Vitter, Indexing Equals Compression: Experiments on Suffix Arrays and Trees, ACM Transactions on Algorithms, 2(4), 2006, 611-639.
5. W.-K. Hon, R. Shah, S. V. Thankachan, and J. S. Vitter, On Entropy-Compressed Text Indexing in External Memory, Proceedings of the Conference on String Processing and Information Retrieval, August 2009.