在LZ77 / LZSS上与后缀树匹配重叠前瞻
据我了解，给定一个后缀树，我们感兴趣（粗略地）计算中，对于每个后缀S，较长的后缀与S最长的公共前缀。
将每个树节点的引用添加到后缀最长的后代叶（使用DFS的线性时间）。 从每片叶子，向根部走，检查新的参考，如果找到更长的后缀则停止。 后一步的运行时间是线性的，因为每个树边缘只被检查一次。
不幸的是，一个有界窗口的生活更加困难。 我们传播了几个，而不是传播一个参考。 为了计算从一个节点引用的一组后缀，我们按照长度排序顺序合并它们。 那么每当我们有长度为x> y> z的后缀时，如果x-z <8192（例如），那么我们可以放弃y，因为对于当前节点是最叶共同祖先的所有后缀，所有三个后缀同样适用，如果y在窗口中，则x或z是。 由于窗口是文件总数的很大一部分，因此每个节点至多会有一些引用。
如果你想回顾一下最短的距离，那么就有一个O（n log ^ 2 n）时间算法（可能用O（n log n）可以用各种难以实现的魔法来改进）。 在算法的过程中，我们为每个节点构建后代后缀的二叉搜索树，然后进行下一个最长的查找。 要从其子节点构建节点的树，从最大的子树开始，插入其他元素。 通过重路径参数，每个长度都插入O（log n）次。
链接地址: http://www.djcxy.com/p/27487.html上一篇: Matches overlapping lookahead on LZ77/LZSS with suffix trees
下一篇: Using Spring as a dependency injection framework with play 2.4.x?