Linear-size suffix tries

Abstract : Suffix trees are highly regarded data structures for text indexing and string algorithms [MCreight 76, Weiner 73]. For any given string w of length n=|w|, a suffix tree for w takes O(n) nodes and links. It is often presented as a compacted version of a suffix trie for w, where the latter is the trie (or digital search tree) built on the suffixes of w. Here the compaction process replaces each maximal chain of unary nodes with a single arc. For this, the suffix tree requires that the labels of its arcs are substrings encoded as pointers to w (or equivalent information). On the contrary, the arcs of the suffix trie are labeled by single symbols but there can be Θ(n²) nodes and links for suffix tries in the worst case because of their unary nodes. It is an interesting question if the suffix trie can be stored using O(n) nodes. We present the linear-size suffix trie, which guarantees O(n) nodes. We use a new technique for reducing the number of unary nodes to O(n), that stems from some results on antidictionaries. For instance, by using the linear-size suffix trie, we are able to check whether a pattern p of length m=|p| occurs in w in O(m log⁡|Σ|) time and we can find the longest common substring of two strings w1 and w2 in O((|w1|+|w2|) log⁡|Σ|) time for an alphabet Σ.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2016, 638, pp.171 - 178. 〈10.1016/j.tcs.2016.04.002〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01388452
Contributeur : Marie-France Sagot <>
Soumis le : mardi 30 mai 2017 - 13:45:26
Dernière modification le : jeudi 5 juillet 2018 - 14:45:54
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 13:27:50

Fichier

LinearSizeSuffixTrie4.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Maxime Crochemore, Chiara Epifanio, Roberto Grossi, Filippo Mignosi. Linear-size suffix tries. Theoretical Computer Science, Elsevier, 2016, 638, pp.171 - 178. 〈10.1016/j.tcs.2016.04.002〉. 〈hal-01388452〉

Partager

Métriques

Consultations de la notice

350

Téléchargements de fichiers

62