自动机解压中的非递归算法

之前,自动机词典仅用来存储自然语言处理的语料、url、query 等单条数据很小数据集,为了简单,解压算法用的是递归实现。前段时间对自动机进行了一个改进,可以压缩存储单条数据很大数据集。于是,该发生的事情终于发生了:堆栈溢出,也叫爆栈!

两年前写那个递归算法的时候,我就觉得不够完美,只要是递归(尾递归不算),爆栈总有一天会发生。但最终我还是偷了懒,没有费脑筋去改成非递归。

这个的需求很简单,以 Trie 树为例:给定一个结点,枚举这个结点能表达的所有字符串。

递归算法很简单:

当然,现实中比这个要复杂一些:

  1. 自动机不是 Trie,是 ADFA (Acyclic DFA),不过这一点对算法本身无任何影响
  2. 结点可能包含压缩的路径,此时需要做一些特殊处理
    • 起始位置是用 (root, zidx) 表达的,zidx是压缩路径中间某个位置
  3. 结点的表达方式是非常紧凑的,而不像 DemoNode 那样铺张浪费

想象一下,当 buf 长度 16M 时(单条数据最大长度限制),这个递归有多深,需要多大的的栈,不可能开个 1G 的栈吧?

现在,回到开始的问题:非递归算法怎么写呢?

作者:
该日志由 rockeet 于2015年02月14日发表在未分类分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
转载请注明: 自动机解压中的非递归算法
标签:
【上一篇】
【下一篇】

您可能感兴趣的文章:

发表评论

您必须 登录 后才能发表评论。