后缀树索引

后缀树索引（suffix tree index），管理学-情报学-情报技术-情报组织技术，将给定字符串（或文本）的所有后缀以树的形式链接创建的索引。后缀树是字符串处理领域的一种非常重要的数据结构，其研究可以追溯到20世纪60年代末的后缀字典树的概念。其基本性质是：给定一个具有n个字符（词）的字符串S，其后缀树T是一棵包含一个根节点、n个叶子节点的有向树；除了根节点以外的每一个内部节点都至少有两个子节点，且每条边都用一个非空子串来标识；出自同一节点的任意两条边的标识不会以相同的字符（词）开始。后缀树索引的关键特征是：对于任何叶子i，从根节点到该叶子所经历的边的所有标识串联起来，恰好是S从i位置开始的后缀（S[i,…,n]）。下图为字符串“BANANAS”后缀树表示。字符串“BANANAS”后缀树表示在使用后缀树索引时，通常一棵后缀树只能表达一个字符串（或文本）的索引，为了处理多个字符串（或文本），需要使用“广义后缀树”。广义后缀树是指一棵包含了字符串（或文本）集合｛S1,…,Sn｝中所有字符串后缀的后缀树。