Pregled bibliografske jedinice broj: 719822
Using static suffix array in dynamic application: Case of text compression by longest first substitution
Using static suffix array in dynamic application: Case of text compression by longest first substitution // Information processing letters, 115 (2015), 2; 175-181 doi:10.1016/j.ipl.2014.08.014 (međunarodna recenzija, članak, znanstveni)
CROSBI ID: 719822 Za ispravke kontaktirajte CROSBI podršku putem web obrasca
Naslov
Using static suffix array in dynamic application: Case of text compression by longest first substitution
Autori
Ristov, Strahil ; Korenčić, Damir
Izvornik
Information processing letters (0020-0190) 115
(2015), 2;
175-181
Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni
Ključne riječi
Algorithms; Enhanced suffix array; Grammar text compression; Longest first substitution; Text index update
Sažetak
Over the last decade, enhanced suffix arrays (ESA) have replaced suffix trees in many applications. Algorithms based on ESAs require less space, while allowing the same time efficiency as those based on suffix trees. However, this is only true when a suffix structure is used as a static index. Suffix trees can be updated faster than suffix arrays, which is a clear advantage in applications that require dynamic indexing. We show that for some dynamic applications a suffix array and the derived LCP-interval tree can be used in such a way that the actual index updates are not necessary. We demonstrate this in the case of grammar text compression with longest first substitution and provide the source code. The proposed algorithm has O(N2) worst case time complexity but runs in O(N) time in practice.
Izvorni jezik
Engleski
Znanstvena područja
Računarstvo
POVEZANOST RADA
Ustanove:
Institut "Ruđer Bošković", Zagreb
Citiraj ovu publikaciju:
Časopis indeksira:
- Current Contents Connect (CCC)
- Web of Science Core Collection (WoSCC)
- Science Citation Index Expanded (SCI-EXP)
- SCI-EXP, SSCI i/ili A&HCI
- Scopus
