字符串匹配中的图论

作者: csdn-whinah 发表日期: 2013年03月24日分类: 自动机评论: 0 条阅读次数: 2,500 次

有一个字符串由多个变量拼接而成： “$x1$x2$x3$x4$x5$x6…” ，这个列表可以一直延伸到 $x10000，而每个变量都至少有一种可能的取值，为了简化问题，每个变量不会再引用别的变量。问题是：给定一个字符串T，判断这个字符串是否能由上面这个 “$x1$x2$x3$x4$x5$x6…” 生成。

分析

我们可以算出，总的可能性（最多）是 n1*n2*n3*n4*n5*n6…。

最笨的办法

因为现实中不会有太极端的情况，我们可以将这些字符串全部扩展出来，放入一个hash table。但是，如何得到这些扩展结果呢？

这是一个笛卡尔积的问题，可以用最简单的数数的方法，先从最低位数，数到最大值时，进一位，低位置零，直到最高位也达到最大：

// radix[i] 表示第 i 位的进制
// digit 数组是输出，长度也是 len
// 开始调用该函数时要将 digit 清零
bool next(const int* radix, int len, int* digit) {
    for (int i = len-1; i >= 0; --i) {
        assert(radix[i] > 0);
        assert(digit[i] < radix[i]);
        if (++digit[i] == radix[i])
            digit[i] = 0;
        else
            return true; // 下一个数字
    }
    return false; // 已结束，数字数完了
}

// radix[i] 表示第 i 位的进制

// digit 数组是输出，长度也是 len

// 开始调用该函数时要将 digit 清零

bool next(const int* radix, int len, int* digit) {

for (int i = len-1; i >= 0; --i) {

assert(radix[i] > 0);

assert(digit[i] < radix[i]);

if (++digit[i] == radix[i])

digit[i] = 0;

else

return true; // 下一个数字

}

return false; // 已结束，数字数完了

}

当然这个问题还有别的解法，例如用直接的树的深度优先遍历法。不过 next 函数本质上就是一个树深度优先遍历的 iterator。每次 next 函数返回 true，就可以拼接字符串了：

str = "";
for (int i = 0; i < len; ++i)
    str += x[i][digit[i]];

str = "";

for (int i = 0; i < len; ++i)

str += x[i][digit[i]];

正则表达式

对正则表达式熟悉的朋友可能一开始就想到了：”(x11|x12|x13…)(x21|x22|x23…)(x31|x32|x33…)…”

这个方法比hash table 好一点，现实中这种办法用起来也很快捷。但是，如果$x1 有 1,000,000 种可能，$x2 到 $x6 都只有 1 种可能，现存的任何一个正则表达式引擎都会爆掉！此时这种办法反而远比 hash table 要差。

使用自动机

有没有更好的办法？hash table 和正则表达式都各有自己的局限性……

使用正则表达式，至少思路对了，正则表达式引擎爆掉的问题，那是另外一回事了。我们可以针对这个特殊需求，自己 Craft 一个“正则表达式引擎”。很多正则表达式引擎都是用(有穷状态)自动机实现的，直接用自动机，要高效得多。

我写的 febird.automata 是一个高效的自动机实现，特别是实现了 MinADFA 的动态构造算法。要解决这个问题，在 MinADFA 上还要解决另外一个问题：每次扩展一个前缀集合之后：也就是说，当将$Xn加入之后，会有多个末尾（需要继续在后面追加的状态，此时被标记为终止状态），要继续扩展到$Xn+1，这多个末尾怎么办？经典的MinADFA动态构造法只能从一个初始状态添加字符串！

还好，如果对图论熟悉，这个问题其实可以规约到拓扑排序：对当前的MinADFA进行拓扑排序，按照拓扑序列的反序，在每个末尾（终止）状态上对整个$Xn+1 集合应用 MinADFA 构造算法（需要先将该末尾状态设为非终止状态）。

最终的结果，对一个比较小的集合进行测试，这个算法比(DFA的)正则表达式节省300多倍的内存。构造（对应于正则表达式编译）速度要快100多倍，匹配速度倒是相当，稍微快一点。NFA的正则表达式编译速度倒还可以，匹配就不说了，超慢，要慢 2000 倍以上！

总的可能性

前面说，总的可能性最多是 n1*n2*n3*n4*n5*n6…，为什么不是精确等于 n1*n2*n3*n4*n5*n6…呢？

我就只举一个例子，假定：

$X1 = ( a, aa, aaa, aaaa, aaaaa )

$X2 = ( a, aa, aaa, aaaa, aaaaa )

总的可能性是多少呢？