Reverse engineering of compact suffix trees and links: A novel algorithm
Reverse engineering of compact suffix trees and links: A novel algorithm
复制标题
DOI：
10.1016/j.jda.2014.07.002
复制
发表时间：
2014-09-01
期刊：
影响因子：
--
通讯作者：
Rivals, Eric
中科院分区：
文献类型：
--
作者：
Cazaux, Bastien;Rivals, Eric
后缀树（ST）于1970年代发明，是一种数据结构，该数据结构索引了线性空间中文本的所有substring。尽管比其他索引要求更高的空间，但ST仍然可能是一个鼓舞人心的索引，因为它代表了层次树结构中的子字符串。随着时间的流逝，STS在文本算法中获得了中心位置，其中包括无数算法和应用程序，例如图案发现，生物序列比较或文本压缩。众所周知，不同的单词可以导致具有不同标签的相同后缀树结构。此外，STS的特性阻止了所有树结构是STS。即使是在有效的构造算法和许多应用中起关键作用的后缀链接也不足以区分不同单词的后缀树。认识到可以在STS上抬起并称为反向工程的问题的问题。对于具有潜在后缀链接的树的情况，开创性的工作仅为二进制字母提供线性时间解决方案。在这里，我们还通过链接调查了ST上的反向工程问题，并展示了一种新颖的方法和算法。希望这种新的后缀树表征迈出了对后缀树组合学的更好理解的宝贵一步。 （c）2014 Elsevier B.V.保留所有权利。
Invented in the 1970s, the Suffix Tree (ST) is a data structure that indexes all substrings of a text in linear space. Although more space demanding than other indexes, the ST remains likely an inspiring index because it represents substrings in a hierarchical tree structure. Along time, STs have acquired a central position in text algorithmics with myriad of algorithms and applications to for instance motif discovery, biological sequence comparison, or text compression. It is well known that different words can lead to the same suffix tree structure with different labels. Moreover, the properties of STs prevent all tree structures from being STs. Even the suffix links, which play a key role in efficient construction algorithms and many applications, are not sufficient to discriminate the suffix trees of distinct words. The question of recognising which trees can be STs has been raised and termed Reverse Engineering on STs. For the case where a tree is given with potential suffix links, a seminal work provides a linear time solution only for binary alphabets. Here, we also investigate the Reverse Engineering problem on ST with links and exhibit a novel approach and algorithm. Hopefully, this new suffix tree characterisation makes up a valuable step towards a better understanding of suffix tree combinatorics. (C) 2014 Elsevier B.V. All rights reserved.