demonstrate 的 blog

前面简单的提到了 suffix tree 的基本用途，在给定字符串中进行快速搜索。但这仅仅是最基本的一个应用。

Exact set matching

前面提到过的 Aho-Corasick algorithm（是 KMP 的推广）为求解这个问题提供了一种思路，实际上· suffix tree 同样可以求解这个问题，并且我们只需要使用 exact string matching 策略遍历给定集合里面的每个字符串就行了。

两者的时间渐进复杂度是相当的，但是两种策略各有优缺点：如果 P(attern) 大于 T(ext)，尽管占用的空间比较小，但是搜索比较慢；如果 P 小于 T，则 Aho-Corasick 算法尽管占用空间小，但却搜索较慢。这就需要我们 trade-off 时间和空间。有一点 suffix tree 在固定的语料集合上有优势的是只需要建立一次 suffix tree 后面可以重复使用。从 KMP 的思路也可以看出来，KMP 系的做法是预处理 pattern，而 suffix tree 是预处理 text。

Substring problem

这个问题与 bioinfo 里面检索某些 DNA 序列比较像，但是对于 DNA sequence 一般只能用 inexact match，这里是一个简化的版本。即有一个 database，里面存放有若干字符串，现给定一个字符串，如何获得含有这个字符串的集合（可以是空集）。Suffix tree 对这类问题基本是门当户对。

Longest common substring

所谓 longest common substring 与 longest common subsequence 的区别是前者要求找到的是连续的（所以是个 substring），后者不要求是连续的（所以后者的长度不小于前者）。

一般求解这个问题比较“笨”的方案是做一个 的表，里面填两个字符串对应元素是否 match，然后找对角线上连续为匹配最长的位置。后者一般使用 dynamic programming，建立 的表从前开始填，如果相同 ；否则取两种情况的大者 。通过 suffix tree 可以将这个问题的时间复杂度从 降低到 ，这需要对 suffix tree 本身进行一定的推广，这时两个字符串的 suffix 都对应于 leaf，如果有共用的 suffix 对应于一个 leaf。这样我们就把原问题转换成为了在这个 tree 上搜两个 string 共用的 path，对应的 string depth 最深，这一般可以通过对 tree 做遍历（线性时间复杂度）获得。

DNA contamination problem

给定两个字符串，其中一个可能是被污染的字符串，另一个是用来污染的字符串，如果前者里面出现了后者里面的字串长度超过了一定的大小就认为被后者污染了。这经常在 DNA 测序里面检验获得的 DNA 序列是否被一些已知的污染 DNA 片段污染，以保证获得的 DNA 序列的纯洁性。

后缀树求解的方法和前者类似，出现 contamination 的是一些 internel node 如果有来自两者的 leaf，这说明两者含有公共的字串，如果 string depth 超过给定值，则说明的确是发现了 contamination。

Common substrings of multiple strings

这是对两个字符串寻找公共子串的推广问题。这个问题的正是描述是，对于 K 个字符串，需要对任意 k 满足大于等于 2 小于等于 K，获得 l(k) 表示至少有 k 个字符串公共的子串中长度的最大值。该问题的最优解是 ，其中 n 是字符串总长度，比较 naieve 的做法可以做到 。这个方法就是将两个 string 的想法推广，为 internal node 记录 K 个标志位表示被几个字符串包含。

DAG compression

给定一个 suffix tree，如何将其用一个 DAG 表达出来，这个 DAG 是能识别所有 suffix 的最小 FSA。基本的想法就是将 suffix tree 中 share 的子树结构（同构）进行 merge，这样 tree 就变成了 DAG 了。一般意义下的 subtree isomorphism 是相对较难的问题，但是对于 suffix tree 这种特殊的 tree，则要简单许多。可以证明，如果两个 node，其一有到另外一个的 suffix link（即到前者的 prefix 是另一个 prefix 的 suffix），且两者子节点含有相同多的 leaf，则两者对应的子树同构。利用这个结论 top-down 的寻找符合条件的 pair 进行 merge 就能获得需要的 DAG。

Matching statistics

这是反向应用 suffix tree 解决 matching 问题里面的一种核心技术，所谓反向应用 suffix tree 是指，为 pattern 建立 suffix tree 而不是对 text。所谓的 matching statistics（MS）是指 对应 text 中第 个字符开始与 pattern 某子串匹配上的最长的子串长度。比较简单的应用 P 的 suffix tree，然后遍历 T 的每个字符是不能在 linear time 获得 的。核心的观察是计算下一个 时是否能利用前面的结果进行简化，这个窍门据说与 Ukkenon 算法相同。

应用这个思路求解 longest common substring 问题时，我们可以对短的 string 处理获得其 suffix tree 以减少 space 的额外需求。

All-pairs suffix-prefix matching

给定两个字符串，寻找前者的一个后缀与后者的一个前缀的匹配称为 suffix-prefix matching。如果给定 k 个字符串，总长度为 m，找到任意两个之间的 suffix-prefix matching 中最长匹配的问题称为 all-pairs suffix-prefix matching。

利用 suffix tree 求解该问题的思路如下，将所有 string 利用 generalized suffix tree 建立索引，寻找第 j 个字符串对应的 leaf（即完整的第 j 个字符串出现在整个 root path 上），如果这条 path 上存在某个节点 v，且 i 属于 ，即 v 是 internal node 但链接了 terminal edge（即对应 label 是终止符），则 是所有这条 root path 对应的字符串的集合，这样相当于找到了第 i 个字符串的 suffix 正好是第 j 个字符串的 prefix。

这种策略的时间复杂度将会是 。

Finding maximal pairs

所谓的 maximal pair 指字符串两个不同的子串，它们完全相同，且其对应左右字符均不同，这保证不能在其基础上继续扩大，其中这个重复的字符串（可能有 overlap）称为 maximal repeat。supermaximal repeat 指这样一种 maximal repeat，它不是其他 maximal repeat 的子串。

使用 suffix tree 求解该问题的第一个观察是如果字符串是 maximal repeat，则一定是到某个节点的 root path 对应的子串。长度为 n 的字符串最多也只会有 n 个 maximal repeat。这告诉我们应该在哪里寻找 maximal repeat。第二个观察表明，当且仅当节点 v 是 left diverse 的时候对应的 root path 的子串才是 maximal repeat。所谓 left diverse 指该节点至少有两个 leaf （这对应两个 suffix）对应的 left character（即这个 suffix 前面一个字符）是不同的。因此 leaf 本身不是 left diverse 的。

这样就把寻找 maximal repeat 转换成为寻找 left diverse 的 node，如何紧凑的将 left character 在 suffix tree 中表示出来就可以较好的解决原问题了。我们可以用所谓的 frontier 节点来看待最终的表示，所谓 frontier 指这样的 node，他本身是 left diverse 但其任意子节点都不是 left diverse。这样每个到 frontier 的 root path 就代表一个 maximal repeat 了。比较容易的做法就是从每个 leaf 开始将其 left character 向父节点传递，如果某个父节点获得了两个不同的 left character 就是 frontier，并停止继续向上传递。

如果是想找到 supermaximal repeat，可以使用如下观察：其所有子节点都是 leaf 且对应的 left character 不同。另外有所谓的 near-supermaximal repeat，可以用类似的分析求解。

Circular string linearization

给定一个长度为 n 的 circular string，找到一个开始的地方对应的 linearized string 具有最小的字典序。

求解该问题可以先将字符串随便 linearize 记为 L，然后对 LL 建立 suffix tree，这样遍历 tree 的时候选择首字母最小的直到 string depth 为 n 停止。

Suffix array

前面简单的介绍了 suffix array 比较 naieve 的构造方法。我们可以简单的将长度为 m 的字符串对应的 m 个 suffix 编号为整数，并且将其用对应的顺序排序，这样可以简洁的表达出 suffix array。这样我们建立了 suffix tree 之后通过 lexical depth first 遍历，就能获得这种表示吓得 suffix array，对不少问题来说，直接使用 suffix array 就足够了（效率差不多），suffix tree 本身可以丢弃。这样就可以节省不少内存的开销。

在这种表示下进行 pattern search 我们可以使用 binary search，比较 P 与 suffix array 每个后缀对应的 suffix。因此需要的时间（仅搜索部分）是 。事实上有一些 trick 可以用来加速这个搜索，前面说了可以保留与前一个 suffix 公共前缀的长度，利用这个可以加速跳转，这可以 improve 到 。

Ziv-Lempel compression

这个压缩算法的核心思想是如果前面一部分“字符串”表示出来（压缩表示）了，那么后面碰到类似子串时就可以直接“引用”前面的子串。比如标记为前面在哪里出现长度是多少的子串。实现这样一个压缩算法可以利用 suffix tree，比较简单的做法是建立 suffix tree 后，在搜索可替代某处子串的时候要求这个 prefix 出现的 path 里面有小于当前位置的 leaf。为了快速获得是否含有这个 leaf，我们可以为每个顶点加上一个属性，表示通过该节点的 root path 中 leaf 编号最小的是谁。这也是线性时间可以解决的，这样搜索就可以简单的查询这个属性就 ok 了，这样完成压缩是 。

这样看来使用 suffix tree 需要多次扫描输入，但实际上整个过程可以 one-pass 做掉。

—————-
Then Lot chose him all the plain of Jordan; and Lot journeyed east: and they separated themselves the one from the other.