Suffix Array for Large Alphabet

Abstract

Burrows-Wheelerova Transformace (BWT) [3] je používána jako hlavní část blokové komprese, která má dobrý kompresní poměr a přijatelný čas běhu. Suffixová pole jsou používána v kódovací fázi BWT a my se soustředíme na jejich tvorbu pro abecedu větší než 2^8 symbolů. Motivací pro tuhle práci byl softwarový projekt XBW [4] - aplikace pro kompresi velkých XML souborů. Úkolem BWT je přeuspořádat vstup před použitím jiných algoritmů. Popisujeme a implementujeme tři skupiny algoritmů pro kódování. První je inspirována prací Sadakana [10] a dále vylepšená Larssonem [8]. Druhá skupina obsahuje algoritmus od Sewarda [11] a algoritmus od Itoha vylepšený Kaoem [5]. Závěrem prezentujeme algoritmus od Kärkkäinena a Sanderse [6] pro konstrukci suffixových polí v lineárním čase. Jako hlavní výsledek ukážeme, že pro textová data použití slabik nebo slov jako abecedy zlepšuje čas běhu i kompresní poměr.

Burrows-Wheeler Transform (BWT) [3] is used as the major part in block compression which has good balance of speed and compression ratio. Suffix arrays are used in the coding phase of BWT and we focus on creating them for alphabet larger than 2^8 symbols. The motivation for this work has been software project XBW[4] - an application for compression of large XML files. The role of BWT is to reorder input before applying other algorithms. We describe and implement three families of algorithms for encoding. First is inspired by the work of Sadakane [10] and further improved by Larsson [8]. Second family includes algorithm by Seward [11] and algorithm by Itoh further improved by Kao [5]. Finally we present algorithm by Kärkkäinen and Sanders [6] for constructing suffix arrays in linear time.