压缩LCE数据结构：重组技术提升效率
107 浏览量
更新于2024-08-25
收藏 519KB PDF 举报
"Longest Common Extension with Recompression" 是一篇发表于 2016 年 11 月 16 日的计算机科学论文，由 Tomohiro I 作者来自日本九州大学科技学院。该研究专注于解决字符串处理中的一个重要问题：在给定字符串 T 的两个位置 i 和 j 时，如何快速查找以这两个位置结尾的后缀之间的最长公共前缀（Longest Common Extension, LCE）长度。在文本处理中，LCE 查询是一个常见的需求，特别是在数据压缩和生物信息学等场景下，高效的数据结构对于性能至关重要。
传统上，LCE 数据结构用于存储字符串 T 的压缩形式，以支持快速查询。然而，该论文提出了一个创新的方法，即“重新压缩”技术，它被证明对压缩 LCE 数据结构非常有用。这种技术允许构建一个新型的压缩 LCE 数据结构，其空间复杂度优化到了 O(zlg(N/z))，其中 z 是字符串 T 的Lempel-Ziv 77 分解（一种自包含因子分解算法）的大小，不包括自我引用部分。这意味着数据结构能够有效地利用压缩的信息，降低存储需求。
论文的核心贡献在于设计了一个能够在 O(lgN) 时间内执行 LCE 查询的数据结构。这与传统的线性时间复杂度相比，有了显著提升，尤其是在处理大规模数据时。此外，作者还提供了两种构建方法：
1. 当字符串 T 以未压缩的形式存在时，他们展示了如何在 O(N) 的时间复杂度和空间复杂度内构建这个数据结构。
2. 当 T 是通过语法压缩，即使用一个生成 T 的大小为 n 的直译程序表示时，构建过程可以在 O(nlg(N/n)) 的时间复杂度和 O(n+zlg(N/z)) 的空间复杂度内完成。
值得注意的是，这些算法是确定性的，确保始终返回正确的 LCE 长度结果。这篇论文提供了一种高效且适用于各种压缩格式的 LCE 数据结构解决方案，对于那些需要频繁处理大量文本数据的应用来说，具有重要的实际价值。通过结合压缩技术和高效的查询算法，作者推动了这一领域的发展，提升了计算效率和存储效率。
Technically, this work owes very much to two papers [
9
,
8
]. For instance, our construction algorithm
of Theorem 1 is essentially the same as the grammar compression algorithm based on recompression
presented in [
9
]. Our contribution is in discovering the above mentioned property that can be used for
fast LCE queries. Also, we use the property to upper bound the size of our data structure in terms of
z
rather than the smallest grammar size
g
∗
. Since it is known that
z ≤ g
∗
holds, an upper bound in
terms of
z
is preferable. Our construction algorithm of Theorem 2 owes to [
8
], in which the recompression
technique solves the fully-compressed pattern matching problems. Basically our results can be obtained
by applying the technique. However, we make some contributions on top of it: We give a new observation
that simplifies the implementation and analysis of a component of recompression called
BComp
(see
Section 4.1.2). Also, we show that we can improve the time complexity from
O
(
n lg N
) to
O
(
n lg
(
N /n
)).
2 Preliminaries
An alphabet Σ is a set of characters. A string over Σ is an element in Σ
∗
. For any string
w ∈
Σ
∗
,
|w|
denotes the length of
w
. Let
ε
be the empty string, i.e.,
|ε|
= 0. Let Σ
+
= Σ
∗
\ {ε}
. For any
1
≤ i ≤ |w|
,
w
[
i
] denotes the
i
-th character of
w
. For any 1
≤ i ≤ j ≤ |w|
,
w
[
i..j
] denotes the substring of
w
beginning at
i
and ending at
j
. For convenience, let
w
[
i..j
] =
ε
if
i > j
. For any 0
≤ i ≤ |w|
,
w
[1
..i
]
(resp.
w
[
|w| − i
+ 1
..|w|
]) is called the prefix (resp. suffix) of
w
of length
i
. We say taht a string
x
occurs
at position
i
in
w
iff
w
[
i..|x| −
1] =
x
. A substring
w
[
i..j
] =
c
d
(
c ∈
Σ
, d ≥
1) of
w
is called a block iff it is
a maximal run of a single character, i.e., w[i − 1] 6= c and w[j + 1] 6= c.
The text on which LCE queries are performed is denoted by T
∈
Σ
∗
with
N
=
|
T
|
throughout this
paper. We assume that Σ is an integer alphabet [1
..N
O(1)
] and the standard word RAM model with word
size Ω(lg N).
The size of our compressed LCE data structure is bounded by
O
(
z lg
(
N /z
)), where
z
is the size of the
LZ77 factorization of T defined as follows:
Definition 4
(LZ77 factorization)
.
The factorization T =
f
1
f
2
· · · f
z
is the LZ77 factorization of T iff
the following condition holds: For any 1
≤ i ≤ z
, let
p
i
=
|f
1
f
2
· · · f
i−1
|
+ 1, then
f
i
= T[
p
i
] if T[
p
i
] does
not appear in T[1..p
i
− 1], otherwise f
i
is the longest prefix of T[p
i
..N] that occurs in T[1..p
i
− 1].
Example 5. The LZ77 factorization of abaabaabb is a · b · a · aba · ab · b and z = 6.
In this article, we deal with grammar compressed strings, in which a string is represented by a Context
Free Grammar (CFG) generating the string only. In particular, we consider Straight-Line Programs
(SLPs) that are CFGs in Chomsky normal form. Formally, an SLP that generates a string T is a triple
S
= (Σ
, V, D
), where Σ is the set of characters (terminals),
V
is the set of variables (non-terminals),
D
is the set of deterministic production rules whose righthand sides are in
V
2
∪
Σ, and the last variable
derives T.
3
Let
n
=
|V|
. We treat variables as integers in [1
..n
] (which should be distinguishable from Σ
by having extra one bit), and
D
as an injective function that maps a variable to its righthand side. We
assume that given any variable
X
we can access in
O
(1) time to the data space storing the information of
X
, e.g.,
D
(
X
). We refer to
n
as the size of
S
since
S
can be encoded in
O
(
n
) space. Note that
N
can be
as large as 2
n−1
, and so, SLPs have a potential to achieve exponential compression.
We extend SLPs by allowing run-length encoded rules whose righthand sides are of the form
X
d
with
X ∈ V and d ≥ 2, and call such CFGs run-length SLPs (RLSLPs). Since a run-length encoded rule can
be stored in O(1) space, we still define the size of an RLSLP by the number of variables.
Let us consider the derivation tree
T
of an RLSLP
S
that generates a string T, where we delete all
the nodes labeled with terminals for simplicity. That is, every node in
T
is labeled with a variable. The
height of
S
is the height of
T
. We say that a sequence
C
=
v
1
· · · v
m
of nodes is a chain iff the nodes are
all adjacent in this order, i.e., the beginning position of
v
i+1
is the ending position of
v
i
plus one for any
1 ≤ i < m. C is labeled with the sequence of labels of v
1
· · · v
m
.
For any sequence
p ∈ V
∗
of variables, let
val
S
(
p
) denote the string obtained by concatenating the
strings derived from all variables in the sequence. We omit
S
when it is clear from context. We say that
p
generates
val
(
p
). Also, we say that
p
occurs at position
i
iff there is a chain that is labeled with
p
and
begins at i.
The next lemma, which is somewhat standard for SLPs, also holds for RLSLPs.
Lemma 6.
For any RSLP
S
of height
h
generating T, by storing
|val
(
X
)
|
for every variable
X
, we can
support Extract(i, `) in O(h + `) time.
3
We treat the last variable as the starting variable.
3
剩余10页未读，继续阅读
2021-04-22 上传
2024-10-12 上传
2024-08-22 上传
2022-09-24 上传
2024-08-22 上传
2024-10-17 上传
2024-10-13 上传
2024-08-22 上传
2024-09-27 上传
weixin_38741950
- 粉丝: 2
- 资源: 962
我的内容管理
展开
最新资源
- Android圆角进度条控件的设计与应用
- mui框架实现带侧边栏的响应式布局
- Android仿知乎横线直线进度条实现教程
- SSM选课系统实现：Spring+SpringMVC+MyBatis源码剖析
- 使用JavaScript开发的流星待办事项应用
- Google Code Jam 2015竞赛回顾与Java编程实践
- Angular 2与NW.js集成：通过Webpack和Gulp构建环境详解
- OneDayTripPlanner：数字化城市旅游活动规划助手
- TinySTM 轻量级原子操作库的详细介绍与安装指南
- 模拟PHP序列化:JavaScript实现序列化与反序列化技术
- ***进销存系统全面功能介绍与开发指南
- 掌握Clojure命名空间的正确重新加载技巧
- 免费获取VMD模态分解Matlab源代码与案例数据
- BuglyEasyToUnity最新更新优化：简化Unity开发者接入流程
- Android学生俱乐部项目任务2解析与实践
- 掌握Elixir语言构建高效分布式网络爬虫
