后缀数组_计算机科学名词

后缀数组

计算机科学名词

在计算机科学里, 后缀数组（英语：suffix array）是一个通过对字符串的所有后缀经过排序后得到的数组。此数据结构被运用于全文索引、数据压缩算法、以及生物信息学。

简介

在计算机科学里,后缀数组（英语：suffix array）是一个通过对字符串的所有后缀经过排序后得到的数组。此数据结构被运用于全文索引、数据压缩算法、以及生物信息学。

后缀数组被乌迪·曼伯尔与尤金·迈尔斯于1990年提出，作为对后缀树的一种替代，更简单以及节省空间。它们也被Gaston Gonnet 于1987年独立发现，并命名为“PAT数组”。

定义

令字符串，表示S的子字符串，下标从i到j。

S的后缀数组A被定义为一个数组，内容是S的所有后缀经过字典排序后的起始下标。对于所有的有：。

例子

考虑字符串S=banana$:

字符串的结尾是特殊字符$，用作特殊标志。该字符串有以下后缀：

后缀经过升序排序后：

后缀数组A包含这些后缀的起始位置：

参考资料

最新修订时间：2022-06-12 11:26

条目作者

概述

简介

定义

例子

参考资料