自动机解压中的非递归算法
之前，自动机词典仅用来存储自然语言处理的语料、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 的栈吧？
现在，回到开始的问题：非递归算法怎么写呢？
