A Searchable Compressed Edit-Sensitive Parsing
Naoya Kishiue, Masaya Nakahara, Shirou Maruyama, Hiroshi Sakamoto · arXiv (Cornell University) · 2010
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+ε)n\log n+4n+o(n) bits for any 0