Compressed Dictionary Matching on Run-Length Encoded Strings

doi:10.1007/s00453-026-01398-0

Compressed Dictionary Matching on Run-Length Encoded Strings

2026-05-01

0

PRE

AI

DOI：10.1007/s00453-026-01398-0

原文链接

原文求助

摘要

En 中文

给定一组模式字符串 $\mathcal{P}=\{P_1, P_2,\ldots P_k\}$ 和一个文本字符串 $S$，经典的词典匹配问题是要报告 $S$ 中每个模式的所有出现位置。我们在压缩设置下研究词典问题，其中模式字符串和文本字符串使用游程编码进行压缩，目标是在不解压缩的情况下解决问题，并在压缩字符串大小的时间内和空间内实现高效。设 $m$ 和 $n$ 分别为模式 $\mathcal{P}$ 和文本字符串 $S$ 的总长度，以及 $\overline{m}$ 和 $\overline{n}$ 分别为模式 $\mathcal{P}$ 和 $S$ 在游程编码中的总游程数。我们的主要结果是算法在 $O((\overline{m}+\overline{n})\log \log m+\text{occ})$ 预期时间内实现，空间为 $O(\overline{m})$，其中 $\text{occ}$ 是 $S$ 中模式的总出现次数。这是该问题的第一个非平凡解决方案。由于任何解决方案都必须读取输入，我们的时间界限在 $\log \log m$ 因子内是最优的。我们引入了几种新技术来实现我们的界限，包括经典的 Aho-Corasick 自动机的新压缩表示和一个新的高效字符串索引，支持在游程编码字符串中的快速查询。

Keyword:

Dictionary matching

Run-length encoding

Compressed pattern matching

Compressed Dictionary Matching on Run-Length Encoded Strings

摘要

期刊

机构

引用论文