Compact directed acyclic word graphs for a sliding window

详细信息    查看全文

• 作者：Shunsuke Inenaga ; Ayumi Shinohara ; Masayuki Takeda ; Setsuo Arikawa
• 关键词：Author Keywords ; On-line text compression ; Linear-time algorithm ; Sliding window ; Compact directed acyclic word graphs
• 刊名：Journal of Discrete Algorithms
• 出版年：2004
• 出版时间：March 2004
• 年：2004
• 卷：2
• 期：1
• 页码：33-51
• 全文大小：482 K

文摘

Suffix trees are a well-known and widely-studied data structure highly useful for string matching. The suffix tree of a string w can be constructed in O(n) time and space, where n denotes the length of w. Larsson achieved an efficient algorithm to maintain suffix trees for a sliding window. It contributes to prediction by partial matching (PPM) style statistical data compression scheme. Compact directed acyclic word graphs (CDAWGs) are a more space-economical data structure for indexing strings. In this paper we propose a linear-time algorithm to maintain CDAWGs for a sliding window.