Reducing the space requirement of suffix trees

作者：Stefan Kurtz · 发表于：Software Practice and Experience · 年份：1999 · DOI：10.1002/(sici)1097-024x(199911)29:13<1149::aid-spe274>3.0.co;2-o · 被引用次数：337 · 研究领域：Algorithms and Data Compression、Network Packet Processing and Optimization、semigroups and automata theory

We show that suffix trees store various kinds of redundant information. We exploit these redundancies to obtain more space efficient representations. The most space efficient of our representations requires 20 bytes per input character in the worst case, and 10.1 bytes per input character on average for a collection of 42 files of different type. This is an advantage of more than 8 bytes per input character over previous work. Our representations can be constructed without extra space, and as fast as previous representations. The asymptotic running times of suffix tree applications are retained. Copyright © 1999 John Wiley & Sons, Ltd.