Linear time construction of compressed text indices in compact space

被引：27

作者：

Belazzougui, Djamal ^{[1
]}

机构：

[1] Univ Helsinki, Dept Comp Sci, HIIT, Helsinki, Finland

来源：

STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING | 2014年

基金：

芬兰科学院;

关键词：

Text indexing; Pattern matching; Succinct space; SUFFIX ARRAYS; RETRIEVAL; REPRESENTATIONS; TREES;

D O I：

10.1145/2591796.2591885

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that the compressed suffix array and the compressed suffix tree for a string of length n over an integer alphabet of size a < n can both be built in 0(n) (randomized) time using only 0(n log o-) bits of working space. The previously fastest construction algorithms that used 0 (n log a) bits of space took times 0(n log logo-) and 0(n log' n) respectively (where E is any positive constant smaller than 1).

引用

页码：184 / 193

页数：10

共 43 条

[1]

Apostolico A., 1985, Combinatorial Algorithms on Words, P85

[2] Alphabet-Independent Compressed Text Indexing [J].

Belazzougui, Djamal ;

Navarro, Gonzalo .

ACM TRANSACTIONS ON ALGORITHMS, 2014, 10 (04)

[3]

Belazzougui D, 2013, LECT NOTES COMPUT SC, V8125, P133, DOI 10.1007/978-3-642-40450-4_12

[4] Improved compressed indexes for full-text document retrieval [J].

Belazzougui, Djamal ;

Navarro, Gonzalo ;

Valenzuela, Daniel .

JOURNAL OF DISCRETE ALGORITHMS, 2013, 18 :3-13

[5]

Belazzougui D, 2009, PROCEEDINGS OF THE TWENTIETH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P785

[6]

Belazzougui Djamal, 2014, ABS14010936 CORR

[7]

BELLER T, 2012, SPIRE, V7608, P99

[8] Computing the longest common prefix array based on the Burrows-Wheeler transform [J].

Beller, Timo ;

Gog, Simon ;

Ohlebusch, Enno ;

Schnattinger, Thomas .

JOURNAL OF DISCRETE ALGORITHMS, 2013, 18 :22-31

[9]

Beller T, 2011, LECT NOTES COMPUT SC, V7024, P197, DOI 10.1007/978-3-642-24583-1_20

[10]

Clark D., 1996, THESIS

← 1 2 3 4 5 →