A comparison of imperative and purely functional suffix tree constructions
A comparison of imperative and purely functional suffix tree constructions
复制标题
DOI：
10.1016/0167-6423(95)00003-8
复制
发表时间：
1995-12-01
影响因子：
1.3
通讯作者：
Kurtz, S
中科院分区：
文献类型：
--
作者：
Giegerich, R;Kurtz, S
我们探索在函数范式中实现后缀树算法的设计空间。我们回顾了 McCreight 和 Ukkonen 的线性时间和空间算法。基于嵌套后缀和嵌套前缀的新术语，我们对这些算法给出了比以前已知的更简单、更具声明性的解释。我们设计了这些算法的两个“简单”版本，它们不是线性时间的，但使用更简单的数据结构，并且可以以纯函数风格实现。此外，我们提出了一种新的、更简单的“惰性”后缀树结构。我们评估这些算法的命令式和函数式实现。我们的结果表明，朴素算法的性能非常好，特别是惰性构造与所有其他算法相比非常好。
We explore the design space of implementing suffix tree algorithms in the functional paradigm. We review the linear time and space algorithms of McCreight and Ukkonen. Based on a new terminology of nested suffixes and nested prefixes, we give a simpler and more declarative explanation of these algorithms than was previously known. We design two ''naive'' versions of these algorithms which are not linear time, but use simpler data structures, and can be implemented in a purely functional style. Furthermore, we present a new, ''lazy'' suffix tree construction which is even simpler. We evaluate both imperative and functional implementations of these algorithms. Our results show that the naive algorithms perform very favourably, and in particular, the lazy construction compares very well to all the others.