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

DONG Yuxuan @ Nov 16, 2015 Asia/Shanghai

计算给定单词与词典中所有单词的编辑距离与最长公共子序列

概述

我们考虑这样一个问题,给定一个称为模式串的字符串 pat,以及一个包含若干字符串(称为文本串)的字典,我们要在字典中找出与模式串最相似的文本串。

此问题的朴素解法是计算模式串与每个文本串的相似度,然后选择相似度最大的文本串作为结果。对于目前最常用的字符串相似度指标: 最长公共子序列( LCS ) 与编辑距离,计算相似度的时间复杂度都为 $O(M^2)$,这里 $M$ 为字符串的长度,如果词典含有 $N$ 个文本串,那么总的时间复杂度为 $O(NM^2)$。

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

最长公共子序列

回顾单对字符串的最长公共子序列( LCS )长度是怎么计算的。考虑两个字符串 s 和 t,长度分别为 $n$ 和 $m$,令 $f(i,j)$ 表示 s 的长度为 $i$ 的前缀与 t 的长度为 $j$ 的前缀的 LCS 长度,显然我们有状态转移方程:

\[f(i,j)=\begin{cases} 0\ (当i=0或j=0)\\ \\f(i-1,j-1)+1 \\(当\ i>0,\ j>0,\ s[i-1]=t[j-1])\\ \\max(f(i-1,j),f(i,j-1)) \\(当\ i>0,\ j>0,\ s[i-1]\neq t[j-1]) \end{cases}\]

为了避免词典中重复前缀的重复计算,我们将词典组织为一颗 Trie 树,并为其每个结点 x 维护一个数组 x.lcs[]。x.lcs[i] 表示 pat 的长度为 i 的前缀与此结点对应文本串前缀的 LCS 长度,根据前述的状态转移方程,我们可以通过 x 的父节点 x.par 的 lcs 数组,以及 x.lcs[i - 1],来计算 x.lcs[i] 的值(ch 字段表示 Trie 结点对应的字符):

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 完成时,就获得了 pat 与每个文本的 LCS 长度。

编辑距离

编辑距离的计算与 LCS 是一样的,我们先考虑单对字符串编辑距离的动态规划算法。对于两个字符串 s 和 t,长度分别为 $n$ 和 $m$,s 到 t 的编辑距离定义为利用增加单个字符,删除单个字符,替换单个字符这三种操作将 s 变换到 t 所需的最少操作数。令 $f(i,j)$ 表示s的长度为 $i$ 的前缀与 t 的长度为 $j$ 的前缀的编辑距离,显然我们有状态转移方程:

\[f(i,j)=\begin{cases} j\ (当\ i=0)\\ \\i\ (当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]) \\(当\ i \neq 0,\ j \neq 0) \end{cases}\]

其中 $\delta(x,y)$ 定义为

\[\delta(x,y)=\begin{cases} 0 &x=y\\ 1 &x\neq y \end{cases}\]

对于词典组成的 Trie 树,我们为其每个结点 x 维护一个数组 x.ed[],x.ed[i] 表示 pat 的长度为 i 的前缀与此结点对应文本前缀的编辑距离,根据前述的状态转移方程,我们可以通过 x 的父节点 x.par 的 ed 数组,以及 x.ed[i-1],来计算 x.ed[i] 的值(ch域表示 Trie 结点对应的字符):

x->ed[i] = MIN(
	x->par->ed[i] + 1, 
	x->ed[i - 1] + 1, 
	x->par->ed[i - 1] + S(pat[i - 1], x->ch)
)

这里的 S() 对应于方程中的 $\delta$ 函数。

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