.png){kind=icon}
返回
Relative Compressed Reverse Suffix Array
.png){kind=icon}
PRE
AI
DOI：10.4230/LIPIcs.STACS.2026.62.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
后缀树和后缀数组是字符串算法领域的两种基本数据结构。对于一个长度为n、基于大小为sigma的字母表的字符串（又称文本或序列），这些结构通常需要O(n log n)位空间。FM-索引提供了近似于n log sigma位的后缀数组压缩表示，允许在近对数时间内高效查询后缀数组及其逆数组。在某些应用中，如近似模式匹配（即包含通配符、错配、编辑），需要访问文本的后缀数组以及文本的逆后缀数组。受此启发，我们在假设原始文本的FM-索引可用的情况下，探索以紧凑形式编码逆文本后缀数组的可能性。我们的第一种解决方案是对逆文本后缀数组进行O(n)位（相对）编码，其中解码一个条目的时间仅为使用FM-索引解码文本后缀数组条目的O(log* n)倍。然后，我们演示如何将空间减少到O(n/kappa)位，而时间乘数因子变为约O(kappa log* n + kappa(3))。我们还可以支持逆后缀数组和最长公共扩展查询在逆文本上进行。这些结果通过一些细致且非平凡的简洁数据结构技术实现。
Keyword:
String Matching
Text Indexing
Data Structures
Suffix Trees
期刊
机构
查看更多机构
引用论文
暂无论文信息