A Searchable Compressed Edit-Sensitive Parsing

Details A Searchable Compressed Edit-Sensitive Parsing A Searchable Compressed Edit-Sensitive Parsing

2010-12-30

arxiv.org/abs/1101.0080v3

Computer Science

Data Structures and Algorithms

16 pages, 14 figures

Scientific paper

Practical data structures for the edit-sensitive parsing (ESP) are proposed. Given a string S, its ESP tree is equivalent to a context-free grammar G generating just S, which is represented by a DAG. Using the succinct data structures for trees and permutations, G is decomposed to two LOUDS bit strings and single array in (1+\epsilon)n\log n+4n+o(n) bits for any 0<\epsilon <1 and the number n of variables in G. The time to count occurrences of P in S is in O(\frac{1}{\epsilon}(m\log n+occ_c(\log m\log u)), whereas m = |P|, u = |S|, and occ_c is the number of occurrences of a maximal common subtree in ESPs of P and S. The efficiency of the proposed index is evaluated by the experiments conducted on several benchmarks complying with the other compressed indexes.

Affiliated with

Also associated with

No associations

Rating

A Searchable Compressed Edit-Sensitive Parsing 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 Searchable Compressed Edit-Sensitive Parsing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Searchable Compressed Edit-Sensitive Parsing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-400850