A Faster Grammar-Based Self-Index

Details A Faster Grammar-Based Self-Index A Faster Grammar-Based Self-Index

2011-09-19

arxiv.org/abs/1109.3954v3

Computer Science

Data Structures and Algorithms

Accepted to LATA '12

Scientific paper

To store and search genomic databases efficiently, researchers have recently started building compressed self-indexes based on straight-line programs and LZ77. In this paper we show how, given a balanced straight-line program for a string (S [1..n]) whose LZ77 parse consists of $z$ phrases, we can add $\Oh{z \log \log z}$ words and obtain a compressed self-index for $S$ such that, given a pattern (P [1..m]), we can list the $\occ$ occurrences of $P$ in $S$ in $\Oh{m^2 + (m + \occ) \log \log n}$ time. All previous self-indexes are either larger or slower in the worst case.

Affiliated with

Also associated with

No associations

Rating

A Faster Grammar-Based Self-Index does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Faster Grammar-Based Self-Index, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Faster Grammar-Based Self-Index will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-96325