[算法理论] 高效构建紧凑有向无环字图的突破性方法

摘要

紧凑有向无环字图（CDAWG）可以通过两种等价方式来理解：作为字符串的边压缩有向无环图（DAWG），以及通过合并同构子树节点而得到的后缀树的有向无环图（DAG）。

我们利用这两种视角的互补性，展示了如何为长度为 $n$ 的（反向）输入字符串构建CDAWG。具体而言，若输入字符串有 $e_L$ 条边，我们能够在 $O(e_L\log n\log(n/r))$ 时间内完成构建，同时使用 $O(r\log(n/r)+e_L)$ 个工作空间字。这里，$r$ 表示输入字符串的 BWT-runs 数量。

此外，该方法依赖于 Gagie、Navarro 和 Prezza 提出的功能齐全的压缩后缀树，其大小为 $O(r\log(n/r))$。

结论

此方法在构建CDAWG时的时间和空间复杂度均具有较好的表现，为字符串处理提供了新的思路与工具。

博主点评： 本文提出的高效构建CDAWG的方法，充分利用了后缀树的结构特性，展示了算法在处理字符串图形结构时的创新性。对字符串处理领域的研究具有重要的推动作用。