Efficient implementation of lazy suffix trees
Efficient implementation of lazy suffix trees
复制标题
DOI：
10.1002/spe.535
复制
发表时间：
2003-09-01
影响因子：
3.5
通讯作者：
Stoye, J
中科院分区：
文献类型：
--
作者：
Giegerich, R;Kurtz, S;Stoye, J
我们提出了一个有效的实现只写自顶向下的后缀树建设。我们的实现是基于一个新的，空间有效的表示后缀树，只需要12个字节，每个输入字符在最坏的情况下，和8.5字节，每个输入字符平均为不同类型的文件的集合。我们展示了如何有效地实现后缀树的惰性评估，使得子树仅在第一次遍历时进行评估。我们的实验表明，对于在一个固定的输入字符串中搜索多个精确模式的问题，懒惰的自顶向下构造通常比其他方法更快，更节省空间。版权所有（C）2003约翰威利父子有限公司。
We present an efficient implementation of a write-only top-down construction for suffix trees. Our implementation is based on a new, space-efficient representation of suffix trees that requires only 12 bytes per input character in the worst case, and 8.5 bytes per input character on average for a collection of files of different type. We show how to efficiently implement the lazy evaluation of suffix trees such that a subtree is evaluated only when it is traversed for the first time. Our experiments show that for the problem of searching many exact patterns in a fixed input string, the lazy top-down construction is often faster and more space efficient than other methods. Copyright (C) 2003 John Wiley Sons, Ltd.