Rank/Select Operations on Large Alphabets: a Tool for Text Indexing

被引：109

作者：

Golynski, Alexander ^{[1
]}

Munro, J. Ian ^{[1
]}

Rao, S. Srinivasa ^{[1
]}

机构：

[1] Univ Waterloo, Sch Comp Sci, Waterloo, ON N2L 3G1, Canada

来源：

PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS | 2006年

关键词：

D O I：

10.1145/1109557.1109599

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider a generalization of the problem of supporting rank and select queries on binary strings. Given a string of length n from an alphabet of size sigma, we give the first representation that supports rank and access operations in O(lg lg sigma) time, and select in O(1) time while using the optimal n lg sigma + o(n lg o) bits. The best known previous structure for this problem required O(lg sigma) time, for general values of sigma. Our results immediately improve the search times of a variety of text indexing methods.

引用

页码：368 / 373

页数：6

共 14 条

[1]

Clark DR, 1996, PROCEEDINGS OF THE SEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P383

[2]

Ferragina P, 2004, LECT NOTES COMPUT SC, V3246, P150

[3] Opportunistic data structures with applications [J].

Ferragina, P ;

Manzini, G .

41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2000, :390-398

[4]

FERRAGINA P, 2004, TRDCC20045 U CHIL

[5]

FERRAGINA P, 2005, P 46 ANN IEEE S FDN

[6]

Grossi R, 2003, SIAM PROC S, P841

[7]

GROSSI R, 2006, P 17 ANN ACM SIAM S

[8] SPACE-EFFICIENT STATIC TREES AND GRAPHS [J].

JACOBSON, G .

30TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 1989, :549-554

[9]

MAKINEN V., 2004, C200420 U HELS DEP C

[10]

Munro JI, 2003, LECT NOTES COMPUT SC, V2719, P345

← 1 2 →