1.介绍

在本教程中,我们将探索什么是通用的后缀树是如何使用的一个例子查找最长公共子字符串。查找最长公共子串是一种特殊情况字符串相似性方法通过找到共同的子序列。这类方法中的“序列”是子字符串。

我们将演示查找最长公共子串的广义后缀树的一个应用

然后,我们将构建一个广义后缀树,首先构建一个后缀trie和Patricia trie(使用字段的术语),然后对这些树进行注释,以形成一个广义后缀树。

2.后缀试

回答第一个问题,不,我们没有拼错单词“tree”。在后缀树语言中,a单词查找树是构建可用于我们的任务的完整通用后缀树的中间部分。后缀trie是一个树边缘,即线连接节点,都是用我们的后缀字母标记的

我们通过跟随每个后缀并为每个字符创建一条边(从顶节点开始)来构建一个后缀树。如果要放入树中的新后缀以一组已经存在于树中的字符开始,那么我们将一直跟踪这些字符,直到有一个不同的字符,从而创建一个新的分支。

这最好用一个例子来解释。我们会用到这个词废话。这个单词有8个后缀,外加一个空后缀(用$表示):

  1. 美元
  2. e
  3. se
  4. 分析了无
  5. 语态
  6. 感觉
  7. nsense
  8. onsense
  9. 废话

我们开始构建带有起始节点和空白后缀的后缀trie,标记为$:

然后后缀trie是累积的,后缀的第一个字母连接到开始节点。我们看到前三个非空后缀都以不同的字母开头,所以我们在空白分支中添加三个分支:

下一个后缀,语态,始于e,它在开始节点中已经有一个节点。我们将它作为分支添加到e节点通过跟随后缀的公共部分,在本例中只是e,并在字母不同的地方添加额外的分支:

我们继续这个过程,在后缀不同的地方添加分支,在必要的地方添加新分支。当我们完成时,我们得到:

这里,我们可以看到有三个后缀n。我们看到,在有公共子字符串部分的地方,它们遵循相同的分支,例如分析了无分析了无nsense后缀。

我们也看到,如果字符串的大小T米,即| | = T m,后缀树恰好m + 1叶节点。在……的情况下废话,我们用9节点。算法的复杂度取决于节点的个数。所以我们可以问下一个问题:

我们可以减少节点的数量在尝试?

答案将在下一节中解释,即构建所谓的“Patricia Trie”。

3.帕特里夏·特里结构

一个帕特里夏·特里结构所有只有一个子节点(没有分支)的“简单”节点是否被组合在一起。在我们的例子中,我们得到:

我们可以看到,节点的数量减少了,但是叶节点的数量是相同的,即后缀的数量。构建Patricia trie是构建后缀树(和广义后缀树)的一步,它将用于完成子字符串识别中的许多任务。

4.后缀树

后缀树,我们离创建数据结构更近了一步,以方便我们的子串识别任务。字符串的后缀树T帕特丽夏是什么T每个叶子都用索引标记,对应的后缀在哪里开始T。这个标签给了我们一个对原始后缀的直接引用:

5.广义后缀树

一个后缀树只有对单个字符串的描述,T但是,一个广义上面描述的数据结构的版本可以用于索引多个字符串。在这种情况下,搜索操作的结果可以是包含给定输入字符串的字符串的引用。

广义的后缀树T_1,……, T_k后缀树是T_1,……, T_k,但是叶子节点上的标签不仅有在字符串中的位置,而且有它所指的字符串的索引。这些叶子贴上了标签我:我,意思是“j字符串后缀ThT_{识别我}

我们将用一个有两个字符串的广义后缀树来说明这一点,T_1 =胡说八道T_2 =进攻:

6.最长公共子串

我们可以使用广义后缀树来方便子串识别。其主要思想是,一个字符串中的每个子字符串都是该字符串的某个后缀的前缀。换句话说,当我们在树中放置每个后缀时,我们也将每个后缀的开始字符放在树的顶部(连接到开始节点)。后缀的开头字符也是前缀的开头字符。两个子字符串只需要部分匹配树。

寻找最长公共子串的算法有三个步骤:

  1. 为。构建一个通用后缀树T_1T_2
  2. 对树中的每个内部节点进行注解,说明该节点是否至少包含来自每个节点的一个叶节点T_1T_2
  3. 在树上运行深度优先搜索,以找到具有最高字符串深度的标记节点。

在我们的示例中,我们构建了一个带有两个字符串的通用后缀树,废话,进攻。然后用该分支是否只有字符串来注释每个节点1只有字符串2或者两个字符串1、2:

看着树(深度优先搜索),我们看到红结点,表示语态是最长公共子字符串。绿色节点代表更短的字符串,分析了无se。因为浓缩的帕特里夏树,它们出现在相同的层次上。

7.结论

本文概述了如何构建广义后缀树来解决子字符串识别问题。我们在这里概述的是一种生成通用后缀树的简单方法,但是有许多高级技巧可以加快算法的速度,比如后缀树的在线构建赫尔辛基大学教授。

有几个源代码可以用几种语言构建树,例如Python实现Java实现

对这篇文章的评论关闭!