字符串索引结构

字符串索引结构将文本预处理成可搜索的形式——如字典树、后缀树或后缀数组——以便快速回答许多后续的模式查询以及关于重复和公共子字符串的问题。

Definition

字符串索引结构是一种从文本（或字符串集合）构建的数据结构，它支持对文本进行高效查询——例如模式是否出现以及出现的位置、最长重复子字符串或两个文本的最长公共子字符串——通常通过表示文本的前缀或后缀来实现。

Scope

本主题涵盖了用于快速重复查询的字符串索引数据结构：用于字符串集合的字典树（前缀树）、表示文本所有后缀以实现线性时间模式搜索的后缀树、作为其空间高效对应物的后缀数组，以及如最长公共前缀数组等辅助结构。它讨论了它们的构建算法和它们所加速的查询，但不包括不预处理文本的单次模式匹配。

Core questions

• 字典树如何组织字符串集合以进行基于前缀的搜索？
• 后缀树如何表示所有后缀，使得模式查询的时间与模式长度成比例？
• 后缀数组如何以更少的内存实现类似的功能？
• 哪些构建算法可以高效地构建这些结构，理想情况下是线性时间？
• 这些索引能优雅地解决哪些文本问题（重复、公共子字符串）？

Key concepts

• 字典树（前缀树）
• 后缀树
• 后缀数组
• 最长公共前缀数组
• 在线构建
• 最长重复子字符串
• 最长公共子字符串
• 时空权衡

Key theories

后缀树和线性时间构建

后缀树紧凑地表示文本的每个后缀，允许以与模式长度成比例的时间搜索模式；Ukkonen算法以文本长度的线性时间在线构建它。

作为空间高效索引的后缀数组

后缀数组在一个简单的整数数组中存储所有后缀的排序顺序；结合最长公共前缀数组，它支持快速模式搜索，并且比后缀树使用更少的内存。

Clinical relevance

文本索引驱动大规模搜索和生物信息学：后缀数组和相关的压缩索引是基因组读取比对器和全文搜索引擎的基础，字典树支持自动补全和IP路由表，这些结构使得对海量文本进行重复查询变得可行，而重新扫描则会耗费巨大。

History

Peter Weiner于1973年引入了后缀树，McCreight（1976）和Ukkonen（1995）提出了更简单的线性时间构建方法。Manber和Myers于1990年引入了后缀数组，作为一种更节省空间的替代方案，后来的压缩索引和FM索引工作将这些思想扩展到非常大的文本和基因组。

Key figures

• Peter Weiner
• Edward McCreight
• Esko Ukkonen
• Udi Manber
• Gene Myers
• Dan Gusfield

Seminal works

• ukkonen1995
• manber1993
• gusfield1997

Frequently asked questions

我什么时候应该使用后缀数组而不是后缀树？

后缀数组比后缀树占用更少的内存，并且具有良好的缓存行为，这使得它们更适合大型文本，例如基因组。后缀树直接暴露了更多的结构，可以使某些算法在概念上更简单，但空间成本更高；后缀数组加上最长公共前缀数组可以恢复大部分功能。

字典树有什么用？

字典树通过共享前缀存储一组字符串，提供快速前缀搜索、自动补全和有序遍历。它非常适合字典、自动补全建议和最长前缀匹配，例如在IP路由中，其中键共享共同的开头。