Edit and Alphabet-Ordering Sensitivity of Lex-parse
We investigate the compression sensitivity [Akagi et al., 2023] of lex-parse [Navarro et al., 2021] for two operations: (1) single character edit and (2) modification of the alphabet ordering, and give tight upper and lower bounds for both operations. For both lower bounds, we use the family of Fibo...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.19223 http://arxiv.org/abs/2402.19223 |
| Tags: |
No Tags, Be the first to tag this record!
|
Similar Items: Edit and Alphabet-Ordering Sensitivity of Lex-parse
- Computing longest palindromic substring after single-character or block-wise edits
- Optimal LZ-End Parsing is Hard
- Computing maximal palindromes in non-standard matching models
- Detecting $k$-(Sub-)Cadences and Equidistant Subsequence Occurrences
- Tight bounds for the sensitivity of CDAWGs with left-end edits
- Grammar Index By Induced Suffix Sorting