匹配统计数据——一项调查

《Theoretical Computer Science》：Matching Statistics—a survey

匹配统计量在计算生物学、数据压缩及字符串处理中的应用研究，涵盖存储优化、算法构造及后缀数组/BWT预处理等，分析近30年技术演进与多领域应用案例。

　　

Zsuzsanna Lipták|Francesco Masillo|Simon J. Puglisi

意大利维罗纳大学信息学系

摘要

给定两个字符串 S 和 R，S 相对于 R 的匹配统计信息是一个长度为 |S| 的数组，其中第 个元素编码了 S 的第 个后缀在 R 中出现的最长前缀。这一概念由 Chang 和 Lawler 在 1990 年首次提出，用于近似字符串匹配，此后在计算生物学、数据压缩和字符串处理等领域得到了广泛应用。在本文中，我们回顾了这些应用，以及过去 30 年中出现的一些高效构建匹配统计信息算法的主要思想。

引言

给定两个字符串 S 和 R（它们使用相同的字母表 Σ），S 相对于 R 的匹配统计信息由一个长度为 |S| 的数组组成，该数组的第 个元素包含从位置 开始的 S 的最长子串在 R 中出现的长度。

匹配统计信息最初由 Chang 和 Lawler [1], [2] 作为近似模式匹配的算法工具引入。从那时起，它被应用于许多其他字符串处理任务¹，例如 DNA 芯片设计 [3]、字符串核的计算 [4], [5]、全基因组系统发育 [6], [7]，以及检测读集合中的 SNVs（单核苷酸变异）或测序错误 [8]。Gusfield 的经典著作 [9] 中还介绍了其他字符串处理应用，如最长公共子串、精确匹配、最长前缀匹配等。最近，匹配统计信息被用作预处理步骤，以加快高度相似字符串集合的后缀数组 [10] 和 Burrows-Wheeler 变换（BWT）[11], [12], [13], [14] 的计算速度。此外，匹配统计信息与 Lempel-Ziv 分解 [15] 和相对 Lempel-Ziv 分解 [16] 密切相关，并在这些领域也得到了成功应用。

在这篇综述中，我们概述了过去 30 年开发的计算匹配统计信息的不同方法，并介绍了上述应用。下一节将介绍我们在整篇文章中使用的符号和基本概念。第 3 节解释了高效存储匹配统计信息的新方法，第 4 节回顾了不同的匹配统计信息构建算法。第 5 和第 6 节描述了如何利用匹配统计信息高效解决各种字符串处理问题。第 7 节以总结和展望结束。

部分摘录

基础

设 Σ 是一个大小为 σ 的有序字母表。字符串 T 是 Σ 中的有限字符序列，Σ* 是所有 Σ 上的字符串集合。字符串 T 的第 个字符表示为 T[]，其长度为 |T|。对于一个长度为 $\left|T\right|=n的字符串$T，我们使用符号 T[..j] 表示子串 T[]???T[j（其中 1?≤?i, j?≤?n）。如果 i?j，则 T[..j] 是空字符串 ε。后缀 $T[i..]=T[i..n]被称为第$ 个后缀 ${\mathrm{suf}}_i\left(T\right)，而$$T[..i]被称为第$ 个前缀 。当 T 明确时，

存储匹配统计信息

设 S 和 R 是两个使用字母表 Σ 的字符串，$\mathrm{MS}表示$S 相对于 R 的匹配统计信息。存储匹配统计信息的最简单方法是使用一个长度为 |S| 的数组，每个元素需要存储两个整数的空间。更准确地说，$\mathrm{MS}需要\; 2|$S|?log?|R|? 位的空间，因为 ?_i 和 p_i 的值都在 0 到 |R| 的范围内。

构建匹配统计信息

众所周知，S 相对于 R 的匹配统计信息可以在 $O\left(\right|R|+|S\left|\right)的时间内计算出来。例如，可以使用$R 的后缀树来实现这一计算，正如 Chang 和 Lawler 在他们的原始论文 [2] 中所描述的。在本节中，我们首先概述这个算法，然后介绍更现代的 MS 构建算法。

在字符串处理任务中的应用

在本节中，我们将非全面地介绍匹配统计信息在字符串处理问题中的应用。

在索引构建和数据压缩中的应用

在本节中，我们将重点讨论匹配统计信息在压缩相关应用（特别是 Lempel-Ziv 和相对 Lempel-Ziv 解析）以及在其他数据结构（特别是 SA 和 BWT）构建中的应用。

结论

本综述介绍了当前和历史上的计算及表示匹配统计信息的方法，并概述了它们的许多重要应用。其中许多工作是最近的研究成果，关于这一迷人数据结构仍有许多有趣的研究方向。其中一个方向是探索匹配统计信息的泛化，例如借鉴 Wheeler DFA 的最新研究成果 [87]。在空间和/或时间上与最新技术相当的情况下计算匹配统计信息。

CRediT 作者贡献声明

Zsuzsanna Lipták：撰写 – 审稿与编辑，撰写 – 原始草稿，监督，项目管理，方法论，调查，形式分析，概念化。Francesco Masillo：撰写 – 审稿与编辑，撰写 – 原始草稿，监督，方法论，调查，形式分析，概念化。Simon J. Puglisi：撰写 – 审稿与编辑，撰写 – 原始草稿，监督，项目管理，方法论，调查，形式分析，概念化。

利益冲突声明

作者声明他们没有已知的可能会影响本文所述工作的财务利益或个人关系。

作者声明以下可能被视为潜在利益冲突的财务利益/个人关系：

Simon J. Puglisi 表示获得了芬兰研究委员会的财务支持。Zsuzsanna Liptak 表示获得了 Francesco Severi 国家高等研究院的财务支持。