Trie上的动态规划:编辑距离与最长公共子序列的批量计算

DONG Yuxuan https://www.dyx.name

16 Nov 2015 (+0800)

给定一个称为模式串的字符串,以及一个包含若干字符串(称为文本串)的字典,我们要在字典中找出与模式串最相似的文本串。此问题的朴素解法是计算模式串与每个文本串的相似度,然后选择相似度最大的文本串。最常用的字符串相似度指标是最长公共子序列(LCS)与编辑距离。计算的时间复杂度都为O(M^2),这里M为字符串的长度。如果词典含有N个文本串,那么总的时间复杂度为O(NM^2)。

这个结果是可以优化的。不管是LCS还是编辑距离,他们的计算都是通过以两个字符串的前缀为状态的动态规划算法完成的。字典中各文本串之间可能存在大量的公共前缀。这便导致了大量的重复计算。我们可以通过将词典建成一颗Trie来合并前缀,并在Trie上执行DFS来计算所有的相似度。将时间复杂度降低到O(RM),其中R是Trie的结点个数。

最长公共子序列

回顾单对字符串的最长公共子序列长度是怎么计算的。用f(i,j)表示s的长度为i的前缀,和t的长度为j的前缀的LCS长度,我们有如下方程。

f(i,j)  = 0,                            if i=0 or j=0
        = f(i-1,j-1)+1,                 if s[i-1] = t[j-1]
        = max(f(i-1,j), f(i,j-1))

为了避免词典中重复前缀的重复计算,我们将词典组织为一颗Trie。对每个结点指针x,用x->ch表示此节点对应的字符x->par指向父节点。再维护一个数组x->lcs[]。x->lcs[i]表示模式串的长度为i的前缀与此结点对应文本串前缀的LCS长度。x->lcs[]可以通过如下代码计算:

x->lcs[0] = 0;
for (i = 1; i <= patlen; ++i)
        if (x->ch == pat[i - 1])
                x->lcs[i] = x->par->lcs[i - 1] + 1;
        else
                x->lcs[i] = MAX(x->par->lcs[i], x->lcs[i - 1]);

这样一来,我们可以在Trie上做DFS。对于每一个遍历到的结点,都通过上面的代码计算lcs[]。当DFS完成时,就获得了模式串与每个文本的LCS长度。

编辑距离

编辑距离的计算与LCS是一样的。我们先考虑单对字符串编辑距离的动态规划算法。令f(i,j)表示s的长度为i的前缀与t的长度为j的前缀的编辑距离。

f(i,j)  = j,                                    if i=0
        = i,                                    if j=0
        = min(
                f(i,j-1)+1,
                f(i-1,j)+1,
                f(i-1,j-1)+delta(s[i-1],t[j-1])
        )

其中delta(x, y)定义为:

delta(x, y)     = 0,    if x=y
                = 1,    if x!=y

将词典组织为Trie。对每个结点指针x,用x->ch表示此节点对应的字符,x->par指向父节点,x->len表示当前节点对应的文本串前缀长度,x.ed[i]表示模式串的长度为i的前缀与此结点对应文本前缀的编辑距离。x.ed[]数组可以通过如下代码计算:

x->ed[0] = x->len;
for (i = 1; i <= patlen; ++i)
        x->ed[i] = MIN(
                x->par->ed[i] + 1, 
                x->ed[i - 1] + 1, 
                x->par->ed[i - 1] + delta(pat[i - 1], x->ch)
        );

与计算LCS一样,我们在Trie上做DFS。对于每一个遍历到的结点,都通过上述的方法计算其ed[]。这样便计算了所有的编辑距离。