自动机解压中的非递归算法
之前,自动机词典仅用来存储自然语言处理的语料、url、query 等单条数据很小的数据集,为了简单,解压算法用的是递归实现。前段时间对自动机进行了一个改进,可以压缩存储单条数据很大的数据集。于是,该发生的事情终于发生了:堆栈溢出,也叫爆栈!
两年前写那个递归算法的时候,我就觉得不够完美,只要是递归(尾递归不算),爆栈总有一天会发生。但最终我还是偷了懒,没有费脑筋去改成非递归。
这个的需求很简单,以 Trie 树为例:给定一个结点,枚举这个结点能表达的所有字符串。
递归算法很简单:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
struct DemoNode { DemoNode* children[256]; bool is_final; }; void print_loop(const DemoNode* root, std::string* buf) { if (root->is_final) { printf("%s\n", buf->c_str()); } for (int label = 0; label < 256; ++label) { if (root->children[label]) { buf->push_back(char(label)); print_loop(root->children[label], buf); buf->pop_back(); // c++11 has string::pop_back } } } void print(const DemoNode* root) { assert(root != NULL); std::string buf; print_loop(root, &buf); } |
当然,现实中比这个要复杂一些:
- 自动机不是 Trie,是 ADFA (Acyclic DFA),不过这一点对算法本身无任何影响
- 结点可能包含压缩的路径,此时需要做一些特殊处理
- 起始位置是用 (root, zidx) 表达的,zidx是压缩路径中间某个位置
- 结点的表达方式是非常紧凑的,而不像 DemoNode 那样铺张浪费
想象一下,当 buf 长度 16M 时(单条数据最大长度限制),这个递归有多深,需要多大的的栈,不可能开个 1G 的栈吧?
现在,回到开始的问题:非递归算法怎么写呢?