Suffix Trees, DAWGs and CDAWGs for Forward and Backward Tries

研究成果: 書籍/レポート タイプへの寄稿会議への寄与

1 被引用数 (Scopus)


The suffix tree, DAWG, and CDAWG are fundamental indexing structures of a string, with a number of applications in bioinformatics, information retrieval, data mining, etc. An edge-labeled rooted tree (trie) is a natural generalization of a string, which can also be seen as a compact representation of a set of strings. Kosaraju [FOCS 1989] proposed the suffix tree for a backward trie, where the strings in the trie are read in the leaf-to-root direction. In contrast to a backward trie, we call a usual trie as a forward trie. Despite a few follow-up works after Kosaraju’s paper, indexing forward/backward tries is not well understood yet. In this paper, we show a full perspective on the sizes of indexing structures such as suffix trees, DAWGs, and CDAWGs for forward and backward tries. In particular, we show that the size of the DAWG for a forward trie with n nodes is Ω(σn), where σ is the number of distinct characters in the trie. This becomes Ω(n2) for an alphabet of size σ= Θ(n). Still, we show that there is a compact O(n)-space implicit representation of the DAWG for a forward trie, whose space requirement is independent of the alphabet size. This compact representation allows for simulating each DAWG edge traversal in O(log σ) time, and can be constructed in O(n) time and space over any integer alphabet of size O(n).

ホスト出版物のタイトルLATIN 2020
ホスト出版物のサブタイトルTheoretical Informatics - 14th Latin American Symposium 2021, Proceedings
編集者Yoshiharu Kohayakawa, Flávio Keidi Miyazawa
出版社Springer Science and Business Media Deutschland GmbH
出版ステータス出版済み - 2020
イベント14th Latin American Symposium on Theoretical Informatics, LATIN 2020 - Sao Paulo, ブラジル
継続期間: 1月 5 20211月 8 2021


名前Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
12118 LNCS


会議14th Latin American Symposium on Theoretical Informatics, LATIN 2020
CitySao Paulo

!!!All Science Journal Classification (ASJC) codes

  • 理論的コンピュータサイエンス
  • コンピュータサイエンス一般


「Suffix Trees, DAWGs and CDAWGs for Forward and Backward Tries」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。