Suffix Tree for a Sliding Window: An Overview
Suffix Tree for a Sliding Window: An Overview
复制标题
滑动窗口的后缀树：概述
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
M. Senft
中科院分区：
文献类型：
--
作者：
M. Senft
后缀树是一种非常强大的数据结构，最初是为字符串匹配和字符串搜索而开发的。随着时间的推移，它已经找到了许多应用，其中一些属于数据压缩领域。许多这些应用程序需要一个后缀树建立一个滑动窗口和t这里存在两个聪明的算法Fiala和格林和拉尔森，使这成为可能。然而，正如我们所展示的，这两种方法都有缺陷的证明。我们补救这种情况，解释一个简单的替代算法，并给出了正确的证明。
The suffix tree is a very powerful data structure developed originally for string matching and string searching. It has found many applications over the time and some of them belong into the data compression field. Many of these applications need a suffix tree built for a sliding window and t here exist two clever algorithms by Fiala and Greene and by Larsson that make this possible. However, as we show both approaches have flawed proofs. We remedy this situation both by explaining a simple alternative algorithm and giving a correct proof.